5
$\begingroup$

Every source I can find just says "too big to be practical."

$\endgroup$
4
  • 1
    $\begingroup$ I'm not sure anyone ever computed it. By the way, what constant are you looking for ? The constant for the number of multiplications ? Arithmetic operations ? Etc. $\endgroup$
    – GBat
    Jul 30, 2020 at 21:33
  • $\begingroup$ Arithmetic operations I suppose. Just to get some idea what the order of magnitude would be for CW and similar algorithms. $\endgroup$ Jul 30, 2020 at 22:34
  • 4
    $\begingroup$ Someone has definitely computed an upper bound on the leading constant for the number of arithmetic ops, but I do not remember who (it was submitted to a conference years ago) and I am not sure the writeup was ever made public... I will check. My recollection is that it was < 10^(500)... $\endgroup$ Jul 31, 2020 at 23:02
  • $\begingroup$ @RyanWilliams No luck? $\endgroup$ Aug 24, 2020 at 17:54

1 Answer 1

2
$\begingroup$

I don't know the exact answer, but here are some relevant quotes regarding fast matrix multiplication in general:

(This quote is about an earlier method with $O(N^{2.77})$ complexity. $m^{*}(3^s|F)$ is the number of scalar multiplications required to multiply two $3^s \times 3^s$ matrices, excluding multiplications involved in constructing linear combinations of matrix entries.)

The last step is the crucial point with respect to all practical applications of the method. Of course, we can assume that $F$ is infinite and use Lemma 2.6, which gives the better bound $m^{*}(3^s|F) \leq (1 + 2s)21^s$, but even then the minimal value of $s$ for which this becomes smaller than the trivial bound $27^s$ is $s = 14$, and $3^{14} = 4,782,969$. The same will apply for all other bounds given in this paper.

Schönhage, A., Partial and total matrix multiplication, SIAM J. Comput. 10, 434-455 (1981).

Actually, there are two groups of algorithms that support an exponent lower than Strassen’s value of 2.81. The first group consists of algorithms that use various advanced techniques and support exponents from 2.38 to 2.775. [...]

If we restrict our study to the multiplication of $N \times N$ matrices for $N < 10^{20}$, the only competition for Strassen’s algorithm comes from a second group of algorithms. [...] These algorithms support exponents $\omega$ of about 2.775. Since the crossover value of $N$ for which such algorithms improve on Strassen’s is as low as 20, these algorithms are good candidates for being of practical value when compared to Strassen’s and classical algorithms for MM [matrix multiplication].

Laderman, Julian; Pan, Victor; Sha, Xuan-He, On practical algorithms for accelerated matrix multiplication, Linear Algebra Appl. 162-164, 557-588 (1992).

All known algorithms supporting matrix multiplication exponents below 2.7733, however, suffer from the curse of recursion: they involve very long recursive processes, whose each recursive step squares the input size, and so these algorithms supersede the classical matrix multiplication only for inputs of astronomical sizes, being far above the level of any imaginable practical interest. The design and the study of these algorithms was widely advertised and generously supported, but made no impact on real world computations for matrix multiplication or any other problem of Mathematics and Computational Mathematics. As of 2017 the record bound $\omega < 2.7734$ of [114] for feasible matrix multiplication of dimensions $n$ of at most 1 000 000 000 has remained unbeaten since 1982.

Pan, Victor Ya., Fast matrix multiplication and its algebraic neighbourhood, Sb. Math. 208, No. 11, 1661-1704 (2017); translation from Mat. Sb. 208, No. 11, 90-138 (2017).

So everything below $O(N^{\approx 2.8})$ is really impractical.

(off-topic) Actually, even Strassen's algorithm has little practical importance. It gives only $O((\mathrm{number\ of\ operations})^{0.023})$ increase in the maximum matrix size that you can afford given limited computational resources. For large-scale linear algebra, better options are available, such as preconditioned iterative linear solvers or Monte Carlo matrix multiplication.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.