All Questions
Tagged with linear-algebra matrix-product
15 questions
1
vote
1
answer
231
views
Face-splitting product of two Vandermonde matrices: When is is invertible?
Let $A$ and $B$ be two $n^2 \times n$ Vandermonde matrices with coefficients $\alpha_1,\ldots,\alpha_{n^2}$ and $\beta_1,\ldots,\beta_{n^2}$. Let $M$ be the face-splitting product of $A$ and $B$, that ...
- 1,481
43
votes
3
answers
6k
views
Evidence that matrix multiplication is not in $O(n^2\log^kn)$ time
It is commonly believed that for all $\epsilon > 0$, it is possible to multiply two $n \times n$ matrices in $O(n^{2 + \epsilon})$ time. Some discussion is here.
I have asked some people who are ...
- 531
2
votes
1
answer
500
views
Matrix multiplication with transpose
Let $A,B\in\mathbb{F}^{n\times n}$ be two $n\times n$ matrices over
the underlying field $\mathbb{F}$. In addition, $A$ is guaranteed
to be a symmetric matrix, i.e, $A=A^{T}$. We assume complexity ...
- 727
0
votes
0
answers
125
views
Is there a diagonal matrix D such that DMD is SDD, where M is SPD matrix
Let $M$ be symmetric and positive definite matrix (SPD). It is known [1] that
if $M$ is SPD and
in addition satisfies $M_{ij}\leq 0$, for $i\neq j$ (called M-matrix)
then there is a positive ...
- 1
4
votes
1
answer
478
views
state-of-the-art bit complexity of the determinant
I'm trying to understand the full bit-complexity of computing the determinant of an $n\times n$ integer matrix, with each entry represented by $M$ bits.
I would like to know what is the state-of-the-...
- 1,224
-3
votes
1
answer
346
views
the product of a matrix and a permutation matrix [closed]
Can a permutation matrix (P) be used to change the rank of another matrix (M)?
Is there any literature to this effect, or to the contrary?
I've tried a few small examples and the resulting matrix (M2)...
- 17
3
votes
2
answers
659
views
Matrix multiplication algorithms for research
I am implementing a matrix library for use in my research. This should support 2D matrices of size 100x100 (or more perhaps later on). I am a little confused about the algorithm I should be using for ...
- 101
12
votes
0
answers
286
views
the largest element of a matrix product
Given two matrices, I'm interested in finding the largest element of their product. I wonder if it's possible to do it significantly faster than the matrix multiplication the solution seems to require?...
- 259
22
votes
3
answers
798
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 ...
user4292
2
votes
1
answer
402
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 ...
- 241
4
votes
0
answers
677
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 ...
14
votes
1
answer
8k
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 ...
- 149
21
votes
1
answer
828
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 ...
- 13.8k
64
votes
4
answers
4k
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$?
I'm ...
- 823
14
votes
1
answer
4k
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 ...
- 3,450