Matrix Multiplication

 The core of many equation solvers is a matrix multiplication routine. The time complexity of calculating the matrix product C=AB where A, B, and C are tex2html_wrap_inline317 matrices, using traditional matrix multiplication, is tex2html_wrap_inline319 . Strassen's matrix multiplication algorithm is able to perform this calculation in time tex2html_wrap_inline321 [8, 15]. Thus one might be able to speed up the code by using Strassen's algorithm instead of the traditional algorithm. Both IBM and Cray support routines for fast matrix multiplications using Strassen's algorithm. See also [2, 3] for examples of implementations of Strassen's algorithm. However, the error bound given by Strassen's algorithm is weaker than that of the traditional algorithm [5, 9]. Thus the approaches might give different answers. If one suspects that this is the case one can use comparative debugging to determine if and when the result of Strassen's algorithm differs significantly from that of the ordinary algorithm.

View example of Strassen' algorithm: , or .