<p>Here is a relevant reference and Sasho has graciously added a high-level summary.</p>

<p><em>A Group-theoretic Approach to Fast Matrix Multiplication</em> by Cohn and Umans. (2004, <a href="http://arxiv.org/abs/math/0307321" rel="nofollow">arxiv</a>).</p>

<blockquote>
  <p>There is a close analogy between the framework we propose in this paper and the well-known algorithm for multiplying two degree n polynomials in O(n log n) operations
  using the Fast Fourier Transform (FFT). In this section we
  elucidate this analogy to give a high-level description of our
  technique.</p>
</blockquote>

<p>On a very high level, the FFT-base polynomial multiplication algorithm can be seen as the following strategy: 1) embed the polynomials as elements of the group algebra of a not-too-large abelian group; 2) apply the DFT to the group algebra elements in order to embed them as complex-valued diagonal matrices; 3) multiply the diagonal matrices.</p>

<p>(Note: the group algebra here is the algebra of formal "linear combinations" of group elements with complex or real coefficients). </p>

<p>The same approach almost works for matrix multiplication. Step 1) becomes hard, where it was trivial with polynomials. The embedding can be done with abelian groups of size $n^3$, and no better, so for $n^{2 + o(1)}$ size groups you need to abandon commutativity. Then 2) turns out to still be doable with non-abelian groups using the appropriate generalization of DFT that you get from representation theory, but the resulting object is a block-diagonal matrix rather than a diagonal matrix. Then 3) is no longer the trivial pointwise multiplication operation, but multiplication of smaller matrices. Bounding the sizes of these matrices is a question about dimensions of irreducible representations of the group we used. </p>

<p>See also the follow-up <em>Group-Theoretic Algorithms for Matrix Multiplication</em> by Cohn, R. Kleinberg, Szegedy, and Umans (2005, <a href="http://arxiv.org/abs/math/0511460" rel="nofollow">arxiv</a>).</p>

<p>Perhaps there have been advancements (or even a survey) since then. Of course this probably doesn't answer your question about how the complexities of the problems are related....</p>

CC BY-SA 3.0
2013-10-30T18:29:15.220Z
also, some recent progress: a SODA 2013 paper by Cohn and Umans http://arxiv.org/abs/1207.6528, and http://users.cms.caltech.edu/~umans/papers/ASU11-final.pdf, and results by Alon, Shpilka and Umans that the Erdos-Rado sunflower conjecture is inconsistent with some conjectures from CKSU.
Sasho Nikolov
CC BY-SA 3.0
2013-10-30T17:52:28.720Z
2013-10-30T18:56:38.320Z
2013-10-30T18:56:38.320Z
usul
<blockquote>
  <p>is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it?</p>
</blockquote>

<p>some related history: <a href="http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm">Schonhage/Strassen</a> give a fast algorithm for binary multiplication and <a href="http://en.wikipedia.org/wiki/Strassen_algorithm">Strassen</a> also gave a faster matrix multiplication method.</p>

<ul>
<li>A. Schonhage and V. Strassen, “Schnelle Mu ¨ ltiplikation grosser Zahlen,” Computing 7 (1971),
281–292</li>
</ul>

CC BY-SA 3.0
2013-10-30T18:18:21.393Z
+1, it's a good question. but the "related history" says nothing unless you expand it, the same author could work on unrelated problems or weakly related ones, and most people do.
Sasho Nikolov
CC BY-SA 3.0
2013-11-04T14:09:53.427Z
Actually, I saw more of a connection between Karatsuba-multiplication and Strassen's fast-matrix-multiplication.
Realz Slaw
<cc.complexity-theory><reference-request><boolean-functions><matrices>
any connection between binary/integer multiplication and matrix multiplication?
vzn
# any connection between binary/integer multiplication and matrix multiplication?

(Asked by: username_0 on 2013-10-30)

> is there a connection between the inherent complexity of binary/integer multiplication algorithms and matrix multiplication algorithms? if so what is a ref that outlines/discusses it?

some related history: [Schonhage/Strassen](http://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm) give a fast algorithm for binary multiplication and [Strassen](http://en.wikipedia.org/wiki/Strassen_algorithm) also gave a faster matrix multiplication method.

* A. Schonhage and V. Strassen, “Schnelle Mu ¨ ltiplikation grosser Zahlen,” Computing 7 (1971),
  281–292

**Tags:** cc.complexity-theory, reference-request, boolean-functions, matrices

> **Comments:**
> **username_1**: +1, it's a good question. but the "related history" says nothing unless you expand it, the same author could work on unrelated problems or weakly related ones, and most people do.  
> **username_2**: Actually, I saw more of a connection between Karatsuba-multiplication and Strassen's fast-matrix-multiplication.  

---

## 1 answers

### Answer by username_3 on 2013-10-30. Score: 5 | Accepted answer

Here is a relevant reference and Sasho has graciously added a high-level summary.

*A Group-theoretic Approach to Fast Matrix Multiplication* by Cohn and Umans. (2004, [arxiv](http://arxiv.org/abs/math/0307321)).

> There is a close analogy between the framework we propose in this paper and the well-known algorithm for multiplying two degree n polynomials in O(n log n) operations
> using the Fast Fourier Transform (FFT). In this section we
> elucidate this analogy to give a high-level description of our
> technique.

On a very high level, the FFT-base polynomial multiplication algorithm can be seen as the following strategy: 1) embed the polynomials as elements of the group algebra of a not-too-large abelian group; 2) apply the DFT to the group algebra elements in order to embed them as complex-valued diagonal matrices; 3) multiply the diagonal matrices.

(Note: the group algebra here is the algebra of formal "linear combinations" of group elements with complex or real coefficients).

The same approach almost works for matrix multiplication. Step 1) becomes hard, where it was trivial with polynomials. The embedding can be done with abelian groups of size $n^3$, and no better, so for $n^{2 + o(1)}$ size groups you need to abandon commutativity. Then 2) turns out to still be doable with non-abelian groups using the appropriate generalization of DFT that you get from representation theory, but the resulting object is a block-diagonal matrix rather than a diagonal matrix. Then 3) is no longer the trivial pointwise multiplication operation, but multiplication of smaller matrices. Bounding the sizes of these matrices is a question about dimensions of irreducible representations of the group we used.

See also the follow-up *Group-Theoretic Algorithms for Matrix Multiplication* by Cohn, R. Kleinberg, Szegedy, and Umans (2005, [arxiv](http://arxiv.org/abs/math/0511460)).

Perhaps there have been advancements (or even a survey) since then. Of course this probably doesn't answer your question about how the complexities of the problems are related....

> **Comments:**
> **username_1**: also, some recent progress: a SODA 2013 paper by Cohn and Umans http://arxiv.org/abs/1207.6528, and http://users.cms.caltech.edu/~umans/papers/ASU11-final.pdf, and results by Alon, Shpilka and Umans that the Erdos-Rado sunflower conjecture is inconsistent with some conjectures from CKSU.  

---

