[ADOL-C] Can ADOL-C handle FFTs?

[Ralf Juengling]

Thanks, Kshitij.

I was thinking of the library case where the source of the FFT is not available and algorithmic differentiation would need to treat it as a primitive operation somehow.

To clarify, I do not want to compute dF(x)/dx, but \delta F(x)/\delta f(y), the functional derivative.
Or back in the discrete setting, if we wrote the DFT as a matrix-vector product

F = D f

then derivative of F wrt. f would be D.

In the case I am looking at FFTs are used to implement convolution operations; so each FFT is paired with an inverse FFT, and the input and output quantities are all real-valued. Intuitively it should be possible for algorithmic differentiation to handle this if the FFT, or the convolution, is treated as a primitive operation.

Does anyone know of prior work where this was pursued?

Thanks,
Ralf

-----Original Message-----
From: adol-c-bounces at list.coin-or.org [mailto:adol-c-bounces at list.coin-or.org] On Behalf Of Kshitij Kulshreshtha
Sent: Wednesday, April 08, 2015 7:19 AM
To: adol-c at list.coin-or.org
Subject: Re: [ADOL-C] Can ADOL-C handle FFTs?

Hello,

FFTs involve complex numbers, so one must do complex differentiation.
This is a complicated subject in algorithmic differentiation due to the addition of Cauchy-Riemann equations in the picture. ADOL-C by itself does not handle complex numbers or complex differentiation. You could use std::complex<adouble> as your complex type but the side-effects are unforseeable.

Of course it also depends on how the FFT is being computed. If you're using a library like FFTW then ADOL-C or any tool cannot know about the internals of this FFT library.

Analytically one could use a second Fourier Transform to compute the derivative of the first one. As

F(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} f(y) e^{i y x} dy

assuming that this integral exists and is convergent

dF(x)/dx = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} f(y) i y e^{i y x} dy

So if F(x) = FT(f(y)) then dF(x)/dx = FT(i y f(y)).

The same holds for inverse Fourier transform. The discrete FFT is written as a sum but should have the same property.

You could use the external function interface to handcode your derivative of an FFT in this way, if you can safely ignore the complex differentiation problem above.

Best wishes
Kshitij

On 2015-04-07 22:32, Ralf Juengling wrote:
> I would like to use ADOL-C for a problem Y = C(X) where the 
> implementation of C uses FFT routines and I want ADOL-C to give me the 
> gradient of C wrt X.
> 
>  
> 
> I did a quick trial using the pyadolc Python wrapper and that failed.
> Before I play around further, could someone tell me if ADOL-C can 
> handle FFTs at all? If not, can any automatic differentiation tool do this?
> 
>  
> 
> Thanks,
> Ralf
> 
>  
> 
> 
> 
> _______________________________________________
> ADOL-C mailing list
> ADOL-C at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/adol-c
> 

--
Dr. Kshitij Kulshreshtha

Institut für Mathematik,
Universität Paderborn,
Warburger Straße 100,
33098 Paderborn.

Büro: TP21.1.21
Besucheradresse:
Technologiepark 21
33098 Paderborn.

Privatanschrift:
Arnikaweg 62
33100 Paderborn.
_______________________________________________
ADOL-C mailing list
ADOL-C at list.coin-or.org
http://list.coin-or.org/mailman/listinfo/adol-c