Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(8)
Computational Complexity
Error Analysis
Error Bound
Floating Point
Inner Product
Matrix Multiplication
Numerical Stability
Satisfiability
Related Publications
(8)
Gaussian elimination is not optimal
GEMMW: A Portable Level 3 BLAS Winograd Variant of Strassen's MatrixMatrix Multiply Algorithm
Exploiting fast matrix multiplication within the level 3 BLAS
Error analysis of algorithms for matrix multiplication and triangular decomposition using Winograd's identity
ArchitectureEff...
Subscribe
Academic
Publications
ALGORITHMS FOR MATRIX MULTIPLICATION
ALGORITHMS FOR MATRIX MULTIPLICATION,R. P. BRENT
Edit
ALGORITHMS FOR MATRIX MULTIPLICATION
(
Citations: 26
)
BibTex

RIS

RefWorks
Download
R. P. BRENT
Strassen's and Winograd's algorithms for n ◊ n
matrix multiplication
are investigated and compared with the normal algorithm. The normal algorithm requires n3 + O(n2) multiplications and about the same number of additions. Winograd's algorithm almost halves the number of multiplications at the expense of more additions. Strassen's algorithm reduces the total number of operations to O(n2.82) by recursively multiplying 2n ◊ 2n matrices using seven n ◊ n matrix multiplications. Floatingpoint error bounds are obtained for both Strassen's and Winograd's methods. It is shown that Strassen's method satisfies a certain
numerical stability
property (albeit weaker than that satisfied by the normal method); and that scaling is essential for numerical accuracy using Winograd's method. In practical cases, for moderate n, Winograd's method appears to be slightly faster than the other two methods, but the gain is, at most, about 20 percent. Strassen's method should be faster for suciently large n, and this will be important in the future as memory sizes increase. An attempt to generalize Strassen's method is described.
Published in 1970.
Cumulative
Annual
Citation Context
(14)
...The roundingerror analysis of Strassen’s method was initiated by Brent ([
Bre70
, Hig90], [Hig02, chap...
Olga Holtz
,
et al.
Computational Complexity and Numerical Stability of Linear Problems
...algorithm [46] by Brent ([
12
, 33], [34, chap...
James DemmelIoana Dumitriu
,
et al.
Fast linear algebra is stable
...The rounding error analysis of Strassen’s method was initiated by Brent ([
4
,13 ], Chap...
James Demmel
,
et al.
Fast matrix multiplication is stable
...To overcome this, several authors have shown hybrid algorithms; that is, deploying Strassen’s MM in conjunction with conventional MM [5,
4
, 20], where for a specific problem size n1, or recursion point [22], Strassen’s algorithm yields the computation to the conventional MM implementations...
Paolo D'alberto
,
et al.
Adaptive Strassen's matrix multiplication
...In [22] p. 501, quoting [
3
], Knuth writes “He (R. P. Brent) estimated that Strassen’s scheme would not begin to excel over Winograd’s until n ≈ 250 and such enormous matrices rarely occur in practice unless they are very sparse, when other techniques apply.”...
Akpodigha Filatei
,
et al.
Implementation techniques for fast polynomial arithmetic in a highlev...
References
(6)
ERROR ANALYSIS OF ALGORITHMS FOR MATRIX MULTIPLICATION AND TRIANGULAR DECOMPOSITION USING WINOGRAD
(
Citations: 9
)
R. P. Brent
Published in 1970.
V gaussian elimination is not optimal numer math 13 (1969)
(
Citations: 13
)
V. Strassen
Published in 1969.
A New Algorithm for Inner Product
(
Citations: 54
)
S. Winograd
Journal:
IEEE Transactions on Computers  TC
, vol. C17, no. 7, pp. 693694, 1968
Gaussian elimination is not optimal
(
Citations: 672
)
Volker Strassen
Journal:
Numerische Mathematik  NUMER MATH
, vol. 13, no. 4, pp. 354356, 1969
ALGORITHMS FOR MATRIX MULTIPLICATION
(
Citations: 26
)
R. P. BRENT
Published in 1970.
Sort by:
Citations
(26)
Adaptive Winograd's matrix multiplications
(
Citations: 2
)
Paolo D'alberto
,
Alexandru Nicolau
Journal:
ACM Transactions on Mathematical Software  TOMS
, vol. 36, no. 1, pp. 123, 2009
Computational Complexity and Numerical Stability of Linear Problems
Olga Holtz
,
Noam Shomron
Journal:
Computing Research Repository  CORR
, vol. abs/0906.0, 2009
Fast linear algebra is stable
(
Citations: 8
)
James DemmelIoana Dumitriu
,
Ioana Dumitriu
,
Olga Holtz
Journal:
Numerische Mathematik  NUMER MATH
, vol. 108, no. 1, pp. 5991, 2007
Fast matrix multiplication is stable
(
Citations: 4
)
James Demmel
,
Ioana Dumitriu
,
Olga Holtz
,
Robert Kleinberg
Journal:
Numerische Mathematik  NUMER MATH
, vol. 106, no. 2, pp. 199224, 2007
Adaptive Strassen's matrix multiplication
(
Citations: 2
)
Paolo D'alberto
,
Alexandru Nicolau
Conference:
International Conference on Supercomputing  ICS
, pp. 284292, 2007