article

Free access

Inversion of Matrices by Partitioning

Author:

Marshall C. PeaseAuthors Info & Claims

Journal of the ACM (JACM), Volume 16, Issue 2

Pages 302 - 314

https://doi.org/10.1145/321510.321522

Published: 01 April 1969 Publication History

PDF eReader

Abstract

The inversion of nonsingular matrices is considered. A method is developed which starts with an arbitrary partitioning of the given matrix. The separate submatrices are grouped into sets determined by the nonzero entries of some appropriate group, G, of permutation matrices. The group structure of G then establishes a sequence of operations on these sets of submatrices from which the corresponding representation of the inverse is obtained.

Whether the method described is to be preferred to, say, Gauss's algorithm will depend on the capabilities that are required by other parts of the algorithm that is to be implemented in the special-purpose parallel computer. The basic speed, measured by the count of parallel multiplications and divisions, is comparable to that obtained with Gauss's algorithm and is slightly better under certain conditions. The principal difference is that this method uses primarily matrix multiplication, whereas Gauss's algorithm uses primarily row combinations. When the special-purpose computer under design must supply this capability anyway, the method developed here should be considered.

Application of the process is limited to matrices for which we can set up a partitioning such that we can guarantee, a priori, that certain of the submatrices are nonsingular. Hence the method is not useful for arbitrary nonsingular matrices. However, it can be applied to certain important classes of matrices, notably those that are “dominated by the diagonal.” Noise covariance matrices are of this type; therefore the method can be applied to them. The inversion of a noise covariance matrix is required in some problems of optimal prediction and control. It is for applications of this sort that the method seems particularly attractive.

References

[1]

GANTMACHER, F.R. The Theory of Matrices, Vol. I. Chelsea, New York, 1960.

Google Scholar

[2]

PEASE, M.C. Methods of Matrix Algebra. Academic .Press, New York, 1965.

Google Scholar

[3]

FADDEEW V.N. Computational Melhods of Linear Algebra (translated by D. C. Benster). Dover, New York, 1959.

Google Scholar

[4]

HALL, MARSHALI, JR. The Theory of Groups. Macmillan, New York, 1959.

Google Scholar

[5]

PEASE, M. C. Matrix inversioa using parallel processing. J. ACM 14, 4 (Oct. 1967), 757- 764.

Crossref

Google Scholar

Cited By

View all

Heller D(2020)A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review10.1137/102009620:4(740-777)Online publication date: 30-Jun-2020
https://dl.acm.org/doi/10.1137/1020096
Hains G(1991)Matrix Inversion in 3 DimensionsArrays, Functional Languages, and Parallel Systems10.1007/978-1-4615-4002-1_16(295-302)Online publication date: 1991
https://doi.org/10.1007/978-1-4615-4002-1_16
Papadopoulou ESaridakis YPJapatheodorou TSzygenda S(1987)Orderings and partition of PDE computations for a fixed-size VLSI architectureProceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow10.5555/42040.42107(366-375)Online publication date: 1-Dec-1987
https://dl.acm.org/doi/10.5555/42040.42107
Show More Cited By

Index Terms

Inversion of Matrices by Partitioning
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Inversion of k-tridiagonal matrices with Toeplitz structure

In this paper, we consider an inverse problem with the k-tridiagonal Toeplitz matrices. A theoretical result is obtained that under certain assumptions the explicit inverse of a k-tridiagonal Toeplitz matrix can be derived immediately. Two numerical ...
Moore-Penrose Inversion of Square Toeplitz Matrices

Fast algorithms for the computation of the Moore-Penrose inverse $A^+$ of a square Toeplitz matrix $A$ are constructed based on Bezoutian representations of $A^+$. Two approaches are presented. The first approach is a recursion of the nested ...
Fast inversion of triangular Toeplitz matrices
Algebraic and numerical algorithm

In this paper, we present an approximate inversion method for triangular Toeplitz matrices based on trigonometric polynomial interpolation. To obtain an approximate inverse of high accuracy for a triangular Toeplitz matrix of size n, our algorithm ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 16, Issue 2

April 1969

157 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321510

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1969

Published in JACM Volume 16, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
1,139
Total Downloads

Downloads (Last 12 months)287
Downloads (Last 6 weeks)60

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Heller D(2020)A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review10.1137/102009620:4(740-777)Online publication date: 30-Jun-2020
https://dl.acm.org/doi/10.1137/1020096
Hains G(1991)Matrix Inversion in 3 DimensionsArrays, Functional Languages, and Parallel Systems10.1007/978-1-4615-4002-1_16(295-302)Online publication date: 1991
https://doi.org/10.1007/978-1-4615-4002-1_16
Papadopoulou ESaridakis YPJapatheodorou TSzygenda S(1987)Orderings and partition of PDE computations for a fixed-size VLSI architectureProceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow10.5555/42040.42107(366-375)Online publication date: 1-Dec-1987
https://dl.acm.org/doi/10.5555/42040.42107
Faddeev DFaddeeva V(1981)Computational methods of linear algebraJournal of Soviet Mathematics10.1007/BF0108654415:5(531-650)Online publication date: 1981
https://doi.org/10.1007/BF01086544
Faddeeva VFaddeev D(1978)Parallel computations in linear algebraCybernetics10.1007/BF0106884913:6(822-834)Online publication date: 1978
https://doi.org/10.1007/BF01068849
Kautz W(1971)An Augmented Content-Addressed Memory Array for Implementation With Large-Scale IntegrationJournal of the ACM10.1145/321623.32162618:1(19-33)Online publication date: 1-Jan-1971
https://dl.acm.org/doi/10.1145/321623.321626

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Inversion of k-tridiagonal matrices with Toeplitz structure

Moore-Penrose Inversion of Square Toeplitz Matrices

Fast inversion of triangular Toeplitz matrices

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations