Fast matrix multiplication and its algebraic neighbourhood

V. Ya. Pan

Sbornik. Mathematics, Tome 208 (2017) no. 11, pp. 1661-1704

Résumé

Matrix multiplication is among the most fundamental operations of modern computations. By 1969 it was still commonly believed that the classical algorithm was optimal, although the experts already knew that this was not so. Worldwide interest in matrix multiplication instantly exploded in 1969, when Strassen decreased the exponent 3 of cubic time to $2.807$. Then everyone expected to see matrix multiplication performed in quadratic or nearly quadratic time very soon. Further progress, however, turned out to be capricious. It was at stalemate for almost a decade, then a combination of surprising techniques (completely independent of Strassen's original ones and much more advanced) enabled a new decrease of the exponent in 1978–1981 and then again in 1986, to $2.376$. By 2017 the exponent has still not passed through the barrier of $2.373$, but most disturbing was the curse of recursion — even the decrease of exponents below $2.7733$ required numerous recursive steps, and each of them squared the problem size. As a result, all algorithms supporting such exponents supersede the classical algorithm only for inputs of immense sizes, far beyond any potential interest for the user. We survey the long study of fast matrix multiplication, focusing on neglected algorithms for feasible matrix multiplication. We comment on their design, the techniques involved, implementation issues, the impact of their study on the modern theory and practice of Algebraic Computations, and perspectives for fast matrix multiplication. Bibliography: 163 titles.

Détail

Keywords: bilinear algorithms, feasible matrix multiplication
Mots-clés : matrix multiplication, tensor decomposition, exponent of matrix multiplication.

Bibliographie

[1] A. V. Aho, J. E. Hopcroft, J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, MA–London–Amsterdam, 1974, x+470 pp. | MR | Zbl

[2] N. Alon, Z. Galil, O. Margalit, “On the exponent of the all pairs shortest path problem”, J. Comput. System Sci., 54:2 (1997), 255–262 | DOI | MR | Zbl

[3] N. Alon, A. Shpilka, C. Umans, “On sunflowers and matrix multiplication”, Comput. Complexity, 22:2 (2013), 219–243 | DOI | MR | Zbl

[4] A. Ambainis, Y. Filmus, F. Le Gall, “Fast matrix multiplication: limitations of the laser method”, Electronic Colloquium on Computational Complexity (ECCC), 2014, TR14-154, 38 pp. }; arXiv: {http://eccc.hpi-web.de/report/2014/1541411.5414

[5] R. R. Amossen, R. Pagh, “Faster join-projects and sparse matrix multiplications”, ICDT' 09 Proceedings of the 12th international conference on database theory (St. Petersburg, 2009), ACM, New York, 2009, 121–126 | DOI

[6] V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, I. A. Faradzhev, “On economical construction of the transitive closure of an oriented graph”, Soviet Math. Dokl., 11:5 (1970), 1209–1210 | MR | Zbl

[7] A. Azad, G. Ballard, A. Buluç, J. Demmel, L. Grigori, O. Schwartz, S. Toledo, S. Williams, “Exploiting multiple levels of parallelism in sparse matrix-matrix multiplication”, SIAM J. Sci. Comput., 38:6 (2016), C624–C651 | DOI | MR | Zbl

[8] G. Ballard, A. R. Benson, A. Druinsky, B. Lipshitz, O. Schwartz, “Improving the numerical stability of fast matrix multiplication algorithms”, SIAM J. Matrix Anal. Appl., 37:4 (2016), 1382–1418 ; arXiv: 1507.00687 | DOI | MR | Zbl

[9] G. Ballard, E. Carson, J. Demmel, M. Hoemmen, N. Knight, O. Schwartz, “Communication lower bounds and optimal algorithms for numerical linear algebra”, Acta Numer., 23 (2014), 1–155 | DOI | MR

[10] G. Ballard, J. Demmel, O. Holtz, B. Lipshitz, O. Schwartz, “Graph expansion analysis for communication costs of fast rectangular matrix multiplication”, Design and analysis of algorithms, Lecture Notes in Comput. Sci., 7659, Springer, Heidelberg, 2012, 13–36 | DOI | MR | Zbl

[11] G. Ballard, A. Druinsky, N. Knight, O. Schwartz, Hypergraph partitioning for sparse matrix-matrix multiplication, arXiv: 1603.05627

[12] N. Bansal, R. Williams, “Regularity lemmas and combinatorial algorithms”, FOCS' 09 50th annual IEEE symposium on foundations of computer science, IEEE Computer Soc., Los Alamitos, CA, 2009, 745–754 | DOI | MR | Zbl

[13] G. Bard, Algorithms for solving linear and polynomial systems of equations over finite fields with applications to cryptanalysis, PhD Thesis, Univ. of Maryland, College Park, 2007, xix+159 pp.

[14] D. H. Bailey, “Extra high speed matrix multiplication on the Cray-2”, SIAM J. Sci. Statist. Comput., 9:3 (1988), 603–607 | DOI | MR | Zbl

[15] B. Beckermann, A. Townsend, “On the singular values of matrices with displacement structure”, SIAM J. Matrix Anal. Appl. (to appear)

[16] E. G. Belaga, “Nekotorye voprosy vychisleniya mnogochlenov”, Dokl. AN SSSR, 123:5 (1958), 775–777 | MR | Zbl

[17] T. Bella, Y. Eidelman, I. Gohberg, V. Olshevsky, “Computations with quasiseparable polynomials and matrices”, Theoret. Comput. Sci., 409:2 (2008), 158–179 | DOI | MR | Zbl

[18] A. R. Benson, G. Ballard, “A framework for practical parallel fast matrix multiplication”, PPoPP 2015 Proceedings of the 20th ACM SIGPLAN symposium on principles and practice of parallel programming (San Francisco, CA, 2015), ACM, New York, 2015, 42–53 | DOI

[19] D. Bini, “Relations between exact and approximate bilinear algorithms. Applications”, Calcolo, 17:1 (1980), 87–97 | DOI | MR | Zbl

[20] D. Bini, M. Capovani, F. Romani, G. Lotti, “$O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication”, Inform. Process. Lett., 8:5 (1979), 234–235 | DOI | MR | Zbl

[21] D. Bini, M. Capovani, G. Lotti, F. Romani, Complessità numerica, Boringhieri publisher, Torino, 1981, 237 pp.

[22] D. A. Bini, G. Fiorentino, “Design, analysis, and implementation of a multiprecision polynomial rootfinder”, Numer. Algorithms, 23:2-3 (2000), 127–173 | DOI | MR | Zbl

[23] D. Bini, G. Lotti, “Stability of fast algorithms for matrix multiplication”, Numer. Math., 36:1 (1980), 63–72 | DOI | MR | Zbl

[24] D. Bini, G. Lotti, F. Romani, “Approximate solutions for the bilinear form computational problem”, SIAM J. Comput., 9:4 (1980), 692–697 | DOI | MR | Zbl

[25] D. Bini, V. Y. Pan, Polynomial and matrix computations, v. 1, Progr. Theoret. Comput. Sci., Fundamental algorithms, Birkhäuser Boston, Inc., Boston, MA, 1994, xvi+415 pp. | DOI | MR | Zbl

[26] M. Bläser, “A $5/2 n^{2}$-lower bound for the rank of $n\times n$-matrix multiplication over arbitrary fields”, 40th annual symposium on foundations of computer science (New York, 1999), IEEE Computer Soc., Los Alamitos, CA, 1999, 45–50 | DOI | MR

[27] M. Bläser, “Lower bounds for the bilinear complexity of associative algebras”, Comput. Complexity, 9:2 (2000), 73–112 | DOI | MR | Zbl

[28] J. Blasiak, T. Church, H. Cohn, J. A. Grochow, E. Naslund, W. F. Sawin, C. Umans, “On cap sets and the group-theoretic approach to matrix multiplication”, Discrete Anal., 2017, Paper No. 3, 27 pp. | MR

[29] M. Bodrato, “A Strassen-like matrix multiplication suited for squaring and higher power computation”, ISSAC' 10 Proceedings of the 2010 international symposium on symbolic and algebraic computation, ACM, New York, 2010, 273–280 | DOI | MR | Zbl

[30] A. Borodin, Private communication, 1979

[31] A. Borodin, I. Munro, The computational complexity of algebraic and numeric problems, Theory of Computation Series, 1, American Elsevier Publishing Co., Inc., New York–London–Amsterdam, 1975, x+174 pp. | MR | Zbl

[32] A. Bostan, C.-P. Jeannerod, É. Schost, “Solving structured linear systems with large displacement rank”, Theoret. Comput. Sci., 407:1-3 (2008), 155–181 | DOI | MR | Zbl

[33] B. Boyer, J.-G. Dumas, C. Pernet, W. Zhou, “Memory efficient scheduling of Strassen–Winograd's matrix multiplication algorithm”, ISSAC' 09 Proceedings of the 2009 international symposium on symbolic and algebraic computation, ACM, New York, 2009, 55–62 | DOI | MR | Zbl

[34] R. P. Brent, Algorithms for matrix multiplication, Tech. rep. TR-CS-70-157, DCS, Stanford Univ., Stanford, 1970, 3+52 pp. http://maths-people.anu.edu.au/~brent/pub/pub002.html

[35] R. W. Brockett, D. Dobkin, “On the optimal evaluation of a set of bilinear forms”, STOC' 73 Proceedings of the 5th annual ACM symposium on theory of computing (Austin, Tex., 1973), ACM, New York, 1973, 88–95 | DOI | MR | Zbl

[36] R. W. Brockett, D. Dobkin, “On the number of multiplications required for matrix multiplication”, SIAM J. Comput., 5:4 (1976), 624–628 | DOI | MR | Zbl

[37] R. W. Brockett, D. Dobkin, “On the optimal evaluation of a set of bilinear forms”, Linear Algebra and Appl., 19:3 (1978), 207–235 | DOI | MR | Zbl

[38] N. H. Bshouty, “A lower bound for matrix multiplication”, SIAM J. Comput., 18:4 (1989), 759–765 | DOI | MR | Zbl

[39] N. H. Bshouty, “On the additive complexity of $2\times 2$ matrix multiplication”, Inform. Process. Lett., 56:6 (1995), 329–335 | DOI | MR | Zbl

[40] A. Buluç, J. R. Gilbert, “Parallel sparse matrix-matrix multiplication and indexing: implementation and experiments”, SIAM J. Sci. Comput., 34:4 (2012), C170–C191 | DOI | MR | Zbl

[41] J. R. Bunch, J. E. Hopcroft, “Triangular factorization and inversion by fast matrix multiplication”, Math. Comp., 28:125 (1974), 231–236 | DOI | MR | Zbl

[42] P. Bürgisser, M. Clausen, M. A. Shokrollahi, Algebraic complexity theory, Grundlehren Math. Wiss., 315, Springer Verlag, Berlin, 1997, xxiv+618 pp. | DOI | MR | Zbl

[43] J. Carrier, L. Greengard, V. Rokhlin, “A fast adaptive multipole algorithm for particle simulations”, SIAM J. Sci. Statist. Comput., 9:4 (1988), 669–686 | DOI | MR | Zbl

[44] M. Cenk, M. A. Hasan, “On the arithmetic complexity of Strassen-like matrix multiplications”, J. Symbolic Comput., 80, Part 2 (2017), 484–501 | DOI | MR | Zbl

[45] T. M. Chan, “Speeding up the Four Russians algorithm by about one more logarithmic factor”, Proceedings of the 26th annual ACM–SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, 2015, 212–217 | DOI | MR

[46] B. A. Cipra, “The best of the 20th century: editors name top 10 algorithms”, SIAM News, 33:4 (2000), 1–2

[47] H. Cohn, R. Kleinberg, B. Szegedy, C. Umans, “Group-theoretic algorithms for matrix multiplication”, FOCS 2005 46th annual IEEE symposium on foundations of computer science (Pittsburgh, PA), IEEE Computer Soc., Los Alamitos, CA, 2005, 379–388 | DOI

[48] H. Cohn, C. Umans, “A group-theoretic approach to fast matrix multiplication”, FOCS 2003 44th annual IEEE symposium on foundations of computer science (Cambridge, MA), IEEE Computer Soc., Los Alamitos, CA, 2003, 438–449 | DOI

[49] H. Cohn, C. Umans, “Fast matrix multiplication using coherent configurations”, Proceedings of the 24th annual ACM–SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, 2013, 1074–1087 | MR

[50] J. W. Cooley, J. W. Tukey, “An algorithm for the machine calculation of complex Fourier series”, Math. Comp., 19:90 (1965), 297–301 | DOI | MR | Zbl

[51] D. Coppersmith, “Rapid multiplication of rectangular matrices”, SIAM J. Comput., 11:3 (1982), 467–471 | DOI | MR | Zbl

[52] D. Coppersmith, “Rectangular matrix multiplication revisited”, J. Complexity, 13:1 (1997), 42–49 | DOI | MR | Zbl

[53] D. Coppersmith, S. Winograd, “On the asymptotic complexity of matrix multiplication”, SIAM J. Comput., 11:3 (1982), 472–492 ; SFCS' 81 22nd annual symposium on foundations of computer science (Nashville, TN, 1981), IEEE Computer Soc., Washington, DC, 1981, 82–90 | DOI | MR | Zbl | DOI

[54] D. Coppersmith, S. Winograd, “Matrix multiplicaton via arithmetic progressions”, J. Symbolic Comput., 9:3 (1990), 251–280 ; STOC' 87 Proceedings of the 19th annual ACM symposium on theory of computing, ACM, New York, 1987, 1–6 ; Res. rep. RC 12104, IBM T. J. Watson Res. Center, Yorktown Heights, NY, 1986, 17 pp. | DOI | MR | Zbl | DOI

[55] P. D'Alberto, A. Nicolau, “Adaptive Winograd's matrix multiplications”, ACM Trans. Math. Software, 36:1 (2009), Art. 3, 23 pp. | DOI | MR | Zbl

[56] A. M. Davie, A. J. Stothers, “Improved bound for complexity of matrix multiplication”, Proc. Roy. Soc. Edinburgh Sect. A, 143:2 (2013), 351–369 | DOI | MR | Zbl

[57] H. F. de Groote, “On varieties of optimal algorithms for the computation of bilinear mappings. II. Optimal algorithms for $2\times 2$-matrix multiplication”, Theoret. Comput. Sci., 7:2 (1978), 127–148 | DOI | MR | Zbl

[58] C. Demetrescu, G. F. Italiano, “Fully dynamic transitive closure: breaking through the $O(n^2)$ barrier”, 41st annual symposium on foundations of computer science (Redondo Beach, CA, 2000), IEEE Comput. Soc., Los Alamitos, CA, 2000, 381–389 | DOI | MR

[59] J. W. Demmel, Applied numerical linear algebra, SIAM, Philadelphia, PA, 1997, xii+419 pp. | DOI | MR | Zbl

[60] J. Demmel, I. Dumitriu, O. Holtz, “Fast linear algebra is stable”, Numer. Math., 108:1 (2007), 59–91 | DOI | MR | Zbl

[61] J. Demmel, I. Dumitriu, O. Holtz, R. Kleinberg, “Fast matrix multiplication is stable”, Numer. Math., 106:2 (2007), 199–224 | DOI | MR | Zbl

[62] C. C. Douglas, M. Heroux, G. Slishman, R. M. Smith, “GEMMW: A portable level 3 BLAS Winograd variant Of Strassen's matrix-matrix multiply algorithm”, J. Comput. Phys., 110:1 (1994), 1–10 | DOI | MR | Zbl

[63] C.-É. Drevet, Md. N. Islam, É. Schost, “Optimization techniques for small matrix multiplication”, Theoret. Comput. Sci., 412:22 (2011), 2219–2236 | DOI | MR | Zbl

[64] P. Drineas, R. Kannan, M. W. Mahoney, “Fast Monte Carlo algorithms for matrices. I. Approximating matrix multiplication”, SIAM J. Comput., 36:1 (2006), 132–157 | DOI | MR | Zbl

[65] R. Duan, S. Pettie, “Fast algorithms for $(\max,\min)$ matrix multiplication and bottleneck shortest paths”, Proceedings of the 20th annual ACM–SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, 2009, 384–391 | DOI | MR

[66] J.-G. Dumas, T. Gautier, C. Pernet, “Finite field linear algebra subroutines”, ISSAC' 02 Proceedings of the 2002 International symposium on symbolic and algebraic computation, ACM, New York, 2002, 63–74 | DOI | MR | Zbl

[67] J.-G. Dumas, P. Giorgi, C. Pernet, “FFPACK: Finite field linear algebra package”, ISSAC' 04 Proceedings of the 2004 international symposium on symbolic and algebraic computation, ACM, New York, 2004, 119–126 | DOI | MR | Zbl

[68] J.-G. Dumas, P. Giorgi, C. Pernet, “Dense linear algebra over word-size prime fields: the FFLAS and FFPACK packages”, ACM Trans. Math. Software, 35:3 (2008), Art. 19, 35 pp. | DOI | MR

[69] J.-G. Dumas, V. Y. Pan, Fast matrix multiplication and symbolic computation, arXiv: 1612.05766

[70] C. M. Fiduccia, “Polynomial evaluation via the division algorithm: the fast Fourier transform revisited”, STOC 1972 Proceedings of the 4th annual ACM symposium on theory of computing (Denver, CO, 1972), ACM, New York, 1972, 88–93 | DOI | Zbl

[71] C. M. Fiduccia, “On obtaining upper bound on the complexity of matrix multiplication”, Complexity of computer computations (IBM T. J. Watson Res. Center, Yorktown Heights, NY, 1972), IBM Research Symposia Series, Plenum, New York, 1972, 31–40 | DOI | MR

[72] P. C. Fischer, “Further schemes for combining matrix algorithms”, Automata, languages and programming (2nd colloq., Univ. Saarbrücken, Saarbrücken, 1974), Lecture Notes in Comput. Sci., 14, Springer, Berlin, 1974, 428–436 | DOI | MR | Zbl

[73] J. von zur Gathen, J. Gerhard, Modern computer algebra, 3rd. ed., Cambridge Univ. Press, Cambridge, 2013, xiv+795 pp. | DOI | MR | Zbl

[74] G. H. Golub, C. F. Van Loan, Matrix computations, Johns Hopkins Stud. Math. Sci., 4th ed., Johns Hopkins Univ. Press, Baltimore, MD, 2013, xiv+756 pp. | MR | Zbl

[75] L. Greengard, V. Rokhlin, “A fast algorithm for particle simulation”, J. Comput. Phys., 73:2 (1987), 325–348 | DOI | MR | Zbl

[76] Y. Han, A $\Theta(n^2)$ time matrix multiplication algorithm, 2016, arXiv: 1612.04208v1

[77] N. J. Higham, “Exploiting fast matrix multiplication within the level 3 BLAS”, ACM Trans. Math. Software, 16:4 (1990), 352–368 | DOI | MR | Zbl

[78] N. J. Higham, Accuracy and stability of numerical analysis, 2nd ed., SIAM, Philadelphia, PA, 2002, xxx+680 pp. | DOI | MR | Zbl

[79] J. E. Hopcroft, L. R. Kerr, “Some techniques for proving certain simple programs optimal”, 10th annual symposium on switching and automata theory (Waterloo, ON, 1969), IEEE Computer Soc., Washington, DC, 1969, 36–45 | DOI

[80] J. E. Hopcroft, L. R. Kerr, “On minimizing the number of multiplications necessary for matrix multiplication”, SIAM J. Appl. Math., 20:1 (1971), 30–36 | DOI | MR | Zbl

[81] J. Hopcroft, J. Musinski, “Duality applied to the complexity of matrix multiplication and other bilinear forms”, SIAM J. Comput., 2:3 (1973), 159–173 | DOI | MR | Zbl

[82] Xiaohan Huang, V. Y. Pan, “Fast rectangular matrix multiplication and applications”, J. Complexity, 14:2 (1998), 257–299 ; Proceedings of the annual ACM international symposium on parallel algebraic and symbolic computation (PASCO' 97), ACM, New York, 1997, 11–23 | DOI | MR | Zbl

[83] Seung Gyu Hyun, R. Lebreton, É. Schost, “Algorithms for structured linear systems solving and their implementation”, ISSAC' 17 Proceedings of the 2017 international symposium on symbolic and algebraic computation, ACM, New York, 2017, 205–212 ; https://hal-lirmm.ccsd.cnrs.fr/lirmm-01484831 | DOI

[84] R. W. Johnson, A. M. McLoughlin, “Noncommutative bilinear algorithms for $3\times 3$ matrix multiplication”, SIAM J. Comput., 15:2 (1986), 595–603 | DOI | MR | Zbl

[85] H. Kaplan, M. Sharir, E. Verbin, “Colored intersection searching via sparse rectangular matrix multiplication”, SCG' 06 Proceedings of the 22nd annual ACM symposium on computational geometry, ACM, New York, 2006, 52–60 | DOI | MR | Zbl

[86] I. Kaporin, “A practical algorithm for faster matrix multiplication”, Numer. Linear Algebra Appl., 6:8 (1999), 687–700 | 3.0.CO;2-I class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[87] I. Kaporin, “The aggregation and cancellation techniques as a practical tool for faster matrix multiplication”, Theoret. Comput. Sci., 315:2-3 (2004), 469–510 | DOI | MR | Zbl

[88] ShanXue Ke, BenSheng Zeng, WenBao Han, V. Y. Pan, “Fast rectangular matrix multiplication and some applications”, Sci. China Ser. A, 51:3 (2008), 389–406 | DOI | MR | Zbl

[89] P. Kirrinnis, “Partial fraction decomposition in $\mathbf C(z)$ and simultaneous Newton iteration for factorization in $\mathbf C[z]$”, J. Complexity, 14:3 (1998), 378–444 | DOI | MR | Zbl

[90] D. Knut, Iskusstvo programmirovaniya na EVM, v. 2, Poluchislennye algoritmy, Mir, M., 1977, 724 pp. ; D. E. Knuth, The art of computer programming, т. 2, Seminumerical algorithms, 1st ed., Addison-Wesley Publishing Co., Reading, MA–London–Don Mills, ON, 1969, xi+624 с. ; 2nd ed., 1981, xiii+688 pp. ; 3rd ed., 1998, xiv+762 pp. | MR | Zbl | MR | Zbl | MR | Zbl | MR | Zbl

[91] D. Knut, Iskusstvo programmirovaniya dlya EVM, v. 3, Sortirovka i poisk, Mir, M., 1978, 846 pp. ; D. E. Knuth, The art of computer programming, т. 3, Sorting and searching, 1st ed., Addison-Wesley Publishing Co., Reading, MA–London–Don Mills, ON, 1973, xi+722 с. ; 2nd ed., 1998, xiv+780 pp. | MR | Zbl | MR | Zbl | MR | Zbl

[92] T. G. Kolda, B. W. Bader, “Tensor decompositions and applications”, SIAM Rev., 51:3 (2009), 455–500 | DOI | MR | Zbl

[93] J. B. Kruskal, “Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics”, Linear Algebra Appl., 18:2 (1977), 95–138 | DOI | MR | Zbl

[94] J. Laderman, V. Pan, Xuan-He Sha, “On practical algorithms for accelerated matrix multiplication”, Linear Algebra Appl., 162/164 (1992), 557–588 | DOI | MR | Zbl

[95] J. M. Landsberg, “New lower bounds for the rank of matrix multiplication”, SIAM J. Comput., 43:1 (2014), 144–149 | DOI | MR | Zbl

[96] L. Lee, “Fast context-free grammar parsing requires fast boolean matrix multiplication”, J. ACM, 49:1 (2002), 1–15 | DOI | MR | Zbl

[97] F. Le Gall, “Faster algorithms for rectangular matrix multiplication”, 2012 IEEE 53rd annual symposium on foundations of computer science, IEEE Computer Soc., Los Alamitos, CA, 2012, 514–523 | DOI | MR

[98] F. Le Gall, “Powers of tensors and fast matrix multiplication”, ISSAC' 14 Proceedings of the 39th international symposium on symbolic and algebraic computation, ACM, New York, 2014, 296–303 | DOI | MR | Zbl

[99] G. Lotti, F. Romani, “On the asymptotic complexity of rectangular matrix multiplication”, Theoret. Comput. Sci., 23:2 (1983), 171–185 | DOI | MR | Zbl

[100] M. W. Mahoney, “Randomized algorithms for matrices and data”, Foundations and Trends in Machine Learning, 3:2 (2011), 123–224 ; Abridged version in: Advances in machine learning and data mining for astronomy, eds. M. J. Way, J. D. Scargle, K. M. Ali, A. N. Srivastava, Chapman Hall/CRC, Boca Raton, FL, 2012, 647–672 | DOI | Zbl | DOI

[101] A. Massarenti, E. Raviolo, “Corrigendum to "The rank of $n\times n$ matrix multiplication is at least $3n^2-2\sqrt 2n^{3/2}-3n$" [Linear Algebra Appl. 438 (11) (2013) 4500–4509]”, Linear Algebra Appl., 445 (2014), 369–371 | DOI | MR | Zbl

[102] R. Moenck, A. Borodin, “Fast modular transform via division”, 13th annual symposium on switching and automata theory, IEEE Comp. Soc. Press, Washington, DC, 1972, 90–96 | DOI

[103] T. S. Motzkin, “Evaluation of polynomials. Evaluation of rational functions”, in “The annual meeting in Pittsburgh”, Bull. Amer. Math. Soc., 61:2 (1955), 163 | DOI

[104] Jinsoo Oh, Jin Kim, Byung-Ro Moon, “On the inequivalence of bilinear algorithms for $3\times 3$ matrix multiplication”, Inform. Process. Lett., 113:17 (2013), 640–645 | DOI | MR | Zbl

[105] I. Oseledets, E. Tyrtyshnikov, “TT-cross approximation for multidimensional arrays”, Linear Algebra Appl., 432:1 (2010), 70–88 | DOI | MR | Zbl

[106] A. Ostrowski, “On two problems in absract algebra connected with Horner's rule”, Studies in mathematics and mechanics presented to Richard von Mises, Academic Press Inc., New York, 1954, 40–48 | MR | Zbl

[107] V. Ya. Pan, “Nekotorye skhemy dlya vychisleniya mnogochlenov s veschestvennymi koeffitsientami”, Dokl. AN SSSR, 127:2 (1959), 266–269 | MR | Zbl

[108] V. Ya. Pan, “Methods of computing values of polynomials”, Russian Math. Surveys, 21:1 (1966), 105–136 | DOI | MR | Zbl

[109] V. Ya. Pan, “O skhemakh vychisleniya proizvedenii matrits i obratnoi matritsy”, UMN, 27:5(167) (1972), 249–250 | MR | Zbl

[110] V. Y. Pan, “Strassen's algorithm is not optimal trilinear technique of aggregating, uniting and canceling for constructing fast algorithms for matrix operations”, 19th annual IEEE symposium on foundations of computer science (Ann Arbor, MI, 1978), IEEE Computer Soc., Long Beach, CA, 1978, 166–176 | DOI | MR

[111] V. Y. Pan, “Field extension and trilinear aggregating, uniting and canceling for the acceleration of matrix multiplications”, 20th annual IEEE symposium on foundations of computer science, IEEE Computer Soc., Long Beach, CA, 1979, 28–38 | DOI

[112] V. Y. Pan, “New fast algorithms for matrix operations”, SIAM J. Comput., 9:2 (1980), 321–342 ; Res. rep. RC 7555, IBM T. J. Watson Res. Center, Yorktown Heights, NY, 1979, 53 pp. | DOI | MR | Zbl

[113] V. Ya. Pan, “New combinations of methods for the acceleration of matrix multiplications”, Comput. Math. Appl., 7:1 (1981), 73–125 | DOI | MR | Zbl

[114] V. Ya. Pan, “Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication”, Comput. Math. Appl., 8:1 (1982), 23–34 | DOI | MR | Zbl

[115] V. Pan, “Fast matrix multiplication without APA-algorithms”, Comput. Math. Appl., 8:5 (1982), 343–366 | DOI | MR | Zbl

[116] V. Pan, “How can we speed up matrix multiplication?”, SIAM Rev., 26 (1984), 393–415 | DOI | MR | Zbl

[117] V. Ya. Pan, “The techniques of trilinear aggregating and the recent progress in the asymptotic acceleration of matrix operations”, Theoret. Comput. Sci., 33:1 (1984), 117–138 | DOI | MR | Zbl

[118] V. Pan, How to multiply matrices faster, Lecture Notes in Comput. Sci., 179, Springer-Verlag, Berlin, 1984, xi+212 pp. | DOI | MR | Zbl

[119] V. Pan, “On computations with dense structured matrices”, Math. Comp., 55:191 (1990), 179–190 ; ISSAC' 89 Proceedings of the ACM–SIGSAM 1989 international symposium on symbolic and algebraic computation, ACM, New York, 1989, 34–42 | DOI | MR | Zbl | DOI

[120] V. Y. Pan, Structured matrices and polynomials. Unified superfast algorithms, Birkhäuser Boston, Inc., Boston, MA; Springer-Verlag, New York, 2001, xxvi+278 pp. | DOI | MR | Zbl

[121] V. Y. Pan, Better late than never: filling a void in the history of fast matrix multiplication and tensor decompositions, arXiv: 1411.1972

[122] V. Y. Pan, “Fast approximate computations with Cauchy matrices and polynomials”, Math. Comp., 86:308 (2017), 2799–2826 ; “Fast approximate computations with Cauchy matrices, polynomials and rational functions”, Computer science – theory and applications, CSR' 2014 Proceedings of the 9th international computer science symposium, Lecture Notes in Comput. Sci., 8476, Springer, Cham, 2014, 287–299 | DOI | MR | Zbl | DOI | MR | Zbl

[123] V. Y. Pan, “Transformations of matrix structures work again”, Linear Algebra Appl., 465 (2015), 107–138 | DOI | MR | Zbl

[124] V. Y. Pan, Matrix multiplication, trilinear decompositions, APA algorithms, and summation, arXiv: 1412.1145

[125] V. Y. Pan, “How bad are Vandermonde matrices?”, SIAM J. Matrix Anal. Appl., 37:2 (2016), 676–694 | DOI | MR | Zbl

[126] V. Pan, A. Sadikou, E. Landowne, “Polynomial division with a reminder by means of evaluation and interpolation”, Inform. Process. Lett., 44:3 (1992), 149–153 | DOI | MR | Zbl

[127] V. Y. Pan, E. P. Tsigaridas, “Nearly optimal computations with structured matrices”, Theoret. Comput. Sci., 681 (2017), 117–137 ; SNC' 2014 Proceedings of the 2014 Symposium on Symbolic-Numeric Computation, ACM, New York, 2014, 21–30 ; arXiv: https://hal.inria.fr/hal-009805911404.4768 | DOI | MR | Zbl | DOI | MR | Zbl

[128] R. L. Probert, “On the complexity of symmetric computations”, INFOR–Canad. J. Operational Res. and Information Processing, 12:1 (1974), 71–86 | DOI | MR | Zbl

[129] R. L. Probert, “On the additive complexity of matrix multiplication”, SIAM J. Comput., 5:2 (1976), 187–203 | DOI | MR | Zbl

[130] R. Raz, “On the complexity of matrix product”, STOC' 02 Proceedings of the 34th annual ACM symposium on theory of computing, ACM, New York, 2002, 144–151 | DOI | MR | Zbl

[131] R. Raz, A. Shpilka, “Lower bounds for matrix product in bounded depth circuits with arbitrary gates”, SIAM J. Comput., 32:2 (2003), 488–513 | DOI | MR | Zbl

[132] F. Romani, Private communication, 1979

[133] F. Romani, “Some properties of disjoint sums of tensors related to matrix multiplication”, SIAM J. Comput., 11:2 (1982), 263–267 | DOI | MR | Zbl

[134] P. Sankowski, M. Mucha, “Fast dynamic transitive closure with lookahead”, Algorithmica, 56:2 (2010), 180–197 | DOI | MR | Zbl

[135] A. Schönhage, “Partial and total matrix multiplication”, SIAM J. Comput., 10:3 (1981), 434–455 | DOI | MR | Zbl

[136] A. Shpilka, “Lower bounds for matrix product”, SIAM J. Comput., 32:5 (2003), 1185–1200 ; 42nd IEEE symposium on foundations of computer science, IEEE Computer Soc., Washington, DC, 2001, 358 | DOI | MR | Zbl | DOI

[137] A. V. Smirnov, “The bilinear complexity and practical algorithms for matrix multiplication”, Comput. Math. Math. Phys., 53:12 (2013), 1781–1795 | DOI | DOI | MR | Zbl

[138] A. J. Stothers, On the complexity of matrix multiplication, Ph.D. Thesis, Univ. of Edinburgh, 2010, 118 pp. http://hdl.handle.net/1842/4734

[139] V. Strassen, “Gaussian elimination is not optimal”, Numer. Math., 13:4 (1969), 354–356 | DOI | MR | Zbl

[140] V. Strassen, “Evaluation of rational functions”, Complexity of computer computations (IBM T. J. Watson Res. Center, Yorktown Heights, NY, 1972), Plenum Press, New York, 1972, 1–10 | MR

[141] V. Strassen, “Vermeidung von Divisionen”, J. Reine Angew. Math., 1973:264 (1973), 184–202 | MR | Zbl

[142] V. Strassen, “Some results in algebraic complexity theory”, Proceedings of the International congress of mathematicians (Vancouver, BC, 1974), v. 2, Canad. Math. Congress, Montreal, QC, 1975, 497–501 | MR | Zbl

[143] V. Strassen, “The asymptotic spectrum of tensors and the exponent of matrix multiplication”, 27th annual symposium on foundation of computer science (Toronto, ON, 1986), IEEE Computer Soc., Washington, DC, 1986, 49–54 | DOI

[144] J. Todd, “Motivation for working in numerical analysis”, Comm. Pure Appl. Math., 8:1 (1955), 97–116 | DOI | MR | Zbl

[145] A. L. Toom, “The complexity of a scheme of functional elements realizing the multiplication of integers”, Soviet Math. Dokl., 3 (1963), 714–716 | MR | Zbl

[146] L. N. Trefethen, D. Bau, Numerical linear algebra, SIAM, Philadelphia, PA, 1997, xii+361 pp. | MR | Zbl

[147] E. E. Tyrtyshnikov, “Tensor approximations of matrices generated by asymptotically smooth functions”, Sb. Math., 194:6 (2003), 941–954 | DOI | DOI | MR | Zbl

[148] L. G. Valiant, “General context-free recognition in less than cubic time”, J. Comput. System Sci., 10:2 (1975), 308–315 | DOI | MR | Zbl

[149] V. Vassilevska Williams, “Multiplying matrices faster than Coppersmith–Winograd”, STOC' 12 Proceedings of the 44th annual ACM symposium on theory of computing, ACM, New York, 2012, 887–898 | DOI | Zbl

[150] A. Waksman, “On Winograd's algorithm for inner products”, IEEE Trans. Computers, C-19:4 (1970), 360–361 | DOI | MR | Zbl

[151] S. Winograd, “On the number of multiplications required to compute certain functions”, Proc. Nat. Acad. Sci. U.S.A., 58:5 (1967), 1840–1842 | DOI | MR | Zbl

[152] S. Winograd, “A new algorithm for inner product”, IEEE Trans. Computers, C-17:7 (1968), 693–694 | DOI | Zbl

[153] S. Winograd, “On the number of multiplications necessary to compute certain functions”, Comm. Pure Appl. Math., 23:2 (1970), 165–179 | DOI | MR | Zbl

[154] S. Winograd, Arithmetic complexity of computations, CBMS–NSF Regional Conference Series in Applied Mathematics, 33, SIAM, Philadelphia, PA, 1980, iii+93 pp. | MR | Zbl

[155] Yuanzhe Xi, Jianlin Xia, S. Cauley, V. Balakrishnan, “Superfast and stable structured solvers for Toeplitz least squares via randomized sampling”, SIAM J. Matrix Anal. Appl., 35:1 (2014), 44–72 | DOI | MR | Zbl

[156] Jianlin Xia, Yuanzhe Xi, Ming Gu, “A superfast structured solver for Toeplitz linear systems via randomized sampling”, SIAM J. Matrix Anal. Appl., 33:3 (2012), 837–858 | DOI | MR | Zbl

[157] Huacheng Yu, “An improved combinatorial algorithm for Boolean matrix multiplication”, Automata, languages, and programming, Part I, Lecture Notes in Comput. Sci., 9134, Springer, Heidelberg, 2015, 1094–1105 | DOI | MR | Zbl

[158] R. Yuster, “Efficient algorithms on sets of permutations, dominance, and real-weighted APSP”, Proceedings of the 20th annual ACM–SIAM symposium on discrete algorithms, SIAM, Philadelphia, PA, 2009, 950–957 | DOI | MR

[159] R. Yuster, U. Zwick, “Detecting short directed cycles using rectangular matrix multiplication and dynamic programming”, Proceedings of the 15th annual ACM–SIAM symposium on discrete algorithms, ACM, New York, 2004, 254–260 | MR | Zbl

[160] R. Yuster, U. Zwick, “Fast sparse matrix multiplication”, ACM Trans. Algorithms, 1:1 (2005), 2–13 | DOI | MR | Zbl

[161] R. Yuster, U. Zwick, “Answering distance queries in directed graphs using fast matrix multiplication”, FOCS 2005 46th annual IEEE symposium on foundations of computer science (Pittsburgh, PA), IEEE Computer Soc., Los Alamitos, CA, 2005, 389–396 | DOI

[162] U. Zwick, “All-pairs shortest paths using bridging sets and rectangular matrix multiplication”, J. ACM, 49:3 (2002), 289–317 | DOI | MR | Zbl