Exact numeric nth derivatives
jliszka.github.io
Exact numeric nth derivatives
1–10 of 55 posts
Re: Exact numeric nth derivatives
#2See also the ad package [1] for Haskell which has a number of interesting features of this vein.
Re: Exact numeric nth derivatives
#3[deleted]
Re: Exact numeric nth derivatives
#4Nice analysis. Hope you don't mind me adding that by omitting terms of the Taylor series you do have some loss of precision, however small. Also, solving linear equation systems may even introduce instability as the following must be preserved: http://en.wikipedia.org/wiki/Diagonally_dominant_matrix
Re: Exact numeric nth derivatives
#5Very 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?
Re: Exact numeric nth derivatives
#6Nice analysis. Hope you don't mind me adding that by omitting terms of the Taylor series you do have some loss of precision, however small. Also, solving linear equation systems may even introduce instability as the following must be preserved: http://en.wikipedia.org/wiki/Diagonally_dominant_matrix
No, the coefficients of the Taylor series are the exact derivatives, assuming the actual arithmetic were exact (it's not, because IEEE 754). There's no loss of precision there.
Re: Exact numeric nth derivatives
#7[deleted]
The exact part struck me the most. I was expecting some technique that tries to figure out the maximal error during the calculations and provides enough space for an exact floating point presentation in advance to avoid the usual problem of continually increasing memory demands that you usually get with exact numbers. Such techniques can be used while calculating delaunay triangulations and maybe they are applicable here as well.
Re: Exact numeric nth derivatives
#8Nice analysis. Hope you don't mind me adding that by omitting terms of the Taylor series you do have some loss of precision, however small. Also, solving linear equation systems may even introduce instability as the following must be preserved: http://en.wikipedia.org/wiki/Diagonally_dominant_matrix
The point is that when you're considering the Taylor series for a dual number argument, you don't lose any precision, because higher powers of the "imaginary" part of the dual number vanish. The example he gives is
f(a + be) = f(a) + f'(a)be + 0.5 * f''(a) b^2 e^2 + O(e^3)
= f(a) + f'(a)be
You will lose some precision by using floating point numbers instead of an arbitrary-precision real number type, but this is a limitation of the machine you're working on. The method is exact.
Re: Exact numeric nth derivatives
#9Very 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]
Re: Exact numeric nth derivatives
#10This seems to be essentially the same thing as "power series arithmetic" (first-order "dual arithmetic" is equivalent to arithmetic in the ring of formal power series modulo x^2, but you can make that x^n).
Encoding power series as matrices is sometimes convenient for theoretical analysis (or, as here, educational purposes), but it's not very efficient. The space and time complexities with matrices are O(n^2) and O(n^3), versus O(n) and O(n^2) (or even O(n log n) using FFT) using the straightforward polynomial representation (in which working with hundreds of thousands of derivatives is feasible). In fact some of my current research focuses on doing this efficiently with huge-precision numbers, and with transcendental functions involved.