Class 33: Intro to Memoization & Matrix Chain Multiplication

Reading

Sections 15.2 of Introduction to Algorithms. Read notes below, too!

Homework

Compute the product:

  .-       -.   .-    -.   
  | 2 -1  1 |   | 2  0 |   .-    -.
  |         |   |      |   | 2  3 |
  | 0  5 -1 | * | 1 -1 | * |      |
  |         |   |      |   | 1 -2 |
  | -1 3 -2 |   | 3  5 |   `-    -'
  `-       -'   `-    -'

Suppose A1, A2, A3 and A4 are matrices of dimensions 4x6, 6x3, 3x10, and 10x2 respectively. What parenthesization yields the fewest multiplications of numbers in computing the matrix product A1*A2*A3*A4? [Hint: Look at the notes below to see how one determines how many multiplications of numbers is required in computing the product of two matrices. Now try all parenthesizations of A1*A2*A3*A4 and see which yields the fewest multiplications.]

Intro to memoization

Consider our old friend, the simple recursive fibanocci function:

(define (f n)
  (if (< n 2)
      1
      (+ (f (- n 1)) (f (- n 2)))))

This function works, it's just really slow. In fact, computing (f 40) is almost prohibitive. Why? Is computing fibanocci numbers really that hard? No! This algorithm is so slow because it computes the same results over and over again. Below you see the "recursion tree" for this program, which simply depicts each fuction call that gets made in computing f(6).

You can see just how many times something like f(2) or even f(3) gets computed by this program. Computing the same thing over and over again is a waste. In this case it's a colossal waste. There's one easy way out of the problem. The first time f(k) is computed, for some k, the value is stored in some table. Next time you need to compute f(k), just look the answer up in the table! that way, each f(k) is computed only once. The program:

(define (f n)
  (if (= (vector-ref T n) -1)
      (vector-set! T n (if (< n 2)
                           1
                           (+ (f (- n 1)) (f (- n 2))))))
  (vector-ref T n))
      
(define T 0)

(define (f-memo n)
  (set! T (make-vector (+ n 1) -1))
  (f n))

... implements this idea. The resulting recursion tree looks like this:

This technique is called memoization. As you can see, a lot of computation is saved. for larger values of n, an ever increasing proportion of the computation is avoided. In fact, the original program runs in exponential time, while the memoized version is Θ(n). Run the two programs, and see how big a difference there is in compuation time for n = 30.

The Matrix Chain Multiplication Problem

Section 15.2 of the text book discusses this problem. Read the intro and "Step1" and "Step2".

Given an array A of matrices, and a range i..j of indices in the array, what is the parenthesization of

A_i A_i+1 ... A_j

that computes the matrix product using the fewest multiplications? (I.e. multiplications of values in the matrices.)

This is called the matrix chain multiplication problem, and it's kind of a tough one. When we're face with a difficult problem the best approach is often to first solve a simplified version of the problem, and then ask how that solution can be augmented to solve the full original problem. The simplified problem we're going to consider is simply to figure out what the fewest multiplications required to compute the matrix product is. We'll call this fmm(A,i,j).

Review: Multiplying Matrices

The dimension of a matrix is the number of rows and the number of columns. So a 5x7 matrix would have 5 rows and 7 columns. When we take the product of two matrices the number of columns in the left-hand matrix must equal the number of rows in the right hand. This is because, as you will recall, we compute element i,j of the produce by multiplying each element of ith row of the left-hand matrix by the associated element of the jth column of the right-hand matrix, and summing all the results. Thus, there better be the same number of elements in the rows of the left-hand matrix as in columns of the right-hand matrix.

The product of an rxc matrix and a r'xc' matrix (remember c=r') is a rxc' matrix. Computing each of the r*c' entries of this matrix requires c multiplications, so the total number of multiplications involved is r*c*c'.

| 4 -1 |                 | 4*-1 + -1*0   4*-1 + -1*2   4*3 + -1*1 |
|      |   |-1 -1  3 |   |                                        |
|-2  0 | x |         | = |-2*-1 +  0*0  -2*-1 +  0*2  -2*3 +  0*1 | 
|      |   | 0  2  1 |   |                                        |
| 2 -1 |                 | 2*-1 + -1*0   2*-1 + -1*2   2*3 + -1*1 |

                         | -4  -6  11 |
                         |            |
                       = |  2   2  -6 |
                         |            |
                         | -2  -4   5 |

See? Two multiplications for every element in the 3x3 product matrix.

If you have a chain of matrices to multiply together the number of columns in one matrix needs to equal the number of rows in the following matrix for the product to even make sense. As long as that is satisfied, you can compute the product. However, products are computed pairwise - i.e. two matrices at a time. Thus, you have to completely parenthisize the chain of matrices in order to really describe how you'll compute the product. The interesting thing is this: The way you do the parenthesization does not affect the answer, but it can have a dramatic effect on the number of multiplications performed in computing the answer.

Example:  Compute A0 x A1 x A3 where:  A0    A1   A2
                                      10x2  2x8  8x3

Parenthesization 1: / A0    A1 \  / A2 \
                    | 10x2  2x8 | | 8x3 | 
                    \          /  \    /
                    10*2*8 = 160
                    mults,
                    \__________/
                       10x8
                    Takes 10*8*3=240 mults for 10x3 reslult

                    Total is 400 multiplications


Parenthesization 2: / A0  \  / A1   A2 \
                    | 10x2 | | 2x8  8x3 | 
                    \      / \         /
                               2*8*3=48
                               mults,
                             \__________/
                                2x3
                    Takes 10*2*3=60 mults for 10x3 reslult

                    Total is 108 multiplications

So, where you put the parenthesese really matters. That's why we're trying to figure out where the best place is to put 'em.

Christopher W Brown

Last modified: Fri Mar 25 08:43:07 EST 2005