{"id":538,"date":"2015-10-18T10:37:10","date_gmt":"2015-10-18T15:37:10","guid":{"rendered":"http:\/\/blogs.ams.org\/beyondreviews\/?p=538"},"modified":"2015-10-20T17:49:03","modified_gmt":"2015-10-20T22:49:03","slug":"geometry-and-computational-complexity-theory","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/beyondreviews\/2015\/10\/18\/geometry-and-computational-complexity-theory\/","title":{"rendered":"Geometry and Computational Complexity Theory"},"content":{"rendered":"

Mathematics flourishes when ideas from one area of mathematics can be used in another area. \u00a0For a long time (certainly since Descartes), algebra has been a great asset to geometry. \u00a0In return, geometry has been helpful to algebra, for instance through representation theory. \u00a0Here are two very fine reviews of papers that bring algebra and geometry to the question of computational complexity. \u00a0Both reviews are by\u00a0Peter B\u00fcrgisser<\/a>.<\/p>\n

The first article is a survey by Volker Strassen<\/a>\u00a0of his work on the complexity of matrix operations, and its growth into a larger application of geometry to the theory of bilinear maps. \u00a0The “well-known discovery” mentioned in the review is Strassen’s paper where he showed how one can\u00a0compute the product of two $n\\times n$ matrices with\u00a0fewer than $4.7n^{\\log_2(7)}\\approx 4.7n^{2.8}$ arithmetical operations. This then implies that one can\u00a0invert a non-singular matrix of order $n$ in less than $5.64 n^{\\log_2(7)} \\approx 6n^{2.8}$ arithmetical operations. \u00a0The traditional result is that if you only work with rows and columns, the lower bound on solving an $n\\times n$ system of linear equations is\u00a0$\\frac{1}{3}n^3$, which is achieved \u00a0by Gaussian elimination. \u00a0Strassen’s survey puts on display a\u00a0variety of mathematical\u00a0tools, such as\u00a0geometric invariant theory and the notion of asymptotic degenerations of bilinear maps. \u00a0 The appendix makes use of\u00a0representation theory.<\/p>\n

So Strassen\u00a0gives us an upper bound on the minimum number of operations needed for matrix multiplication. \u00a0What about a lower bound? \u00a0The second article is by J.M. Landsberg<\/a> wherein he gives a lower bound on the computational complexity of multiplication of $2\\times 2$ matrices. \u00a0(In Strassen’s result, plug in $n=2$ to see why there is a 7 in the title.) \u00a0Landsberg uses techniques from representation theory and geometry, in particular the secant variety<\/a>. \u00a0B\u00fcrgisser mentions in his review that there are some gaps in Landsberg’s original paper. \u00a0On the arXiv<\/a>, you can find an updated version<\/a> where some overlooked cases are treated.<\/p>\n

I hope you enjoy these reviews. \u00a0If you want to dig further into the subject, Landsberg has a book, Tensors: Geometry and Applications<\/a>, that sets up the background, describes the work on complexity of matrix multiplication, and applies the general techniques to other areas, such as P<\/strong> versus NP<\/strong>, signal processing, phylogenetics, and algebraic statistics. \u00a0It’s available from the AMS. \u00a0And there is a nice review<\/a> of it on MathSciNet.<\/p>\n

\n

MR2138544<\/a><\/strong> (2006d:68289)<\/strong>
\nStrassen, Volker<\/a>(D-KNST)<\/a>
\nKomplexit\u00e4t und Geometrie bilinearer Abbildungen.<\/span> (German. English summary)<\/span> [Complexity and geometry of bilinear maps]
\nJahresber. Deutsch. Math.-Verein.<\/em><\/a> 107 <\/a>(2005), <\/a>no. 1,<\/a> 3\u201331.
\n68W30 (14L24 68Q17)<\/a><\/p>\n

This survey (in German) is a summary of Volker Strassen’s work at the interface of complexity and geometry published in the Journal f\u00fcr die Reine und Angewandte Mathematik [375\/376<\/span> (1987), 406\u2013443; MR0882307 (88h:11026)<\/a>; 384<\/span> (1988), 102\u2013152; MR0929980 (89c:11056)<\/a>; 413<\/span> (1991), 127\u2013180; MR1089800 (92m:11038)<\/a>]. It is a pleasure to read and should be accessible to a wide mathematical audience. The main part is similar to Strassen’s overview given in [First European Congress of Mathematics, Vol. II (Paris, 1992)<\/span>, 429\u2013446, Progr. Math., 120, Birkh\u00e4user, Basel, 1994; MR1341854 (96e:68067)<\/a>]. The appendix, however, which covers one third of the article, contains a wealth of new material.<\/p>\n

The starting point, triggered by Strassen’s well-known 1969 discovery [Numer. Math. 13<\/span> (1969), 354\u2013356; MR0248973 (40 #2223)<\/a>], is to determine the minimum number of arithmetic operations sufficient to multiply two square matrices. Hereby, attention is confined to the asymptotic behaviour of this function captured by the exponent $\\omega$<\/span> of matrix multiplication, which is defined as the infimum of the real numbers $\\tau$<\/span> such that two $n\\times n$<\/span> matrices can be multiplied with\u00a0$O(n^\\tau)$<\/span> arithmetic operations. It is known that $2\\le\\omega<2.38$<\/span> [D. Coppersmith and S. Winograd, J. Symbolic Comput. 9<\/span> (1990), no. 3, 251\u2013280;MR1056627 (91i:68058)<\/a>] and most experts nowadays believe that $\\omega=2$<\/span>.<\/p>\n

Strassen has created a geometrical theory of bilinear maps with a considerably larger scope than the original questions of computational complexity. Geometric invariant theory provides a natural framework for addressing these more general questions. The concept of asymptotic degeneration makes it possible to take an asymptotic viewpoint when comparing any two bilinear maps. A bilinear map $f$<\/span> is called an asymptotic degeneration of a bilinear map $g$<\/span> iff, for all $\\nu$<\/span>,\u00a0$f^{\\otimes\\nu}$<\/span> is a degeneration of a direct sum of $2^{o(\\nu)}$<\/span> many copies of $g^{\\otimes\\nu}$<\/span>. (There are natural notions of direct sum and tensor product of bilinear maps.) The following spectral interpretation of this notion is crucial: For any semiring $S$<\/span> of bilinear maps there is an essentially unique compact space$\\Delta(S)$<\/span> and a homomorphism $\\varphi\\colon S\\to C^+(\\Delta(S))$<\/span> from $S$<\/span> to the semiring of nonnegative continuous functions on $\\Delta(S)$<\/span> such that$\\varphi(S)$<\/span> separates the points of $\\Delta(S)$<\/span> and the following property holds: $f$<\/span> is an asymptotic degeneration of $g$<\/span> iff $\\varphi(f)\\le\\varphi(g)$<\/span> pointwise on\u00a0$\\Delta(S)$<\/span>. If $S$<\/span> is generated by $q$<\/span> elements one may assume that $\\Delta(S)\\subseteq\\Bbb{R}^q$<\/span>.<\/p>\n

For semirings $S$<\/span> of bilinear maps of a certain type, a singular simplex in the spectrum $\\Delta(S)$<\/span>, the so-called support simplex, can be explicitly computed. This is achieved by exhibiting, for a probability vector $\\theta\\in\\Bbb{R}^3$<\/span>, a homomorphism $S\\to\\Bbb{R},\\, f\\mapsto\\zeta(\\theta, f)$<\/span> of semirings that is monotonic with respect to asymptotic degeneration. In order to define this, suppose $f\\colon\\Bbb{C}^{m_1}\\times \\Bbb{C}^{m_2}\\to\\Bbb{C}^{m_3}$<\/span> is a tight (straff) bilinear map. This means that there are injective real valued maps $\\alpha(i),\\beta(j),\\gamma(k)$<\/span> such that $\\alpha(i)+\\beta(j)+\\gamma(k)=0$<\/span> for all $(i,j,k)$<\/span> in the support ${\\rm supp }(f)\\colon =\\{(i,j,k)\\mid f_{ijk}\\ne 0\\}$<\/span> of $f$<\/span>. One defines
\n$$ \\zeta(\\theta,f) \\colon = \\max_P 2^{\\sum_{\\kappa=1}^3 \\theta_\\kappa H(P_k)},\\tag1 $$<\/span>
\nwhere $P$<\/span> runs over all probability distributions on ${\\rm supp}\\, f$<\/span>, $P_\\kappa$<\/span> denotes the $\\kappa$<\/span>-th marginal distribution of $P$<\/span>, and $H$<\/span> is the entropy function. It is known that for tight bilinear maps the support simplex and the spectrum have the same minimal points with respect to the product of the natural orders on $\\Bbb{R}^q$<\/span>.<\/p>\n

A main conjecture by Strassen (Vermutung 6) states that for tight bilinear maps, the image of the singular simplex coincides with the asymptotic spectrum. This conjecture would imply $\\omega=2$<\/span>.<\/p>\n

To fully appreciate the appendix, some familiarity with the representation theory of reductive linear algebraic groups is required. Some elegant proofs different from the ones in the literature are given. Moreover, the main conjecture is shown to be equivalent to the following more down-to-earth version (Vermutung 15): for “perfect” bilinear maps $f\\colon\\Bbb{C}^{m_1}\\times \\Bbb{C}^{m_2}\\to\\Bbb{C}^{m_3}$<\/span> and $g\\colon\\Bbb{C}^{n_1}\\times \\Bbb{C}^{n_2}\\to\\Bbb{C}^{n_3}$\u00a0<\/span>the inequalities of the formats $m_i\\le n_i$<\/span> for $i=1,2,3$<\/span> imply that $f$<\/span> is an asymptotic degeneration of $g$<\/span>. (Perfect means that the marginal distributions of the uniform distribution on the support are uniform.)<\/p>\n

Finally, an interesting connection of the support simplex of $f$<\/span> to the moment polytope is made. It states that for a tight bilinear map $f$<\/span>, Equation (1) is also true when $(P_1,P_2,P_3)$<\/span> runs over all elements of the moment polytope of the orbit closure of $f$<\/span>.<\/p>\n

{Reviewer’s remark: In the proof of Satz 16 there are a few typos confusing dimensions and their logarithms.}<\/p>\n

Reviewed by Peter B\u00fcrgisser<\/a><\/span><\/p>\n

\n

MR2188132<\/a><\/strong> (2006j:68034)<\/strong>
\nLandsberg, J. M.<\/a>(1-TXAM)<\/a>
\nThe border rank of the multiplication of $2\\times2$<\/span> matrices is seven.<\/span>
\nJ. Amer. Math. Soc.<\/em><\/a> 19 <\/a>(2006), <\/a>no. 2,<\/a> 447\u2013459.
\n68Q17 (65F05 68W30)<\/a><\/p>\n

V. Strassen presented in 1969 [Numer. Math. 13<\/span> (1969), 354\u2013356; MR0248973 (40 #2223)<\/a>] a bilinear algorithm for multiplying $2\\times2$<\/span> matrices using seven multiplications (instead of eight). This implied that virtually all tasks of numerical linear algebra can be solved in less than cubic time. In subsequent improvements of Strassen’s algorithm, the concept of approximate bilinear algorithms played a crucial role. However, it remained unknown whether there is an approximate bilinear algorithm for the multiplication of $2\\times 2$<\/span> matrices using fewer than seven multiplications. This paper solves this long-standing open problem in algebraic complexity theory (cf. Problem 12.1 in [V. Strassen, in Handbook of theoretical computer science, Vol. A<\/span>, 633\u2013672, Elsevier, Amsterdam, 1990; MR1127177<\/a>]).<\/p>\n

Mathematically, one has to show that the tensor of matrix multiplication is not contained in the secant variety\u00a0$\\sigma_6(\\Bbb{P}^3\\times\\Bbb{P}^3\\times\\Bbb{P}^3)$<\/span>. The key idea is to use a local differential-geometric description of limits of curves in the secant variety. This makes it possible to oversee all possible cancellations and thus to classify the points in $\\sigma_6(\\Bbb{P}^3\\times\\Bbb{P}^3\\times\\Bbb{P}^3)- \\sigma_5(\\Bbb{P}^3\\times\\Bbb{P}^3\\times\\Bbb{P}^3)$<\/span> into fifteen cases. Once this is achieved, the proof proceeds by excluding all the possible cases using the known substitution technique.<\/p>\n

I was recently informed by the author that the proof contains a gap. Apparently, it can be fixed and this will appear as an erratum.<\/p>\n

Reviewed by Peter B\u00fcrgisser<\/a><\/span><\/p>\n

\n

Notes<\/strong>:<\/p>\n

    \n
  1. There is an interesting\u00a0biography<\/a>\u00a0of Volker Strassen on the MacTutor website<\/a>.<\/li>\n
  2. The review<\/a> of Strassen’s ground-breaking result is by Graeme Fairweather<\/a>, long before he became an executive editor of Mathematical Reviews.<\/li>\n<\/ol>\n
    <\/div>","protected":false},"excerpt":{"rendered":"

    Mathematics flourishes when ideas from one area of mathematics can be used in another area. \u00a0For a long time (certainly since Descartes), algebra has been a great asset to geometry. \u00a0In return, geometry has been helpful to algebra, for instance … Continue reading →<\/span><\/a><\/p>\n

    <\/div>\n","protected":false},"author":86,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[2],"tags":[],"class_list":["post-538","post","type-post","status-publish","format-standard","hentry","category-exceptional-reviews"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p6C2KK-8G","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/538","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/users\/86"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/comments?post=538"}],"version-history":[{"count":43,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/538\/revisions"}],"predecessor-version":[{"id":581,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/posts\/538\/revisions\/581"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/media?parent=538"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/categories?post=538"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/beyondreviews\/wp-json\/wp\/v2\/tags?post=538"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}