FFT proposal for gsoc 2021

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

FFT proposal for gsoc 2021

Boost - Dev mailing list
Hi Boost community,

I've been working on a C++ templated library for Fast Fourier Transforms,
https://github.com/Lagrang3/fftx.
Templated because some FFT algorithms are algebraic-field independent, eg. you
could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.
As a result you could have a single algorithm for a variety of underlying, eg.
`std::complex<float>`, `std::complex<double>`, `std::complex<long double>`,
`boost::math::quaternion`, finite field types (this would yield the "Number
theoretic transform" https://cp-algorithms.com/algebra/fft.html#toc-tgt-6).

I would like to improve this library during the GSOC 2021, as a proposal for
inclusion inside Boost.Math or Boost.Algorithms.

Is there anyone interested in supervising this project? Any opinions?

Best regards,
Eduardo Quintana


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
Hello,

Eduardo Quintana via Boost said:     (by the date of Thu, 11 Mar 2021 09:46:58 +0000)
> I've been working on a C++ templated library for Fast Fourier Transforms,
> https://github.com/Lagrang3/fftx.
> Templated because some FFT algorithms are algebraic-field independent, eg. you
> could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.
> As a result you could have a single algorithm for a variety of underlying, eg.
> `std::complex<float>`, `std::complex<double>`, `std::complex<long double>`,
> `boost::math::quaternion`, finite field types (this would yield the
> "Number theoretic transform" https://cp-algorithms.com/algebra/fft.html#toc-tgt-6 ).

(above this link does not work for me)
 
> I would like to improve this library during the GSOC 2021, as a proposal for
> inclusion inside Boost.Math or Boost.Algorithms.
>
> Is there anyone interested in supervising this project? Any opinions?


This was recommended here as a topic for GSOC:

https://github.com/boostorg/math/issues/303#issuecomment-573828731
https://github.com/boostorg/math/issues/303#issuecomment-583140413

So definitely a good idea. I am interested in this project. I might
help with mentoring (I know FFT math and C++14/17 inside-out),
but I cannot be a mentor because I don't know boost library
inside-out. So I can help with technical coding aspects, but a real
mentor has to tell where a specific feature has to go into boost library.

Now I have looked at the code at https://github.com/Lagrang3/fftx

1. It is good that you also provide a wrapper for fftw and OpenMP fftw,
   such wrapper is missing in boost.

2. Isn't there prime factorization somewhere in boost? you do this manually.

3. you are working with std::vector storage, but I think that you
   should use boost::ublas::tensor

Your code looks quite modern, it is definitely a short sketch, not a
complete library, nothing spectacular.

The first thing to do will be to cut corners. The FFT topic is huge,
and GSOC time is limited. Better to do a bit less, but to do it well.
Maybe for example a well written wrapper for libfftw with C++
metaprogramming slots ready to enable full number theoretic transform
at a later stage. Or something similar.

So to summarize: I am interested. I have never took part in GSOC on
either side, so I have no idea how this stuff is organized. I can
help with theoretical mathematical and with technical C++ 14/17/20
aspects. But I don't know boost library well enough, where what types
are defined, etc. Someone else has to take good care of these things
if mentoring. My time is limited, but if others will pick it up,
I will do my best.

best regards
Janek Kozicki

--
Janek Kozicki, PhD. DSc. Arch. Assoc. Prof.
Gdańsk University of Technology
Faculty of Applied Physics and Mathematics
Department of Theoretical Physics and Quantum Information
--
http://yade-dem.org/
http://pg.edu.pl/jkozicki (click English flag on top right)

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
>

> This was recommended here as a topic for GSOC:
>
> https://github.com/boostorg/math/issues/303#issuecomment-573828731
> https://github.com/boostorg/math/issues/303#issuecomment-583140413
>
> So definitely a good idea. I am interested in this project. I might
> help with mentoring (I know FFT math and C++14/17 inside-out),
> but I cannot be a mentor because I don't know boost library
> inside-out. So I can help with technical coding aspects, but a real
> mentor has to tell where a specific feature has to go into boost library.
It's great to see there's actually interested in the topic.
Let's wait to see if someone experienced decides to jump in as mentor.

>
> Now I have looked at the code at https://github.com/Lagrang3/fftx
>
> 1. It is good that you also provide a wrapper for fftw and OpenMP fftw,
>    such wrapper is missing in boost.
>
> 2. Isn't there prime factorization somewhere in boost? you do this manually.
>
> 3. you are working with std::vector storage, but I think that you
>    should use boost::ublas::tensor
>
> Your code looks quite modern, it is definitely a short sketch, not a
> complete library, nothing spectacular.
Just a sketch, of course, not something to boast of.
If you'd like to explore I would suggest to take a look also at the other
branches, where I have been doing experiments
for small vs large size ffts trying to approach FFTW's performance.
I will upload a readme soon and some plots to show some benchmarks results.

>
> The first thing to do will be to cut corners. The FFT topic is huge,
> and GSOC time is limited. Better to do a bit less, but to do it well.

I couldn't agree more.

> So to summarize: I am interested. I have never took part in GSOC on
> either side, so I have no idea how this stuff is organized. I can
> help with theoretical mathematical and with technical C++ 14/17/20
> aspects. But I don't know boost library well enough, where what types
> are defined, etc. Someone else has to take good care of these things
> if mentoring. My time is limited, but if others will pick it up,
> I will do my best.
>
> best regards
> Janek Kozicki
>
> --
> Janek Kozicki, PhD. DSc. Arch. Assoc. Prof.
> Gdańsk University of Technology
> Faculty of Applied Physics and Mathematics
> Department of Theoretical Physics and Quantum Information
> --
> http://yade-dem.org/
> http://pg.edu.pl/jkozicki (click English flag on top right)
Thank you so much.
Eduardo Quintana.


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
 > Hi Boost community,
> I've been working on a C++ templated library> for Fast Fourier Transforms
> ...
> Is there anyone interested in supervising this> project? Any opinions?
Thank you for your interest and query.

Yes. I think I am interested and potentially qualifiedas 5 time GSoC mentor in Multiprecision and Math.
The plan seems good, start with header onlysimple implementation and increase complexityand efficiency as time allows.
This project would fill a present gap and wish listentry in Math/Multirpecision for those unable/unwillingto include FFTW.
I will write a little project description at rthe relevantpage, link will follow...

Feel free to continue this thread, at the moment, i'mtoo busy to put down all my thoughts...

Kind regards, Christopher

    On Thursday, March 11, 2021, 10:55:29 AM GMT+1, Eduardo Quintana via Boost <[hidden email]> wrote:  
 
 Hi Boost community,

I've been working on a C++ templated library for Fast Fourier Transforms,
https://github.com/Lagrang3/fftx.
Templated because some FFT algorithms are algebraic-field independent, eg. you
could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.
As a result you could have a single algorithm for a variety of underlying, eg.
`std::complex<float>`, `std::complex<double>`, `std::complex<long double>`,
`boost::math::quaternion`, finite field types (this would yield the "Number
theoretic transform" https://cp-algorithms.com/algebra/fft.html#toc-tgt-6).

I would like to improve this library during the GSOC 2021, as a proposal for
inclusion inside Boost.Math or Boost.Algorithms.

Is there anyone interested in supervising this project? Any opinions?

Best regards,
Eduardo Quintana

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
> Strongly and beneficially Influence that. But we still need
> To adhere to all formal application Steps

A note regarding these formal steps:

https://github.com/boostorg/wiki/wiki/Google-Summer-of-Code%3A-2021
https://lists.boost.org/Archives/boost/2021/02/250876.php
https://www.boost.org/users/faq.html

> On the board. I can do 1 mentor of Either quad double or FFT.

Yeah, both of them are very useful for me. If we make FFT this year, we can
hope for quad-double next year :-)

best regards
Janek

Christopher Kormanyos said:     (by the date of Fri, 12 Mar 2021 16:00:38 +0100)

> We still need to adhere to the
> Formal application process
> And we should have our dialog
> On the board. I can do 1 mentor of
> Either quad double or FFT.
>
> Having your own idea and a
> Working model is a tremendous
> Advantage in the application
> Process and is likely to very
> Strongly and beneficially
> Influence that. But we still need
> To adhere to all formal application
> Steps
>
> Kindest regards, Chris
>
> Sent from my iPhone
>
> > On 12. Mar 2021, at 07:26, Eduardo Quintana <[hidden email]> wrote:
> >
> > Dear Christopher,
> >
> > I am thrilled to hear from you! Thank you for offering mentorship for this
> > project. I look forward to start working on it.
> >
> > Best regards,
> > Eduardo
> >
> >> On Thu, Mar 11, 2021 at 06:55:37PM +0000, Christopher Kormanyos wrote:
> >>
> >> <html><head></head><body><div class="ydpad5c413ayahoo-style-wrap" style="font-family:Helvetica Neue, Helvetica, Arial, sans-serif;font-size:16px;"><div></div>
> >>        <div dir="ltr" data-setdir="false"><div>&gt; Hi Boost community,<br><div>&gt; I've been working on a C++ templated library</div><div>&gt; for Fast Fourier Transforms</div><div><br></div><div>&gt; ...<br></div></div><div dir="ltr" data-setdir="false"><span>&gt; Is there anyone interested in supervising this</span></div><div dir="ltr" data-setdir="false"><span>&gt; project? Any opinions?</span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>Thank you for your interest and query.<br></span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>Yes. I think I am interested and potentially qualified</span></div><div dir="ltr" data-setdir="false"><span>as 5 time GSoC mentor in Multiprecision and Math.</span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>The plan seems good, start with header only</span></div><div dir="ltr" data-setdir="false"><span>simple implementation and increase complexity</span></div><div dir="ltr" data-setdir="false"><span>and efficiency as time allows.</span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>This project would fill a present gap and wish list</span></div><div dir="ltr" data-setdir="false"><span>entry in Math/Multirpecision for those unable/unwilling</span></div><div dir="ltr" data-setdir="false"><span>to include FFTW.</span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>I will write a little project description at rthe relevant</span></div><div dir="ltr" data-setdir="false"><span>page, link will follow...<br></span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>Feel free to continue this thread, at the moment, i'm</span></div><div dir="ltr" data-setdir="false"><span>too busy to put down all my thoughts...<br></span></div><div dir="ltr" data-setdir="false"><span><br></span></div><div dir="ltr" data-setdir="false"><span>Kind regards, Christopher</span><br></div></div><div><br></div>
> >>
> >>        </div><div id="yahoo_quoted_5520563993" class="yahoo_quoted">
> >>            <div style="font-family:'Helvetica Neue', Helvetica, Arial, sans-serif;font-size:13px;color:#26282a;">
> >>
> >>                <div>
> >>                    On Thursday, March 11, 2021, 10:55:29 AM GMT+1, Eduardo Quintana via Boost &lt;[hidden email]&gt; wrote:
> >>                </div>
> >>                <div><br></div>
> >>                <div><br></div>
> >>                <div>Hi Boost community,<br><br>I've been working on a C++ templated library for Fast Fourier Transforms,<br>https://github.com/Lagrang3/fftx.<br>Templated because some FFT algorithms are algebraic-field independent, eg. you<br>could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.<br>As a result you could have a single algorithm for a variety of underlying, eg.<br>`std::complex&lt;float&gt;`, `std::complex&lt;double&gt;`, `std::complex&lt;long double&gt;`,<br>`boost::math::quaternion`, finite field types (this would yield the "Number<br>theoretic transform" <a href="https://cp-algorithms.com/algebra/fft.html#toc-tgt-6" target="_blank">https://cp-algorithms.com/algebra/fft.html#toc-tgt-6</a>).<br><br>I would like to improve this library during the GSOC 2021, as a proposal for<br>inclusion inside Boost.Math or Boost.Algorithms.<br><br>Is there anyone interested in supervising this project? Any opinions?<br><br>Best regards,<br>Eduardo Quintana<br><br>_______________________________________________<br>Unsubscribe &amp; other changes: <a href="http://lists.boost.org/mailman/listinfo.cgi/boost" target="_blank">http://lists.boost.org/mailman/listinfo.cgi/boost</a><br></div>
> >>            </div>
> >>        </div></body></html>
> > <publickey - [hidden email] - 341e5416.asc>
>


--
--
Janek Kozicki, PhD. DSc. Arch. Assoc. Prof.
Gdańsk University of Technology
Faculty of Applied Physics and Mathematics
Department of Theoretical Physics and Quantum Information
--
http://yade-dem.org/
http://pg.edu.pl/jkozicki (click English flag on top right)

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
 
> I would like to improve this library during> the GSOC 2021, as a proposal for> inclusion inside Boost.Math or Boost.Algorithms.

> Is there anyone interested in supervising this> project? Any opinions?
Yes.
Thank you for your query and display ofneat prototyping code.

Based on further considerations,a potential GSoC 2021 project on this topichas been created. It can be found here:
https://github.com/boostorg/wiki/wiki/Google-Summer-of-Code%3A-2021#boostmath-fft-utilities
Please keep in contact here and feelfree to pose any questions if they arise.
I positively encourage you to considerapplying for this project in GSoC 2021.

    On Thursday, March 11, 2021, 10:55:29 AM GMT+1, Eduardo Quintana via Boost <[hidden email]> wrote:  
 
 Hi Boost community,

I've been working on a C++ templated library for Fast Fourier Transforms,
https://github.com/Lagrang3/fftx.
Templated because some FFT algorithms are algebraic-field independent, eg. you
could FFT an array of N matrices provided a Nth matrix-root-of-unity is given.
As a result you could have a single algorithm for a variety of underlying, eg.
`std::complex<float>`, `std::complex<double>`, `std::complex<long double>`,
`boost::math::quaternion`, finite field types (this would yield the "Number
theoretic transform" https://cp-algorithms.com/algebra/fft.html#toc-tgt-6).

I would like to improve this library during the GSOC 2021, as a proposal for
inclusion inside Boost.Math or Boost.Algorithms.

Is there anyone interested in supervising this project? Any opinions?

Best regards,
Eduardo Quintana

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
On Sun, Mar 14, 2021 at 03:38:49PM +0000, Christopher Kormanyos wrote:
> Please keep in contact here and feel
> free to pose any questions if they
> arise.
> I positively encourage you to consider
> applying for this project in GSoC
> 2021.

I have a question: what would be the next step?

If I understood correctly, I should write a proposal which I should submit to
gsoc website between March 29 and April 13.
But it is not clear to me if there is also going to be a pre-selection of
students applying from Boost.

Thank you,
Eduardo


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list

On 2021-03-11 1:55 p.m., Christopher Kormanyos via Boost wrote:

>   > Hi Boost community,
>> I've been working on a C++ templated library> for Fast Fourier Transforms
>> ...
>> Is there anyone interested in supervising this> project? Any opinions?
> Thank you for your interest and query.
>
> Yes. I think I am interested and potentially qualifiedas 5 time GSoC mentor in Multiprecision and Math.
> The plan seems good, start with header onlysimple implementation and increase complexityand efficiency as time allows.
> This project would fill a present gap and wish listentry in Math/Multirpecision for those unable/unwillingto include FFTW.
> I will write a little project description at rthe relevantpage, link will follow...

At the risk of starting a long and fundamental discussion about Boost's
fundamental goals, I'd like to suggest that we step back a little to
consider different options. Reimplementing FFTs from scratch might be
didactically useful for the person(s) doing that, but for the developer
community not be of much interest if the quality of the result doesn't
match already available options. And to think that you can match freely
available FFT implementations (which have often evolved over decades)
seems foolish.

In that sense, the goal should *not* be to come up with a new and
competitive implementation of an FFT library.

Rather, I would like to propose a slightly different approach:

1) Develop a C++ API that can be used as a thin layer over one or two
existing FFT "backend" libraries (FFTW seems a natural choice).

2) Implement that same API "from scratch", but without much effort put
into performance. The goal isn't to out-perform existing implementations
(which would take many years of effort !), but to provide a functionally
complete and correct reference implementation, useful for testing.

This would open the door for future additions of other back-ends, useful
for developers who are unable or unwilling to use the primary back-end
itself.

(Note that the selection of the backend could be done at compile-time or
at runtime, depending on the available hardware, including GPUs or other
accelerators. Designing a clever dispatch mechanism to pick the "best"
backend given a particular problem set (problem size, data types, data
layout, etc.) is itself a complex problem worth considering...)

---

In a nutshell, the goal should be a modern C++ API that is convenient to
use and which can be bound to different backends for top performance,
yet avoiding explicit dependence on specific implementations.

Stefan
--

       ...ich hab' noch einen Koffer in Berlin...


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
 > At the risk of starting a long and fundamental> discussion about Boost's fundamental goals,
> ...

> 1) Develop a C++ API that can be used as> a thin layer over one or two existing FFT> "backend" libraries (FFTW seems a natural choice).

> 2) Implement that same API "from scratch",> but without much effort put into performance.> The goal isn't to out-perform existing implementations> (which would take many years of effort !),> but to provide a functionally complete and> correct reference implementation, useful for testing.
Yes. Indeed, your 1 and 2 are exactly consistentwith my own subjective personal thoughts.
Thatreally seems rather just sensibleto me.

Many thanks and kind regards, Chris

    On Sunday, March 14, 2021, 6:19:35 PM GMT+1, Stefan Seefeld via Boost <[hidden email]> wrote:  
 
 
On 2021-03-11 1:55 p.m., Christopher Kormanyos via Boost wrote:

>  > Hi Boost community,
>> I've been working on a C++ templated library> for Fast Fourier Transforms
>> ...
>> Is there anyone interested in supervising this> project? Any opinions?
> Thank you for your interest and query.
>
> Yes. I think I am interested and potentially qualifiedas 5 time GSoC mentor in Multiprecision and Math.
> The plan seems good, start with header onlysimple implementation and increase complexityand efficiency as time allows.
> This project would fill a present gap and wish listentry in Math/Multirpecision for those unable/unwillingto include FFTW.
> I will write a little project description at rthe relevantpage, link will follow...

At the risk of starting a long and fundamental discussion about Boost's
fundamental goals, I'd like to suggest that we step back a little to
consider different options. Reimplementing FFTs from scratch might be
didactically useful for the person(s) doing that, but for the developer
community not be of much interest if the quality of the result doesn't
match already available options. And to think that you can match freely
available FFT implementations (which have often evolved over decades)
seems foolish.

In that sense, the goal should *not* be to come up with a new and
competitive implementation of an FFT library.

Rather, I would like to propose a slightly different approach:

1) Develop a C++ API that can be used as a thin layer over one or two
existing FFT "backend" libraries (FFTW seems a natural choice).

2) Implement that same API "from scratch", but without much effort put
into performance. The goal isn't to out-perform existing implementations
(which would take many years of effort !), but to provide a functionally
complete and correct reference implementation, useful for testing.

This would open the door for future additions of other back-ends, useful
for developers who are unable or unwilling to use the primary back-end
itself.

(Note that the selection of the backend could be done at compile-time or
at runtime, depending on the available hardware, including GPUs or other
accelerators. Designing a clever dispatch mechanism to pick the "best"
backend given a particular problem set (problem size, data types, data
layout, etc.) is itself a complex problem worth considering...)

---

In a nutshell, the goal should be a modern C++ API that is convenient to
use and which can be bound to different backends for top performance,
yet avoiding explicit dependence on specific implementations.

Stefan
--

      ...ich hab' noch einen Koffer in Berlin...


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
I've written and uploaded a first draft proposal to GSOC-2021 for the
Boost.Math.FFT library.
https://github.com/Lagrang3/gsoc-2021/releases/download/v1.0/gsoc.pdf
I realize now that maybe I should have given more details about the proposal itself,
like user's interface and implementation ideas.
That can be fixed in version 2.0.

Best regards,
Eduardo


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
Hi Eduardo,

On 2021-03-30 6:58 a.m., Eduardo Quintana via Boost wrote:
> I've written and uploaded a first draft proposal to GSOC-2021 for the
> Boost.Math.FFT library.
> https://github.com/Lagrang3/gsoc-2021/releases/download/v1.0/gsoc.pdf
> I realize now that maybe I should have given more details about the proposal itself,
> like user's interface and implementation ideas.
> That can be fixed in version 2.0.

Your schedule above looks very ambitious, and, I fear, quite unrealistic:

You plan a single week (June 7 - June 13) for

* defining the API for your FFT library
* implementing it
* writing tests for it
* writing benchmarks for it
* documenting (part of) it

Unless the bulk of this is already done, and the tasks merely consist of
polishing the code and integrating it into a new special-purpose git
repo, I don't think this will work.

For that reason, as well as for reasons I already outlined in a previous
post, I strongly suggest you change the ordering (and timing) of your
milestones, to first focus on an API that can be implemented as a
wrapper around FFTW (as I suspect that will be the implementation most
developers will use until you have an alternative that actually
out-performs FFTW), and only then start to re-implement your API with
other backends (including your own).

That will allow you to realize that you won't be able to meet all your
goals, and still make this project a success, i.e. have something
actually usable. If you end up with a library that works, but doesn't
perform well, I'm afraid it won't attract any users, which would be a
pity, wouldn't it !?

Stefan
--

       ...ich hab' noch einen Koffer in Berlin...


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
Hi Stefan,

> Your schedule above looks very ambitious, and, I fear, quite unrealistic:

You're right about the timeline: it is too ambitiuos.
Though some work it is already done and it only needs polishing.
Anyways I'll make it shorter, maybe by scrapping out the multi-threading part
for post-GSOC work.

> For that reason, as well as for reasons I already outlined in a previous
> post, I strongly suggest you change the ordering (and timing) of your
> milestones, to first focus on an API that can be implemented as a
> wrapper around FFTW (as I suspect that will be the implementation most
> developers will use until you have an alternative that actually
> out-performs FFTW), and only then start to re-implement your API with
> other backends (including your own).

Wrapping FFTW is not a priority I have. I believe that the right way to work
towards an FFTW/C++ api will be to do so directly into the FFTW project. Sooner
or later someone will do it.

What I want to bring to Boost.Math are "Generic Programming" FFT algorithms
for situations that FFTW can't handle. And I want them to have decent
performance for complex numbers, I do not aim to outperform FFTW.
With time it can be improved and one day it will become competitive with FFTW.
In part, the success of the FFTW is due to the "codelets", which are functions
for small and fixed-size FFTs that they generate from a C code
that is generated by a program called "genfft". I believe we can do better with
C++ compile-time programming. Not for this summer though...

Thanks for the feedback.
Eduardo


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
Hi Eduardo,

On 2021-03-30 1:01 p.m., Eduardo Quintana via Boost wrote:
> Wrapping FFTW is not a priority I have. I believe that the right way
> to work
> towards an FFTW/C++ api will be to do so directly into the FFTW project. Sooner
> or later someone will do it.
>
> What I want to bring to Boost.Math are "Generic Programming" FFT algorithms
> for situations that FFTW can't handle. And I want them to have decent
> performance for complex numbers, I do not aim to outperform FFTW.

What you have in mind may be an acceptable goal for a stand-alone FFT
library, especially if this is a learning exercise, but as a
contribution to Boost I think it falls short.

Boost's stated goal is to defined modern C++ APIs for common sets of
functionality, perhaps even finding their way into future C++ standards.
As such, it's important to consider the (end-)user expectations, which,
especially for a math-centered library, includes the "three Ps":

* Portability
* Performance
* Productivity

As a user I don't want to see another FFT library that may work well in
some cases but not others. I simply want to be able to use it and trust
that its performance is good no matter the platform, and no matter the
problem type (real vs complex, dimensionality, data layout, size, etc.).

If I have to add logic to switch between APIs depending on those
parameters, I'm no longer productive. If I only get good performance in
some cases (compared to existing and popular libraries), I'm no longer
efficient. Etc.

Please keep this in mind when proposing a project whose ultimate goal is
to be accepted into Boost.

Thanks,

Stefan
--

       ...ich hab' noch einen Koffer in Berlin...


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
 > I've written and uploaded a first draft> proposal to GSOC-2021 for the Boost.Math.FFT> library.

Hello Eduardo,
Thank you for pursuing this project and preparingyour powerful proposal. The proposal contentits technical description, motivation and your personaldetails are very nicely and coherently presented.
These make your proposal already strong.
As has been mentioned, a reduced scope ofthe project might be more realistic. And itseems like there is, in fact, strong interestin the interface.
Stefan mentions
 > focus on an API that can be implemented as a
> wrapper around FFTW
There is a lot of wisdom in this advice.In fact, I encourage you also to look closely at ourwork with Boost.Multiprecision, one of my ownprojects co-authored John. There you will findthat we provide both our own Boost-licensedmultiple-precision types as well as wrappedversoins of GMP and MPFR. So in some sense,we have been living this advice for the past 10years and it has been successful.
I will comment again on your proposal in moredepth. Feel free to refine it any way you like.You might have to place it into the GSoC onlineformat, as I am not sure if a manually-writtenLaTeX proposal can be used in a standalone form.But I'd have to check on that.
Again, as mentioned and still the case,*I strongly encourage you to continue* with theapplication process.
Kind regards, Chris

    On Tuesday, March 30, 2021, 12:59:05 PM GMT+2, Eduardo Quintana via Boost <[hidden email]> wrote:  
 
 I've written and uploaded a first draft proposal to GSOC-2021 for the
Boost.Math.FFT library.
https://github.com/Lagrang3/gsoc-2021/releases/download/v1.0/gsoc.pdf
I realize now that maybe I should have given more details about the proposal itself,
like user's interface and implementation ideas.
That can be fixed in version 2.0.

Best regards,
Eduardo

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
Hey,
Thanks for suggestions, I'll go through formats you suggested, and get
back to you with more questions

On Wed, Mar 31, 2021, 12:31 AM Christopher Kormanyos via Boost <
[hidden email]> wrote:

>  > I've written and uploaded a first draft> proposal to GSOC-2021 for the
> Boost.Math.FFT> library.
>
> Hello Eduardo,
> Thank you for pursuing this project and preparingyour powerful proposal.
> The proposal contentits technical description, motivation and your
> personaldetails are very nicely and coherently presented.
> These make your proposal already strong.
> As has been mentioned, a reduced scope ofthe project might be more
> realistic. And itseems like there is, in fact, strong interestin the
> interface.
> Stefan mentions
>  > focus on an API that can be implemented as a
> > wrapper around FFTW
> There is a lot of wisdom in this advice.In fact, I encourage you also to
> look closely at ourwork with Boost.Multiprecision, one of my ownprojects
> co-authored John. There you will findthat we provide both our own
> Boost-licensedmultiple-precision types as well as wrappedversoins of GMP
> and MPFR. So in some sense,we have been living this advice for the past
> 10years and it has been successful.
> I will comment again on your proposal in moredepth. Feel free to refine it
> any way you like.You might have to place it into the GSoC onlineformat, as
> I am not sure if a manually-writtenLaTeX proposal can be used in a
> standalone form.But I'd have to check on that.
> Again, as mentioned and still the case,*I strongly encourage you to
> continue* with theapplication process.
> Kind regards, Chris
>
>     On Tuesday, March 30, 2021, 12:59:05 PM GMT+2, Eduardo Quintana via
> Boost <[hidden email]> wrote:
>
>  I've written and uploaded a first draft proposal to GSOC-2021 for the
> Boost.Math.FFT library.
> https://github.com/Lagrang3/gsoc-2021/releases/download/v1.0/gsoc.pdf
> I realize now that maybe I should have given more details about the
> proposal itself,
> like user's interface and implementation ideas.
> That can be fixed in version 2.0.
>
> Best regards,
> Eduardo
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list


> On Mar 30, 2021, at 20:01, Eduardo Quintana via Boost <[hidden email]> wrote:
>
> Though some work it is already done and it only needs polishing.

I went through the excercise of choosing a FFT implementation for C++ a few weeks ago.
Your project as it is on github, already carries with it five or more dependencies ( + tbb ? ):
        • Boost
        • FFTW
        • google/benchmark
        • alglib
        • meson
For myself that is too much, so I could not even try your library.

Q1) Do you plan to get rid of external dependencies other than FFTW?

I ended up using FFTW++ which was painless enough.
It is written by pros (meaning: mathematicians published the algorithms in a peer-reviewed paper)
and manages the nitty-gritty of FFTW for you.

There is nothing to learn, basically, three liner usage:
    auto f=array2<complex<double>>(w,h,size_t align=64);
    fft2d Forward2d=fft2d(w,h,1,f,f);                         // SETUP THE TRANSFORM FOR USE AND REUSE
    Forward2d.fft(f, f);

Q2) What do plan offering that exceeds FFTW++ capability?
 
In you file fft-2d.cpp, presumably the example use, it is

    vector<complex<double>> FA;
    FFT_dim<2>(FA.begin(), FA.end(), N, e);

This applies your own templated naive implementations of FFT. However,
FFTW does not wrap into this API ! You are using the plain old C interface for FFTW.

Q3) Is it really within your capabilities to implement the dispatch mechanisms necessary to wrap FFTW into such an API as that one template, FFT_dim<2>?

So three question, Q1,Q2,Q3. Thanks!

Kostas

===============
Institute of Nuclear and Particle Physics
NCSR Demokritos
http://inspirehep.net/author/profile/K.G.Savvidy.1
https://github.com/kotika/random
https://mixmax.hepforge.org

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
 
> Hey,
> Thanks for suggestions, I'll go through> formats you suggested, and get> back to you with more questions

Hello Gagandeep,

Thank you for your interest. This particularthread, however, was, in my opinion,dedicated to a specific query fromanother candidate. General informationI consider to be OK.
If you have a different case (and I am notentirely sure of that...)
then I would, indeed, please request youto start your own specific thread ifyou wish to pursue this project.
Kind regards, Christopher Kormanyos
    On Tuesday, March 30, 2021, 9:25:05 PM GMT+2, Gagandeep Bhatia via Boost <[hidden email]> wrote:  
 
 Hey,
Thanks for suggestions, I'll go through formats you suggested, and get
back to you with more questions

On Wed, Mar 31, 2021, 12:31 AM Christopher Kormanyos via Boost <
[hidden email]> wrote:

>  > I've written and uploaded a first draft> proposal to GSOC-2021 for the
> Boost.Math.FFT> library.
>
> Hello Eduardo,
> Thank you for pursuing this project and preparingyour powerful proposal.
> The proposal contentits technical description, motivation and your
> personaldetails are very nicely and coherently presented.
> These make your proposal already strong.
> As has been mentioned, a reduced scope ofthe project might be more
> realistic. And itseems like there is, in fact, strong interestin the
> interface.
> Stefan mentions
>  > focus on an API that can be implemented as a
> > wrapper around FFTW
> There is a lot of wisdom in this advice.In fact, I encourage you also to
> look closely at ourwork with Boost.Multiprecision, one of my ownprojects
> co-authored John. There you will findthat we provide both our own
> Boost-licensedmultiple-precision types as well as wrappedversoins of GMP
> and MPFR. So in some sense,we have been living this advice for the past
> 10years and it has been successful.
> I will comment again on your proposal in moredepth. Feel free to refine it
> any way you like.You might have to place it into the GSoC onlineformat, as
> I am not sure if a manually-writtenLaTeX proposal can be used in a
> standalone form.But I'd have to check on that.
> Again, as mentioned and still the case,*I strongly encourage you to
> continue* with theapplication process.
> Kind regards, Chris
>
>    On Tuesday, March 30, 2021, 12:59:05 PM GMT+2, Eduardo Quintana via
> Boost <[hidden email]> wrote:
>
>  I've written and uploaded a first draft proposal to GSOC-2021 for the
> Boost.Math.FFT library.
> https://github.com/Lagrang3/gsoc-2021/releases/download/v1.0/gsoc.pdf
> I realize now that maybe I should have given more details about the
> proposal itself,
> like user's interface and implementation ideas.
> That can be fixed in version 2.0.
>
> Best regards,
> Eduardo
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
 

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi Kostas,

> • Boost
> • FFTW
> • google/benchmark
> • alglib
> • meson
> For myself that is too much, so I could not even try your library.
>
> Q1) Do you plan to get rid of external dependencies other than FFTW?

Q1) This repository is meant for experimentation. The compulsory dependencies
are: Boost and Meson, the rest are just for benchmarks. Meson and Boost are not
even necessary if you are not interested in the tests or installing the library.
The library is header only thus for trying it is enough to use the contents
under the `include` directory.

> Q2) What do plan offering that exceeds FFTW++ capability?
>
> In you file fft-2d.cpp, presumably the example use, it is
>
>     vector<complex<double>> FA;
>     FFT_dim<2>(FA.begin(), FA.end(), N, e);
>
> This applies your own templated naive implementations of FFT. However,
> FFTW does not wrap into this API ! You are using the plain old C interface for FFTW.

Q2) It was mentioned before by Stefan Seefeld that Boost.Math.FFT should provide
and FFTW wrapper. I think that's exactly what FFTW++ does. If the time frame of
the GSOC allows it or the urgency to do that overwhelms the rest of my proposal
then I believe that Boost.Math.FFT could provide a user interface that doesn't
necessarily mirrors FFTW.
When it comes to capabilities, consider that FFTW++ (to my knowledge) cannot do
more than FFTW does, ie. it is limited by the types used internally on the FFTW
side.

I will have to take a better look at FFTW++ before giving a more educated
opinion. By looking at the surface of the code, I see that they've built their
own complex type based on double and it even has arithmetic operations. That's a
great improvement with respect to FFTW's POD fftw_complex. Yet I don't see why
they couldn't use std::complex<double>?
What if I need to compute a trascendental function of an fftwpp::Complex?
The standard library provides all kinds of mathematical functions that take
complex<T> as arguments.
What if I need to do a FFT on a complex number with extended precision?

The FFTs I am proposing are templated on the type. So that the user is free to
use std::complex<whathever_Real> or any user defined type for representing
complex numbers, or even weirder Fields/Rings (see the proposal for details).
That's a capability that FFTW/++ don't have.

FFT algorithms are oblivious of the representation of the complex type (in the
case of DFT on the complex Field). I want to put this statement into practice
following the lesson from the std::complex<> and templated algorithms.
FFTW cannot do that by any means without
compromising performance because it is written in C. Any FFTW wrapper follows
suit.

> Q3) Is it really within your capabilities to implement the dispatch mechanisms necessary to wrap FFTW into such an API as that one template, FFT_dim<2>?

Q3) The user interface is not final. It is in the GSOC plan to allocate some
time to decide on that issue.

Thanks for the feedback. Very useful.
Eduardo


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

publickey - eduardo.quintana@pm.me - 341e5416.asc (886 bytes) Download Attachment
signature.asc (304 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list


> On Mar 31, 2021, at 10:12, Eduardo Quintana via Boost <[hidden email]> wrote:
>
>  I want to put this statement into practice
> following the lesson from the std::complex<> and templated algorithms.

I am sympathetic to your idea of making an FFT which works in an arbitrary field, but
according to the C++ ISO spec, §26.2/2:
The effect of instantiating the template complex for any type other than float, double or long double is unspecified.

So we are not going to be able to define a finite field F[p] and plug it into std::complex<>.

Should not then the focus be on the types that Boost.Multiprecision supports, and especially its own complex types?

Cheers,
Kostas

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: FFT proposal for gsoc 2021

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list

On 2021-03-31 3:12 a.m., Eduardo Quintana via Boost wrote:

> Hi Kostas,
>
>> Q2) What do plan offering that exceeds FFTW++ capability?
>>
>> In you file fft-2d.cpp, presumably the example use, it is
>>
>>      vector<complex<double>> FA;
>>      FFT_dim<2>(FA.begin(), FA.end(), N, e);
>>
>> This applies your own templated naive implementations of FFT. However,
>> FFTW does not wrap into this API ! You are using the plain old C interface for FFTW.
> Q2) It was mentioned before by Stefan Seefeld that Boost.Math.FFT should provide
> and FFTW wrapper. I think that's exactly what FFTW++ does. If the time frame of
> the GSOC allows it or the urgency to do that overwhelms the rest of my proposal
> then I believe that Boost.Math.FFT could provide a user interface that doesn't
> necessarily mirrors FFTW.
> When it comes to capabilities, consider that FFTW++ (to my knowledge) cannot do
> more than FFTW does, ie. it is limited by the types used internally on the FFTW
> side.
>
> I will have to take a better look at FFTW++ before giving a more educated
> opinion. By looking at the surface of the code, I see that they've built their
> own complex type based on double and it even has arithmetic operations. That's a
> great improvement with respect to FFTW's POD fftw_complex. Yet I don't see why
> they couldn't use std::complex<double>?

I don't know the FFTW++ project (just had a quick glance), but I did
write another FFTW C++ wrapper many years ago as part of the "OpenVSIP"
project (https://github.com/stefanseefeld/openvsip).

Invoking FFTW from C++ wrappers simply involves some
`reinterpret_cast<>` calls to convert between `std::complex<?>` pointers
and `fftw?_complex`. Not really a big deal. Arguably, adding custom
complex types in FFTW++ just makes matters worse, as users of that API
now have two distinct C++ complex types to deal with.

> What if I need to compute a trascendental function of an fftwpp::Complex?
> The standard library provides all kinds of mathematical functions that take
> complex<T> as arguments.
> What if I need to do a FFT on a complex number with extended precision?
>
> The FFTs I am proposing are templated on the type. So that the user is free to
> use std::complex<whathever_Real> or any user defined type for representing
> complex numbers, or even weirder Fields/Rings (see the proposal for details).
> That's a capability that FFTW/++ don't have.

One thing we did in OpenVSIP is to support different data layouts,
which, depending on your platform, can greatly affect performance. For
example, you may do FFTs on "interleaved complex" arrays or "split
complex" arrays.

It is indeed tricky to offer support for a great range of types (value
types, data layout types, etc.). What we found critical was the ability
to "dispatch" to suitable backends automatically. And that is where
modern C++ techniques can indeed make a big difference. Consider using
template meta-programming to identify whether the data types and layout
are supported by FFTW, and if so, call that, else call a different
backend. Then as an end-user I don't have to think about such choices,
and can simply trust that I get the best performance available.

(More and more computers contain powerful GPUs, so why not anticipate a
later addition of FFT implementations based on OpenCL or CUDA, for
example ? Wouldn't it be nice if the FFT API would be able to
automatically dispatch to that if that would yield better performance ?
Etc., etc., there are many things left on the table that don't involve
re-writing FFT kernels from scratch !)


Regards,

Stefan
--

       ...ich hab' noch einen Koffer in Berlin...


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
12