/optimal-matrix-chain

Implementation of O(n log n) algorithm for matrix chain ordering in Python

Primary LanguageHTML

Optimal Matrix Chain Ordering Algorithm

This repository implements the $O(n \log n)$ algorithm for optimal ordering of a matrix chain first developed by Hu and Shing, with heavy use of Ramanan's simpler exposition of the same algorithm.

Compared to the dynamic programming algorithm used by numpy and most other libraries, which is $O(n^3)$, this algorithm is significantly faster.

Sources

Hu and Shing's work:

Ramanan's work:

DOI link