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).
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.
Comment
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