English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

For a given product of $n$ matrices, the matrix chain multiplication problemasks for a parenthesisation that minimises the number of arithmetic operations.In 1973, Godbole presented a now classical dynamic programming formulation withcubic time complexity on the length of the chain. The best known algorithms runin linearithmic time, and the best known approximation algorithms run in lineartime with an approximation factor smaller than two. All solutions have incommon that they select an optimal parenthesisation from a set of $C_{n-1}$(Catalan number $n - 1$) distinct parenthesisations. We studied the set ofparenthesisations and discovered (a) that all of the exponentially manyparenthesisations are useful in the sense that they are optimal in an infinitesubset of the input space, (b) that only $n + 1$ parenthesisations areessential in the sense that they are arbitrarily better than the second best onan infinite subset of the input space, and (c) that the best essentialparenthesisation is never more than twice as costly as the best non-essentialparenthesisation. Through random sampling of the input space, we furtherdiscovered that the set of essential parenthesisations includes an optimalparenthesisation in the vast majority of inputs, and that the best essentialparenthesisation is on average much closer to optimal than the worst-casebound. The results have direct consequences for the development of compilersfor linear algebra expressions where the matrix sizes are unknown atcompile-time.

The Essential Algorithms for the Matrix Chain