Fast Matrix Multiplication
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]