Questions tagged [matrix-product]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
0 answers
74 views

Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
Mingda Qiao's user avatar
2 votes
0 answers
55 views

Matrix Multiplication $C\cdot (S\otimes S)$ where one product-and is a tensor square?

Let $D\in\mathbb{Z}^{1\times m}$. Let $A, A'\in\mathbb{Z}^{\sqrt{m}\times n}$, so $A\otimes A'\in\mathbb{Z}^{m\times n^2}$. Let $S\in\mathbb{Z}^{n\times 1}$. I am in a regime where $m \gg n$. I am ...
Mark Schultz-Wu's user avatar
2 votes
0 answers
62 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 ...
user43464's user avatar
  • 209
2 votes
0 answers
82 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? ...
Sidharth Ghoshal's user avatar
4 votes
0 answers
214 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 ...
Mitch's user avatar
  • 905
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 ...
karmanaut's user avatar
  • 1,177
1 vote
0 answers
264 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 ...
Mengfan Ma's user avatar
13 votes
2 answers
284 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 ...
user2316602's user avatar
0 votes
0 answers
139 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)....
user2316602's user avatar
1 vote
1 answer
218 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 ...
M.Monet's user avatar
  • 1,429
4 votes
0 answers
148 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 ...
gsv's user avatar
  • 421
44 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 ...
Brian's user avatar
  • 541
4 votes
1 answer
127 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)$?
OmG's user avatar
  • 189
2 votes
0 answers
146 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 ...
Chad Brewbaker's user avatar
2 votes
1 answer
115 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 $\...
ivmihajlin's user avatar
4 votes
1 answer
1k 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. ...
Lijie Chen's user avatar
2 votes
1 answer
492 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 ...
Gorav Jindal's user avatar
-3 votes
1 answer
236 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 ...
YurySerdyuk's user avatar
6 votes
1 answer
274 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 ...
user avatar
17 votes
1 answer
528 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 ...
Mohammad R. Salavatipour's user avatar
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 ...
Pavel's user avatar
  • 1
3 votes
0 answers
53 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
Dingo13's user avatar
  • 131
5 votes
2 answers
341 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 ...
Abuzer Yakaryilmaz's user avatar
4 votes
0 answers
121 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^{...
Peter Purecell's user avatar
8 votes
1 answer
341 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 ...
user avatar
4 votes
1 answer
457 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-...
Lior Eldar's user avatar
  • 1,224
5 votes
2 answers
316 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-...
Turbo's user avatar
  • 12.8k
-3 votes
1 answer
321 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)...
msg's user avatar
  • 17
3 votes
2 answers
648 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 ...
rajaditya_m's user avatar
12 votes
0 answers
277 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?...
MWB's user avatar
  • 251
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 ...
Turbo's user avatar
  • 12.8k
22 votes
3 answers
766 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 ...
user avatar
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 ...
Bush's user avatar
  • 241
4 votes
0 answers
665 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 ...
Immanuel Weihnachten's user avatar
13 votes
1 answer
472 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. ...
Yuval Filmus's user avatar
  • 14.4k
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 ...
inquirer's user avatar
  • 149
-1 votes
1 answer
653 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 ...
Jules's user avatar
  • 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 ...
Turbo's user avatar
  • 12.8k
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 ...
Turbo's user avatar
  • 12.8k
21 votes
1 answer
805 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 ...
Robin Kothari's user avatar
63 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 ...
Steve Flammia's user avatar
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 ...
Saeed's user avatar
  • 3,440
32 votes
2 answers
5k 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 ...
Henry Yuen's user avatar
  • 3,798
13 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 ...
jkff's user avatar
  • 8,941
13 votes
1 answer
546 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 ...
jkff's user avatar
  • 8,941