Matrix Chain Multiplication

[pravalikavis]

Description of the problem

When matrices are given in a sequence, it will find the most efficient way to multiply these matrices together.

Expectations: Time complexity: O(n^2) - (best/ average case)

Applications:

1. Graph algorithms
2. Signal processing
3. Network industry
4. Camera calibration to remove lens distortion.
5. If Matrix is inferred as linear expression i.e., it represents N-dimensional space then it can be used in video games

Methods: multiply(arrayOfMatrices)

Example of the problem

References/Other comments

https://www.riverpublishers.com/journal_read_html_article.php?j=JCSM/7/4/3 https://en.wikipedia.org/wiki/Matrix_chain_multiplication#Hu_&_Shing_(1981)

[czgdp1807]

Can you please suggest the input and output of the algorithm more clearly?

[neha153]

strassen's matrix multiplication method would work. time complexity is O(n ^log7)

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_strassens_matrix_multiplication.htm

this site can give u all the details abt it

[czgdp1807]

@neha153 The references in OP aren't concerned about multiplying two matrices, it is about finding a correct order(with minimum operations) to multiply a chain of matrices.

[pravalikavis]

Input will be a one dimension array specifying the order of matrices that are supposed to be multiplied, the output will be the order in which the matrices need to be multiplied which is the most optimal order.

An explanation of why we want to implement this algorithm: We are given a sequence (chain) --> A1, A2,...,An of n matrices to be multiplied, and we wish to compute the product A1A2···An .

Matrix multiplication is associative, and so all parenthesizations yield the same product. For example, if the chain of matrices is (A1, A2, A3, A4), the product A1A2A3A4 can be fully parenthesized in five distinct ways:

1. (A1(A2(A3A4)))
2. (A1((A2A3)A4))
3. ((A1A2)(A3A4))
4. ((A1(A2A3))A4)
5. (((A1A2)A3)A4).

The way we parenthesize a chain of matrices can have a dramatic impact on the cost of evaluating the product.

To illustrate the different costs incurred by different parenthesizations of a matrix product, consider the problem of a chain A1, A2, A3 of three matrices. Suppose that the dimensions of the matrices are 10 ×100, 100×5, and 5×50, respectively. If we multiply according to the parenthesization ((A1A2)A3), we perform 10 · 100 · 5 = 5000 scalar multiplications to compute the 10 × 5 matrix product A1A2, plus another 10·5·50 = 2500 scalar multiplications to multiply this matrix by A3, for a total of 7500 scalar multiplications. If instead, we multiply according to the parenthesization (A1(A2A3)), we perform 100·5·50 = 25,000 scalar multiplications to compute the 100×50 matrix product A2A3, plus another 10·100·50 = 50,000 scalar multiplications to multiply A1 by this matrix, for a total of 75,000 scalar multiplications. Thus, computing the product according to the first parenthesization is 10 times faster.

Source: Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

[czgdp1807]

IMHO, we should provide an API to solve the following which is a generalisation of the matrix chain multiplication problem,

The matrix chain multiplication problem generalizes to solving a more abstract problem: given a linear sequence of objects, an associative binary operation on those objects, and a way to compute the cost of performing that operation on any two given objects (as well as all partial results), compute the minimum cost way to group the objects to apply the operation over the sequence

This paper has been cited in the above quote, though I do not know how it relates to the above generalised problem.

[pravalikavis]

From my understanding, the paper that you have mentioned has developed an algorithm with a central idea of matrix chain multiplication to multiply multi-dimension matrices. But I wanted to work on linear chain or 2D matrix chain of multiplication.

[czgdp1807]

Applications:

1. Graph algorithms

Where is the result of matrix chain multiplication(i.e., the optimal order of multiplication) is used in graph algorithms? Like is there any algorithm which you are aware of?

A more abstract API for solving generalised problem can have the following inputs,

1. Sequence of objects as list, Array , etc.
2. Cost of associative binary operation - a function.

[pravalikavis]

I have proposed this algorithm based on this article. This article specifies that the algorithm can be used in graph algorithms. I haven't gone through which specific graph algorithm uses matrix chain multiplication.

API description: There will be one API --> get MatrixChainOrder(orderOfMatrixes[])

input for the above API is an array of integers representing the order of matrices that are to be multiplied. For example, I have three matrices to multiply and their order of matrices are as following: A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then input will be [10,30,5]. The output will be (AB)C.

[pravalikavis]

Cost of associative binary operation - a function.

Are you suggesting that the algorithm should run based on this input function?

[czgdp1807]

Are you suggesting that the algorithm should run based on this input function?

Yes to make things more abstract. Matrix chain multiplication is mostly an example for DP problems but an API solving it's generalisation can be more useful.

[pravalikavis]

Ok from my understanding, the algorithm should be based upon the input function. For example, if A, B, C matrices optimally should be multiplied in (AB)C order with 4,500 operations but because of the input function which wanted 6,000 binary operations so we give output as A(BC) order as it has nearly 6,000 operations. But I see one problem with this approach why would anyone want to opt for lesser optimal output? Instead, we can use this as general multiplication of multiple matrices which optimally generates the order ( using DP ) and accordingly multiplies them based on that order and returns the resultant matrix.

[czgdp1807]

For example, if A, B, C matrices optimally should be multiplied in (AB)C order with 4,500 operations but because of the input function which wanted 6,000 binary operations so we give output as A(BC) order as it has nearly 6,000 operations.

Not necessary to be matrices. Consider this use case, A[1], A[2], ..., A[n] are sequence of objects on which an operator say, # this is applied which is having the cost defined by the following function,

def cost(A, B):
    return (A.order + B.order)**2 # arbitrary

So, I will call optimal_grouping([A[1], A[2], A[3], ..., A[n]], cost). Now, I will expect the optimal grouping which will result in minimum total cost. So, I am saying to add an API which solves a generic problem. Obviously by redefining cost you can make, optimal_grouping work for matrices as follows,

def cost(A, B):
    return A.rows*B.cols*B.rows

[pravalikavis]

Ok. Can I start working on this?

[czgdp1807]

Yeah you can.

[Moddy2024]

i am from gssoc 2020 and i want to work on this

[Moddy2024]

i have done a pull request for this please review the files i completed in O(n^2) time complexity please look into it @czgdp1807 @aayush-05 @manaswinidas @robotjellyzone

[robotjellyzone]

i have done a pull request for this please review the files i completed in O(n^2) time complexity please look into it @czgdp1807 @aayush-05 @manaswinidas @robotjellyzone

hi @Moddy2024 but where is you PR , do reference it here . also, have you discussed the API for the same before moving with its PR ?

[Moddy2024]

I AM FROM GSSOC'20 And i have created a pull request for this please look into it