Add FFT to the math library. Use Eigen's implementation.

[syclik]

From @betanalpha on August 16, 2013 14:28

Expose Eigen's FFT into the modeling language:

vector fft(vector x)

Copied from original issue: stan-dev/stan#179

[syclik]

From @betanalpha on August 16, 2013 14:40

Whoops, forgot about the imaginary components, so I guess something like

void fft(vector x, vector r, vector i);

[syclik]

@betanalpha, think we should still have this as part of the language?

[syclik]

From @betanalpha on May 22, 2014 20:47

There are lots of physics use cases, if only for preprocessing in
transformed data. The holdup was whether we wanted to (a)
find a way to limit functions to transformed data or (b) figure
out the analytic gradient for the FFT.

On May 22, 2014, at 9:44 PM, Daniel Lee notifications@github.com wrote:

@betanalpha, think we should still have this as part of the language?

—
Reply to this email directly or view it on GitHub.

[syclik]

From @bob-carpenter on May 23, 2014 13:35

And a bigger issue is data-only arguments. Because in some
cases, we might only want to implement some gradients for a function.

Definitely not impossible, but a fair bit of work in the parser.

On May 22, 2014, at 10:47 PM, Michael Betancourt notifications@github.com wrote:

There are lots of physics use cases, if only for preprocessing in
transformed data. The holdup was whether we wanted to (a)
find a way to limit functions to transformed data or (b) figure
out the analytic gradient for the FFT.

On May 22, 2014, at 9:44 PM, Daniel Lee notifications@github.com wrote:

@betanalpha, think we should still have this as part of the language?

—
Reply to this email directly or view it on GitHub.

—
Reply to this email directly or view it on GitHub.

[syclik]

From @mbrubake on May 23, 2014 15:35

So I totally think we should add FFT at some point as it's very useful for some models. The gradients are easy (the FFT and Inverse FFT are both linear operators) so we don't need to worry about data-only functions.

The problem with adding FFT is that we need some way to handle complex numbers. There are basically two options that aren't complete hacks:

1. Actually implement a complex type which works just like real does.
2. Add support for functions which return more than one parameter. Then, the FFT would simply take and return the real and imaginary coefficients separately.

Both of these options could potentially turn into a fair amount of work. That said, I vote for 2. For one, I don't think complex numbers are going to be widely enough used to be worth the pain of implementing and supporting them. On the other hand, allowing functions to return multiple values seems much more useful and may not be that hard if we make suitable use of boost tuples [http://www.boost.org/doc/libs/1_55_0/libs/tuple/doc/tuple_users_guide.html]

[syclik]

From @bob-carpenter on May 23, 2014 16:51

Yes, I really want to add multiple outputs. What they
call lists in the R world, I think, though of course, I'd want
to type the ones in Stan.

I don't know what the size limits are on Boost's tuples, but we probably don't
need huge lists.

I also really like the Python syntax for literals and assignments,
which lets you do things like (a,b,c) to create a list out of a, b,
and c. It's all kosher for us, because we can infer the type.

vector a;
vector b;
(a,b) <- fft(...);

We probably want to have the right co(ntra)variance with the type, so
that they follow assignment rules pointwise. That is, I can use
an (int,real) argument anywhere I can use a (real,real) agument and
I can use an (int,real) result anwyhere I could use a (real,real) result.

• Bob

On May 23, 2014, at 5:35 PM, Marcus Brubaker notifications@github.com wrote:

So I totally think we should add FFT at some point as it's very useful for some models. The gradients are easy (the FFT and Inverse FFT are both linear operators) so we don't need to worry about data-only functions.

The problem with adding FFT is that we need some way to handle complex numbers. There are basically two options that aren't complete hacks:

• Actually implement a complex type which works just like real does.
• Add support for functions which return more than one parameter. Then, the FFT would simply take and return the real and imaginary coefficients separately.
Both of these options could potentially turn into a fair amount of work. That said, I vote for 2. For one, I don't think complex numbers are going to be widely enough used to be worth the pain of implementing and supporting them. On the other hand, allowing functions to return multiple values seems much more useful and may not be that hard if we make suitable use of boost tuples [http://www.boost.org/doc/libs/1_55_0/libs/tuple/doc/tuple_users_guide.html]

—
Reply to this email directly or view it on GitHub.

[syclik]

From @mbrubake on May 23, 2014 20:8

I'm also a pretty big fan of the python syntax in this case, so that sounds
perfect to me. I'm pretty sure boost::tuple can handle as many options as
we will ever reasonably need. I'm hard pressed to imagine a function
returning more than 5 things.

One challenge we might run into is if we need to have different functions
for different numbers of returns. E.G., a function which does one thing if
it returns one versus two objects. Because we can't deduce template
parameters based on return type in C++, how these functions return values
would need to be different from a simple return value. Probably not hugely
important to begin with but maybe worth thinking about.

​

[syclik]

From @betanalpha on May 24, 2014 16:53

And a bigger issue is data-only arguments. Because in some
cases, we might only want to implement some gradients for a function.

Definitely not impossible, but a fair bit of work in the parser.

I was thinking of something simpler — functions that can only be
called in the transformed data block.

[syclik]

From @bob-carpenter on May 24, 2014 23:16

On May 23, 2014, at 10:08 PM, Marcus Brubaker notifications@github.com wrote:

I'm also a pretty big fan of the python syntax in this case, so that sounds
perfect to me. I'm pretty sure boost::tuple can handle as many options as
we will ever reasonably need. I'm hard pressed to imagine a function
returning more than 5 things.

No, but I can easily imagine an R programmer stuffing 45 things
into a list.

One challenge we might run into is if we need to have different functions
for different numbers of returns. E.G., a function which does one thing if
it returns one versus two objects. Because we can't deduce template
parameters based on return type in C++, how these functions return values
would need to be different from a simple return value. Probably not hugely
important to begin with but maybe worth thinking about.

We do the same thing as C++ in not allowing two different
functions with the same inputs and different return types.
I don't think that's usually a problem though --- when it's
happened to me it's always been a mistake.

• Bob

[syclik]

From @bob-carpenter on May 24, 2014 23:17

On May 24, 2014, at 6:53 PM, Michael Betancourt notifications@github.com wrote:

And a bigger issue is data-only arguments. Because in some
cases, we might only want to implement some gradients for a function.

Definitely not impossible, but a fair bit of work in the parser.

I was thinking of something simpler — functions that can only be
called in the transformed data block.

That would definitely be easier to implement.

• Bob

[syclik]

From @mbrubake on May 24, 2014 23:26

On Sat, May 24, 2014 at 7:17 PM, Bob Carpenter notifications@fd.fxlcf.dpdns.orgwrote:

On May 24, 2014, at 6:53 PM, Michael Betancourt notifications@github.com
wrote:

And a bigger issue is data-only arguments. Because in some
cases, we might only want to implement some gradients for a function.

Definitely not impossible, but a fair bit of work in the parser.

I was thinking of something simpler — functions that can only be
called in the transformed data block.

That would definitely be easier to implement.

I don't understand why we need to though, at least for FFT. The analytic
gradients are pretty easy. Heck, I'll volunteer to do them if someone else
goes through the trouble of implementing everything else but is having
trouble with that.

Cheers,
Marcus

[syclik]

From @bob-carpenter on May 24, 2014 23:53

It sounds like we don't need to do this for FFT.

But there are things like cumulative distribution functions
and some crazy densities that are easy to differentiate for
a few but not all parameters.

But let's cross that bridge when we come to it.

• Bob

On May 25, 2014, at 1:26 AM, Marcus Brubaker notifications@github.com wrote:

On Sat, May 24, 2014 at 7:17 PM, Bob Carpenter notifications@fd.fxlcf.dpdns.orgwrote:

On May 24, 2014, at 6:53 PM, Michael Betancourt notifications@github.com
wrote:

And a bigger issue is data-only arguments. Because in some
cases, we might only want to implement some gradients for a function.

Definitely not impossible, but a fair bit of work in the parser.

I was thinking of something simpler — functions that can only be
called in the transformed data block.

That would definitely be easier to implement.

I don't understand why we need to though, at least for FFT. The analytic
gradients are pretty easy. Heck, I'll volunteer to do them if someone else
goes through the trouble of implementing everything else but is having
trouble with that.

Cheers,
Marcus
—
Reply to this email directly or view it on GitHub.