News for hackers. Stuff that matters.
Re:Matrix Multiplication in Clojure vs Numpy by tzs on Wednesday January 18, 2012 @02:38PM (#3481438)
> BLAS will still need O(N^3) operations for a NxN matrix multiplications, whether they are optimized or not.

Why wouldn't they use an algorithm that is better than O(N^3)?

Re:Matrix Multiplication in Clojure vs Numpy by stephencanon on Thursday January 19, 2012 @03:00PM (#3486346)
Two reasons: first, the matrix multiply algorithms with exponents less than three do not have the same numerical stability properties, which can introduce subtle bugs into software that was developed with the expectation of a "usual" O(n^3) multiplication being used. This makes it unsuitable for use in a general-purpose library.

Second, although algorithms with smaller exponents exist, there is more to high-performance than asymptotic complexity. In particular, the constant factors associated with these "fast" algorithms are typically large enough that there is no benefit to using them for "reasonable" matrix sizes.