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

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

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

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

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

Eduardo Quintana via Boost said: (by the date of Tue, 30 Mar 2021 17:01:43 +0000)

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.

I think this is a mistake. Best approach is to not duplicate existing work, especially when it is written by the experts in the field. Of course major design goal is to design a fftw wrapper in such a way that following is possible:

What I want to bring to Boost.Math are "Generic Programming" FFT algorithms for situations that FFTW can't handle.

So that for the types handled by fftw the fftw library would be used. And for other types, such as Matrices or Clifford algebra, the more generic solution will be used. However the first priority in GSOC in my opinion should be: 1. wrapping fftw and 2. designing a general interface that allows wrapping all the other types Then, if time permits add FFT for one of the other "fancy" types. Stefan Seefeld via Boost said: (by the date of Wed, 31 Mar 2021 08:46:17 -0400)

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.

Yes, completely agree. I think, that since this work is done on par with boost::multiprecision, then only the C++ fundamental types and boost::multiprecision types should be supported. With later addition (see point 2. above) of types constructed from them, such as matrices.

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.

Yes, this is a very important point.

Etc., etc., there are many things left on the table that don't involve re-writing FFT kernels from scratch !)

Agree. best regards Janek -- 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)

Hi Eduardo, On 2021-03-31 2:58 p.m., Eduardo Quintana via Boost wrote:

Hi Janek,

...

I think this is a mistake. Best approach is to not duplicate existing work, especially when it is written by the experts in the field. You are right. But I cannot say that the main goal is to design an FFTW wrapper.

I agree, that wouldn't sound very appealing. I think the best way to look at it is to design a modern C++ FFT API, with a big "I", i.e. an emphasis on "interface", and to test that API by binding it to one (or two, if time permits) existing libraries. Testing such an interface has two sides: 1) Is the API accepted by users, i.e. is it convenient to use ? 2) Is the API implementable, i.e. can it be seamlessly and efficiently bound to existing implementations ? (To test this carefully this requires more than one backend, to avoid the API adopting idiosyncrasies from the first backend it was developed around.) In a nutshell, the above involves a substantial amount of work. Describing it as "design an FFTW wrapper" wouldn't do it justice. :-) And by the way, I would suggest the exact same approach for the `Boost.XML` proposal, for exactly the same reasons. (As it happens I tried this approach many years ago. Then my own interests shifted, and I could never finish the project. If anyone is interested, feel free to steal ideas from https://github.com/stefanseefeld/boost.xml.) Best, Stefan -- ...ich hab' noch einen Koffer in Berlin...

Hi Stefan, On Wed, Mar 31, 2021 at 03:54:57PM -0400, Stefan Seefeld via Boost wrote:

I agree, that wouldn't sound very appealing. I think the best way to look at it is to design a modern C++ FFT API, with a big "I", i.e. an emphasis on "interface", and to test that API by binding it to one (or two, if time permits) existing libraries.

Testing such an interface has two sides:

1) Is the API accepted by users, i.e. is it convenient to use ?

2) Is the API implementable, i.e. can it be seamlessly and efficiently bound to existing implementations ? (To test this carefully this requires more than one backend, to avoid the API adopting idiosyncrasies from the first backend it was developed around.)

Your point of view is very mature. I am enthusiast to adhere to this idea. Eduardo

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

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 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 < boost@lists.boost.org> 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 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

On Apr 2, 2021, at 11:18, Eduardo Quintana via Boost wrote:

Hello,

Thanks to all the feedback that I have had in the previous days I've finished version 2.0 of the Gsoc proposal. That you can find here: https://github.com/Lagrang3/gsoc-2021/releases/download/v2.0/gsoc.pdf

Hi Eduardo, It is clear that you have put a good effort into the proposal and that your understanding of underlying concepts is excellent. I would like to offer a comment on a few aspects of the proposal. Not to criticise you, but in the hope that it will increase the chances of funding the proposal and bring benefits to our beloved Boost. 1) The discussion of NTT. While boost.multiprecision can potentially be used to implement the Zp ring, it currently does not contain any such construct. Reading further, there is nothing about NTT in the deliverables. If the idea is peripheral to the GSOC project, then it does not need to be mentioned at all. Note that even the PARI library does not yet have NTT implemented and for them I think it is a high priority (must be a very hard problem). 2) Section 2.2. Most people know the Convolution Theorem, but at least myself do not know anything about the Rader algorithm. Since you propose to implement it, why not describe it in that Section, maybe instead of the Convolution Theorem. 3) Section 2.3. You say: "FFTW was designed to compute DFT for complex numbers, like in Example 1. There is no support for DFT in the broader sense of Definition 1. For example, we cannot use FFTW to compute the NTTs described in the Example 2." Since you are not going to be able to solve this problem in this GSOC project, it is better to not make such comments. 4) Section 2.3. "scalability of the parallel MPI routines for computing 3-dimensional DFT" , "domain decomposition" - here again I think it is worth to remember that if the project is not going to address domain decomposition, then it is better to not talk about it. 5) Since this project is done under Boost, it seems logical to make sure the proposed code work with Boost.Math complex types. Is this not part of the plan? Why no word about it in the deliverables? Best Regards, Kostas

Hi Janek, Thanks for the detailed review of the proposal. I will fix the text accordingly.

...

https://github.com/Lagrang3/P2.16_Parallel_FFT/tree/master/solution

this link does not work.

That repository is a fork from private, I am not able to publish it. But here is a copy of its contents https://github.com/Lagrang3/SISSA-Parallel_FFT Eduardo

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