Add Matrix multiplication (sequential and parallel)

[HarsheetKakar]

Description of the problem

Example of the problem

References/Other comments

[czgdp1807]

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?

[czgdp1807]

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.

[HarsheetKakar]

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

[HarsheetKakar]

Lets start with naive implementation ( O(n^3) ) of sequential and parallel and then see if strassen is doable.

[czgdp1807]

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?

[czgdp1807]

Lets start with naive implementation ( O(n^3) )

Isn't of much use, it's too simple to implement.

[HarsheetKakar]

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.

[HarsheetKakar]

Lets start with naive implementation ( O(n^3) )

Isn't of much use, it's too simple to implement.

and the parallel one?

[czgdp1807]

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.

[czgdp1807]

and the parallel one?

Yes we can go with that. I think it's not that difficult to implement.