# Tag Info

10

The real answer to this question is that if you play with it long enough, you'll hit an algorithm requiring 7 multiplications – not necessarily the same as Strassen's, but an equivalent one, in a certain sense: it is known that all such algorithms are equivalent, as shown by de Groote in his 1978 paper, On varieties of optimal algorithms for the computation ...

4

It’s reasonably obvious that if you can calculate a 2x2 matrix product with 7 multiplications and quite a few additions, you get an asymptotically faster algorithm. You need 8 products. But for example (a+b)*(c+d) gives you the sum of four products with one multiplication. So it might be possible to calculate many products with seven multiplications in such ...

3

Matrix multiplication and matrix inverse have the same asymptotic running time. If we denote the running time of multiplying two $n \times n$ matrices by $T_1(n)$, and that of inverting an $n \times n$ matrix by $T_2(n)$, then this means that there exist constants $A,B$ such that $$T_1(n) \leq AT_2(n) \\ T_2(n) \leq BT_1(n).$$ However, the constants $A,B$ ...

2

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$. Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} < 2n$. We can extract ...

2

After reading over everything more carefully, I think I was misunderstanding the argument a bit, and as Yuval points out, IMM can be computed transparently in poly size without having a poly size formula. The idea seems pretty straightforward too: Everything stated previously applies to all rings, so if the elements of the matrix were $Z_2$, then we could ...

Only top voted, non community-wiki answers of a minimum length are eligible