Matrix vector multiplication algorithm using minimal number of additions
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.