# Questions tagged [matrix-product]

The tag has no usage guidance.

41 questions
Filter by
Sorted by
Tagged with
103 views

• 829
937 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. ...
• 121
479 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
185 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 ...
246 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 ... 491 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 ...
117 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  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 ...
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
318 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,647
120 views

• 12.5k
740 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
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 ...
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
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,708
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,661