Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the parenthesisations of matrix chains: all are useful, few are essential
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4675-7434
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.ORCID-id: 0000-0002-4972-7097
2025 (Engelska)Ingår i: Journal of combinatorial optimization, ISSN 1382-6905, E-ISSN 1573-2886, Vol. 49, nr 3, artikel-id 52Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Springer Nature, 2025. Vol. 49, nr 3, artikel-id 52
Nyckelord [en]
Approximation algorithm, Linear algebra compilers, Matrix chain, Matrix multiplication
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
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
Forskningsfinansiär
eSSENCE - An eScience CollaborationTillgänglig från: 2025-05-06 Skapad: 2025-05-06 Senast uppdaterad: 2025-05-06Bibliografiskt granskad

Open Access i DiVA

fulltext(381 kB)46 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 381 kBChecksumma SHA-512
ca5f78de7e09df014ebc17e55082cc91162a47f28ab1b25e1673f3b69fd8daf79869691db344df292641606daf5820380ffce8cba6147261ace9688173d1b3ac
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

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

Sök vidare i DiVA

Av författaren/redaktören
López Sánchez, FranciscoKarlsson, LarsBientinesi, Paolo
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
Journal of combinatorial optimization
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 47 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 344 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf