The matrix-product tag has no wiki summary.
8
votes
2answers
156 views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.
It is known that the determinant of an $n\times n$ matrix can ...
15
votes
2answers
237 views
Bigger picture behind the choice of matrices in the Strassen algorithm
In the Strassen algorithm, to compute the product of two matrices $\mathbf{A}$ and $\mathbf{B}$, the matrices $\mathbf{A}$ and $\mathbf{B}$ are divided into $2 \times 2$ block matrices and the ...
1
vote
1answer
206 views
All Pairs Shortest Path - Directed graph with integer weights
I don't understand how Distance Product works (or Min Plus Product). If we replace each argument in $A$ from $a_{i,j}$ to $x^{a_{i,j}}$ and each argument in $B$ from $b_{i,j}$ to $x^{b_{i,j}}$ and ...
3
votes
0answers
153 views
What about apply maxplus algebra for all-pairs shortest paths?
I didn't find deep informations on Wikipedia about all-pairs shortest path, in particular I do not know what is the best algorithm to solve this problem beyond Floyd-Warshall's one, then I do not know ...
10
votes
1answer
210 views
Capacity of Uniquely Solvable Puzzle (USP)
In their seminal paper Group-theoretic algorithms for matrix multiplications, Cohn, Kleinberg, Szegedy and Umans introduce the concept of uniquely solvable puzzle (defined below) and USP capacity. ...
11
votes
1answer
1k views
The computational complexity of matrix multiplication
I am looking for information about the computational complexity of matrix multiplication of rectangular matrices. Wikipedia states that the complexity of multiplying $A \in \mathbb{R}^{m \times n}$ by ...
-1
votes
1answer
235 views
How can a problem have complexity $O(n^{2+\epsilon})$ for all $\epsilon > 0$?
For instance, it is believed that for any $\epsilon>0$ there is an algorithm for matrix multiplication that runs in $O(n^{2+\epsilon})$, but possibly no algorithm that runs in $O(n^2)$. How is this ...
4
votes
0answers
295 views
Multiplication of circulant matrices with a diagonal matrix
Let $A_{i}$, $B_{i}$ be a sequence of circulant matrices of size $n \times n$.
We know that $\sum_{i=1}^{n}A_{i}B_{i}$ can be calculated in quadratic time (use FFT to diagonalize and add the diagonal ...
4
votes
0answers
185 views
Question on size of words in Vandermonde Matrix - Vector multiplication complexity
I am trying to understand how word sizes in a problem affects complexity. The question could be a simple technicality I am trying to clarify since I am not from mainstream CS. Let $V$ be an $n \times ...
14
votes
1answer
376 views
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the ...
45
votes
3answers
1k views
Evidence that matrix multiplication can be done in quadratic time?
It is widely conjectured that $\omega$, the optimal exponent for matrix multiplication, is in fact equal to 2. My question is simple:
What reasons do we have for believing that $\omega = 2$?
...
14
votes
1answer
1k views
Matrix multiplication in $O(n^2 \log n)$
I was searching about Matrix multiplication, So I first visit wiki matrix multiplication algorithms, In references I found a paper which claim that uses $O(n^2 log(n))$ algorithm , I'd going to read ...
25
votes
2answers
1k views
Quantum matrix multiplication?
It doesn't seem like this is known - but are there any interesting lower bounds on the complexity of matrix multiplication in the quantum computing model? Do we have any intuition that we can beat ...
11
votes
2answers
589 views
Fast sparse boolean matrix product with possible preprocessing
What are the most practically efficient algorithms for multiplying two very sparse boolean matrices (say, N=200 and there are just some 100-200 non-zero elements)?
Actually, I have the advantage that ...
10
votes
1answer
337 views
Fast sparse boolean matrix chain product
So, I've got about 100-200 very sparse square boolean matrices with side length ~several dozens, and I need to compute their product. I know that if I multiply them serially, the product will usually ...
