Massively parallel searching for better algorithms

摘要

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 (times) 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 3-vectors that requires only five multiplications.