PaA2 Abstract

Title: A Strassen-Type Matrix Inversion Algorithm (PaA2)

Authors: S.M. Balle, P.C. Hansen, and N.J. Higman

Email: Per.Christian.Hansen@uni-c.dk

Date: July 1993

Abstract:

Strassen's algorithm for matrix-matrix multiplication has turned out to be a competitive alternative to standard matrix-matrix multiplication algorithms on high-speed vector computers. It also seems to perform well on massively parallel computers. In this study we consider a similar divide-and-conquer algorithm for matrix inversion (in which Strassen matrix-matrix multiplication is an essential ``building block''). This algorithm is numerically stable for well-conditioned symmetric positive definite matrices where all submatrices on the diagonal are well-conditioned. We also propose a scheme for handling general well-conditioned matrices by this algorithm, adding a small perturbation to any ill-conditioned submatrix to make it well-conditioned, and refining the solution by iterative refinement, if necessary. We present a brief error analysis of the algorithm, describe when and how the perturbations are made, and give some results from an implementation of the algorithm on a Connection Machine CM-200.

This report is available through