Matrix vector multiplication algorithm using minimal number of additions 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 
What are the relationships between those hypotheses in Fine-Grained Complexity Theory?
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.