3
$\begingroup$

Input : Two matrices $A$ and $B$ of size $n$ X $n$.

Compute : Matrix product $A$ X $B$.

Some of the known results about matrix multiplication are given below.

Brute Force : $O(n^3)$.

Nader H. Bshouty : at least $2.5$ $n^2 -$$o( n^2 )$ [over binary field] multiplications. A lower bound for matrix multiplication

A paper by Yijie Han : Matrix Multiplication Algorithm by Yijie Han

After reading the paper above I come to know that lower bound for matrix multiplication reduces to the problem of finding inner product of two vectors. I know how to compute a inner product of two vector in a brute force way. So my question is

Question : How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications ?.

$\endgroup$
  • $\begingroup$ I don't understand the sentence "it appears that lower bound for matrix multiplication to the Inner product of two vectors". Is the word reduces missing here? $\endgroup$ – Yuval Filmus Mar 9 '17 at 8:15
  • $\begingroup$ @Yuval Filmus yes. I have edited the question. $\endgroup$ – aaag Mar 9 '17 at 8:43
6
$\begingroup$

Here is a proof in the real case. For general fields, this only gives a lower bound of $\lceil n/2 \rceil$, though the correct lower bound should indeed be $n$. For more, take a look at the monograph Algebraic complexity theory by Bürgisser, Clausen and Shokrollahi.

Model

It will be easier to give a lower bound on computing the inner product of a vector with itself; this is a potentially easier task. Consider an arithmetic "straight-line" program for computing the squared norm $\sum_{i=1}^n x_i^2$. Such a program consists of the following operations: addition, subtraction, multiplication, division, all of which of the form $a \gets b \circ c$. We are also allowed to "load" input variables and arbitrary field constants. The final answer must be found in some variable. Since we don't care about space, we can assume that every operation assigns its output to a new variable.

For simplicity we will not allow division in what follows, though divisions can always be eliminated (this is a famous result of Strassen), without too much trouble.

Here is an example of such a program:

$t_1 \gets x_1 \cdot x_1$

$t_2 \gets x_2 \cdot x_2$

...

$t_n \gets x_n \cdot x_n$

$s_2 \gets t_1 + t_2$

$s_3 \gets s_2 + t_3$

...

$s_n \gets s_{n-1} + t_n$

The variable $s_n$ contains the inner product.

Normal form (1)

The first step is coming up with a program in normal form. Let $t$ be a variable occurring in the program. The value of $t$ is always a fixed polynomial in the inputs (if we allowed divisions, it could be a more general power series). We write $t$ as a sum $t = t^{(0)} + t^{(1)} + t^{(2)} + t'$, where

  • $t^{(0)}$ is a constant.
  • $t^{(1)} = \sum_i c_i x_i$.
  • $t^{(2)} = \sum_{i \leq j} d_{ij} x_i x_j$.
  • $t'$ consists of all monomials of degree larger than 2.

We will convert an arbitrary program into one which computes only the parts $t^{(0)},t^{(1)},t^{(2)}$, and furthermore contains no more "essential" multiplications than the original program; a multiplication is not essential if one of the operands is a constant. Since the output variable $o$ satisfies $o = o^{(2)}$, the new program also computes the squared norm.

The base cases are when $t$ is constant or an input variable. In both cases no computation is needed, since each part is either zero, a constant, or an input variable.

We replace the operation $a \gets b + c$ with the sequence $a^{(0)} \gets b^{(0)} + c^{(0)}$, $a^{(1)} \gets b^{(1)} + c^{(1)}$, $a^{(2)} \gets b^{(2)} + c^{(2)}$. Subtraction is similar.

The most interesting operation is $a \gets b \cdot c$, which we replace by the sequence

$a^{(0)} \gets b^{(0)} \cdot c^{(0)}$

$a^{(1')} \gets b^{(0)} \cdot c^{(1)}$

$a^{(1'')} \gets b^{(1)} \cdot c^{(0)}$

$a^{(1)} \gets a^{(1')} + a^{(1'')}$

$a^{(2')} \gets b^{(0)} \cdot c^{(2)}$

$a^{(2'')} \gets b^{(1)} \cdot c^{(1)}$

$a^{(2''')} \gets b^{(2)} \cdot c^{(0)}$

$a^{(2'''')} \gets a^{(2')} + a^{(2'')}$

$a^{(2)} \gets a^{(2''')} + a^{(2'''')}$

The only essential multiplication is involved in computing $a^{(2'')}$.

It is routine to check that the new program indeed computes $t^{(0)},t^{(1)},t^{(2)}$ correctly for all $t$ occurring in the original program.

Normal form (2)

Consider the new program. It is not hard to prove by induction that for each original variable $t$,

  • $t^{(0}$ is a constant.

  • $t^{(1)}$ is a linear combination of inputs, i.e. of the form $\sum_i c_i x_i$.

  • $t^{(2)}$ is a linear combination of the results of essential multiplications (multiplications of the form $s^{(1)} \cdot r^{(1)}$).

In particular, if there are $m$ multiplications in the original program then there are $m$ essential multiplications in the new program, and so it is semantically equivalent to the following program:

  • Compute $2m$ linear combinations $\ell_1,\ldots,\ell_{2m}$ of the inputs.

  • Compute $m$ essential multiplications $p_i \gets \ell_{i_1} \cdot \ell_{i_2}$, for $1 \leq i \leq m$.

  • Output a linear combination $\sum_{i=1}^m c_i p_i$.

In fact, without loss of generality we can assume that $c_i = 1$.

Rank lower bound

Given a program computing the inner product $\sum_{i=1}^n x_i y_i$ using $m$ multiplications, we have shown how to obtain a representation $$ \sum_{i=1}^n x_i^2 = \sum_{j=1}^m \ell_j r_j, $$ where $\ell_j,r_j$ are linear combinations of the $x_i$. Replace $\ell_j,r_j$ with coefficient vectors of length $n$, say column vectors. The representation then implies the matrix identity $$ I_n + S = \sum_{j=1}^m \ell_j r_j^T, $$ where $S$ is a skew-symmetric matrix (we get $S$ since $x_ix_j$ can be represented in two ways for $i \neq j$). If we are working over the reals, then all eigenvalues of $S$ are either zero or pure imaginary, and so $I_n + S$ has full rank. The right-hand side implies that the rank is at most $m$, and we conclude that $m \geq n$.

When working over the complex numbers, we can have shortcuts such as $$ (x_1 + ix_2)(x_1 - ix_2) = x_1^2 + x_2^2. $$ The same method still shows that $n/2$ multiplications are needed, and indeed the optimal number of multiplications to compute the squared norm is $\lceil n/2 \rceil$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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