search

flatironinstitute / FMM3D

Flatiron Institute Fast Multipole Libraries --- This codebase is a set of libraries to compute N-body interactions governed by the Laplace and Helmholtz equations, to a specified precision, in three dimensions, on a multi-core shared-memory machine.
https://fmm3d.readthedocs.io
Other
100 stars 38 forks source link

Possibility to reuse data structures when changing source strengths but not locations #59

Closed morse129 closed 2 months ago

morse129 commented 2 months ago

First of all, thank you for the very nice, easy-to-use library.

I was wondering if it is possible to somehow retain the tree data structures when calling the Laplace FMM evaluation (lfmm3d_t_d_g_vec) if I am providing difference source dipole strengths but the location and number of the sources and targets have not changed. Specifically, I am solving a boundary integral equation where I use the FMM to repeatedly evaluate the matrix-vector product in an iterative linear algebra solver. This leads to a situation where only the source strengths are changing as the solver converges, so I suppose it would be nice to remove the overhead of setting up the tree structures, if possible.

If this overhead cost is minimal or if there's some other possibility I'm missing, please let me know!

Thanks, Nick

ahbarnett commented 2 months ago

I believe the tree construction is minimal (less than a few %) of the total cost, so you wouldn't gain much. (I'll let the authors correct me.) Keep in mind you can send in a stack of strengths together, which has quite a good speedup (factor of a few), but of course for a single RHS in an iterative setting you can't exploit this. However, you could if you were solving multiple RHS together (and you have the RAM), eg via GMRES or Block GMRES... Good luck, Alex

On Fri, Sep 6, 2024 at 9:18 AM Nick Morse @.***> wrote:

First of all, thank you for the very nice, easy-to-use library.

I was wondering if it is possible to somehow retain the tree data structures when calling the Laplace FMM evaluation (lfmm3d_t_d_g_vec) if I am providing difference source dipole strengths but the location and number of the sources and targets have not changed. Specifically, I am solving a boundary integral equation where I use the FMM to repeatedly evaluate the matrix-vector product in an iterative linear algebra solver. This leads to a situation where only the source strengths are changing as the solver converges, so I suppose it would be nice to remove the overhead of setting up the tree structures, if possible.

If this overhead cost is minimal or if there's some other possibility I'm missing, please let me know!

Thanks, Nick

— Reply to this email directly, view it on GitHub https://github.com/flatironinstitute/FMM3D/issues/59, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACNZRSWJJUQQJML2JHNEJALZVGTSVAVCNFSM6AAAAABNYSOUZWVHI2DSMVQWIX3LMV43ASLTON2WKOZSGUYTANBRHE3DINY . 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

lu1and10 commented 2 months ago

I agree with @ahbarnett, the tree construction and memory allocation/initialization time is less than 10% of the main fmm call time for Laplace problem potential only with 5 digit accuracy, for more digits it's less than 5%. If one need more digits, gradient, hessian, or with helm, stokes or maxwell problems. The percentage of the time tree construction spent is much less. @mrachh may have more insight.

morse129 commented 2 months ago

Thanks for the information; I'm glad to know that the construction is not too expensive. I do have multiple source strengths per iteration due to the nature of my solver, so I've added as much stacking and data re-use as possible, which I found to speed up the computations quite a bit.

Best regards, Nick