Multiplikationsketten

Bei einem Matrixprodukt mit mehreren Faktoren kann man durch geeignete Klammerung Zeit sparen.

A_3×2B_2×8C_8×4D_4×1

Annahme: Zeit für A_x×yB_y×z ist $\approx$ xyz.

Was kostet (z. B.) (AB)(CD)?

geeignete Klammerung bestimmt man durch dynamische Optimierung:

c(i, j) : = beste Kosten für A_i ^. ... ^. A_j

A_i hat Abmessung d_i-1×d_i

c(i, i) = 0

c(i, k) = min{c(i, j) + c(j + 1, k) + d_i-1d_jd_k | i$\le$j < k}