An algorithm is presented which enables certain matrix multiplications in a digital computer to be implemented with a considerable savings in storage and computational operations. For NxN matrix vector multiplication (that is a multiplication of a matrix by a vector) a maximum of N Σn-1 r=0 pr, storage words are necessary compared to normal full matrix storage requirements of N2locations. In addition only N Σn-1 r=0 Pr, computer operations are necessary compared to N2operation in a general vector matrix multiplication. N is chosen to be a highly composite number, N= πn-1 r=0 pr, and the pr, are integers. The algorithm takes advantage of the redundancies in the definition of certain matrices and develops a matrix description based on the number of degrees of freedom necessary in defining an NxN matrix. The algorithm is optimal in the sense that it describes a vector matrix multiplication in exactly as many operations as available degrees of freedom N σn-1 r=0 Pr(no greater number of degrees of freedom could be implemented in fewer operations). The matrix transformation formulation is based largely on noting the use of lexicographic positional digit notation in keeping track of the few parameters describing the final N by N matrix. The algorithm includes the generation of the fast Fourier transform, fast Hadamard transform, fast Walsh transform, fast Kronecker matrix transform, and an infinite class of transformations unnamed but potentially useful in generalized spectral analysis as well as coding, bandwidth reduction, and feature selection.

A technique is presented to implement a class of orthogonal transformations on the order of pN logpN operations. The technique is due to Good [1] and implements a fast Fourier transform, fast Hadamard transform, and a variety of other orthogonal decompositions. It is shown how the Kronecker product can be mathematically defined and efficiently implemented using a matrix factorization method. A generalized spectral analysis is suggested, and a variety of examples are presented displaying various properties of the decompositions possible. Finally, an eigenvalue presentation is provided as a possible means of characterizing some of the transforms with similar parameters.