0
$\begingroup$

In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words:

Multiplications are everything. The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.

I was wondering how I should understand this. Why the number of additions doesn't matter?

$\endgroup$
1
  • $\begingroup$ now I realised that the distance of my example is NOT metric. $\endgroup$
    – Mengfan Ma
    Jul 30, 2022 at 5:35

1 Answer 1

Reset to default
2
$\begingroup$

It looks like the article was written by someone who does not understand matrix multiplication.

the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.

With the classic matrix multiplication algorithm (which is the one explained in the example) between two $4\times 4$ matrices, each coefficient of the product requires $3$ additions, so a total of $3\times 16 = 48$ additions, not $16$.

Usually, when it is said that only multiplications matter and not additions, it means of matrices, not coefficients.

For example, a "naive" divide-and-conquer strategy compute $A\times B$ where $A,B$ are matrices of size $n\times n$ by doing $8$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ (and some additions of matrices, but those are done in complexity $O(n^2)$, which is negligible in front of the complexity of matrix multiplication). That way, the complexity verifies $C(n) = 8C\left(\frac{n}{2}\right) + O(n^2)$ and it is easily proven that $C(n) = O(n^3)$, so this strategy is not an improvement.

The Strassen algorithm use a divide-and-conquer strategy to improve complexity: it does $7$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ and some additions, so the complexity verifies $C(n) = 7C\left(\frac{n}{2}\right) + O(n^2)$ and we get $C(n)\simeq O(n^{2.8})$.

In the two examples above, the number of matrices multiplications matter much more than the number of matrices additions. But in both, the number of multiplications/additions on coefficients is not compared.

It is confirmed in the article:

Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!

$\endgroup$
5
  • $\begingroup$ I understood what you said about multiplication/additions of matrices. But what do you mean by multiplications/additions on coefficients? $\endgroup$
    – Mengfan Ma
    Apr 22, 2021 at 2:24
  • $\begingroup$ $5 \times 7$ is a multiplication of coefficients. $\begin{pmatrix}5 & 2 \\3 & 7\end{pmatrix}\times \begin{pmatrix}1 & 8 \\2 & 4\end{pmatrix}$ is a multiplication of matrices. $\endgroup$
    – Nathaniel
    Apr 22, 2021 at 2:32
  • $\begingroup$ Sorry it's may be dumb question: what do you mean by "But in both, the number of multiplications/additions on coefficients is not compared"? I didn't see any multiplications/additions on coefficients in both algorithms. $\endgroup$
    – Mengfan Ma
    Apr 22, 2021 at 2:48
  • $\begingroup$ In both algorithms, additions on coefficients are done when adding matrices (so $n^2$ additions for the sum of two $n\times n$ matrices). Multiplications on coefficients are done in the base case, that is the multiplication of two matrices of size $1 \times 1$ (which is the same as the multiplication of two coefficients). The complexity $C(n)$ counts the total number of arithmetic operations on coefficients, may they be multiplications or additions. $\endgroup$
    – Nathaniel
    Apr 22, 2021 at 3:05
  • $\begingroup$ I see, so the time complexity of Matrix Multiplication indeed measures the number of additions and multiplications on coefficients. This article is kinda misleading. $\endgroup$
    – Mengfan Ma
    Apr 22, 2021 at 4:41

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.