Ames Laboratory, Department of Energy, ISU, Ames, Iowa
next up previous
Next: Introduction

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

John Gustafson
former Ames Laboratory Associate
Ames, Iowa 50011
e-mail: gus@sun.com		 Srinivas Aluru
New Mexico State University
Las Cruces, NM 88001
e-mail: aluru@cs.nmsu.edu

NOTE: Following the appearance of this work in Scientific Programming, the authors were contacted by Charles Fiduccia of the State University of New York at Stony Brook. An existence proof for a 5-multiplication cross product appears in Fiduccia's June 1973 Ph.D. thesis, "On the Algebraic Complexity of Matrix Multiplication" (Brown University), along with a variety of similar operation-reducing methods. This thesis was not discovered in the literature search for the following paper. We thank Dr. Fiduccia for alerting us regarding his work, and refer the interested reader to his thesis.--John Gustafson and Srinivas Aluru

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 by 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.

Keywords: Cross product, massively parallel, matrix multiplication, parallel search, Strassen.



[Return] Return to "Publications by John Gustafson"
The URL for this document is http://www.scl.ameslab.gov


1996 edition