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 ...
- 36.9k
8
votes
Accepted
Matrix multiplication with transpose
No.
Consider block matrices $A = \left(\begin{matrix} 0 & 0 \\ 0 & X \end{matrix}\right)$ (with symmetric $X$) and $B = \left(\begin{matrix} 0 & Y \\ 0 & 0 \end{matrix} \right)$. ...
- 632
5
votes
Accepted
Arithmetic complexity of matrix powering
It depends on the relationship between $m$ and $d$. If $m \geq 3$ is fixed, but $d$ is allowed to grow without bound, then the corresponding class of functions is exactly the same as functions with ...
- 36.9k
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 ...
- 632
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
4
votes
Accepted
Low-depth arithmetic complexity of the product of $k$ matrices
I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of ...
- 4,439
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 ...
- 800
1
vote
Winograd's proof of the lower bound for 2x2 matrix multiplication
Because $\mathbf{c}' = R'\mathbf{p}$ and $R'$ contains 3 nonzero elements in each row.
- 632
Only top scored, non community-wiki answers of a minimum length are eligible