×

A practical algorithm for faster matrix multiplication. (English) Zbl 0982.65048

Summary: The purpose of this paper is to present an algorithm for matrix multiplication based on a formula discovered by V. Ja. Pan [Usp. Mat. Nauk 27, No. 5(167), 249-250 (1972; Zbl 0261.65025)]. For matrices of order up to 10 000, the nearly optimum tuning of the algorithm results in a rather clear non-recurvise one- or two-level structure with the operation count comparable to that of the algorithm by V. Strassen [Numer. Math. 13, 354-356 (1969; Zbl 0185.40101)]. The algorithm takes less workspace and has better numerical stability as compared to the Strassen algorithm, especially in the modification by Winograd, see D. Bini and G. Lotti [Numer. Math. 36, 63-72 (1980; Zbl 0431.65024)]. Moreover, its clearer and more flexible structure is potentially more suitable for efficient implementation on modern supercomputers.

MSC:

65F30 Other matrix algorithms (MSC2010)
65Y20 Complexity and performance of numerical algorithms
68Q25 Analysis of algorithms and problem complexity

Software:

mctoolbox
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bailey, SIAM J. Sci. Stat. Comput. 9 pp 603– (1988) · Zbl 0644.65030 · doi:10.1137/0909040
[2] Bini, Numer. Math. 36 pp 63– (1980) · Zbl 0431.65024 · doi:10.1007/BF01395989
[3] and . The IBM RISC system/6000 and linear algebra operations. Technical report CS-90-122, Computer Science Department, University of Tennessee, 1990.
[4] Douglas, J. Comput. Phys. 110 pp 1– (1994) · Zbl 0793.65031 · doi:10.1006/jcph.1994.1001
[5] Higham, ACM Trans. Math. Soft. 16 pp 352– (1990) · Zbl 0900.65118 · doi:10.1145/98267.98290
[6] Accuracy and Stability of Numerical Algorithms. SIAM Publications, Philadelphia, 1996.
[7] Pan, Uspehi Mat. Nauk. 27 pp 249– (1972)
[8] Pan, SIAM Rev. 26 pp 393– (1984) · Zbl 0563.65028 · doi:10.1137/1026076
[9] Strassen, Numer. Math. 13 pp 354– (1969) · Zbl 0185.40101 · doi:10.1007/BF02165411
[10] Winograd, J. Symbolic Comput. 9 pp 251– (1990) · Zbl 0702.65046 · doi:10.1016/S0747-7171(08)80013-2
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.