Geometry and the complexity of matrix multiplication

Landsberg, J.

doi:10.1090/S0273-0979-08-01176-2

Geometry and the complexity of matrix multiplication
HTML articles powered by AMS MathViewer

by J. M. Landsberg PDF

Bull. Amer. Math. Soc. 45 (2008), 247-284 Request permission

Abstract:

We survey results in algebraic complexity theory, focusing on matrix multiplication. Our goals are (i) to show how open questions in algebraic complexity theory are naturally posed as questions in geometry and representation theory, (ii) to motivate researchers to work on these questions, and (iii) to point out relations with more general problems in geometry. The key geometric objects for our study are the secant varieties of Segre varieties. We explain how these varieties are also useful for algebraic statistics, the study of phylogenetic invariants, and quantum computing.

References

Induction for secant varieties of Segre varieties

A. Alder and V. Strassen, On the algorithmic complexity of associative algebras, Theoret. Comput. Sci. 15 (1981), no. 2, 201–211. MR 623595, DOI 10.1016/0304-3975(81)90070-0
Valery B. Alekseyev, On the complexity of some algorithms of matrix multiplication, J. Algorithms 6 (1985), no. 1, 71–85. MR 780851, DOI 10.1016/0196-6774(85)90019-7
J. Alexander and A. Hirschowitz, Polynomial interpolation in several variables, J. Algebraic Geom. 4 (1995), no. 2, 201–222. MR 1311347

Phylogenetic ideals and varieties for the general Markov model

Elizabeth S. Allman and John A. Rhodes, Phylogenetic invariants for the general Markov model of sequence mutation, Math. Biosci. 186 (2003), no. 2, 113–144. MR 2024609, DOI 10.1016/j.mbs.2003.08.004
Wolf Barth, Submanifolds of low codimension in projective space, Proceedings of the International Congress of Mathematicians (Vancouver, B.C., 1974) Canad. Math. Congress, Montreal, Que., 1975, pp. 409–413. MR 0422294
Ingemar Bengtsson and Karol Życzkowski, Geometry of quantum states, Cambridge University Press, Cambridge, 2006. An introduction to quantum entanglement. MR 2230995, DOI 10.1017/CBO9780511535048
Dario Bini, Milvio Capovani, Francesco Romani, and Grazia Lotti, $O(n^{2.7799})$ complexity for $n\times n$ approximate matrix multiplication, Inform. Process. Lett. 8 (1979), no. 5, 234–235. MR 534068, DOI 10.1016/0020-0190(79)90113-3
Markus Bläser, A $\frac 52 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, pp. 45–50. MR 1916183, DOI 10.1109/SFFCS.1999.814576
Markus Bläser, On the complexity of the multiplication of matrices of small formats, J. Complexity 19 (2003), no. 1, 43–60. MR 1951322, DOI 10.1016/S0885-064X(02)00007-9

On the Alexander-Hirschowitz theorem

Roger W. Brockett and David Dobkin, On the optimal evaluation of a set of bilinear forms, Linear Algebra Appl. 19 (1978), no. 3, 207–235. MR 495183, DOI 10.1016/0024-3795(78)90012-5
Peter Bürgisser, Michael Clausen, and M. Amin Shokrollahi, Algebraic complexity theory, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315, Springer-Verlag, Berlin, 1997. With the collaboration of Thomas Lickteig. MR 1440179, DOI 10.1007/978-3-662-03338-8
M. V. Catalisano, A. V. Geramita, and A. Gimigliano, On the rank of tensors, via secant varieties and fat points, Zero-dimensional schemes and applications (Naples, 2000) Queen’s Papers in Pure and Appl. Math., vol. 123, Queen’s Univ., Kingston, ON, 2002, pp. 133–147. MR 1898833
M. V. Catalisano, A. V. Geramita, and A. Gimigliano, Ranks of tensors, secant varieties of Segre varieties and fat points, Linear Algebra Appl. 355 (2002), 263–285. MR 1930149, DOI 10.1016/S0024-3795(02)00352-X
M. V. Catalisano, A. V. Geramita, and A. Gimigliano, Higher secant varieties of Segre-Veronese varieties, Projective varieties with unexpected properties, Walter de Gruyter, Berlin, 2005, pp. 81–107. MR 2202248
M. V. Catalisano, A. V. Geramita, and A. Gimigliano, Secant varieties of Grassmann varieties, Proc. Amer. Math. Soc. 133 (2005), no. 3, 633–642. MR 2113908, DOI 10.1090/S0002-9939-04-07632-4

On the ideals of secant varieties to certain rational varieties

Invariants of phylogenies in a simple case with discrete states

4

Ciro Ciliberto, Geometric aspects of polynomial interpolation in more variables and of Waring’s problem, European Congress of Mathematics, Vol. I (Barcelona, 2000) Progr. Math., vol. 201, Birkhäuser, Basel, 2001, pp. 289–316. MR 1905326

Group-theoretic algorithms for matrix multiplication

A group theoretic approach to fast matrix multiplication

Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251–280. MR 1056627, DOI 10.1016/S0747-7171(08)80013-2

Multi-particle entanglement

Schmidt measure as a tool for quantifying multiparticle entanglement

64

William Fulton and Joe Harris, Representation theory, Graduate Texts in Mathematics, vol. 129, Springer-Verlag, New York, 1991. A first course; Readings in Mathematics. MR 1153249, DOI 10.1007/978-1-4612-0979-9
Luis David Garcia, Michael Stillman, and Bernd Sturmfels, Algebraic geometry of Bayesian networks, J. Symbolic Comput. 39 (2005), no. 3-4, 331–355. MR 2168286, DOI 10.1016/j.jsc.2004.11.007
Joe Harris, Algebraic geometry, Graduate Texts in Mathematics, vol. 133, Springer-Verlag, New York, 1992. A first course. MR 1182558, DOI 10.1007/978-1-4757-2189-8
Robin Hartshorne, Varieties of small codimension in projective space, Bull. Amer. Math. Soc. 80 (1974), 1017–1032. MR 384816, DOI 10.1090/S0002-9904-1974-13612-8
J. E. Hopcroft and L. R. Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM J. Appl. Math. 20 (1971), 30–36. MR 274293, DOI 10.1137/0120004
Serkan Hoşten and Suela Ruffa, Introductory notes to algebraic statistics, Rend. Istit. Mat. Univ. Trieste 37 (2005), no. 1-2, 39–70 (2006). MR 2227048
Thomas A. Ivey and J. M. Landsberg, Cartan for beginners: differential geometry via moving frames and exterior differential systems, Graduate Studies in Mathematics, vol. 61, American Mathematical Society, Providence, RI, 2003. MR 2003610, DOI 10.1090/gsm/061
Julian D. Laderman, A noncommutative algorithm for multiplying $3\times 3$ matrices using $23$ multiplications, Bull. Amer. Math. Soc. 82 (1976), no. 1, 126–128. MR 395320, DOI 10.1090/S0002-9904-1976-13988-2

A rate-independent technique for analysis of nucleic acid sequences: evolutionary parsimony

4

J. M. Landsberg, The border rank of the multiplication of $2\times 2$ matrices is seven, J. Amer. Math. Soc. 19 (2006), no. 2, 447–459. MR 2188132, DOI 10.1090/S0894-0347-05-00506-0
J. M. Landsberg and L. Manivel, On the ideals of secant varieties of Segre varieties, Found. Comput. Math. 4 (2004), no. 4, 397–422. MR 2097214, DOI 10.1007/s10208-003-0115-9
Joseph M. Landsberg and Laurent Manivel, On the projective geometry of rational homogeneous varieties, Comment. Math. Helv. 78 (2003), no. 1, 65–100. MR 1966752, DOI 10.1007/s000140300003

Generalizations of Strassen’s equations for Secant varieties of Segre varieties

36

Computational complexity and geometry

J. M. Landsberg and Jerzy Weyman, On the ideals and singularities of secant varieties of Segre varieties, Bull. Lond. Math. Soc. 39 (2007), no. 4, 685–697. MR 2346950, DOI 10.1112/blms/bdm049
R. Lazarsfeld and A. Van de Ven, Topics in the geometry of projective space, DMV Seminar, vol. 4, Birkhäuser Verlag, Basel, 1984. Recent work of F. L. Zak; With an addendum by Zak. MR 808175, DOI 10.1007/978-3-0348-9348-0
Thomas Lickteig, A note on border rank, Inform. Process. Lett. 18 (1984), no. 3, 173–178. MR 760371, DOI 10.1016/0020-0190(84)90023-1
Thomas Lickteig, Typical tensorial rank, Linear Algebra Appl. 69 (1985), 95–120. MR 798367, DOI 10.1016/0024-3795(85)90070-9

Symplectic bundles on the plane, secant varieties and Lüroth quartics revisited

Giorgio Ottaviani and Elena Rubei, Quivers and the cohomology of homogeneous vector bundles, Duke Math. J. 132 (2006), no. 3, 459–508. MR 2219264, DOI 10.1215/S0012-7094-06-13233-7
Lior Pachter and Bernd Sturmfels (eds.), Algebraic statistics for computational biology, Cambridge University Press, New York, 2005. MR 2205865, DOI 10.1017/CBO9780511610684
A. Schönhage, Partial and total matrix multiplication, SIAM J. Comput. 10 (1981), no. 3, 434–455. MR 623057, DOI 10.1137/0210032
Jean-Pierre Serre, Linear representations of finite groups, Graduate Texts in Mathematics, Vol. 42, Springer-Verlag, New York-Heidelberg, 1977. Translated from the second French edition by Leonard L. Scott. MR 0450380, DOI 10.1007/978-1-4684-9458-7

Sintorno ai punti doppi impropri di una superficie generale dello spazio a quattro dimensioni, e a suio punti tripli apparenti

15

Secant varieties and prolongations

V. Strassen, Rank and optimal computation of generic tensors, Linear Algebra Appl. 52/53 (1983), 645–685. MR 709378, DOI 10.1016/0024-3795(83)80041-X
V. Strassen, Relative bilinear complexity and matrix multiplication, J. Reine Angew. Math. 375/376 (1987), 406–443. MR 882307, DOI 10.1515/crll.1987.375-376.406
Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354–356. MR 248973, DOI 10.1007/BF02165411
R. C. Vaughan and T. D. Wooley, Waring’s problem: a survey, Number theory for the millennium, III (Urbana, IL, 2000) A K Peters, Natick, MA, 2002, pp. 301–340. MR 1956283, DOI 10.1198/004017002320256684
Abraham Waksman, On Winograd’s algorithm for inner products, IEEE Trans. Comput. C-19 (1970), no. 4, 360–361. MR 455534, DOI 10.1109/t-c.1970.222926
Jerzy Weyman, Cohomology of vector bundles and syzygies, Cambridge Tracts in Mathematics, vol. 149, Cambridge University Press, Cambridge, 2003. MR 1988690, DOI 10.1017/CBO9780511546556
S. Winograd, On multiplication of $2\times 2$ matrices, Linear Algebra Appl. 4 (1971), 381–388. MR 297115, DOI 10.1016/0024-3795(71)90009-7
F. L. Zak, Projections of algebraic varieties, Mat. Sb. (N.S.) 116(158) (1981), no. 4, 593–602, 608 (Russian). MR 665860
F. L. Zak, Tangents and secants of algebraic varieties, Translations of Mathematical Monographs, vol. 127, American Mathematical Society, Providence, RI, 1993. Translated from the Russian manuscript by the author. MR 1234494, DOI 10.1090/mmono/127