search

melonjs / melonJS

a fresh, modern & lightweight HTML5 game engine
https://melonjs.org
MIT License
5.92k stars 643 forks source link

optimize matrix operations using Strassen algorithm ? #1181

Open obiot opened 1 year ago

obiot commented 1 year ago

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

sudarshanmg commented 1 year ago

Hey I can do it and send a PR.

obiot commented 1 year ago

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 :)

sudarshanmg commented 1 year ago

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.

obiot commented 1 year ago

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 :)

sudarshanmg commented 1 year ago

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