Matrix Multiplication and Fast Fourier Transforms

Factoring a viatrix and multiplying successively by the factors can sometimes be used to speed up matrix multiplications. This is, in fact, the trick which creates the fantastic gains oj the jast Fourier transform. The same trick which creates the fantastic gains of the fast Fourier transform may be used with other matrices. As an example, suppose the matrix 1 -5 2 -20 4 -10 2 -20 1 -5 4 -20 1 -10 2 3 -7 6 -28 12 -14 6 -28 3 -7 12 -28 3 -14 6 4 -14 12 - 7 . -5 -10 is to be multiplied by a large number of different vectors, so that it is worthwhile to try to be as efficient as possible. At first glance, it would appear that (neglecting the possibility that multiplications by one might not actually be performed) multiplying this matrix with a single column vector would require 62 = 36 multiplications and 6(6-1) = 30 additions. The crafty person, however, might notice that this matrix may be written as the product of two matrices: 1 2 · . 4 . · 1 . . -4 _2 -1 -4 -2 5 · -1 1099 4 · -1 -2 -4 -5 1 · -1 · · · 5 7 · · -3 -7 2 4 · 1 2 .