The Matrix Chain Algorithm to Compile Linear Algebra Expressions

Henrik Barthels, Paolo Bientinesi

The matrix chain problem consists in finding the parenthesization of a matrix product $M:=A_1{A}_2\cdots A_n$ that minimizes the number of scalar operations. In practical applica…