Pascal's Triangle Rule O(N,k) Is Comb(N,k) And We Have The Following Algorithm:

2) Problem analysis

We see that:

Due to the associative nature of matrix multiplication, matrices A i can be grouped in many different ways, without the resulting matrix A changing. However, there are differences in the cost of changing the combinations of matrices A i .

Below is the algorithm to multiply two matrices A and B, the attributes rows and columns are the number of rows and columns of the matrix.

MATRIX-MULTIPLY(A, B)

{

if ( columns[A]  rows[B]) return;

else for(i=1;i<=rows[A];i++)

for(j=1;j<=columns[B];j++)

{

}

return C;

}

C[i, j] = 0

for(k=1;k<=columns[A];k++)

C[i, j] = C[i, j] + A[i, k] * B[k, j];

We can multiply two matrices A and B if and only if it is appropriate: the number of columns of matrix A must be equal to the number of rows of matrix B. If A is a matrix of size m  n and B is an n  p matrix, then the resulting matrix C has size m  p. The time to compute C is determined by the number of operations C[i, j] = C[i, j] + A[i, k] * B[k, j], that is m  n  p.

To illustrate the difference in computing time C due to different placement of parentheses in matrix multiplication, consider matrices A, B, C, D with the following sizes:

A 30x1 B 1x40 C 40x10 D 10x25

Calculate the matrix product A × B × C × D

We will see that the cost of multiplying matrices depends on how the matrices are combined by multiplying them in different orders and calculating the cost in each way as follows:

Order

Figure 6.2. Costs according to matrix combinations

3) Idea

We solve the problem using a bottom-up approach. We will calculate and store the optimal solution for each small part to avoid recomputing the larger problem.

First for sets of 2 matrices, sets of 3 matrices...

For example, to calculate A×B×C we can calculate in the following ways: (A×B)×C or A×(B×C).

So the cost to calculate A×B×C is the cost calculated from 2 parts:

Part one is the cost kq1×C, with kq1 = A×B (this cost has been calculated and saved).

storage)

The second part is the cost A × kq2, with kq2 = B×C (this cost has been stored) Compare the above 2 parts and store the smaller cost. . .

4) Algorithm design

The key is to compute the cost of multiplying sets of matrices: A i ×...×A j , with 1≤ i < j ≤ n, where smaller sets have already been computed and the results stored.

With a combination of matrices:

A i ×...×A j = (A i ×...×A k ) × (A k+1 ×...×A j )

The cost of multiplying matrices A i ,...,A j will be the sum of: Cost of multiplying A i ×...×A k ( kq1), cost of multiplying A k+1 ×...×A j ( kq2), and cost kq1×kq2.

then:

If M ij is called the minimum cost of multiplying the set of matrices A i ×...×A j ,1≤ i < j ≤ n

* M ik is the minimum cost to multiply the set of matrices A i ×...×A k

* M k+1,j is the minimum cost to multiply the set of matrices A k+1 ×...×A j With matrix kq1 of size d i-1 ×d k and kq2 of size d k ×d j , so the cost to multiply

kq1×kq2 is d i-1 d k d j .

Therefore:

M ij = Min {M ik + M k +1, j + d i −1 d k d j };1 ≤ i < j ≤ n

i ≤ k ≤ j −1

M ii = 0

We can consider M as an upper triangular matrix: (M ij )1≤i<j≤n . We need to calculate and fill the elements of this matrix until we determine M 1n . All elements on the main diagonal are 0.

To calculate M ij , we need to know M ik , M k+1,j . We calculate the table along the diagonals starting from the diagonal next to the main diagonal and moving towards the upper right corner.

We want to know the best order to multiply the array of matrices (in the sense of minimum cost). Each time we determine the best combination, we use a variable k to store this order. That is, O ij = k, for M ik + M k +1, j + d i −1 d k d j reaches min.

The k indices to determine M ij are stored in a 2-dimensional array O.

The size of the matrices we store in a 1-dimensional array d : Ai is a matrix with d i-1 rows and d i columns.

Algorithm:

Input d = (d0,d1,...,dn); Output M = (Mij) ,

O = (Oij); MO(d,n,O,M)

{

for (i = 1; i <= n; i++) M[i][i] = 0;

for (diag = 1; diag <= n-1; diag++) for (i = 1; i <= n - diag; i++)

{

j = i + diag; csm = i;

min = M[i][i]+M[i+1][j]+d[i-1]*d[i]*d[j]; for (k= i; k <= j - 1; k++)

if (min > (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j] ))

{

min= M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]; csm = k;

}

M[i][j] = min;

O[i][j] = csm;

}

return M[1][n];

}

Then use the following function to output the order of matrix multiplication combinations: MOS(i, j, O)

{

if (i == j)

printf(Ai);

}

Example 6.1.

else

{

}

k = O[i][j];

printf("(");

MOS(i,k,O);

printf("*:);

MOS (k+1,j,O);

printf(")");

The algorithm is illustrated by matrix multiplication:

A 1 × A 2 × A 3 × A 4 × A 5 × A 6

With the sizes of the matrices being:

Matrix

Figure 6.3. Size of the matrices

6

1

j

5

15,125

2

i

4 11,875 10,500

3

3

9,375

7.125

5.375

4

For convenience, we rotate arrays M and O so that the main diagonal is horizontal.

A 1 A 2 A 3 A 4 A 5 A 6

Figure 6.4. Array M

6

1

j

5

3

2

i

4

3

3

3

3

3

3

3

4

2

1

3

3

5

1

2

3

4

5

5

Figure 6.5. Array O