Fast matrix multiplication is stable

Abstract: We perform forward error analysis for a large class of recursive matrix multiplication algorithms in the spirit of [D. Bini and G. Lotti, Stability of fast algorithms for matrix multiplication, Numer. Math. 36 (1980), 63--72]. As a consequence of our analysis, we show that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms. We also show that new group-theoretic algorithms proposed in [H. Cohn, and C. Umans, A group-theoretic approach to fast matrix multiplication, FOCS 2003, 438--449] and [H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic algorithms for matrix multiplication, FOCS 2005, 379--388] are all included in the class of algorithms to which our analysis applies, and are therefore numerically stable. We perform detailed error analysis for three specific fast group-theoretic algorithms.

Review text

This paper gives the proof that a wide class of matrix multiplication algorithms are stable. A forward error analysis of recursive matrix multiplication algorithms is performed. In detail, algorithms with stationary partition, non stationary partition and those that combine partitioning with pre- and post-processing are investigated. The class of group-theoretic recursive algorithms -- Abelian simultaneous triple product (Abelian STP) algorithms -- are extensively introduced with the necessary theory, examples that are helpful illustrations of the theory, and a running example algorithm. The group-theoretic algorithms proposed by \textit{H. Cohn} and \textit{C. Umans} [A group-theoretic approach to matrix multiplication. In: Foundations of Computer Science. 44th annual IEEE Symposium, 438--449 (2003)] and \textit{H. Cohn, R. Kleinberg, B. Szegedy} and \textit{C. Umans} [Group theoretic algorithms for matrix multiplication. In: Foundations of Computer Science. 46th annual IEEE Symposium, 23--25 October 2005, 379--388 (2005)] are included in the investigated class. As a consequence of the given analysis it is shown that the exponent of matrix multiplication (the optimal running time) can be achieved by numerically stable algorithms.

Recommendations

Cites work

Cited in

(23)

Describes a project that uses

Uses Software

This page was built for publication: Fast matrix multiplication is stable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q879926)