-
Notifications
You must be signed in to change notification settings - Fork 268
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Matrix Chain Multiplication #230
Comments
Can you please suggest the input and output of the algorithm more clearly? |
strassen's matrix multiplication method would work. this site can give u all the details abt it |
@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. |
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: 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:
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. |
IMHO, we should provide an API to solve the following which is a generalisation of the matrix chain multiplication problem,
This paper has been cited in the above quote, though I do not know how it relates to the above generalised problem. |
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. |
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,
|
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: input for the above API is an array of integers representing the order of matrices that are to be multiplied. |
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. |
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. |
Not necessary to be matrices. Consider this use case, A[1], A[2], ..., A[n] are sequence of objects on which an operator say,
So, I will call def cost(A, B):
return A.rows*B.cols*B.rows |
Ok. Can I start working on this? |
Yeah you can. |
i am from gssoc 2020 and i want to work on this |
i have done a pull request for this please review the files |
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 ? |
I AM FROM GSSOC'20 And i have created a pull request for this please look into it |
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:
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)
The text was updated successfully, but these errors were encountered: