4 ms·

Very neat. Presumably there is a more efficient method for implementing Nth order automatic differentiation than encoding the dual numbers as NxN matrices, thou

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?

deleted 13y ago
[deleted]
- crntaylor 13y ago
  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.
  - 30thElement 13y ago
    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.
    - deleted 13y ago
      [deleted]
    - rcthompson 13y ago
      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.
jliszka 13y ago
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.

4 ms·

Very neat. Presumably there is a more efficient method for implementing Nth order automatic differentiation than encoding the dual numbers as NxN matrices, thou

by crntaylor 13y ago

deleted 13y ago
[deleted]
- crntaylor 13y ago
  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.
  - 30thElement 13y ago
    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.
    - deleted 13y ago
      [deleted]
    - rcthompson 13y ago
      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.
jliszka 13y ago
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.