concept · INFO-CS-ADS-180Matrix 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
| Name | Dimensions |
|---|
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.
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.
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