Fast Matrix Multiplication

by Markus Bläser

Theory of Computing, Graduate Surveys 5, pp. 1-60, 2013

Bibliography with links to cited articles

[1]   Valery B. Alekseyev: On the complexity of some algorithms of matrix multiplication. J. Algorithms, 6(1):71–85, 1985. [doi:10.1016/0196-6774(85)90019-7]

[2]   Noga Alon, Amir Shpilka, and Christopher Umans: On sunflowers and matrix multiplication. Comput. Complexity, 22(2):219–243, 2013. Preliminary version in CCC’12. See also at ECCC. [doi:10.1007/s00037-013-0060-1]

[3]   Ulrich Baum and Michael Clausen: Fast Fourier Transforms. Spektrum Akademischer Verlag, 1993.

[4]   Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti: O(n2.7799) complexity for n×n approximate matrix multiplication. Inform. Process. Lett., 8(5):234–235, 1979. [doi:10.1016/0020-0190(79)90113-3]

[5]   Markus Bläser: On the complexity of the multiplication of matrices of small formats. J. Complexity, 19(1):43–60, 2003. [doi:10.1016/S0885-064X(02)00007-9]

[6]   Alfred T. Brauer: On addition chains. Bull. Amer. Math. Soc., 45(2):736–739, 1939. [doi:10.1090/S0002-9904-1939-07068-7]

[7]   Nader H. Bshouty: On the additive complexity of 2 × 2-matrix multiplication. Inform. Process. Lett., 56(6):329–335, 1995. Preliminary version in SAC’91. [doi:10.1016/0020-0190(95)00176-X]

[8]   Peter Bürgisser, Michael Clausen, and Mohammad Amin Shokrollahi: Algebraic Complexity Theory. Springer, 1997. [doi:10.1007/978-3-662-03338-8]

[9]   Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, and Christopher Umans: Group-theoretic algorithms for matrix multiplication. In Proc. 46th FOCS, pp. 379–388. IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.39]

[10]   Henry Cohn and Christopher Umans: A group-theoretic approach to fast matrix multiplication. In Proc. 44th FOCS, pp. 438–449. IEEE Comp. Soc. Press, 2003. [doi:10.1109/SFCS.2003.1238217]

[11]   Henry Cohn and Christopher Umans: Fast matrix multiplication using coherent configurations. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 1074–1087. ACM Press, 2013. SIAM. See also at arXiv.

[12]   Don Coppersmith and Shmuel Winograd: On the asymptotic complexity of matrix multiplication. SIAM J. Comput., 11(3):472–492, 1982. Preliminary version in FOCS’81. [doi:10.1137/0211038]

[13]   Don Coppersmith and Shmuel Winograd: Matrix multiplication via arithmetic progressions. J. Symbolic Comput., 9(3):251–280, 1990. Preliminary version in STOC’87. [doi:10.1016/S0747-7171(08)80013-2]

[14]   Alexander M. Davie and Andrew James Stothers: Improved bound for complexity of matrix multiplication. Proc. Royal Soc. Edinburgh: Sect. A Math., 143(2):351–369, 2013. [doi:10.1017/S0308210511001648]

[15]   Hans F. de Groote: On the varieties of optimal algorithms for the computation of bilinear mappings II: Optimal algorithms for 2 × 2–matrix multiplication. Theoret. Comput. Sci., 7(2):127–148, 1978. [doi:10.1016/0304-3975(78)90045-2]

[16]   Hans F. de Groote: Lectures on the Complexity of Bilinear Problems. Volume 245 of Lecture Notes in Computer Science. Springer, 1987. [doi:10.1007/BFb0020719]

[17]   Johan Håstad: Tensor rank is NP-complete. J. Algorithms, 11(4):644–654, 1990. Preliminary version in ICALP’89. [doi:10.1016/0196-6774(90)90014-6]

[18]   Gordon James and Martin Liebeck: Representations and Characters of Groups. Cambridge Univ. Press, 2001. [doi:10.1017/CBO9780511814532]

[19]   Anatolii Alexeevich Karatsuba: The complexity of computations. Proc. Steklov Institute of Mathematics, 211(169–183), 1995. Translation from Trudy Mat. Inst. Steklova, 207, 180–196 (1994). Available at http://www.cs.ru/personal/karatsuba/divcen.pdf.

[20]   Anatolii Alexeevitch Karatsuba and Yuri Petrovich Ofman: Multiplication of many-digit numbers by automatic computers. Proc. USSR Academy of Sciences, 145(293–294), 1962.

[21]   Julian D. Laderman: A noncommutative algorithm for multiplying 3× 3–matrices using 23 multiplications. Bull. Amer. Math. Soc., 82(1):126–128, 1976. [doi:10.1090/S0002-9904-1976-13988-2]

[22]   Theodore S. Motzkin: Evaluation of polynomials. Bull. Amer. Math. Soc., 61(2):113–184, 1955. [doi:10.1090/S0002-9904-1955-09897-5]

[23]   Alexander M. Ostrowksi: On two problems in abstract algebra connected with Horner’s rule. In Studies in Mathematics and Mechanics presented to Richard von Mises, pp. 40–48. Academic Press, 1954.

[24]   Victor Ya. Pan: Methods of computing values of polynomials. Russ. Math. Surv., 21(1):105–136, 1966. [doi:10.1070/RM1966v021n01ABEH004147]

[25]   Victor Ya. Pan: New fast algorithms for matrix operations. SIAM J. Comput., 9(2):321–342, 1980. [doi:10.1137/0209027]

[26]   Arnold Scholz: Aufgabe 253. Jahresberichte der deutschen Mathematiker-Vereinigung, 47(4):41–42, 1937.

[27]   Arnold Schönhage: A lower bound for the length of addition chains. Theoret. Comput. Sci., 1(1):1–12, 1975. [doi:10.1016/0304-3975(75)90008-0]

[28]   Arnold Schönhage: Partial and total matrix multiplication. SIAM J. Comput., 10(3):434–455, 1981. [doi:10.1137/0210032]

[29]   Kenneth B. Stolarsky: A lower bound for the Scholz–Brauer problem. Canad. J. Math., 21:675–683, 1969. [doi:10.4153/CJM-1969-077-x]

[30]   Andrew James Stothers: On the complexity of matrix multiplication. Ph. D. thesis, The University of Edinburgh, 2010. Edinburgh Research Archive.

[31]   Volker Strassen: Gaussian elimination is not optimal. Numer. Math., 13(4):354–356, 1969. [doi:10.1007/BF02165411]

[32]   Volker Strassen: Vermeidung von Divisionen. J. Reine Angew. Math., 264:184–202, 1973. EUMDL.

[33]   Volker Strassen: Relative bilinear complexity and matrix multiplication. J. Reine Angew. Math., 375/376:406–443, 1987. EUDML.

[34]    Abraham Waksman: On Winograd’s algorithm for inner products. IEEE Trans. Comput., C–19(4):360–361, 1970. [doi:10.1109/T-C.1970.222926]

[35]   Virginia Vassilevska Williams: Multiplying matrices faster than Coppersmith-Winograd. In Proc. 44th STOC, pp. 887–898. ACM Press, 2012. [doi:10.1145/2213977.2214056]

[36]   Shmuel Winograd: A new algorithm for inner product. IEEE Trans. Comput., C–17(7):693–694, 1968. [doi:10.1109/TC.1968.227420]

[37]   Shmuel Winograd: On the number of multiplications necessary to compute certain functions. Comm. Pure and Appl. Math, 23(2):165–179, 1970. Preliminary version in PNAS 1967. [doi:10.1002/cpa.3160230204]

[38]   Shmuel Winograd: On multiplication of 2×2–matrices. Lin. Alg. Appl., 4(4):381–388, 1971. [doi:10.1016/0024-3795(71)90009-7]