Using Strassen's Algorithm to Accelerate the Solution of Linear Systems

摘要

Strassen's algorithm for fast matrix-matrix multiplication has been implemented for matrices of arbitrary shapes on the Cray-2 and Cray Y-MP supercomputers. A number of techniques have been used to reduce the scratch space requirement for this algorithm, at the same time preserving a high level of performance. When the resulting Strassen-based matrix multiply routine is combined with some routines from the new LAPACK library, LU decomposition can be performed with rates significantly higher than by conventional means. We succeeded in factoring a 2048 x 2048 matrix on the Cray Y-MP at a rate equivalent to 325 MFLOPS.