Summary and Conclusions

With the speed of computers continuing to increase about 60% per year, it is prudent to examine some of the problems and solution methods traditionally thought of as `intractable'. Contrary to the philosophy taught in most computer science programs, even programs of combinatorially explosive complexity can yield interesting results for small problems. The computer-aided discovery of a cross product with 5 multiplications is an example of the kind of problem we can now pose to the fastest machines available.

In 1992, computers are capable of about 10¹¹ integer operations per second, So a run within the limits of human patience might involve 10¹⁷ operations. At the current rate of performance improvement, computers will eventually be fast enough to `discover' the Strassen product trick in a two-week run. As we find better rules for pruning the search tree, we might well move this date up by many years, and be able to attempt larger problems with the MPP computers of the future.

Acknowledgements

We wish to thank Dr. G. M. Prabhu for many suggestions during the development of this paper and for verifying the proofs of the validity of the conservative pruning rules. We are also indebted to Sandia National Laboratories for generous amounts of time on their 1024-processor nCUBE 2 computer, on which many of our results were obtained.