Matrix chain multiplication test cases

Daily Programmer - Matrix Chain Multiplication.md

Description

Consider the problem of matrix multiplication. A matrix A of shape (n, m) may be multiplied by a matrix B of shape (m, p) to produce a new matrix A * B of shape (n, p). The number of scalar multiplications required to perform this operation is n * m * p.

Now consider the problem of multiplying three or more matrices together. It turns out that matrix multiplication is associative, but the number of scalar multiplications required to perform such operation depends on the association.

For example, consider three matrices of the following shapes:

A: (3, 5)
B: (5, 7)
C: (7, 9)

The matrix multiplication (A * B) * C would require 294 scalar multiplications while the matrix multiplication A * (B * C) would require 450 scalar multiplications.

The challenge is to find the optimal order for a chain of matrix multiplications given the shapes of the matrices.

Formal Inputs and Outputs

Your program should accept as input the number of matrices followed by their shapes. For the example above, the inputs would be:

3
3 5
5 7
7 9

Your program should output the optimal number of scalar multiplications and the association tree, where the leaves of the tree are the indices of the matrices. So for the example above, the outputs would be:

294
((0, 1), 2)

where 0 refers to the matrix A, 1 refers to B and 2 refers to C. Note that matrix multiplication is not commutative, so the leaves of the tree will always be in order.

Challenge Inputs

Challenge 1:

4
14 14
14 2
2 4
4 5

Challenge 2:

8
9 16
16 4
4 1
1 7
7 2
2 11
11 4
4 16

Challenge 3:

16
12 11
11 6
6 2
2 10
10 13
13 11
11 7
7 8
8 13
13 3
3 10
10 4
4 8
8 3
3 5
5 8

Bonus

An optimizer is no good if it takes longer than the solution it finds. Simply trying all combinations requires a runtime of O(2^(n)). A dynamic programming solution exists with a runtime of O(n^(3)), and the best known algorithm has a runtime cost of O(n * log(n)). Can you find these optimized solutions?

The following link contains additional test cases for 32, 64, and 128 matrices: https://gist.github.com/cbarrick/ce623ce2904fd1921a0da7aac3328b37

Hints

This is a classic problem taught in most university level algorithms courses. Mosts textbooks covering dynamic programming will discuss this problem. It even has its own Wikipedia page.

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

input_004.txt

4
14 14
14 2
2 4
4 5

input_008.txt

8
9 16
16 4
4 1
1 7
7 2
2 11
11 4
4 16

input_016.txt

16
12 11
11 6
6 2
2 10
10 13
13 11
11 7
7 8
8 13
13 3
3 10
10 4
4 8
8 3
3 5
5 8

input_032.txt

32
3 11
11 16
16 4
4 4
4 3
3 6
6 13
13 7
7 9
9 3
3 6
6 8
8 3
3 3
3 1
1 1
1 4
4 7
7 7
7 7
7 15
15 12
12 3
3 4
4 1
1 1
1 5
5 15
15 6
6 9
9 10
10 1

input_064.txt

64
13 6
6 7
7 12
12 14
14 7
7 7
7 5
5 13
13 5
5 11
11 11
11 15
15 11
11 3
3 1
1 7
7 11
11 15
15 6
6 8
8 3
3 7
7 2
2 3
3 13
13 9
9 11
11 14
14 3
3 4
4 9
9 16
16 3
3 16
16 13
13 2
2 5
5 14
14 10
10 4
4 9
9 15
15 4
4 16
16 14
14 13
13 4
4 12
12 9
9 11
11 6
6 14
14 9
9 6
6 14
14 2
2 7
7 3
3 4
4 4
4 12
12 2
2 5
5 16

input_128.txt

128
3 7
7 13
13 12
12 6
6 10
10 8
8 9
9 12
12 5
5 9
9 3
3 7
7 13
13 13
13 12
12 12
12 1
1 9
9 10
10 3
3 5
5 10
10 8
8 8
8 15
15 9
9 4
4 8
8 6
6 7
7 2
2 14
14 4
4 10
10 1
1 1
1 7
7 2
2 16
16 14
14 7
7 1
1 16
16 3
3 3
3 9
9 13
13 16
16 8
8 7
7 2
2 12
12 14
14 16
16 5
5 12
12 7
7 3
3 16
16 2
2 15
15 15
15 8
8 1
1 3
3 11
11 7
7 6
6 6
6 1
1 8
8 10
10 11
11 5
5 8
8 8
8 5
5 1
1 12
12 14
14 10
10 8
8 2
2 8
8 4
4 7
7 9
9 11
11 1
1 1
1 5
5 7
7 7
7 12
12 13
13 12
12 5
5 14
14 12
12 13
13 11
11 9
9 5
5 3
3 1
1 14
14 16
16 15
15 6
6 14
14 6
6 11
11 7
7 11
11 7
7 16
16 15
15 1
1 16
16 2
2 14
14 2
2 10
10 9
9 8
8 15
15 7
7 15

Wow, I wrote this up ages ago.

Do you plan on using it? I don't really have time to write a solver until maybe this weekend.

If you do plan on using this, I'll make time to write the solver and get the answers.

The solutions is a textbook dynamic programming problem.