<p>I don't know the exact answer, but here are some relevant quotes regarding fast matrix multiplication in general:</p>
<p>(This quote is about an earlier method with <span class="math-container">$O(N^{2.77})$</span> complexity. <span class="math-container">$m^{*}(3^s|F)$</span> is the number of scalar multiplications required to multiply two <span class="math-container">$3^s \times 3^s$</span> matrices, excluding multiplications involved in constructing linear combinations of matrix entries.)</p>
<blockquote>
<p>The last step is the crucial point with respect to all practical
applications of the method. Of course, we can assume that <span class="math-container">$F$</span> is
infinite and use Lemma 2.6, which gives the better bound <span class="math-container">$m^{*}(3^s|F) \leq (1 + 2s)21^s$</span>, but even then the minimal value of <span class="math-container">$s$</span>
for which this becomes smaller than the trivial bound <span class="math-container">$27^s$</span> is <span class="math-container">$s = 14$</span>,
and <span class="math-container">$3^{14} = 4,782,969$</span>. The same will apply for all other bounds given
in this paper.</p>
</blockquote>
<p><em>Schönhage, A.</em>, <a href="https://dx.doi.org/10.1137/0210032" rel="nofollow noreferrer"><strong>Partial and total matrix multiplication</strong></a>, SIAM J. Comput. 10, 434-455 (1981).</p>
<blockquote>
<p>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. [...]</p>
<p>If we restrict our study to the
multiplication of <span class="math-container">$N \times N$</span> matrices for <span class="math-container">$N &lt; 10^{20}$</span>, the only competition
for Strassen’s algorithm comes from a second group of algorithms.
[...] These algorithms support exponents <span class="math-container">$\omega$</span> of about 2.775. Since the
crossover value of <span class="math-container">$N$</span> 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].</p>
</blockquote>
<p><em>Laderman, Julian; Pan, Victor; Sha, Xuan-He</em>, <a href="https://www.sciencedirect.com/science/article/pii/002437959290393O/pdf?md5=a704930f7084a84b64a6007040d6253a&amp;pid=1-s2.0-002437959290393O-main.pdf" rel="nofollow noreferrer"><strong>On practical algorithms for accelerated matrix multiplication</strong></a>, Linear Algebra Appl. 162-164, 557-588 (1992).</p>
<blockquote>
<p>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 <span class="math-container">$\omega &lt; 2.7734$</span> of [114] for
feasible matrix multiplication of dimensions <span class="math-container">$n$</span> of at most 1 000 000
000 has remained unbeaten since 1982.</p>
</blockquote>
<p><em>Pan, Victor Ya.</em>, <a href="https://dx.doi.org/10.1070/SM8833" rel="nofollow noreferrer"><strong>Fast matrix multiplication and its algebraic neighbourhood</strong></a>, Sb. Math. 208, No. 11, 1661-1704 (2017); translation from Mat. Sb. 208, No. 11, 90-138 (2017).</p>
<p>So everything below <span class="math-container">$O(N^{\approx 2.8})$</span> is <em><strong>really</strong></em> impractical.</p>
<p>(<em>off-topic</em>) Actually, even Strassen's algorithm has little practical importance. It gives only <span class="math-container">$O((\mathrm{number\ of\ operations})^{0.023})$</span> 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.</p>

CC BY-SA 4.0
2022-04-18T14:05:56.370Z
2022-04-18T14:05:56.370Z
Better late than never
<p>Every source I can find just says &quot;too big to be practical.&quot;</p>

CC BY-SA 4.0
2020-07-30T21:33:02.813Z
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.
GBathie
CC BY-SA 4.0
2020-07-30T22:34:48.513Z
Arithmetic operations I suppose. Just to get some idea what the order of magnitude would be for CW and similar algorithms.
Adam Tolnay
CC BY-SA 4.0
2020-07-31T23:02:39.037Z
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)...
Ryan Williams
CC BY-SA 4.0
2020-08-24T17:54:24.230Z
@RyanWilliams No luck?
Adam Tolnay
<ds.algorithms><time-complexity>
What's the constant coefficient of the Coppersmith-Winograd algorithm?
Adam Tolnay
# What's the constant coefficient of the Coppersmith-Winograd algorithm?

(Asked by: username_0 on 2020-07-30)

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

**Tags:** ds.algorithms, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: Arithmetic operations I suppose. Just to get some idea what the order of magnitude would be for CW and similar algorithms.  
> **username_2**: 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)...  
> **username_0**: @RyanWilliams No luck?  

---

## 1 answers

### Answer by username_3 on 2022-04-18. Score: 2

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**](https://dx.doi.org/10.1137/0210032), 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**](https://www.sciencedirect.com/science/article/pii/002437959290393O/pdf?md5=a704930f7084a84b64a6007040d6253a&pid=1-s2.0-002437959290393O-main.pdf), 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**](https://dx.doi.org/10.1070/SM8833), 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.


---

