[Numpy-discussion] Improvement of performance

[Guilherme P. de Freitas]

On Tue, May 4, 2010 at 9:23 PM,  <josef.pktd at gmail.com> wrote:
> In [2] I didn't see anything about higher derivatives, so to get the
> Hessian I still had to do a finite difference (Jacobian) on the
> complex_step_grad. Even then the results look pretty good.

Yes, the traditional complex step does not solve the second
derivatives problem. I think there are papers that try to address that
(I don't know the literature though). But I have seen a paper [0] that
extends the notion of complex number to multi-complex numbers, and
then using the algebra of those multi-complex numbers the authors
obtain higher order derivatives. It lacks the convenience of the
complex step (in the sense that complex numbers are already
implemented), but it's something to keep in mind.

[0] http://soliton.ae.gatech.edu/people/rrussell/FinalPublications/ConferencePapers/2010Feb_SanDiego_AAS-10-218_mulicomplex.pdf

But if we were to go that way (defining new numbers), maybe (I'm no
expert in this area, some of the proponents of AD via dual numbers say
it would be a better idea) it would be better to define dual numbers.
They are like complex numbers, but their "imaginary component"  (I
don't think it's called that) d has the property that d^2 = 0. Using
these numbers, one can obtain first and higher order derivatives
"automatically" [1][2] (forward mode only, see refs.)

[1] http://en.wikipedia.org/wiki/Automatic_differentiation#Automatic_differentiation_using_dual_numbers
[2] http://conal.net/papers/beautiful-differentiation/ (recent paper
with references, related blog posts and video of a talk)

There is a group of people in the Haskell community [3][4] that are
working on Automatic Differentiation via dual numbers (that gives you
the "forward mode" only, see refs.). It looks really interesting. I
saw somewhere that one could write external modules in Haskell for
Python...

[3] http://www.haskell.org/haskellwiki/Automatic_Differentiation
[4] http://hackage.haskell.org/packages/archive/fad/1.0/doc/html/Numeric-FAD.html

Just throwing ideas out there. I found it really neat, and potentially
very useful. Now, as for the reverse mode of AD, there seems to be no
shortcut, and it would be really nice, as it seems that the
computational complexity of the reverse mode is lower than the forward
mode. There are libraries, like TAPENADE [5] and ADIFOR [6] that do
it, though. They do it by source code transformation. The TAPENADE
tool even accepts C or Fortran code via the web and returns a
differentiated code (worth playing with). Really neat.

[5] http://www-sop.inria.fr/tropics/
[6] http://www.mcs.anl.gov/research/projects/adifor

Ok, now all we need is easy access to these tools from Python, and we
are set! :)

-- 
Guilherme P. de Freitas
http://www.gpfreitas.com