6
$\begingroup$

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 give a fast algorithm for binary multiplication and Strassen also gave a faster matrix multiplication method.

  • A. Schonhage and V. Strassen, “Schnelle Mu ¨ ltiplikation grosser Zahlen,” Computing 7 (1971), 281–292
$\endgroup$
  • 1
    $\begingroup$ +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. $\endgroup$ – Sasho Nikolov Oct 30 '13 at 18:18
  • $\begingroup$ Actually, I saw more of a connection between Karatsuba-multiplication and Strassen's fast-matrix-multiplication. $\endgroup$ – Realz Slaw Nov 4 '13 at 14:09
5
$\begingroup$

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).

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).

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....

$\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.