Why is fast matrix multiplication impractical?

Question

I am wondering why fast matrix multiplications are impractical, especially for Boolean matrix multiplication.

I read some content saying fast matrix multiplications are impractical because of large constant factors. These constant factors are because of algebraic techniques.

I do not understand where these constant factors come from. Some references also say $O(n^{3-\omega})$ may become practical when $O(n^{3-\omega})$ combinatorial algorithm exists. What is the large constant factor and combinatorial algorithm for Boolean matrix multiplication?

Answer 1

Matrix multiplication based on Strassen's algorithm is in $O(n^{\log(7)/\log(2)})$ and is quite practical. As far as I am aware, for any exponent $\omega<\log(7)/\log(2)$ the corresponding algorithm is impractical, indeed because of huge constants.

Added Oct. 9, 2022:

Apparently, Alphatensor by Deepmind has found (many) ways to multiply $4\times4$ matrices in $47$ multiplications, so I guess the "practicality exponent" is now down to $\log(47)/\log(4)$.

Answer 2

I acknowledge that the question concerns Boolean matrix multiplication. However, a good deal of the opposition to fast matrix multiplication algorithms is due to stability issues that can arise when using floating point arithmetic.

Useful algorithms are stable, accurate and fast. Blinding speed is utterly irrelevant if the algorithm is unstable or inaccurate for valid input.

The standard algorithm for computing matrix matrix product $C = AB$ using IEEE floating point arithmetic is forward stable in the following sense. If $\hat{C}$ denotes the computed value, then $$|C - \hat{C}| \leq \gamma_{2n-1} |A||B|, \quad \gamma_k: = \frac{ku}{1-ku}.$$ This inequality should be understood in the component sense, i.e. $$|c_{ij} - \hat{c}_{ij}| \leq \gamma_{2n-1} |f_{ij}|, \quad F = |A||B|.$$ Here $u$ is the unit roundoff and $n$ is number of columns of $A$. It is assumed that $nu<1$ and that the calculation runs to completion without exceeding the representational range (overflow). How is this relevant in the context of fast algorithms? Any polynomial time algorithm for multiplying $n$-by-$n$ matrices together which is stable in the sense described above must use at least $n^3$ multiplications. This is the relevant reference:

W. Miller, “Computational complexity and numerical stability,” SIAM Journal on Computing, vol. 4, no. 2, pp. 97–107, 1975.

It follows that Strassen's algorithm cannot be forward stable in the sense stated above. It does however satisfy the following bound $$ \|C -\hat{C} \| \leq c(n,k) u \|A\| \|B\| + O(u^2), \quad u \rightarrow 0, \quad u > 0$$ where $k$ is the block size where we switch to regular matrix matrix multiplication.

The relevant reference is

N. J. Higham, Accuracy and stability of numerical algorithms. SIAM, 2002.

Do we need forward stability in the componentwise sense? This very much depends on the underlying real life application. If we ignore the question of accuracy and stability, then we just might endanger the people who depend on our software.

Answer 3

Addressing the Boolean part.

Usually, fast matrix multiplication relies heavily on the element type being a ring; in particular, that every element has an additive inverse. For example, Strassen's algorithm contains subtractions. This works fine, for example, with reals, integers, rationals, and finite fields. In particular, you could easily do fast matrix multiplication on $\mathbb{F}_2$, that is, elements are bits with addition defined modulo two (so $1+1=0$).

However, in Boolean matrix multiplication the addition of elements is the Boolean disjunction: $1+1=1$ instead of zero. This innocent change means that subtraction no longer works: from $x+1=1$ you cannot know whether $x=0$ or $x=1$. Thus Strassen's algorithm, unmodified, does not work with Booleans.

Yes, this is a slight "impracticality", but it is well known that this can be circumvented relatively easily, by embedding the Booleans into a suitable ring. You can use $b$-bit integers modulo $2^b$, with $b$ chosen large enough so that overflows (wraparounds) will not happen in the fast matrix multiplication. Generally $b$ will be something like a logarithm of the matrix size.

In fact there have been implementations of Strassen-like algorithms for Booleans. One example is Karppa & Kaski (2019), Engineering Boolean Matrix Multiplication for Multiple-Accelerator Shared-Memory Architectures (arxiv).

Answer 4

As an example, Strassen's algorithm can multiply two 2n x 2n matrices by doing 7 multiplications and 18 additions of n x n matrices. So you save one multiplication for 18 additions of n x n matrices. You have to find temporary memory to store intermediate results, so all in all there is quite a bit of overhead. On the other hand, using brute force a 2n x 2n multiplication will do more operations per second than n x n. So it takes a reasonably large matrix size to make Strassen faster than brute force.

For faster methods, the overhead is much higher. So high that a matrix must be huge to make the "faster" methods actually faster.

But there is more to consider: Strassen's algorithm may use up to 12.5% fewer operations for very large n, but there are plenty of things that have a much larger impact. Like processor caches, reducing the latency of operations,combining multiply and add, vectorising, multi-threading. These things become harder to do when the algorithm gets more complicated. So not only do you need to have fewer operations, you also to have the same number of operations per seconds.