Patent US 6,401,189

General base hypercube transformations using general base perfect shuffles and Kronecker matrix products are applied to the problem of parallel, to massively parallel processing of sparse matrices. The approach is illustrated by applying the hypercube transformations to general base factorizations of generalized spectral analysis transformation matrices. Hypercube transformations lead to optimal scheduling with contention-free memory allocation at any level of parallelism and up to massive parallelism. The approach is illustrated by applying the generalized-parallelism hypercube transformations to factorizations of generalized spectral analysis transformation matrices, and in particular to Generalized Walsh-Chrestenson transformation matrices of which the Discrete Fourier transform and hence the Fast Fourier transform are but a special case. These factorizations are a function of four variables, namely, the general base p, the number of members of the class of matrices n, a parameter k describing the matrix structure and the number M of parallel processing elements. The degree of parallelism, in the form of M=pm processors can be chosen arbitrarily by varying m between zero to its maximum value of n−1. The result is an equation describing the solution as a function of the four variables n, p, k and m.