Matrix Chain Multiplier
Matrix Chain Multiplication is perhaps the quintessential example of dynamic programming, a technique that nearly every data structures and algorithms book explores. My implementation is no different from the rest, using Introduction to Algorithms by Cormen, Leiserson, and Rivest as the basis for its design. The problem can be stated as follows: given a chain <A1, A2,..., An> of n matrices, where for i = 1, 2,...,n, matrix Ai has dimension pi-1 x pi, fully parenthesize the product A1A2...An in a way that minimizes the number of scalar multiplications. This program does exactly that, for a chain of up to 26 matrices. You may input your own dimensions for a matrix chain or have the computer generate them for you. If you choose to specify your own dimensions, you also have the option to input integer values for the matrix entries, since this program is capable of performing the multiplication.
matrix(rows, cols, [int, int,..., int]) * matrix(rows, cols, [int, int,..., int]) * ...Rows and cols must, of course, be integers, and the number of entries within brackets must be exactly rows * cols. For example, for the matrix pictured below (in the screenshots section), you would enter
matrix(3, 3, [-362, -385, -408, 570, 675, 780, -362, -301, -240]) * matrix(...If you choose not to input values for matrix entries, use the following syntax:
matrix(rows, cols) * matrix(rows, cols) * ...
Specific example: matrix(3, 2) * matrix(2, 4)Note: The cols of matrix Ai-1 must equal the rows of Matrix Ai for all i.
Screenshots
|
|
|
