News for hackers. Stuff that matters.

A comment on The eigenvector of “Why we moved from language X to language Y”. Parent comment

Re:The eigenvector of “Why we moved from language X to langu... by j2kun on Thursday March 16, 2017 @11:50AM (#13886013)
Power method is not matrix-matrix multiplication (which is not N^3, BTW [1]), but rather matrix-vector multiplication. So the power method is N^2*k where k is the number of iterations required to reach precision (usually polylogarithmic).

All this being said, scalability is _obviously_ a non-issue when talking about a matrix of programming languages. All methods are constant time.

[1]: https://en.wikipedia.org/wiki/Matrix_multiplication_algorith... Interesting tidbit: nobody can even prove it's not N^2 :)

[ Parent | on HN ]
Re:The eigenvector of “Why we moved from language X to langu... by howeman on Saturday March 18, 2017 @01:18AM (#13900020)
Oh right, of course, because you're iterating the distribution. Duh.

And yea, mat mul is not N^3 theoretically, but most implementations are. I've heard that some (mkl maybe) are 2.8, but haven't had someone point code to me. My personal attempts at implementing Strassen were slower than a tuned N^3 implementation, at least for matrices that fit into memory.

[ Parent | on HN ]