×

On the arithmetic complexity of Strassen-like matrix multiplications. (English) Zbl 1353.68309

Summary: The Strassen algorithm for multiplying \(2 \times 2\) matrices requires seven multiplications and 18 additions. The recursive use of this algorithm for matrices of dimension \(n\) yields a total arithmetic complexity of \((7 n^{2.81} - 6 n^2)\) for \(n = 2^k\). S. Winograd [Linear Algebra Appl. 4, 381–388 (1971; Zbl 0225.68018)] showed that using seven multiplications for this kind of matrix multiplication is optimal. Therefore, any algorithm for multiplying \(2\times 2\) matrices with seven multiplications is called a Strassen-like algorithm. Winograd also discovered an additively optimal Strassen-like algorithm with 15 additions. This algorithm is called the Winograd’s variant, whose arithmetic complexity is \((6 n^{2.81} - 5 n^2)\) for \(n = 2^k\) and \((3.73 n^{2.81} - 5 n^2)\) for \(n = 8 \cdot 2^k\), which is the best-known bound for Strassen-like multiplications. This paper proposes a method that reduces the complexity of Winograd’s variant to \((5 n^{2.81} + 0.5 n^{2.59} + 2 n^{2.32} - 6.5 n^2)\) for \(n = 2^k\). It is also shown that the total arithmetic complexity can be improved to \((3.55 n^{2.81} + 0.148 n^{2.59} + 1.02 n^{2.32} - 6.5n^2)\) for \(n = 8 \cdot 2^k\), which, to the best of our knowledge, improves the best-known bound for a Strassen-like matrix multiplication algorithm.

MSC:

68W30 Symbolic computation and algebraic computation

Citations:

Zbl 0225.68018
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Albrecht, M. R.; Bard, G. V.; Hart, W., Algorithm 898: efficient multiplication of dense matrices over GF(2), ACM Trans. Math. Softw., 37, 1 (2010) · Zbl 1364.65092
[2] Bailey, D. H., Extra high speed matrix multiplication on the cray-2, SIAM J. Sci. Stat. Comput., 9, 3, 603-607 (1988) · Zbl 0644.65030
[3] Bard, G. V., Algebraic Cryptanalysis (2009), Springer Publishing Company, Incorporated · Zbl 1183.94019
[4] Bini, D.; Capovani, M.; Romani, F.; Lotti, G., \(O(n^{2.7799})\) complexity for \(n \ast n\) approximate matrix multiplication, Inf. Process. Lett., 8, 5, 234-235 (1979) · Zbl 0395.68048
[5] Bodrato, M., A Strassen-like matrix multiplication suited for squaring and higher power computation, (Symbolic and Algebraic Computation, International Symposium, Proceedings. Symbolic and Algebraic Computation, International Symposium, Proceedings, ISSAC 2010, Munich, Germany, July 25-28, 2010 (2010)), 273-280 · Zbl 1321.68523
[6] Boyer, B.; Dumas, J.; Pernet, C.; Zhou, W., Memory efficient scheduling of Strassen-Winograd’s matrix multiplication algorithm, (Symbolic and Algebraic Computation, International Symposium, Proceedings. Symbolic and Algebraic Computation, International Symposium, Proceedings, ISSAC 2009, Seoul, Republic of Korea, July 29-31, 2009 (2009)), 55-62 · Zbl 1237.68252
[7] Brent, R.; Zimmermann, P., Modern Computer Arithmetic (2010), Cambridge University Press: Cambridge University Press New York, NY, USA
[8] Cohen, J.; Roth, M., On the implementation of Strassen’s fast multiplication algorithm, Acta Inform., 6, 4, 341-355 (1976) · Zbl 0312.68026
[9] Cohn, H.; Umans, C., A group-theoretic approach to fast matrix multiplication, (FOCS (2003)), 438-449
[10] Cohn, H.; Kleinberg, R. D.; Szegedy, B.; Umans, C., Group-theoretic algorithms for matrix multiplication, (FOCS (2005)), 379-388
[11] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (1990) · Zbl 0702.65046
[12] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2009), MIT Press · Zbl 1187.68679
[13] Douglas, C. C.; Heroux, M.; Slishman, G.; Smith, R. M., Gemmw: a portable level 3 {BLAS} Winograd variant of Strassen’s matrix-matrix multiply algorithm, J. Comput. Phys., 110, 1, 1-10 (1994) · Zbl 0793.65031
[14] Dumas, J.; Gautier, T.; Pernet, C., Finite field linear algebra subroutines, (Symbolic and Algebraic Computation, International Symposium, Proceedings. Symbolic and Algebraic Computation, International Symposium, Proceedings, ISSAC 2002, Lille, France, July 7-10, 2002 (2002)), 63-74 · Zbl 1072.68661
[15] Dumas, J.; Giorgi, P.; Pernet, C., FFPACK: finite field linear algebra package, (Symbolic and Algebraic Computation, International Symposium, Proceedings. Symbolic and Algebraic Computation, International Symposium, Proceedings, ISSAC 2004, Santander, Spain, July 4-7, 2004 (2004)), 119-126 · Zbl 1134.12300
[16] Dumas, J.; Giorgi, P.; Pernet, C., Dense linear algebra over word-size prime fields: the FFLAS and FFPACK packages, ACM Trans. Math. Softw., 35, 3 (2008)
[17] Hasan, M. A.; Meloni, N.; Namin, A. H.; Nègre, C., Block recombination approach for subquadratic space complexity binary field multiplication based on Toeplitz matrix-vector product, IEEE Trans. Comput., 61, 2, 151-163 (2012) · Zbl 1365.65113
[18] Huss-Lederman, S.; Jacobson, E. M.; Johnson, J. R.; Tsao, A.; Turnbull, T., Implementation of Strassen’s algorithm for matrix multiplication, (Proceedings of the 1996 ACM/IEEE Conference on Supercomputing. Proceedings of the 1996 ACM/IEEE Conference on Supercomputing, Pittsburgh, PA, USA, November 17-22, 1996 (1996)), 32
[19] Joux, A., Algorithmic Cryptanalysis (2009), Chapman & Hall/CRC · Zbl 1172.94008
[20] Kaporin, I., The aggregation and cancellation techniques as a practical tool for faster matrix multiplication, Theor. Comput. Sci., 315, 2-3, 469-510 (2004) · Zbl 1057.65020
[21] Pan, V. Y., Strassen’s algorithm is not optimal: trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations, (FOCS (1978)), 166-176
[22] Pan, V. Y., New fast algorithms for matrix operations, SIAM J. Comput., 9, 2, 321-342 (1980) · Zbl 0446.68034
[23] Pan, V. Y., How to Multiply Matrices Faster, Lecture Notes in Computer Science, vol. 179 (1984), Springer · Zbl 0548.65022
[24] Probert, R. L., On the additive complexity of matrix multiplication, SIAM J. Comput., 5, 2 (1976) · Zbl 0328.65029
[25] Schönhage, A., Partial and total matrix multiplication, SIAM J. Comput., 10, 3, 434-455 (1981) · Zbl 0462.68018
[26] Stothers, A., On the complexity of matrix multiplication (2010), University of Edinburgh, Ph.D. thesis
[27] Strassen, V., Gaussian elimination is not optimal, Numer. Math., 13, 354-356 (1969) · Zbl 0185.40101
[28] Strassen, V., The asymptotic spectrum of tensors and the exponent of matrix multiplication, (FOCS (1986)), 49-54
[29] Williams, V. V., Multiplying matrices faster than Coppersmith-Winograd, (STOC (2012)), 887-898 · Zbl 1286.65056
[30] Winograd, S., On multiplication of \(2 \times 2\) matrices, Linear Algebra Appl., 4, 381-388 (1971) · Zbl 0225.68018
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.