Fast matrix multiplication is stable (Q879926): Difference between revisions

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.