Massively Parallel Searching for Better Algorithms or How to Do a Cross Product with Five Multiplications

Article type: Research Article

Authors: GUSTAFSON, JOHN | ALURU, SRINIVAS

Affiliations: Ames Laboratory, Iowa State University, Ames, IA 50011; e-mail: gus@scl.ameslab.gov | Department of Computer and Information Science, Syracuse University, Syracuse, NY 13244; e-mail: aluru@top.cis.syr.edu

Abstract: A number of "tricks" are known that trade multiplications for additions. The term "tricks" reflects the way these methods seem not to proceed from any general theory, but instead jump into existence as recipes that work. The Strassen method for 2 × 2 matrix product with seven multiplications is a well-known example, as is the method for finding a complex number product in three multiplications. We have created a practical computer program for finding such tricks automatically, where massive parallelism makes the combinatorially explosive search tolerable for small problems. One result of this program is a method for cross products of three-vectors that requires only five multiplications.

Journal: Scientific Programming, vol. 5, no. 3, pp. 203-217, 1996