Error Analysis of Algorithms for Matrix Multiplication and Triangular Decomposition using Winograd's Identity

4. R. P. Brent, Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity, Numerische Mathematik 16 (1970), 145-156. CR 12#21408, MR 43#5702.

Abstract: dvi (2K), pdf (59K).

Paper: pdf (925K).


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.


For the application of Winograd's identity to matrix multiplication, and an error analysis of Strassen's matrix multiplication algorithm, see Brent [2].

Go to next publication

Return to Richard Brent's index page