On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909567589285888 |
|---|---|
| author | López, Francisco Karlsson, Lars Bientinesi, Paolo |
| author_facet | López, Francisco Karlsson, Lars Bientinesi, Paolo |
| contents | 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. The best algorithm to select a parenthesisation that minimises the cost runs in $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$ 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_17352 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential López, Francisco Karlsson, Lars Bientinesi, Paolo Discrete Mathematics 68N20, 68Q25, 68W25 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. The best algorithm to select a parenthesisation that minimises the cost runs in $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$ 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$. |
| title | On the Parenthesisations of Matrix Chains: All are Useful, Few Are Essential |
| topic | Discrete Mathematics 68N20, 68Q25, 68W25 |
| url | https://arxiv.org/abs/2303.17352 |