<p>If you do <em>not</em> allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The interest in computational geometry is that range counting can be encoded as matrix-vector multiplication.) For example, the following lower bounds on the size of monotone linear circuits are known:</p>

<ul>
<li><p>$\Omega(n (\log n/\log \log n)^{d-1})$ for $M$ an $n\times n$ incidence matrix of axis-aligned boxes in $d$ dimensions;</p></li>
<li><p>$\Omega(n^{4/3})$ for $M$ an $n\times n$ incidence matrix of lines and points in $d$ dimensions;</p></li>
<li><p>$\tilde{\Omega}(n^{2-2/(d+1)})$ for $M$ an $n\times n$ incidence matrix of simplices in $d$ dimensions.</p></li>
</ul>

<p>These bounds are all essentially the best possible. See Chapter 6.3. in <a href="https://www.cs.princeton.edu/~chazelle/pubs/book.pdf" rel="nofollow">Chazelle's book</a>.</p>

CC BY-SA 3.0
2015-09-25T18:37:44.627Z
2015-09-26T12:42:59.090Z
2015-09-26T12:42:59.090Z
Sasho Nikolov
<p>This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history). </p>

<p>A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can one do better. It is known that for a random matrix one cannot do significantly better.</p>

<p>Some matrices - such as the Fourier transform matrix, a matrix of low rank, or a sparse matrix - can be done significantly better. </p>

<p>A sufficiently rigid matrix cannot be computed by linear circuits that are simultaneously linear size and log depth (Valiant), but to this day no explicit matrices are known for which there is a super-linear lower bound on the size of linear circuits. </p>

<p>I don't recall seeing results saying that it's hard to compute the size of the smallest linear circuit for a given matrix, but I wouldn't be surprised if it were NP-hard. </p>

CC BY-SA 3.0
2015-09-26T01:06:16.583Z
It is NP-hard, see http://cstheory.stackexchange.com/a/32272/225
Ryan Williams
CC BY-SA 3.0
2015-09-25T14:22:15.877Z
2015-09-25T14:22:15.877Z
Joshua Grochow
<p>Consider the following problem:</p>

<blockquote>
  <p>Given a matrix $M$ 
  we want to optimize the number of additions in 
  the multiplication algorithm for computing $v \mapsto Mv$.</p>
</blockquote>

<p>I find this problem interesting because of its ties with 
the complexity of matrix multiplication
(this problem is a restricted version of matrix multiplication).</p>

<p>What is know about this problem?</p>

<p>Is there any interesting results 
relating this problem to the complexity of matrix multiplication problem?</p>

<p>The answer to the problem seems to involve 
finding circuits with only addition gates. 
What if we allow subtraction gates?</p>

<p>I am looking for reductions between this problem and other problems.</p>

<hr>

<p>Motivated by  </p>

<ul>
<li><a href="https://cs.stackexchange.com/q/45596/">Automated optimization of 0-1 matrix vector multiplication</a> </li>
<li><a href="https://cstheory.stackexchange.com/q/32584/">What are the relationships between those hypotheses in Fine-Grained Complexity Theory?</a></li>
</ul>

CC BY-SA 3.0
2015-09-27T17:02:08.230Z
If $M$ is a $n\times n$ 0-1 matrix, then known lower bounds on the number of additions crucially depend on what group/semigroup we work over. If we work over the semigroup $(N,+)$ or even $(\{0,1\},\lor)$, then Nechiporuk's bound, together with known constructions, gives an explicit lower bound of about $n^{2-o(1)}$. If, however we are in the group $(GF(2),+)$, then the situation is rather depressing: the strongest known lower bounds are only of the form $\omega(n)$. More can be found [here](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/Knizka/).
Stasys
<cc.complexity-theory><reference-request><circuit-complexity><matrices><arithmetic-circuits>
Matrix vector multiplication algorithm using minimal number of additions
vzn
# Matrix vector multiplication algorithm using minimal number of additions

(Asked by: username_0 on 2015-09-25)

Consider the following problem:

> Given a matrix $M$
> we want to optimize the number of additions in
> the multiplication algorithm for computing $v \mapsto Mv$.

I find this problem interesting because of its ties with
the complexity of matrix multiplication
(this problem is a restricted version of matrix multiplication).

What is know about this problem?

Is there any interesting results
relating this problem to the complexity of matrix multiplication problem?

The answer to the problem seems to involve
finding circuits with only addition gates.
What if we allow subtraction gates?

I am looking for reductions between this problem and other problems.

---

Motivated by

* [Automated optimization of 0-1 matrix vector multiplication](https://cs.stackexchange.com/q/45596/)
* [What are the relationships between those hypotheses in Fine-Grained Complexity Theory?](https://cstheory.stackexchange.com/q/32584/)

**Tags:** cc.complexity-theory, reference-request, circuit-complexity, matrices, arithmetic-circuits

> **Comments:**
> **username_1**: If $M$ is a $n\times n$ 0-1 matrix, then known lower bounds on the number of additions crucially depend on what group/semigroup we work over. If we work over the semigroup $(N,+)$ or even $(\{0,1\},\lor)$, then Nechiporuk's bound, together with known constructions, gives an explicit lower bound of about $n^{2-o(1)}$. If, however we are in the group $(GF(2),+)$, then the situation is rather depressing: the strongest known lower bounds are only of the form $\omega(n)$. More can be found [here](http://lovelace.thi.informatik.uni-frankfurt.de/~jukna/Knizka/).  

---

## 2 answers

### Answer by username_3 on 2015-09-25. Score: 9 | Accepted answer

This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history).

A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can one do better. It is known that for a random matrix one cannot do significantly better.

Some matrices - such as the Fourier transform matrix, a matrix of low rank, or a sparse matrix - can be done significantly better.

A sufficiently rigid matrix cannot be computed by linear circuits that are simultaneously linear size and log depth (Valiant), but to this day no explicit matrices are known for which there is a super-linear lower bound on the size of linear circuits.

I don't recall seeing results saying that it's hard to compute the size of the smallest linear circuit for a given matrix, but I wouldn't be surprised if it were NP-hard.

> **Comments:**
> **username_4**: It is NP-hard, see http://cstheory.stackexchange.com/a/32272/225  

---

### Answer by username_2 on 2015-09-25. Score: 7

If you do *not* allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The interest in computational geometry is that range counting can be encoded as matrix-vector multiplication.) For example, the following lower bounds on the size of monotone linear circuits are known:

* $\Omega(n (\log n/\log \log n)^{d-1})$ for $M$ an $n\times n$ incidence matrix of axis-aligned boxes in $d$ dimensions;
* $\Omega(n^{4/3})$ for $M$ an $n\times n$ incidence matrix of lines and points in $d$ dimensions;
* $\tilde{\Omega}(n^{2-2/(d+1)})$ for $M$ an $n\times n$ incidence matrix of simplices in $d$ dimensions.

These bounds are all essentially the best possible. See Chapter 6.3. in [Chazelle's book](https://www.cs.princeton.edu/~chazelle/pubs/book.pdf).


---

