SUNY Geneseo Department of Computer Science

Matrix Chain Multiplication

Return to List of Lectures

Questions?

Matrix Chain Multiplication

Section 15.2

Try it

• 10-by-4  times  4-by-8  times  8-by-20  times  20-by-6

• Two ways of grouping these for multiplication

• Purpose of the algorithm is to find the fewest number of multiplications needed and an order that achieves it

Reading technical material

• Introductions
  • “Does this make sense?”
  • “Where is this going?”
• Body
  • “What does this (paragraph, sentence, term) mean?”
  • “Does this make sense?”
  • “Can I think of an example?”
  • “Where is this going?”

Key ideas

• Trivial (one-element) chains are single matrices, and so require no multiplications at all
• Non-trivial chain from position i to j (A_i..j) must be multiplied as two sub-chains, split at some position k

• Loops in final algorithm correspond to stepping through possible chain lengths, possible starting points for chains of those lengths, and possible splitting points within each chain

Next

Longest common subsequences

Section 15.4