On the parenthesisations of matrix chains: All are useful, few are essential

Francisco López (), Lars Karlsson () and Paolo Bientinesi ()
Additional contact information
Francisco López: Umeå Universitet
Lars Karlsson: Umeå Universitet
Paolo Bientinesi: Umeå Universitet

Journal of Combinatorial Optimization, 2025, vol. 49, issue 3, No 17, 18 pages

Abstract: Abstract The product of a matrix chain consisting of n matrices can be computed in $$C_{n-1}$$ C n - 1 (Catalan’s number) different ways, each identified by a distinct parenthesisation of the chain. The best algorithm to select a parenthesisation that minimises the cost runs in $$O(n \log n)$$ O ( n log n ) time. Approximate algorithms run in O(n) time and find solutions that are guaranteed to be within a certain factor from optimal; the best factor is currently 1.155. In this article, we first prove two results that characterise different parenthesisations, and then use those results to improve on the best known approximation algorithms. Specifically, we show that (a) each parenthesisation is optimal somewhere in the problem domain, and (b) exactly $$n + 1$$ n + 1 parenthesisations are essential in the sense that the removal of any one of them causes an unbounded penalty for an infinite number of problem instances. By focusing on essential parenthesisations, we improve on the best known approximation algorithm and show that the approximation factor is at most 1.143.

Keywords: Matrix multiplication; Matrix chain; Approximation algorithm; Linear algebra compilers; 68N20; 68Q25; 68W25 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01290-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:3:d:10.1007_s10878-025-01290-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01290-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().