Ames Laboratory, Department of Energy, ISU, Ames, Iowa

Numerical Stability

The Search program can be used to derive methods for computing expressions with minimum number of operations but such a method is not guaranteed to be numerically stable. Thus, analysis of the numerical stability of the derived algorithm is necessary before advocating its use.

Numerical stability of algorithms for real and complex matrix multiplication are discussed in [7,8,15]. Miller [15] analyzes the tradeoff between computational complexity and numerical stability. He defines the notion of Strong stability and Brent stability, which is a much weaker requirement with Strong stability implying Brent stability. For a thorough discussion of these notions, see [15]. It is shown that any algorithm for matrix multiplication that possesses Strong stability should have at least n³ multiplications and that the Strassen's method possesses Brent stability.

Applying a similar analysis to the new Croos Product method discovered by the Search program, we found that eight multiplications are necessary for Strong stability and that the method discovered by the Search program possesses Brent stability. A similar result is true for the complex multiplication methods.