Hacker News Reader

Comment by crntaylor | Hacker News Reader

Very neat. Presumably there is a more efficient method for implementing Nth order automatic differentiation than encoding the dual numbers as NxN matrices, though? To multiply the matrices takes O(N^3) time, whereas by exploiting their known structure I think you should be able to do it in O(N^2) time. Am I wrong?

View on HN

You're right, there's only O(n) information in these particular n x n matrices, so you can multiply them in O(n^2).

The code provided memoizes cell values using the key (r - c), so only O(n^2) work is required to read off the top row of the matrix. I'm planning to make that more explicit in a follow-up post.

Deleted comment

True, but I don't think Strassen and other efficient algorithms are much used in practice. If you go poke around in the source code for BLAS or LAPACK you'll see that the matrix multiplication algorithm used is an O(N^3) algorithm.

It's not the naive O(N^3) algorithm though - it's a block multiplication algorithm which generally gives faster results than the naive algorithm, because it's able to exploit locality so that you don't need to shift data into and out of the CPU cache all the time.

If I remember correctly, the most efficient algorithms have a ridiculously large constant factor, to the point where you don't have enough RAM to even store the matrix, let alone do anything with it.

That's not what GP is talking about. Those algorithms are the sub-cubic ones, the ones that are O(x^2.something). GP is talking about an algorithm that is still O(n^3), but is not just a straight translation of the matrix multiplication formula into code, but rather does things in a way that is more friendly to the CPU cache, resulting in significant speed gains.

Reply on news.ycombinator.com