The role of arithmetic in fast parallel matrix inversion (Q5940607)

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.