Tag Info

12

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

3

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

2

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

1

Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.

1

Per row of A you would perform 9 multiplication and six additions, which you could perform with 3 multiplications and 6 fused multiply-add instructions. Like ResultX = ax * c00 + bx * c01 + cx * c02 ResultY = ax * c10 + bx * c11 + cx * c12 ResultZ = ax * c20 + bx * c21 + cx * c22 Use a switch for the 27 possible values of c00, c10 and c20. Then we need just ...

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