790 Advanced

790-matrix-chain-multiplication — Matrix Chain Multiplication

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "790-matrix-chain-multiplication — Matrix Chain Multiplication" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. The matrix chain multiplication problem asks: in what order should a sequence of matrices be multiplied to minimize the total number of scalar multiplications? Key difference from OCaml: 1. **Interval DP pattern**: Both languages use the same outer

Tutorial

The Problem

The matrix chain multiplication problem asks: in what order should a sequence of matrices be multiplied to minimize the total number of scalar multiplications? Different association orders can differ by orders of magnitude: (A × B) × C might cost 1000 operations while A × (B × C) costs 100. The O(n³) DP solution, from Godbole (1973), is a textbook example of interval DP and is used in query optimization in databases (join reordering) and deep learning compilers (operation fusion).

🎯 Learning Outcomes

• Model matrix chain as dims: &[usize] where dims[i] × dims[i+1] is the size of matrix i

• Fill a 2D DP table where dp[i][j] = min cost to multiply matrices i through j

• Understand interval DP: building solutions to larger intervals from smaller ones

• Implement the split-point recurrence: try all k in i..j as split points

• Use the optimal ordering for actual computation (requires parenthesization reconstruction)

Code Example

#![allow(clippy::all)]
//! # Matrix Chain Multiplication

pub fn matrix_chain(dims: &[usize]) -> usize {
    let n = dims.len() - 1;
    if n <= 1 {
        return 0;
    }
    let mut dp = vec![vec![0; n]; n];
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = usize::MAX;
            for k in i..j {
                let cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = dp[i][j].min(cost);
            }
        }
    }
    dp[0][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_matrix_chain() {
        assert_eq!(matrix_chain(&[10, 20, 30, 40, 30]), 30000);
    }
    #[test]
    fn test_two() {
        assert_eq!(matrix_chain(&[10, 20, 30]), 6000);
    }
}

(* Matrix Chain Multiplication — top-down memoised DP
   dims.(i) = rows of matrix i, dims.(i+1) = cols of matrix i
   e.g., for 3 matrices: dims = [|p0; p1; p2; p3|] *)

let matrix_chain dims =
  let n = Array.length dims - 1 in
  (* dp.(i).(j) = min cost to multiply matrices i..j (0-indexed) *)
  let dp    = Array.make_matrix n n 0 in
  let split = Array.make_matrix n n 0 in
  (* chain length l from 2 to n *)
  for l = 2 to n do
    for i = 0 to n - l do
      let j = i + l - 1 in
      dp.(i).(j) <- max_int;
      for k = i to j - 1 do
        let cost = dp.(i).(k) + dp.(k+1).(j)
                   + dims.(i) * dims.(k+1) * dims.(j+1) in
        if cost < dp.(i).(j) then begin
          dp.(i).(j)    <- cost;
          split.(i).(j) <- k
        end
      done
    done
  done;
  (dp.(0).(n-1), split)

(* Reconstruct optimal parenthesization as a string *)
let rec parenthesize split i j =
  if i = j then
    Printf.sprintf "M%d" (i + 1)
  else
    let k = split.(i).(j) in
    Printf.sprintf "(%s × %s)"
      (parenthesize split i k)
      (parenthesize split (k+1) j)

let () =
  (* Example: 4 matrices with dims 30×35, 35×15, 15×5, 5×10 *)
  let dims = [| 30; 35; 15; 5; 10; 20; 25 |] in
  let n    = Array.length dims - 1 in
  Printf.printf "Number of matrices: %d\n" n;
  let (cost, split) = matrix_chain dims in
  Printf.printf "Minimum multiplications: %d\n" cost;
  Printf.printf "Optimal order: %s\n" (parenthesize split 0 (n-1));

  (* Small example *)
  let dims2  = [| 10; 30; 5; 60 |] in
  let (c2, s2) = matrix_chain dims2 in
  Printf.printf "\n3-matrix example (10×30, 30×5, 5×60):\n";
  Printf.printf "Min cost: %d, Order: %s\n" c2 (parenthesize s2 0 2)

Key Differences

Interval DP pattern: Both languages use the same outer-loop-over-length approach to ensure subproblem ordering; the code structure is nearly identical.

Initialization: Rust uses dp[i][j] = usize::MAX as infinity; OCaml uses max_int — same concept.

Real-world: Database query optimizers use the same interval DP for join ordering; Rust-based databases like TiKV use this internally.

Space: O(n²) space is required; no known space-efficient algorithm exists for this problem.

OCaml Approach

OCaml implements interval DP with Array.make_matrix n n 0 and nested for loops. The outer loop is over chain length, not indices directly, to ensure smaller subproblems are solved before larger ones. OCaml's min function and imperative array updates make this direct. The reconstruction uses a separate split: int array array table storing optimal split points.

Full Source

#![allow(clippy::all)]
//! # Matrix Chain Multiplication

pub fn matrix_chain(dims: &[usize]) -> usize {
    let n = dims.len() - 1;
    if n <= 1 {
        return 0;
    }
    let mut dp = vec![vec![0; n]; n];
    for len in 2..=n {
        for i in 0..=n - len {
            let j = i + len - 1;
            dp[i][j] = usize::MAX;
            for k in i..j {
                let cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
                dp[i][j] = dp[i][j].min(cost);
            }
        }
    }
    dp[0][n - 1]
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_matrix_chain() {
        assert_eq!(matrix_chain(&[10, 20, 30, 40, 30]), 30000);
    }
    #[test]
    fn test_two() {
        assert_eq!(matrix_chain(&[10, 20, 30]), 6000);
    }
}

(* Matrix Chain Multiplication — top-down memoised DP
   dims.(i) = rows of matrix i, dims.(i+1) = cols of matrix i
   e.g., for 3 matrices: dims = [|p0; p1; p2; p3|] *)

let matrix_chain dims =
  let n = Array.length dims - 1 in
  (* dp.(i).(j) = min cost to multiply matrices i..j (0-indexed) *)
  let dp    = Array.make_matrix n n 0 in
  let split = Array.make_matrix n n 0 in
  (* chain length l from 2 to n *)
  for l = 2 to n do
    for i = 0 to n - l do
      let j = i + l - 1 in
      dp.(i).(j) <- max_int;
      for k = i to j - 1 do
        let cost = dp.(i).(k) + dp.(k+1).(j)
                   + dims.(i) * dims.(k+1) * dims.(j+1) in
        if cost < dp.(i).(j) then begin
          dp.(i).(j)    <- cost;
          split.(i).(j) <- k
        end
      done
    done
  done;
  (dp.(0).(n-1), split)

(* Reconstruct optimal parenthesization as a string *)
let rec parenthesize split i j =
  if i = j then
    Printf.sprintf "M%d" (i + 1)
  else
    let k = split.(i).(j) in
    Printf.sprintf "(%s × %s)"
      (parenthesize split i k)
      (parenthesize split (k+1) j)

let () =
  (* Example: 4 matrices with dims 30×35, 35×15, 15×5, 5×10 *)
  let dims = [| 30; 35; 15; 5; 10; 20; 25 |] in
  let n    = Array.length dims - 1 in
  Printf.printf "Number of matrices: %d\n" n;
  let (cost, split) = matrix_chain dims in
  Printf.printf "Minimum multiplications: %d\n" cost;
  Printf.printf "Optimal order: %s\n" (parenthesize split 0 (n-1));

  (* Small example *)
  let dims2  = [| 10; 30; 5; 60 |] in
  let (c2, s2) = matrix_chain dims2 in
  Printf.printf "\n3-matrix example (10×30, 30×5, 5×60):\n";
  Printf.printf "Min cost: %d, Order: %s\n" c2 (parenthesize s2 0 2)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_matrix_chain() {
        assert_eq!(matrix_chain(&[10, 20, 30, 40, 30]), 30000);
    }
    #[test]
    fn test_two() {
        assert_eq!(matrix_chain(&[10, 20, 30]), 6000);
    }
}

Deep Comparison

OCaml vs Rust: Matrix Chain Multiplication

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Add a matrix_chain_order(dims) function that returns the optimal parenthesization as a string like "((A(BC))D)".

Implement the memoized top-down version and verify it produces the same results as the bottom-up tabulation.

Apply matrix chain optimization to a sequence of 10 randomly-sized matrices and measure how much the optimal ordering reduces the operation count vs. left-to-right.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust