A Strassen-Newton Algorithm for High-Speed Parallelizable Matrix Inversion

摘要

This paper describes techniques to compute matrix inverses by means of algorithms that are highly suited to massively parallel computation. In contrast, conventional techniques such as pivoted Gaussian elimination and LU decomposition are efficient only on vector computers or fairly low-level parallel systems. These techniques are based on an algorithm suggested by Strassen in 1969. Variations of this scheme employ matrix Newton iterations and other methods to improve the numerical stability while at the same time preserving a very high level of parallelism. One-processor Cray-2 implementations of these schemes range from one that is up to 55 faster than a conventional library routine to one that, while slower than a library routine, achieves excellent numerical stability. The problem of computing the solution to a single set of linear equations is discussed, and it is shown that shown that this problem can also be solved efficiently using these techniques.