Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the parenthesisations of matrix chains: all are useful, few are essential
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4675-7434
Umeå University, Faculty of Science and Technology, Department of Computing Science.ORCID iD: 0000-0002-4972-7097
2025 (English)In: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 49, no 3, article id 52Article in journal (Refereed) Published
Abstract [en]

The product of a matrix chain consisting of n matrices can be computed in Cn-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(nlogn) 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.

Place, publisher, year, edition, pages
Springer Nature, 2025. Vol. 49, no 3, article id 52
Keywords [en]
Approximation algorithm, Linear algebra compilers, Matrix chain, Matrix multiplication
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:umu:diva-238200DOI: 10.1007/s10878-025-01290-7ISI: 001466493300002Scopus ID: 2-s2.0-105002887010OAI: oai:DiVA.org:umu-238200DiVA, id: diva2:1956464
Funder
eSSENCE - An eScience CollaborationAvailable from: 2025-05-06 Created: 2025-05-06 Last updated: 2025-05-06Bibliographically approved

Open Access in DiVA

fulltext(381 kB)7 downloads
File information
File name FULLTEXT01.pdfFile size 381 kBChecksum SHA-512
ca5f78de7e09df014ebc17e55082cc91162a47f28ab1b25e1673f3b69fd8daf79869691db344df292641606daf5820380ffce8cba6147261ace9688173d1b3ac
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

López Sánchez, FranciscoKarlsson, LarsBientinesi, Paolo

Search in DiVA

By author/editor
López Sánchez, FranciscoKarlsson, LarsBientinesi, Paolo
By organisation
Department of Computing Science
In the same journal
Journal of combinatorial optimization
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 8 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 100 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf