melonJS icon indicating copy to clipboard operation
melonJS copied to clipboard

optimize matrix operations using Strassen algorithm ?

Open obiot opened this issue 1 year ago • 5 comments

Adding this one here, as it's quite interesting :

Strassen multiplication algorithm is faster, with a complexity of approximately O(n^2.8074) , compared to O(n^3) for standard multiplication algorithm.

Strassen Matrix multiplication is based on a divide and conquer-based approach, by diving matrix into smaller square matrix https://www.topcoder.com/thrive/articles/strassenss-algorithm-for-matrix-multiplication

obiot avatar Apr 05 '23 07:04 obiot

Hey I can do it and send a PR.

sudarshanmg avatar Jul 15 '23 13:07 sudarshanmg

Hi, that would be awesome honestly !

If you, don't replace the current multiply method, just add a fastMul() one or something, this way we can also properly test and benchmark it against the normal one.

thanks :)

obiot avatar Jul 16 '23 00:07 obiot

Absolutely! :love_you_gesture: Just to be clear, Matrix multiplication is currently in matrix3.js right? If so, is the mutiply method for a 4x4 matrix? because the indexing is from 0-15.

sudarshanmg avatar Jul 16 '23 06:07 sudarshanmg

Absolutely! 🤟 Just to be clear, Matrix multiplication is currently in matrix3.js right? If so, is the mutiply method for a 4x4 matrix? because the indexing is from 0-15.

indeed, we called it Matrix3d but yes it's a 4x4 matrix. Same for the Matrix2d one it's 3x3 matrix.

can't disagree it's maybe a bit confusing :)

obiot avatar Jul 16 '23 07:07 obiot

Hey :wave:
Implemented strassen's as requested, please check it out!

sudarshanmg avatar Jul 16 '23 08:07 sudarshanmg