The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
38 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
180 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
89 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
269 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
175 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 ...
2
votes
1answer
148 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
111 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
294 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
150 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
507 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
321 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
345 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
253 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
268 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
3k 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
255 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
554 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
196 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
448 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 ...
47
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$? ...
14
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 ...
26
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
806 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
370 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 ...