t = fmm(A,i,k)
+ fmm(k+1,j)
+ rows(Ai)*cols(Ak)*cols(Aj);
... where i ≤ k < j.
That corresponds to needing table entries
T[i,i], T[i,i+1], ..., T[i,j-1] T[i+1,j], T[i+2,j], ..., T[j,j]If you look at the diagonal (I mean upper-left to lower-right) on which T[i,j] lies, you'll see that all the table entries we need lie below that diagonal. So, we'll fill in our table from the "0th diagonal", i.e. the one that runs from the upper-left corner to the lower right corner, followed by the 1st diagonal, i.e. the one just above the 0th, and continuing until the (n-1)st diagonal, which consists solely of the upper right cell in the table.
So we'll fill in our table entries a diagonal at a time, starting from diagonal d=0 and progressing to diagonal d=n-1. Each diagonal gets filled in from top (i.e. row i=0) to bottom (i.e. row i=n-1-d). We like to think of table entries as row i and column j, not diagonal d and row i, so it'd be nice if we could figure out j from d and i. The row i entry on diagonal 0 is clearly T[i,i]. The row i entry on diagonal 1 is clearly T[i,i+1]. Follow the pattern and we see that the row i entry on diagonal d is j=i+d.
This table shows the entries required to fill in T[i,j]. Notice that they all all below the diagonal on which i,j falls.
Now, once we decide on a table entry T[i,j] to fill in, how do we come up with a value? We just use the original fmm exactly as always, except that the recursive calls are replace with table look-ups, since we know the values we need are already in the table. Below you'll see the dynamic programming solution to this problem, along with the memoized and original algortithms. Pay attention to how both the memoized and the dynamic programming versions of fmm simply wrap the original fmm algorithm in some code that manipulates tables.
| Original Recursive Algorithm | Memoized Version | Dynamic Programming Version |
int fmm(A,i,j)
{
int m = -1;
if (i == j)
m = 0;
else
{
for(int k = i; k < j; ++k)
{
t = fmm(A,i,k) + fmm(A,k+1,j)
+ rows(Ai)*cols(Ak)*cols(Aj);
if (m == -1 || t < m)
m = t;
}
}
return m;
} |
int fmm(A,i,j)
{
if (T[i,j] == -1)
{
int m = -1;
if (i == j)
m = 0;
else
{
for(int k = i; k < j; ++k)
{
t = fmm(A,i,k) + fmm(A,k+1,j)
+ rows(Ai)*cols(Ak)*cols(Aj);
if (m == -1 || t < m)
m = t;
}
}
T[i,j] = m;
}
return T[i,j];
} |
int fmm-dynamic(A,n)
{
T = nxn table, all values initialized to -1
for(d = 0; d < n; d++)
{
for(i = 0; i < n - d; i++)
{
j = d + i;
int m = -1;
if (i == j)
m = 0;
else
{
for(int k = i; k < j; ++k)
{
t = T[i,k] + T[k+1,j]
+ rows(Ai)*cols(Ak)*cols(Aj);
if (m == -1 || t < m)
m = t;
}
}
T[i,j] = m;
}
}
}
|
| Notice how the original fmm code (i.e. the code in blue) pops up in both the memoized and dynamic progrmmming versions. | ||
bestK[i,j] = the "k" value that produces the fewest multiplications when computing the product Ai..Aj.The file mcm-sol.scm implements this in scheme. Here's a sample run for 5 random matrices:
> (mcm-sol (random-mcm-problem 5 10)) 160 > (table-print bestK) -1 0 0 2 2 -1 -1 1 2 2 -1 -1 -1 2 2 -1 -1 -1 -1 3 -1 -1 -1 -1 -1 >Using bestK, we can recover the parenthesization that produced the fewest multiplications in computing A0 A1...An.
| start with | find best k | resulting parenthesization |
| A0 A1 A2 A3 A4 |
_|__0__1__2__3__4_
0| -1 0 0 2 2
1| -1 -1 1 2 2
2| -1 -1 -1 2 2
3| -1 -1 -1 -1 3
4| -1 -1 -1 -1 -1 |
(A0 A1 A2)(A3 A4) |
| (A0 A1 A2)(A3 A4) |
_|__0__1__2__3_4_
0| -1 0 0 2 2
1| -1 -1 1 2 2
2| -1 -1 -1 2 2
3| -1 -1 -1 -1 3
4| -1 -1 -1 -1 -1 |
((A0)(A1 A2))(A3 A4) |
| Optimum parenthesization is ((A0)(A1 A2))(A3 A4) | ||
Now, the interesting problem is to write an algorithm that can recover this parenthesization from any given table bestK.