Randomization of approximate bilinear computation for matrix multiplication

ABSTRACT

We present a method for randomizing formulas for bilinear computation of matrix products which does not increase the leading order complexity of the computation. We consider the implications of such randomization when there are two sources of error. The first source is due to the computation formula itself only being approximately correct. Such formulas come up when numerically searching for faster matrix multiplication algorithms. The second source is due to using floating point arithmetic. This kind of error is especially important when computing on low precision hardware like GPUs. Our theoretical results and numerical experiments indicate that our method can improve performance when the two kinds of error are present individually, as well as when they are present at the same time.

Keywords:

• Randomized algorithms
• approximate algorithms
• matrix multiplication
• Strassen's algorithm

2010 Mathematics Subject Classifications:

• 15-02
• 65F30

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant No. ECCS-1810314.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 We present results for square matrices, but we believe the results can be extended to rectangular matrices.

2 There appears to be a few typos in the definition of $w_r^{\left(s\right)}$ in Equation (5.2) in [3], which defines the APA scheme. We encourage the reader to consult our code for a corrected definition.

Additional information

Funding

This material is based upon work supported by the National Science Foundation under Grant No. ECCS-1810314.