The role of arithmetic in fast parallel matrix inversion

DOI10.1007/S00453-001-0033-7MaRDI QIDQ5940607zbMATH OpenOpenAlexFDO

Authors Bruno Codenotti, Mauro Leoncini, F. P. Preparata

Publication date 9 August 2001

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-001-0033-7

zbMATH Keywords

comparison of methodscomputer arithmetic modelsCsanky's algorithmGaussian eliminationinteger matrixmatrix inversionNewton's methodparallel algorithmsrecursive factorization algorithmvariable-precision models

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Iterative numerical methods for linear systems (65F10) Parallel numerical computation (65Y05) Analysis of algorithms (68W40)

Review text

The authors analyse the numerical behaviour of known fast parallel matrix inversion algorithms, e.g., \textit{L. Csanky}'s algorithm [SIAM J. Comput. 5, 618-623 (1976; Zbl 0353.68063)], a recursive factorization algorithm [see \textit{J. H. Reif}, \({\mathcal O}(\log^2n)\) time efficient parallel factorization of dense, sparse separable, and banded matrices. Proc. 6th ACM Symp. on Parallel Algorithms and Architectures, ACM Press, New York, 278-289 (1994); \textit{D. Bini} and \textit{V. Y. Pan}, Polynomial and matrix computations. Vol. I (1994; Zbl 0809.65012)], Gaussian elimination with no pivoting [see \textit{A. Borodin, J. von zur Gathen}, and \textit{J. Hopcroft}, Inf. Control 52, 241-256 (1982; Zbl 0507.68020)], and Newton's iterative method [see \textit{V. Pan} and \textit{J. H. Reif}, Fast and efficient parallel solution of linear systems. Proc. 17th ACM Symp. on Theory of Computing, AMS, Providence, RI, 143-152 (1985); \textit{V. Pan} and \textit{J. H. Reif}, Comput. Math. Appl. 17, No. 11, 1481-1491 (1989; Zbl 0684.65024); \textit{V. Pan} and \textit{R. Schreiber}, SIAM J. Sci. Stat. Comput. 12, No. 5, 1109-1131 (1991; Zbl 0733.65023)]. A comparative analysis under both fixed- and variable-precision models of arithmetic is developed. It is shown that Csanky's algorithm, the recursive factorization algorithm, and Gaussian elimination are practically infeasible for computing the exact inverse of an integer matrix of large size. They require word sizes linear or superlinear in the order of the matrix. Only Newton's iterative algorithm admits sufficiently accurate NC (polylogarithmic time) implementations.

Recommendations

• scientific article; zbMATH DE number 3965444
• Parallel evaluation of the determinant and of the inverse of a matrix
• A note on parallel matrix inversion
• Complexity of parallel matrix computations
• Fast and efficient parallel solution of dense linear systems

Cited in

(9)

• A \(p\)-adic algorithm for computing the inverse of integer matrices
• Parallel evaluation of the determinant and of the inverse of a matrix
• A note on parallel matrix inversion
• An Improved Newton Iteration for the Generalized Inverse of a Matrix, with Applications
• scientific article; zbMATH DE number 3956317 (Why is no real title available?)
• scientific article; zbMATH DE number 3965444 (Why is no real title available?)
• scientific article; zbMATH DE number 139846 (Why is no real title available?)
• scientific article; zbMATH DE number 1894936 (Why is no real title available?)
• The unpredictable deviousness of models

This page was built for publication: The role of arithmetic in fast parallel matrix inversion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5940607)