✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-180

Matrix Chain Multiplication

Learn how dynamic programming determines the most efficient parenthesization of a matrix multiplication chain by minimizing the number of scalar multiplications.

Explanation

Overview

Matrix Chain Multiplication is an optimization problem involving a sequence of matrices. Matrix multiplication is associative, so different parenthesizations produce the same final mathematical result but can require very different numbers of scalar multiplications.

Key concepts

Matrix dimensions; Associativity; Interval dynamic programming; Optimal split point; Cost minimization

Variables

p: The dimension array describing the matrices.; A_i: The i-th matrix, with dimensions p[i-1] × p[i].; i: The starting matrix index of a chain.; j: The ending matrix index of a chain.; k: A possible position at which to split the chain.; dp[i][j]: The minimum scalar multiplication count for matrices i through j.

Complexity

tabulation: O(n^3) time and O(n^2) space.; variables: n is the number of matrices.

Example

matrices: name: A1; dimensions: 10 × 30; name: A2; dimensions: 30 × 5; optimalParenthesization: (A1 × A2) × A3; scalarMultiplications: 4500; explanation: Multiplying A1 by A2 first costs 10 × 30 × 5 = 1500 operations. Multiplying the resulting 10 × 5 matrix by A3 costs 10 × 5 × 60 = 3000 more, giving 4500 total.

Pseudocode

function matrixChain(p, n):
dp = 2D array of size n × n filled with 0
for length = 2 to n:
for i = 1 to n - length + 1:
j = i + length - 1
dp[i][j] = infinity
for k = i to j - 1:
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
dp[i][j] = min(dp[i][j], cost)
return dp[1][n]

Applications

Numerical computing.; Database query optimization.; Scientific computing.; Compiler optimization.; Linear algebra software.

Variables

P

The dimension array describing the matrices.

A i

The i-th matrix, with dimensions p[i-1] × p[i].

I

The starting matrix index of a chain.

J

The ending matrix index of a chain.

K

A possible position at which to split the chain.

Dp[i][j]

The minimum scalar multiplication count for matrices i through j.

Example or application

Matrices

NameDimensions

A1

10 × 30

A2

30 × 5

A3

5 × 60

Optimal Parenthesization

(A1 × A2) × A3

Scalar Multiplications

4500

Explanation

Multiplying A1 by A2 first costs 10 × 30 × 5 = 1500 operations. Multiplying the resulting 10 × 5 matrix by A3 costs 10 × 5 × 60 = 3000 more, giving 4500 total.

Definition

Matrix Chain Multiplication is an optimization problem involving a sequence of matrices. Matrix multiplication is associative, so different parenthesizations produce the same final mathematical result but can require very different numbers of scalar multiplications.

Mathematical Representation

dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1] × p[k] × p[j]) for i <= k < j.

Approaches

Interval Dynamic Programming

Solves shorter matrix chains before considering longer chains.

Memoization

Stores the minimum multiplication cost for each matrix interval.

Tabulation

Fills the dynamic programming table in increasing order of chain length.

Reconstruction

Stores the best split point for each interval to recover the optimal parenthesization.

Pseudocode

function matrixChain(p, n):
dp = 2D array of size n × n filled with 0
for length = 2 to n:
for i = 1 to n - length + 1:
j = i + length - 1
dp[i][j] = infinity
for k = i to j - 1:
cost = dp[i][k] + dp[k + 1][j] + p[i - 1] * p[k] * p[j]
dp[i][j] = min(dp[i][j], cost)
return dp[1][n]

Complexity

Tabulation

O(n^3) time and O(n^2) space.

Variables

n is the number of matrices.

Key Concepts

  • Matrix dimensions

  • Associativity

  • Interval dynamic programming

  • Optimal split point

  • Cost minimization

Advantages

  • Finds a multiplication order with minimum scalar multiplication cost.

  • Avoids evaluating every possible parenthesization independently.

  • Demonstrates interval-based dynamic programming.

  • Can reconstruct the optimal multiplication order.

Limitations

  • The standard algorithm requires O(n^3) time.

  • It minimizes scalar multiplication count rather than every possible real-world execution cost.

  • All matrix dimensions must be compatible for the chain multiplication to be valid.

Applications

  • Numerical computing.

  • Database query optimization.

  • Scientific computing.

  • Compiler optimization.

  • Linear algebra software.

Related Topics

  • Dynamic Programming

  • Optimal Substructure

  • Interval DP

  • Matrix Multiplication

Practice Question

Why can different parenthesizations of a matrix chain have different computational costs?

Practice Answer

Intermediate matrix dimensions change with the multiplication order, affecting the number of scalar multiplications.

Learning Objectives

  • Explain the central idea and purpose of matrix chain multiplication.

  • Identify the assumptions, inputs, and conditions relevant to matrix chain multiplication.

  • Evaluate an application of matrix chain multiplication for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Dynamic Programming Applications

Suggest a correction or source · More in Algorithms & Data Structures