article

Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity

Author:

R. P. BrentAuthors Info & Claims

Numerische Mathematik, Volume 16, Issue 2

Pages 145 - 156

https://doi.org/10.1007/BF02308867

Published: 01 November 1970 Publication History

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.

References

[1]

Brent, R. P.: Algorithms for matrix multiplication. Tech. Report CS 157 (March 1970), Computer Sci. Dept., Stanford Uni.

Digital Library

Google Scholar

[2]

Fox, B. L.: AcceleratingLP algorithms. CACM12,7 (July 1969). 384---385.

Crossref

Google Scholar

[3]

Klyuyev, V. V., Kokovkin-Shcherbak, N. L.: On the minimization of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Tech. Report CS 24 (June 1965), Computer Sci. Dept., Stanford Uni.

Google Scholar

[4]

Strassen, V.: Gaussian elimination is not optimal. Numer. Math.13, 354---356 (1969)

Digital Library

Google Scholar

[5]

Wilkinson, J. H.: Error analysis of direct methods of matrix inversion. JACM8, 281---330 (1961).

Crossref

Google Scholar

[6]

---- Rounding errors in algebraic processes. London: H.M. S.O.; New Jersey: Prentice-Hall 1963.

Google Scholar

[7]

---- The algebraic eigenvalue problem. Oxford: Clarendon Press 1965.

Crossref

Google Scholar

[8]

Winograd, S.: A new algorithm for inner product. IEEE Trans. C-17 (1968), 693---694.

Crossref

Google Scholar

Cited By

View all

Moran YSchwartz OAgrawal KShun J(2023)Multiplying 2 × 2 Sub-Blocks Using 4 MultiplicationsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591083(379-390)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591083
Arrigoni VMaggioli FMassini ARodolà E(2021)Efficiently Parallelizable Strassen-Based Multiplication of a Matrix by its TransposeProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473519(1-12)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3473519
D'alberto PBodrato MNicolau A(2011)Exploiting parallelism in matrix-computation kernels for symmetric multiprocessor systemsACM Transactions on Mathematical Software10.1145/2049662.204966438:1(1-30)Online publication date: 7-Dec-2011
https://dl.acm.org/doi/10.1145/2049662.2049664
Show More Cited By

Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms

Recommendations

Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product

The error complexity analysis of three algorithms for matrix multiplication and matrix chain product has been given. It is shown that the usual inner product type algorithm is by far the best algorithm for simple matrix multiplication or matrix chain ...
Generalized matrix inversion is not harder than matrix multiplication

Starting from the Strassen method for rapid matrix multiplication and inversion as well as from the recursive Cholesky factorization algorithm, we introduced a completely block recursive algorithm for generalized Cholesky factorization of a given ...
New Accurate Algorithms for Singular Value Decomposition of Matrix Triplets

This paper presents a new algorithm for accurate floating-point computation of the singular value decomposition (SVD) of the product $A = B^{\tau} S C,$ where $ B\in {\hbox{{\bf R}$^{p\times m}$}},$ $C\in {\hbox{{\bf R}$^{q\times n}$}},$ $S\in {\hbox{{\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Numerische Mathematik Volume 16, Issue 2

November 1970

96 pages

ISSN:0029-599X

Issue’s Table of Contents

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 1970

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Moran YSchwartz OAgrawal KShun J(2023)Multiplying 2 × 2 Sub-Blocks Using 4 MultiplicationsProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591083(379-390)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591083
Arrigoni VMaggioli FMassini ARodolà E(2021)Efficiently Parallelizable Strassen-Based Multiplication of a Matrix by its TransposeProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3473519(1-12)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3473519
D'alberto PBodrato MNicolau A(2011)Exploiting parallelism in matrix-computation kernels for symmetric multiprocessor systemsACM Transactions on Mathematical Software10.1145/2049662.204966438:1(1-30)Online publication date: 7-Dec-2011
https://dl.acm.org/doi/10.1145/2049662.2049664
D'Alberto PNicolau A(2009)Adaptive Winograd's matrix multiplicationsACM Transactions on Mathematical Software10.1145/1486525.148652836:1(1-23)Online publication date: 16-Mar-2009
https://dl.acm.org/doi/10.1145/1486525.1486528
D'Alberto PNicolau ASmith B(2007)Adaptive Strassen's matrix multiplicationProceedings of the 21st annual international conference on Supercomputing10.1145/1274971.1275010(284-292)Online publication date: 17-Jun-2007
https://dl.acm.org/doi/10.1145/1274971.1275010
D'Alberto PNicolau A(2005)Using recursion to boost ATLAS's performanceProceedings of the 6th international symposium on high-performance computing and 1st international conference on Advanced low power systems10.5555/1783214.1783228(142-151)Online publication date: 7-Sep-2005
https://dl.acm.org/doi/10.5555/1783214.1783228
D'Alberto PNicolau A(2005)Adaptive Strassen and ATLAS's DGEMMProceedings of the Eighth International Conference on High-Performance Computing in Asia-Pacific Region10.1109/HPCASIA.2005.18Online publication date: 30-Nov-2005
https://dl.acm.org/doi/10.1109/HPCASIA.2005.18
Higham N(1990)Exploiting fast matrix multiplication within the level 3 BLASACM Transactions on Mathematical Software10.1145/98267.9829016:4(352-368)Online publication date: 1-Dec-1990
https://dl.acm.org/doi/10.1145/98267.98290
Nai-Kuan Tsao (1981)Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain ProductIEEE Transactions on Computers10.1109/TC.1981.167569430:10(758-771)Online publication date: 1-Oct-1981
https://dl.acm.org/doi/10.1109/TC.1981.1675694
Bini DLotti G(1980)Stability of fast algorithms for matrix multiplicationNumerische Mathematik10.1007/BF0139598936:1(63-72)Online publication date: 1-Mar-1980
https://dl.acm.org/doi/10.1007/BF01395989
Show More Cited By

Abstract

References

Cited By

Recommendations

Error Complexity Analysis of Algorithms for Matrix Multiplication and Matrix Chain Product

Generalized matrix inversion is not harder than matrix multiplication

New Accurate Algorithms for Singular Value Decomposition of Matrix Triplets

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations