Skip to content

Limits On Matrix Multiplication

August 30, 2018
tags: , , , , , ,


Can 2.3728639 be best?

Personal site; note puzzles

Josh Alman is a graduate student at a technical school in the Boston area. He is working on matrix multiplication, among other problems in complexity theory, and is advised by Ryan Williams and Virginia Vassilevska Williams.

Today we comment on his recent paper with Virginia on the limits of approaches to matrix multiplication.

This paper is titled, “Limits on All Known (And Some Unknown) Approaches to Matrix Multiplication,” and appears in the 2018 FOCS. An earlier paper by them was presented at the 2018 Innovations in Theoretical Computer Science conference.

Since Volker Strassen’s famous result that matrix multiplication (MM) can be computed in less than cubic time, there has been great interest in discovering the best possible exponent. More precisely, what is the smallest {\omega} so that MM can be done in time {O(n^{\omega})}? A widely discussed conjecture is that {\omega} can be any number greater than {2}. Of course the best currently is higher—much higher?—and is equal to

\displaystyle 2.3728639.

This is due to François Le Gall—see his paper entitled “Powers of Tensors and Fast Matrix Multiplication.”

The number {2.3728639} as a continued fraction is

Calculated here

Does this suggest any pattern to you? Can any number below 2.37 and above 2 be “the” number?

Limits on Limits

Since Strassen there have been several advances in reducing the value of {\omega}. We discussed the history here following our two–part presentation of the advances by Andrew Stothers and Virginia. There was a time when it was thought by many that {2.500} might be a barrier. It is not. Note the cluster of points near 1980 in this graphic on Wikipedia’s matrix multiplication algorithms page:

Squashed from Wikipedia source

It is poetic that after Don Coppersmith and Shmuel Winograd (CW) broke {2.500} ever so slightly, Strassen himself made a larger break in 1986. Then CW in 1991 produced a running time of {O(n^{2.375477\dots})} whose first three digits have stood all the past 27 years despite massive efforts. It seems {\omega} is stuck at around {\approx 2.37}. This clearly suggests that maybe there is a reason that we cannot make further progress. So an idea is:

Are there limits to what we can prove about {\omega}?

This is precisely the focus of Josh and Virginia’s joint paper. They divide the known methods of proving better upper bounds on MM into categories according to techniques employed:

  • Laser Method: This is due to Strassen.

  • Group Method: This is due to Henry Cohn and Christopher Umans.

  • Solar Method: Josh and Virginia created this and next one too.

  • Galactic Method: This is a common generalization of the previously known methods.

They show that the above methods cannot prove that {\omega=2}. Namely, they show:

Theorem 1 There is an absolute constant {\omega_{\infty}>2} so that any proof that uses the above methods can only prove {\omega} for a value above {\omega_{\infty}}.

Their result is not the first result on the limitations of MM approaches, however. The first “limitation” result was by Noga Alon, Amir Shpilka and Umans in a paper titled, “On Sunflowers and Matrix Multiplication.” That paper had the sobering message that several “hopeful” conjectures working toward {\omega = 2} are incompatible with versions of the Sunflower Conjecture by Paul Erdős and Richard Rado that are widely believed. Here is a graphic from that paper on the implications it proves:

The New Paper

Rather then show how Josh and Virginia prove their limit results perhaps it is better to explain what they have proved. As usual we will refer to their paper to get the full details.

The point, as we see it, is this. Deciding how many operations are needed to compute the matrix product boils down to determining the rank of a certain tensor. A tensor has a rank like matrices. However, the rank is hard to compute and thus the direct calculation of the rank seems to be impossible. So the above methods starting with the Laser method are methods that try to control the difficulty of determining the rank of a tensor.

An analogy is this: Imagine you are searching some large space for an optimal value of a function. This can be complex both computationally and also from a proof point of view. That is, it may be hard to even prove that particular instances have a claimed value.

A natural approach that avoids these issues is to restrict the search space in some way. Of course whenever you restrict a search space you may lose some optimal values. The paper in question shows that the tradeoff for using restricted search spaces is indeed you may lose some optimal values. But you gain because the search space is easier to understand. It may, however, be too easy: you may not be able to show that {\omega=2}.

The strangest aspect to our eyes is that they prove the existence of {\omega_{\infty} > 2} but do not give an estimate for it. Here the earlier paper is highly informative. It observes that all previous advances could be made by analyzing the tri-linear forms (tensors)

\displaystyle T_q = \sum_{i=0}^{q-1} \sum_{j=0}^{q-1} x_i y_j z_{-i-j},

where the last subscript is modulo {q} for some fixed {q}. In the simplest case where {q} is prime (or a prime power), it shows that any {\omega} achieved via similar analysis of {T_q} is bounded below by

\displaystyle \omega_q = 2\frac{\ln(q)}{\ln(\gamma)}, \qquad\text{where}\qquad \gamma = \frac{1-z^q}{(1-z)z^{(q-1)/3}},

and where {z} is the unique real solution in {(0,1)} to {\sum_{j=1}^{q-1} z^j = (q-1)(1+2z^q)/3.} These numbers are explicit—for instance, {\omega_7} is about {2.1413.} But they give {\omega_q \to 2} as {q \to \infty,} so this didn’t rule out getting {\omega = 2} by these means.

The new paper shows that getting upper bounds that are similarly asymptotic to {2} by these (and other) methods is impossible. The proof feels like working by contradiction from this supposition. Josh and Virginia tell us that in the case of only the Galactic method applied to extended CW tensors, extracting estimates without trying to optimize them gives a lower limit of about {2.00003}.

Even an optimized estimate, however, would not rule out the “true” {\omega} being much higher. The full paper when it is out will shed further light. For now, purely as a joke, we did a quadratic regression on the Wikipedia figure’s data points for {\omega} since 1968 and got a minimum of {2.3357}—which the regression says would have come in the year 2004. Oh well.

Open Problems

What is the best value for {\omega}? Do these limit results really help us determine a value and understand why a particular value—greater than 2—might be the barrier?


[updated main paper title and gave link]

from → algorithms, All Posts, fast, History, Ideas, News, Open Problems, Proofs, Results
22 Comments leave one →
  1. curious permalink
    September 3, 2018 11:14 pm

    What does Ryan Williams say?

    Reply
    • curious permalink
      September 3, 2018 11:15 pm

      $=2$ seems the correct bound and there is no natural reason $\neq2$.

      Reply
      • KWRegan permalink
        September 6, 2018 12:17 pm

        We hinted at that opinion in the post. After the work by Cohn and Umans (and others) we might have agreed. But there may be some number akin to Euler’s constant lurking. Ryan skirts this in his recent “Likelihoods” piece, which we intend to cover at some point.

      • curious permalink
        September 8, 2018 12:22 am

        May be the problem is not as contorted as is studied as of now.

  2. spencer permalink
    September 6, 2018 8:30 am

    Fitting an exponential to the wikipedia figure suggests that {\omega \to 2.312}, but that proving this will take infinite time.

    Reply
  3. Frank Vega permalink
    January 7, 2025 11:58 am

    aegypti 0.0.7: Faster Triangle Finding and More!

    https://pypi.org/project/aegypti/

    ● Ultra-Fast Triangle Detection: We’ve developed a groundbreaking O(n + m) algorithm for identifying all triangles in a graph. This means lightning-fast performance, even for massive datasets.
    ● Triangle-Free Problem Solved: Say goodbye to complex triangle-free problem solutions! Our innovative O(n + m) algorithm tackles it with ease, streamlining your workflows.
    ● Broader Applications: These advancements extend beyond triangles, impacting various computational problems in combinatorial optimization and computational geometry

    Install it using pip: pip install aegypti

    Reply
  4. Frank Vega permalink
    January 7, 2025 2:23 pm

    Introducing Aegypti 0.0.8: Optional Brute Force Comparison

    Now you can enable brute-force comparison as an option in Aegypti 0.0.8! This powerful new feature gives you even more flexibility and control over your data analysis.

    Reply
  5. Frank Vega permalink
    January 7, 2025 2:44 pm

    Aegypti – Hacker News Robot

    https://news.ycombinator.com/item?id=42624665

    Reply
  6. Frank Vega permalink
    January 7, 2025 8:22 pm

    Aegypti 0.0.9: Enhanced Efficiency and Focused Functionality

    This release of Aegypti brings significant improvements:

    * Algorithm Completion and Testing: The core algorithm is now fully implemented and has undergone rigorous testing.
    * Streamlined Functionality: Aegypti now focuses on efficiently finding at least one triangle in a given scenario. This optimization ensures reliable results in a wider range of situations.

    Installation:

    “`bash
    pip install aegypti
    “`

    Documentation:

    For detailed information and usage instructions, please refer to the official documentation: https://pypi.org/project/aegypti/

    Reply
  7. Frank Vega permalink
    January 8, 2025 5:07 am

    Aegypti 0.1.0: Released with improved performance, correctness, and accuracy across all options. (This is the most straightforward and likely best version.)

    https://pypi.org/project/aegypti/

    This version guarantees the complete enumeration of all triangles. We’ve also added an option to count the total number of triangles. Furthermore, we’ve corrected an algorithm that previously exhibited inaccuracies in certain cases. This revised version has been rigorously tested against naive approaches, such as matrix multiplication, and performs as expected.

    Our algorithm now identifies and counts all triangles by considering pairs of connected vertices in O(n + m) time. These vertex pairs represent the minimal set of edges required to generate all triangles, as each such edge can form the base of a triangle. By using this minimal generating set, we efficiently construct all possible triangles.

    I’m excited to share progress on Aegypti, reaching version 0.1.0! I’d love for you to check it out! Installation is easy with pip: pip install aegypti

    Reply
  8. Frank Vega permalink
    January 8, 2025 9:28 am

    Aegypti 0.1.1: Enhanced Efficiency and Focused Functionality

    Comment: We remove all extra features except the Triangle-free/detection algorithm

    This release of Aegypti brings significant improvements:

    * Algorithm Completion and Testing: The core algorithm is now fully implemented and has undergone rigorous testing.
    * Streamlined Functionality: Aegypti now focuses on efficiently finding at least one triangle in a given scenario. This optimization ensures reliable results in a wider range of situations.

    Installation:

    “`bash
    pip install aegypti
    “`

    Documentation:

    For detailed information and usage instructions, please refer to the official documentation: https://pypi.org/project/aegypti/

    Reply
  9. Frank Vega permalink
    February 1, 2025 11:48 am

    (Aegypti: 0.1.9) can efficiently identify all triangles in a graph and determine if the graph is triangle-free, all within an impressive O(n + m) time complexity, where n is the number of vertices and m is the number of edges. You can easily install Aegypti using PyPI:

    https://pypi.org/project/aegypti/

    Reply
  10. Frank Vega permalink
    March 2, 2025 10:38 pm

    A linear-time solution for the Triangle Finding Problem enhances efficiency in sparse graph analysis, enabling faster detection of triangles in large networks, improved calculation of clustering coefficients, and more efficient community detection. This advancement benefits diverse fields such as social network analysis, where understanding user interactions is crucial, bioinformatics for studying protein interaction networks, and recommendation systems that infer user preferences from interaction graphs. Overall, it accelerates the study of crucial graph properties, making it practical for large-scale networks.

    https://pypi.org/project/aegypti/

    Reply

Trackbacks

  1. How fast can you multiply matrices?
  2. New top story on Hacker News: Limits on Matrix Multiplication – Tech + Hckr News
  3. New top story on Hacker News: Limits on Matrix Multiplication – News about world
  4. New top story on Hacker News: Limits on Matrix Multiplication – Latest news
  5. New top story on Hacker News: Limits on Matrix Multiplication – World Best News
  6. New top story on Hacker News: Limits on Matrix Multiplication – New Content
  7. Limits on Matrix Multiplication – Hacker News Robot
  8. A Quantum Connection For Matrix Rank | Gödel's Lost Letter and P=NP
  9. Baby Steps | Gödel's Lost Letter and P=NP

Leave a Reply to Frank VegaCancel reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading