File MatrixChain.h

↰ Parent directory (ADS/numeric)

The multiplication of a chain of matrices of section 13.3: A_i of size c[ i ] x c[ i + 1 ], 0 <= i < n, and the order of the products with the fewest scalar multiplications.

Definition (ADS/numeric/MatrixChain.h)

Detailed Description

The number of parenthesizations is the Catalan number :math:` F( n ) = Omega( 4^n / n^{3/2} ) `, but :math:`[

DP[ i ][ j ] = min_{i leq k < j} { DP[ i ][ k ] + DP[ k + 1 ][ j ] + c[ i ] c[ k + 1 ] c[ j + 1 ] } , qquad DP[ i ][ i ] = 0 ,

` filled by increasing length h = j - i + 1 in O( n^3 ) time, with S[ i ][ j ] the best k, from which stampaPar() writes the parenthesization in O( n ).

The contracts [see File Contract.h]: the vector of the sizes c_0 , … , c_n has n + 1 >= 1 positive items, and the parenthesization needs i <= j < n. The functions are defined in MatrixChain.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 13.3, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

    1. Hu, M. T. Shing, Computation of matrix chain products, part I, SIAM Journal on Computing 11(2), 362-373, 1982, doi:10.1137/0211028

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions