10
$\begingroup$

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

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Stasys
    Commented Sep 27, 2015 at 17:02

2 Answers 2

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
7
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.