ruck@sphere.UUCP (John R Ruckstuhl Jr) (05/29/90)
How might I determine the most efficient way to compute C=AB, where A is
a matrix of small integers, B is a vector of arbitrary real numbers, and
the computation algorithm is restricted to additions/subtractions?
For example, ?clever? separation allows one to compute
C = [ 2 0 0 0 0 ] B
[ -1 -2 2 -1 2 ]
[ -2 -1 -3 0 -1 ]
[ 1 1 1 1 -2 ]
[ 0 0 0 0 1 ]
with 13 additions:
c0 = (b0 + b0)
c1 = -(b0 + b3 - b4 - b4) - (b1 - b2) - (b1 - b2)
c2 = -(b0 + b0) - (b1 + b2) - (b1 + b2) + (b1 - b2) - b4
c3 = (b0 + b3 - b4 - b4) + (b1 + b2)
c4 = b4
I would like an algorithm (or a pointer to a reference to same) to
determine the sequence of additions needed to compute such a matrix
product. I am not concerned with sensitivity to rounding errors.
I am an EE with little advanced algebra background.
The application is to code efficient algorithms for linear convolution
in digital signal processing. This is analagous to multiplication of
polynomials. The above example is suggested by a 3 by 3 linear
convolution using a modified Cook-Toom algorithm which is based on
Lagrange interpolation. This technique is useful only for small
convolutions (smaller than 4 by 4 or so); larger convolutions
(polynomial multiplications) exhaust the supply of small integers at
which to evaluate the polynomial product.
Thank you.
--
John R Ruckstuhl, Jr UUCP: sphere!ruck (or hplabs!hp-lsd!sphere!ruck)
DOMAIN: ruck%sphere@hp-lsd.cos.hp.com