Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Exact numeric nth derivatives

jliszka.github.io

Post reply on HN
Print view View original

11–20 of 55 posts

Re: Exact numeric nth derivatives

#11

Post by jliszka »

crntaylor wrote: post #5

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?

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.

Re: Exact numeric nth derivatives

#14

Post by waqf »

[deleted] wrote: post #3

[deleted]

Well, it's exact until you evaluate it at a float — because it's the floats that are inexact, not the technique.

And that limitation is just as true of symbolic algebra. Symbolic algebra is "exact" iff you can do exact evaluation, or if your application doesn't require you to evaluate at all. Automatic differentiation is the same, it's just that the unevaluated forms in symbolic algebra are "nicer".

Re: Exact numeric nth derivatives

#15

Post by crntaylor »

[deleted] wrote: post #9
crntaylor wrote: post #5

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]

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.

Re: Exact numeric nth derivatives

#17

Post by [deleted] »

waqf wrote: post #14
[deleted] wrote: post #3

[deleted]

Well, it's exact until you evaluate it at a float — because it's the floats that are inexact, not the technique. And that limitation is just as true of symbolic algebra. Symbolic algebra is "exact" iff you can do exact evaluation, or if your application doesn't require you to evaluate at all. Automatic differentiation is the same, it's just that the unevaluated forms in symbolic algebra are "nicer".

[deleted]

Re: Exact numeric nth derivatives

#18

Post by jordigh »

Am I missing something or is this begging the question?

For any function that is not a combination of polynomials, you need to have its Taylor expansion up to the desired order of derivatives, so you can't just take an "arbitrary" function and use this method to compute its derivative in exact arithmetic.

So for anything other than polynomials, you just reword the problem of finding exact derivatives to finding exact Taylor series, and in order to find Taylor series in most cases, you have to differentiate or express your function in terms of the Taylor series of known functions.

Edit: Indeed, take the only non-polynomial example here, a rational function (division by a polynomial). In order to make this work, you have to know the geometric series expansion of 1/(1-x). For each function that you want to differentiate this way, you have to keep adding more such pre-computed Taylor expansions.

Re: Exact numeric nth derivatives

#19

Post by ot »

[deleted] wrote: post #3

[deleted]

> they are almost never used in any real automatic differentiation system

They're efficient enough for first-order derivatives. For example they are used in Ceres, Google's library for non-linear least-squares optimization

https://ceres-solver.googlesource.com/ceres-solver/+/master/...

Re: Exact numeric nth derivatives

#20

Post by porges »

[deleted] wrote: post #17
waqf wrote: post #14

Earlier quoted context omitted.

Well, it's exact until you evaluate it at a float — because it's the floats that are inexact, not the technique. And that limitation is just as true of symbolic algebra. Symbolic algebra is "exact" iff you can do exact evaluation, or if your application doesn't require you to evaluate at all. Automatic differentiation is the same, it's just that the unevaluated forms in symbolic algebra are "nicer".

[deleted]

>Dual numbers cannot, because they use plain old floating point math in the derivative equations.

There's nothing stopping you from switching out the floating point for rationals or something like that.

For example, the Haskell `ad` package has its functions parameterized over all instances of Num: http://hackage.haskell.org/package/ad-3.4/docs/Numeric-AD.ht...

Post reply on HN