32
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
There's an algorithm for multiplying an $N \times N^{0.172}$ matrix with an $N^{0.172} \times N$ matrix in $N^2 \operatorname{polylog}\left(N\right)$ arithmetic operations. The main identity used for ...
- 421
15
votes
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
Well, one thing is I think that all the constructions we know of - and even the families of potential constructions that people have proposed (e.g., Cohn-Umans approaches, generalizations of ...
- 37.8k
5
votes
Accepted
Fast Finding Main Diagonal of Matrix Multiplication
Not unless $\omega = 2$. Take $B = \operatorname{id}$, $A = \begin{bmatrix}X & Y\end{bmatrix}$. You can extract $XY$ from $A^TBA$.
UPDATE: I missed the main diagonal part of the question. Even ...
- 687
4
votes
Bigger picture behind the choice of matrices in the Strassen algorithm
Several authors have attempted to elucidate the structure of Strassen's algorithm. The two most recent I am aware of are:
Ikenmeyer and Lysikov '17 give a beautiful exposition, though ultimately the ...
- 37.8k
4
votes
Accepted
Is the exponent in the rectangular matrix multiplication convex?
Does Lemma 3.6 of https://arxiv.org/abs/2009.10217 answer your original question of convexity of the matrix multiplication constant?
- 136
2
votes
Is the exponent in the rectangular matrix multiplication convex?
I found an answer in the paper "Fast sparse matrix multiplication" as Theorem 2.4. The authors cite "Fast rectangular matrix multiplications and applications", so that's the ...
- 630
2
votes
Face-splitting product of two Vandermonde matrices: When is is invertible?
Sorry if I am missing something, but isn't it always singular in your special case? The first column is identically $1$, the second column is $(\beta_1,\ldots,\beta_{n^2})^T$, and the $n+1$'th column ...
- 995
Only top scored, non community-wiki answers of a minimum length are eligible