Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Strassen products

The Strassen algorithm for 2 2 matrix products [20] was cited in the Introduction. Applied recursively to matrices of size N, it reduces the complexity of matrix-matrix products from order N³ to order N^log₂7. The lack of an obvious pattern in the algorithm was the original motive for the work described in this paper. We intended to generate the Strassen method by exhaustive search, and then attempt to find similar 'tricks' for 3 3 and 4 4 matrix products. For 3 3 matrix products, a method using only 23 multiplications has been found [13], presumably by hand. With optimal methods for 2 2, 3 3, and 4 4, we hoped to find a pattern that would reduce the exponent for matrix products without requiring very large values of N, the matrix size.

The budget for a Strassen product, using the Winograd improvement, is 22 operations (7 multiplications and 15 additions). Since the search grows exponentially in the number of operations in the budget, the search is significantly harder than those described in previous sections:

Based on the number of "stems" generated by the parallel algorithm and the rate at which progress is made through that set of stems, we estimate that exhaustive search for the Strassen matrix product on the 1,024-processor nCUBE 2, even with aggressive pruning rules, would take many centuries. We continue to seek exploitable symmetries and search orderings that will result in discovery of methods, if not search of the entire space.