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

[Kshitij Kulshreshtha]

Hello,

> 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.
>

For convolutions it is known that

\frac{\partial (f * g)}{\partial x_i}
= \frac{\partial f}{\partial x_i} * g
= f * \frac{\partial g}{\partial x_i}

So the derivative of a convolution can be computed using the convolution
of one of the derivatives and the other original function. You can use
this property to propogate derivatives.

The way to treat any operation as a primitive in ADOL-C is to define an
external function with all relevant modes of AD, forward and reverse,
defined by hand. See externfcts.h and
examples/additional_examples/ext_diff_func/ directory in the ADOL-C
sources. This will work as long as all the inputs and outputs to this
primitive are real and not complex.

Best wishes
Kshitij



On 2015-04-08 16:44, Ralf Juengling wrote:
> 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
> 

-- 
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.