Convolution for non-uniform signal

[RaphaelLabeyrie]

Hello, first i'd like to thank you for your project, it is truly interesting and promising !
I am trying to use the fortran interface to increase the speed and flexibility of our team's f90 code, currently using an old FFT subroutine, and I have a general question that may be easy to answer for someone experienced.

What we are ultimately doing is a convolution of two 3D functions in real space, however they can be very inhomogeneous and thus needs a high resolution to be accurately described, hence the idea to use NUFFT.
From what I understood, one should use the type-I to go from NU data to Fourier coefficients, do the convolution there, then ideally use the Inverse NUFFT to go back to real data. The issue is that this convolution is actually part of a larger minimization algorithm and is repeated a lot of times, so probably using the Inverse NUFFT would be too inefficient for our use. Hence my question :

• I red in Inverse NUFFT by finufft #264 and other sources that type-II can be used instead, what are the conditions for it to hold true, or the precautions to take ? Does it even make sense in our case ?
  (I tried to look for it in the documentation but must have missed it or didn't understand when I saw it)

Thank you !

[ahbarnett]

Dear Raphael, Whether NUFFTs can help you do convolutions isn't clear. It depends on what *representation* your input function come in. If they are well represented by point samples on regular grids, then I cannot see any advantage of using a NUFFT: instead just do padded FFT convolutions as usual. If they are on adaptive tree-structure grids (assuming your word "inhomogeneous" means "containing a wide range of length scales at different locations"), a global Fourier representation would not be efficient (it would require too large an N), so a global NUFFT would not help either. The convolution of two *adaptive-gridded* functions is I believe a research topic. The convolution of one such function against a known Green's function, in quasi-linear time, is the topic of many papers, and called "box codes", eg https://askhamwhat.github.io/assets/postprints/2017-poisson-funextend.pdf But *two* such functions I have not seen. If there is only one "fine-grid" region in each function, you could split each func into two pieces and sum the four contributions... Good luck, Alex

…

On Wed, Jun 26, 2024 at 10:39 AM RaphaelLabeyrie ***@***.***> wrote: Hello, first i'd like to thank you for your project, it is truly interesting and promising ! I am trying to use the fortran interface to increase the speed and flexibility of our team's f90 code, currently using an old FFT subroutine, and I have a general question that may be easy to answer for someone experienced. What we are ultimately doing is a convolution of two 3D functions in real space, however they can be very inhomogeneous and thus needs a high resolution to be accurately described, hence the idea to use NUFFT. From what I understood, one should use the type-I to go from NU data to Fourier coefficients, do the convolution there, then ideally use the Inverse NUFFT to go back to real data. The issue is that this convolution is actually part of a larger minimization algorithm and is repeated a lot of times, so probably using the Inverse NUFFT would be too inefficient for our use. Hence my question : - I red in #264 <#264> and other sources that type-II can be used instead, what are the conditions for it to hold true, or the precautions to take ? Does it even make sense in our case ? (I tried to look for it in the documentation but must have missed it or didn't understand when I saw it) Thank you ! — Reply to this email directly, view it on GitHub <#469>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNZRSRAC4OU5PQHVENTBXLZJLHAFAVCNFSM6AAAAABJ6BOX6SVHI2DSMVQWIX3LMV43ERDJONRXK43TNFXW4OZWHA3DMMJVG4> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- *-------------------------------------------------------------------~^`^~._.~' |\ Alex Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

[RaphaelLabeyrie]

Dear Alex, thank you for your answer !
I'm sorry if I wasn't specific enough, we are working on molecular Density Functional Theory to predict the density distributions of fluids confined in nanoporous cavities. However, recently we have been dealing with 3D structures in which these functions are highly spatially inhomogeneous and thus we need a high resolution at specific spatial locations, since it is computationally prohibitive on an uniform grid. Is it the kind of "wide range of length scales" you were talking about ?

Note that our problem is intrinsically at equilibrium, so we do not need our discretization to evolve during the calculation ; I am not sure if it is what you meant by "adaptative grid" ?

Here's the kind of geometry we are looking at with a rough idea of the kind discretization we thought of using NUFFT for :

Bright colors represent a higher fluid density, and it is where we need to have high resolution in order to be able to obtain quantitatively accurate results. We cannot really split our simulation because at those scale the fluid-fluid molecular interaction are essential.

[ahbarnett]

"adaptive" means spatially (not over time), so, yes, this is what I meant. I think it's fair to say that a fast convolution of two such adaptive grids remains a research problem! (and it may be true that upsampling to the finest scale then FFT convolution wins for a long time... as long as you don't run out of RAM!). Good luck, Alex