An O(n) algorithm for determining a near-optimal computation order of matrix chain products

DOI10.1145/359545.359556MaRDI QIDQ4156871zbMATH OpenOpenAlexFDO

Authors Francis Y. L. Chin

Publication date 1978

Published in Communications of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/359545.359556

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to linear algebra (15-04) Matrix equations and identities (15A24) Algorithms in computer science (68W99)

Cited in

(5)

• Dynamic programming and graph optimization problems
• Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
• An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
• Lower bounds for the matrix chain ordering problem (extended abstract)
• On the parenthesisations of matrix chains: all are useful, few are essential

This page was built for publication: An O(n) algorithm for determining a near-optimal computation order of matrix chain products

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