Hack the derivative • Hacker News Board

Re: Hack the derivative

#21

Post by srean » Sat, Oct 03, 2015, 12:57 PM UTC

cabinpark wrote: post #19

srean wrote: post #18

Earlier quoted context omitted.

Thanks for pointing to the right direction in case I want scratch that itch more. I am not surprised though that this has been done, expected the same. From a quick look, no one seems to suggest reflecting the original analytic function to get a periodic function, I guess some caveats lurk there. Does other integral transforms work better than Fourier ?

When you use this method you are implicitly making the function periodic. I can give you any function on some interval (sufficiently well behaved) and you can compute the Fourier series of it. Even though it's only defined on the interval, if you plotted the Fourier series you would still find it to be periodic. The same idea carries over to the spectral derivative. Even if the function isn't periodic, the method sti…

Given the local nature of the problem and the potential for using O(n) operations (as opposed n log n) my first suspect was wavelet transforms and sure enough people have done that but that body of work seems more recent than the use of FFT.

Re: Hack the derivative

#22

Post by jjoonathan » Sat, Oct 03, 2015, 1:19 PM UTC

jordigh wrote: post #20

lloda wrote: post #14

Earlier quoted context omitted.

No. Automatic differentiation is superior to the complex step method in every way. The only reason to use the complex step method is if you're using legacy languages where it's difficult to implement dual numbers but you have good support for complex numbers. I don't think anybody should be using the complex step method in new applications. Some reading ~ http://aero-comlab.stanford.edu/Papers/martins.aiaa.01-0921...…

wtf Automatic differentiation only works for the simplest functions for which you already know what the Taylor series looks like. For those cases, you might as well just hardcode derivative functions and the basic derivative rules (linearity and chain rule). It is not a general-purpose method. For functions that you can't even express by a simple formula, you still have to rely on finite differencing. Don't call "leg…

Can you comment on the space of functions which you know to be complex differentiable but for which you can't analytically evaluate/approximate the real derivative?

If so, I look forward to learning about it. If not, you were throwing stones in a glass house.

Re: Hack the derivative

#23

Post by lloda » Sat, Oct 03, 2015, 1:26 PM UTC

jordigh wrote: post #20

lloda wrote: post #14

Earlier quoted context omitted.

No. Automatic differentiation is superior to the complex step method in every way. The only reason to use the complex step method is if you're using legacy languages where it's difficult to implement dual numbers but you have good support for complex numbers. I don't think anybody should be using the complex step method in new applications. Some reading ~ http://aero-comlab.stanford.edu/Papers/martins.aiaa.01-0921...…

wtf Automatic differentiation only works for the simplest functions for which you already know what the Taylor series looks like. For those cases, you might as well just hardcode derivative functions and the basic derivative rules (linearity and chain rule). It is not a general-purpose method. For functions that you can't even express by a simple formula, you still have to rely on finite differencing. Don't call "leg…

The question was about automatic differentiation vs the method in the article (the complex step method) which is essentially a defective variant of automatic differentiation with a spurious numerical parameter.

Automatic differentiation works for any composition of those ‘simplest functions’ you mention, which is quite a lot of stuff, including whole programs.

Approximation methods have their place, sure. Sometimes they're good enough and sometimes it's all you can do. What does that have to do with anything?

Re: Hack the derivative

#24

Post by jjoonathan » Sat, Oct 03, 2015, 1:39 PM UTC

lloda wrote: post #23

jordigh wrote: post #20

Earlier quoted context omitted.

wtf Automatic differentiation only works for the simplest functions for which you already know what the Taylor series looks like. For those cases, you might as well just hardcode derivative functions and the basic derivative rules (linearity and chain rule). It is not a general-purpose method. For functions that you can't even express by a simple formula, you still have to rely on finite differencing. Don't call "leg…

The question was about automatic differentiation vs the method in the article (the complex step method) which is essentially a defective variant of automatic differentiation with a spurious numerical parameter. Automatic differentiation works for any composition of those ‘simplest functions’ you mention, which is quite a lot of stuff, including whole programs. Approximation methods have their place, sure. Sometimes t…

Thanks for the link, btw. I'm in the process of digesting the paper.

Re: Hack the derivative

#25

Post by jjoonathan » Sat, Oct 03, 2015, 1:49 PM UTC

jacobolus wrote: post #7

jjoonathan wrote: post #6

Earlier quoted context omitted.

I already know that a book on numerical analysis is likely to contain the answer I seek. The point of asking was to avoid a trip to the library since the working memory of someone who has been investigating differentiation techniques also likely contains the answer I seek.

I don’t quite understand what your question is, so I’m going to assume you were trying to ask, “When would you not want to use automatic differentiation?” I think the main time you can’t get much out of automatic differentiation is when your function is a black box or approximation, e.g. it comes from measuring physical data, or is the output of some kind of simulation, etc. I’m not an expert though. You can get a lo…

Someone who knows to bring automatic differentiation into a discussion about complex-step differentiation with the implication that they have already compared them and found one wanting (while implying that they may have missed something and are receptive to contrary opinions) already knows how CSD and AD work. This person also likely know how to use google, the library / amazon, and stack exchange (at the very least) but upon running a few simple queries has determined that the approximate effort to find an answer exceeds their interest in the subject. Unless someone else can use their own greater familiarity with the subject to provide an opinion or a pointer to a specific easily accessible resource (example: lloda's pdf link, counterexample: your book link) the line of inquiry will fizzle out due to the tyranny of cost/benefit analysis and having better things to do.

I appreciate that you were trying to be helpful, which is why I'm trying to be gentle (and explanatory) as I tell you that you weren't.

Re: Hack the derivative

#26

Post by jacobolus » Sat, Oct 03, 2015, 2:49 PM UTC

gjm11 wrote: post #10

jacobolus wrote: post #2

Yay for functions which are analytic in some neighborhood. Here’s the original paper from the 60s about the idea in this post: http://www.math.fsu.edu/~okhanmoh/media/Lyness,%20Moler,%20S... The latest work on this general topic is http://arxiv.org/pdf/1404.2463.pdf which manages to compute extremely accurate high-order derivatives (“...even the 100th derivative of an analytic function can be computed with near machi…

The paper by Lyness and Moler is nice, but if it's really "about the idea in this post" then the fact is somewhat hidden. It's mostly about using the Cauchy integral formula to turn derivatives into integrals, using the Poisson summation formula to relate those to finite sums, and using the Moebius inversion formula to get those relations into a form from which you can extract the derivatives. Maybe taking a very sho…

Fair enough. :-)

Re: Hack the derivative

#27

Post by eriktaubeneck » Sat, Oct 03, 2015, 3:47 PM UTC

jamessb wrote: post #13

The article comments: "In a lot of respects, it’s quite amazing how accurate many calculations can be made with floating numbers, like orbital mechanics and heat equations" I'm not sure it is so surprising. In Nick Trefethen's Numerical Analysis entry in The Princeton Companion to Mathematics , he notes: "Thus, on a computer, the interval [1 , 2] , for example, is approximated by about 10^16 numbers. It is interestin…

That's an interesting point I had not considered. My view (mostly from the math side, my shallow dive into physical systems was just from a PDE class in grad school) is from the view of unstable differential equations where very small changes to initial conditions can cause massive changes to the output of the system. My uninformed instincts would tell me that even with orders of more digits than atoms in a physical system, changes smaller than the available accuracy to initial conditions could have significant impact on the eventual state of the system.

Re: Hack the derivative

#28

Post by eriktaubeneck » Sat, Oct 03, 2015, 3:54 PM UTC

eccstartup wrote: post #5

I DO think Python libraries can do this already.

Did not intend to make any claims that Python libraries don't do this, but rather to explore the subject as a way to better understand the implementation and limits of floating point numbers and numerical analysis based on them.

Re: Hack the derivative

#29

Post by eriktaubeneck » Sat, Oct 03, 2015, 3:56 PM UTC

mbroshi wrote: post #16

edoloughlin wrote: post #8

Lost me a bit at Im(f(x+ih))/h near the end (that's a fancy I that android FF won't paste). Can anyone explain where 'm' came from? Or is 'Im' just a fn returning the imaginary part of its argument? EDIT: reading the code following, it's clear that Im is just that.

I was also lost at that part, although for a different reason. The function f was assumed to be from R to R, so it does not make formal sense to plug in f(x+ih). I guess the author has the unstated assumption that f is the restriction to R of a function on C.

Great point, and I apologize for the confusion. The function should be C to C, with the added restriction of R to R.

Re: Hack the derivative

#30

Post by eriktaubeneck » Sat, Oct 03, 2015, 3:58 PM UTC

edoloughlin wrote: post #8

Lost me a bit at Im(f(x+ih))/h near the end (that's a fancy I that android FF won't paste). Can anyone explain where 'm' came from? Or is 'Im' just a fn returning the imaginary part of its argument? EDIT: reading the code following, it's clear that Im is just that.

Thanks, I just realized that when I introduced the notation above, I just used I(f), but then when I used it below I wrote Im(f). I will clear that up.