On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential

Francisco López, Lars Karlsson, Paolo Bientinesi

The product of a matrix chain consisting of $n$ matrices can be computed in $C_{n-1}$ (Catalan's number) different ways, each identified by a distinct parenthesisation of the chain…