The BLAS3 (Level 3 Basic Linear Algebra Subprograms) is a set of specifications, based on matrix-matrix operations, for efficient and portable routines to be used on high-performance computers. This interesting and clearly written paper explores the possibility of enhancing the performance of the BLAS3 routines using variants of Strassen’s algorithm for matrix multiplication.

Much of the paper surveys previous work on the Strassen algorithm. The algorithm, which was the first published scheme that broke the O(n²) operations barrier for multiplying n×n matrices, is still considered by many to be of theoretical interest only. The author shows, however, as others have shown, that it is of practical importance for n greater than about 100.

Higham gives a lucid description of the basic algorithms in terms of a product of rectangular matrices. He then presents Strassen-based recursive algorithms for the other BLAS3 basic operations: rank-r and rank-2r updates of a real symmetric matrix; multiplication of a matrix by a triangular matrix; and solving a triangular system of equations with multiple right-hand sides.

Because of their recursive nature, there is concern for the stability of these algorithms. The author presents a detailed error analysis, obtaining essentially the same result as that of Brendt [1]. Numerical experiments were conducted to verify the error bounds. Unlike the conventional BLAS3 routines, the so-called “fast” BLAS3 routines do not satisfy strong component-wise bounds for the residuals. They do satisfy similar norm-wise bounds, but with somewhat larger constant terms. No timing runs were made to confirm the analytical results.

The tradeoff between accuracy and efficiency remains unclear, but the author’s results are sufficiently encouraging to warrant further study. The paper should interest anyone working on algorithms that involve, or could involve, matrix products.