pydatastructs
pydatastructs copied to clipboard
codezonediitj
Add Matrix multiplication (sequential and parallel)
Description of the problem
Example of the problem
References/Other comments
We would be needing strassen's algorithm to be implemented, which is the best I know, for sequential version. Any other you are aware of?
A lot of algorithms are described here https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm
We need to implement them all. Should go to, linear_data_structures.algorithms.
We would be needing strassen's algorithm to be implemented, which is the best I know, for sequential version. Any other you are aware of?
I have tried to pitch that idea in many repos but they all come to the same conclusion to not do it because it takes up a lot of space and practically is slow even if the asymptotics are better
Lets start with naive implementation ( O(n^3) ) of sequential and parallel and then see if strassen is doable.
it takes up a lot of space and practically is slow
Can you provide any numbers(time, space) of from the analysis they used to arrive at the conclusion?
Lets start with naive implementation ( O(n^3) )
Isn't of much use, it's too simple to implement.
it takes up a lot of space and practically is slow
Can you provide any numbers(time, space) of from the analysis they used to arrive at the conclusion?
One of the senior programmers stopped me from actually approaching the problem and closed the issue. So I dont know the actual issues they have but I can try it.
Lets start with naive implementation ( O(n^3) )
Isn't of much use, it's too simple to implement.
and the parallel one?
In practice, Strassen's algorithm can be implemented to attain better performance than conventional multiplication even for small matrices, for matrices that are not at all square, and without requiring workspace beyond buffers that are already needed for a high-performance conventional multiplication
Quoting from, https://en.wikipedia.org/wiki/Strassen_algorithm#Implementation_considerations
The image under https://en.wikipedia.org/wiki/Matrix_multiplication#Computational_complexity gives a graph where all the algorithms are named, so all of them should be implemented.
and the parallel one?
Yes we can go with that. I think it's not that difficult to implement.
and the parallel one?
Yes we can go with that. I think it's not that difficult to implement.
sure
One of the senior programmers stopped me from actually approaching the problem and closed the issue. So I dont know the actual issues they have but I can try it.
Can you please provide a link to that issue? A proper research is needed on this is needed before reaching to any conclusion.
We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of the ring R).
May be due to recursion it may be slow for small matrices. We should use iterative logic using stacks.
One of the senior programmers stopped me from actually approaching the problem and closed the issue. So I dont know the actual issues they have but I can try it.
Can you please provide a link to that issue? A proper research is needed on this is needed before reaching to any conclusion.
if I could have I would have but the thing is I was preparing for gsoc last year when I pushed this issue so I have no recollection what so ever from where I got it.
We iterate this division process n times (recursively) until the submatrices degenerate into numbers (elements of the ring R).
May be due to recursion it may be slow for small matrices. We should use iterative logic using stacks.
we can start it and we can optimize as we move, I will start with the parallel multiplication first and then move to strassen.
should it be applicable for DODA also? If yes then how should the None values be handled?
@czgdp1807 Let me take up this work and it seems the Parallel matrix multiplication was already implemented and what's left is Sequential multiplication. Should I go with Strassen algorithm for study or any suggestions!?
This issue is not in priority as of now.
Ok I will look for other issues