Efficient Matrix Chain Ordering in Polylog Time

DOI10.1137/S0097539794270698MaRDI QIDQ4388882zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Phillip G. Bradford, Gregory J. E. Rawlins, Gregory E. Shannon

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539794270698

zbMATH Keywords

dynamic programmingmatrix chain orderingoptimizationparallel

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Parallel numerical computation (65Y05) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• scientific article; zbMATH DE number 512836
• An optimal parallel algorithm for computing a near-optimal order of matrix multiplications
• An Efficient Parallel Algorithm for the Matrix-Chain-Product Problem
• Very Fast Approximation of the Matrix Chain Product Problem

Cited in

(10)

• On efficient parallel computations for some dynamic programming problems
• Greedy algorithms for optimal computing of matrix chain products involving square dense and triangular matrices
• Sequential optimization of matrix chain multiplication relative to different cost functions
• Computation of Matrix Chain Products. Part II
• scientific article; zbMATH DE number 4126588 (Why is no real title available?)
• scientific article; zbMATH DE number 512836 (Why is no real title available?)
• COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE
• Very Fast Approximation of the Matrix Chain Product Problem
• Lower bounds for the matrix chain ordering problem (extended abstract)
• Revisiting ``Computation of matrix chain products

This page was built for publication: Efficient Matrix Chain Ordering in Polylog Time

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