Multiplying a 
matrix by a 
vector usually
requires 
multiplications. However, a matrix of the form
can be multiplied by a 
vector in 
operations by
taking advantage of its particular structure. Yates' algorithm
that we describe in this appendix is one method to achieve that saving.
Define the following tensor product of the matrices 
and 
:
where 
is at position 
.
Let 
be the matrix A expanded as:
Then, we can state the following result:
Theorem Let 
and 
be the expansions of A
and B as described above. Then,
This result generalizes to powers, with a suitable definition of
along the lines described above.
Let's consider a simple example where m=n=2.
Now, to multiply 
by the vector v, we take advantage of
the sparsity of the matrices 
and 
. Each row or
has only two non-zero elements, so 
is
computed in 
multiplications. 
is
also computed in 
operations. In general, the number of
multiplications is 
. In our simple example,
we do not save anything, because the total number of multiplications
(16) is the same with the ordinary matrix multiplication. However,
when 
.
We can also use Yates' algorithm to multiply 
by a
vector v. The matrix 
is 
with only
m non-zero elements on each of its rows. The product 
involves 
multiplications. To get 
, we
repeat the product p times, for a total of 
multiplications. The saving is huge even for moderately large p
compared to the 
multiplications of an ordinary matrix by
vector product. For example, for m=2 and 
but 
.