The tag has no usage guidance.

learn more… | top users | synonyms

3
votes
1answer
72 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 ...
5
votes
1answer
158 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. ...
3
votes
1answer
183 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 ...
-4
votes
1answer
57 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 ...
6
votes
1answer
189 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 ...
15
votes
1answer
264 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
0answers
45 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 ...
3
votes
0answers
42 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
4
votes
2answers
199 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 ...
4
votes
0answers
103 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 ...
7
votes
1answer
281 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 ...
4
votes
1answer
201 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 ...
5
votes
2answers
231 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 ...
-3
votes
1answer
163 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 ...
-1
votes
2answers
349 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 ...
11
votes
0answers
164 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 ...
11
votes
2answers
711 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 ...
16
votes
2answers
350 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 ...
2
votes
1answer
356 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 ...
4
votes
0answers
358 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
1answer
295 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. ...
13
votes
1answer
4k 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
273 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 ...
8
votes
1answer
660 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
206 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 ...
18
votes
1answer
474 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 ...
50
votes
3answers
2k 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$? ...
13
votes
1answer
2k 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 ...
27
votes
2answers
2k 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 ...
12
votes
2answers
993 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 ...
11
votes
1answer
384 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 ...