Questions tagged [matrix-product]
The matrix-product tag has no usage guidance.
44
questions
2
votes
0
answers
51
views
computational complexity of sparse matrix powers
Given a sparse matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in it. What is the computational complexity of computing $A^k$, for some positive integer $k$? As $k$ gets larger, I ...
- 209
2
votes
0
answers
51
views
Has there been any research on faster tensor inner products?
Matrix multiplication is a well studied problem which is recently back in the news due to deepmind.
That got me wondering has anyone looked at the more general problem of faster tensor multiplication? ...
- 369
4
votes
0
answers
156
views
Exact lower bound on matrix multiplication
The recent publication in Nature of "Discovering faster matrix multiplication algorithms with reinforcement learning" by Fawzi et al. has shown a method for discovering fewer element ...
- 895
0
votes
0
answers
119
views
How far easier is Boolean matrix multiplication, compared to matrix multiplication?
It is obvious that boolean matrix multiplication can be solved in $O(n^\omega)$, as a simple variant of regular matrix multiplication. I saw a recent paper solving boolean matrix multiplication in $O(...
4
votes
0
answers
86
views
Flipping one bit to maximize BMM output
Consider a boolean matrix $A$ of size $N \times N$ and let $A^\top$ be its transpose. Let $C = AA^\top$ be the boolean matrix multiplication (BMM) result and let $c$ be the number of non-negative ...
- 1,167
1
vote
0
answers
240
views
An $O(n^2\log^c{n})$ algorithm for matrix multiplication in this paper?
In the newest version of this paper by Yijie Han, the author claims that matrix multiplication can be solved by an $\tilde{O}(n^2)$ algorithm. It should be a big result, but it is still in arxiv and ...
- 451
12
votes
2
answers
229
views
Is the exponent in the rectangular matrix multiplication convex?
My question is regarding the paper "Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor". In the paper, the authors show an algorithm for multiplying a ...
- 600
0
votes
0
answers
129
views
Triangle counting using approximate matrix multiplication -- suspicious paper
This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper)....
- 600
1
vote
1
answer
198
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,217
4
votes
0
answers
144
views
Dynamic matrix-matrix multiplication
Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each ...
- 361
41
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 ...
- 511
4
votes
1
answer
117
views
Fast Finding Main Diagonal of Matrix Multiplication
Suppose we have two matrices $A_{m\times n}$ and $B_{m\times m}$. Such that $B$ is a symmetric positive definite matrix. Is it possible to compute main diganoal of $A^TBA$ in $O(n\times m)$?
- 189
2
votes
0
answers
141
views
Trying to find Warren D. Smith's Matrix Multiplication article
One of my favorite articles on the complexity of matrix multiplication has gone dark.
Warren Smith, Fast Matrix Algorithms And Multiplication Formulae, https://math.cst.temple.edu/~wds/matgrant.ps
...
- 2,351
2
votes
1
answer
113
views
Low-depth arithmetic complexity of the product of $k$ matrices
Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?
Trivial upper bounds (up to small factors) are:
if $k=2$, then there are $\...
- 829
4
votes
1
answer
966
views
Space complexity for multiplying $m$ matrices
Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.
The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. ...
- 131
2
votes
1
answer
482
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 ...
- 717
-3
votes
1
answer
197
views
Winograd's proof of the lower bound for 2x2 matrix multiplication
There is the basic paper of S.Winograd (http://www.sciencedirect.com/science/article/pii/0024379571900097) about 2x2 matrix multiplication.
In the proof of the main Theorem 3.1, there is a some ...
- 11
6
votes
1
answer
253
views
Arithmetic complexity of matrix powering
Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables.
We know that size of smallest formula that computes $\mathsf{Tr}(M^d)$ where $d\in\Bbb N$ could be ...
user34945
17
votes
1
answer
504
views
smallest circuit size using XOR gates
Suppose we are given a set of n boolean variables x_1,...,x_n and a set of m functions y_1...y_m where each y_i is the XOR of a (given) subset of these variables.
The goal is to compute the minimum ...
0
votes
0
answers
123
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
3
votes
0
answers
52
views
Best complexity bound for parallel matrix-vector product?
I'm looking for the best known complexity (and a bound for the number of processors invoved) to do the calculation of a $(n,n)$ matrix-vector product.
Thank you
- 131
5
votes
2
answers
327
views
Decision version of matrix multiplication problem
Is there any known decision version of matrix multiplication problem such that the time complexity of the best known algorithm for this decision problem is $O(n^k)$ for $n \times n$-dimensional ...
- 3,677
4
votes
0
answers
120
views
Complexity of a variant of matrix multiplication
Assume a family of $n\times n$ integer matrices $\{M_a \mid a\in A\}$ for some finite set $A$, I want to decide whether for given vectors $\alpha$ and $\beta$,
$\alpha M(w) \beta=0$ for all $w\in A^{...
8
votes
1
answer
336
views
"Matrix complexity" - is it possible?
While browsing old CStheory.se posts, I ran across a fascinating blog post on the matrix mortality problem. Unless I've misinterpreted the problem, it states that given a finite collection of 3 x 3 ...
user1338
4
votes
1
answer
428
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
5
votes
2
answers
307
views
Commutative matrix multiplication algorithms
What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-...
- 12.6k
-3
votes
1
answer
295
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
636
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
253
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?...
- 231
11
votes
2
answers
1k
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 ...
- 12.6k
19
votes
2
answers
608
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
394
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
660
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 ...
13
votes
1
answer
467
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. ...
- 14.2k
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
-1
votes
1
answer
599
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 ...
- 390
8
votes
1
answer
1k
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 ...
- 12.6k
4
votes
0
answers
228
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 ...
- 12.6k
21
votes
1
answer
771
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.4k
61
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 ...
- 793
13
votes
1
answer
3k
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,430
30
votes
2
answers
4k
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 ...
- 3,718
12
votes
2
answers
2k
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 ...
- 8,721
13
votes
1
answer
531
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 ...
- 8,721