ERROR ANALYSIS OF ALGORITHMS FOR MATRIX MULTIPLICATION AND TRIANGULAR DECOMPOSITION USING WINOGRAD’S IDENTITY

R. P. BRENT

Abstract

The number of multiplications required for matrix multiplication, for the triangular decomposition of a matrix with partial pivoting, and for the Cholesky decomposition of a positive definite symmetric matrix, can be roughly halved if Winograd’s identity is used to compute the inner products involved. Floating-point error bounds for these algorithms are shown to be comparable to those for the normal methods provided that care is taken with scaling.

Comments

Only the Abstract is given here. The full paper appeared as [2]. For related work see [1, 3, 4].

References

1. R. P. Brent, Algorithms for Matrix Multiplication, Report TR-CS-70-157, Computer Science Department, Stanford University (March 1970), 52 pp. Available from NTIS, #AD705509. rpb002.

2. R. P. Brent, “Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd’s identity”, Numerische Mathematik 16 (1970), 145–156. MR 43#5702, CR 12#21408. rpb004.

3. V. Strassen, “Gaussian elimination is not optimal”, Numerische Mathematik 13 (1969), 354–356.

4. S. Winograd, “A new algorithm for inner product”, IEEE Transactions on Computers C-17 (1968), 693–694.

Department of Computer Science, Stanford University, Stanford, CA 94305, USA

1991 Mathematics Subject Classification. Primary 65G99; Secondary 65F05, 65F30, 65F35, 68Q25. Key words and phrases. Matrix multiplication, inner-product, error analysis, scaling, Winograd,

Strassen, computational complexity.

The author wishes to thank Drs. G. Forsythe, J. Herriot and J. Wilkinson for their helpful advice, and CSIRO (Australia) for its generous financial support.

Received December 3, 1969. Copyright \begin{matrix}c \\ ◯ \end{matrix} 1970, Springer-Verlag. Comments \begin{matrix}c \\ ◯ \end{matrix} 1993, R. P. Brent.

rpb004a typeset using AMS-L^{A}TEX