arrow
Volume 41, Issue 6
A Fast Free Memory Method for an Efficient Computation of Convolution Kernels

Matthieu Aussal & Marc Bakry

J. Comp. Math., 41 (2023), pp. 1093-1116.

Published online: 2023-11

Export citation
  • Abstract

We introduce the Fast Free Memory method (FFM), a new implementation of the Fast Multipole Method (FMM) for the evaluation of convolution products. The FFM aims at being easier to implement while maintaining a high level of performance, capable of handling industrially-sized problems. The FFM avoids the implementation of a recursive tree and is a kernel independent algorithm. We give the algorithm and the relevant complexity estimates. The quasi-linear complexity enables the evaluation of convolution products with up to one billion entries. We illustrate numerically the capacities of the FFM by solving Boundary Integral Equations problems featuring dozen of millions of unknowns. Our implementation is made freely available under the GPL 3.0 license within the Gypsilab framework.

  • AMS Subject Headings

65T50, 65Z05, 65R20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-41-1093, author = {Aussal , Matthieu and Bakry , Marc}, title = {A Fast Free Memory Method for an Efficient Computation of Convolution Kernels}, journal = {Journal of Computational Mathematics}, year = {2023}, volume = {41}, number = {6}, pages = {1093--1116}, abstract = {

We introduce the Fast Free Memory method (FFM), a new implementation of the Fast Multipole Method (FMM) for the evaluation of convolution products. The FFM aims at being easier to implement while maintaining a high level of performance, capable of handling industrially-sized problems. The FFM avoids the implementation of a recursive tree and is a kernel independent algorithm. We give the algorithm and the relevant complexity estimates. The quasi-linear complexity enables the evaluation of convolution products with up to one billion entries. We illustrate numerically the capacities of the FFM by solving Boundary Integral Equations problems featuring dozen of millions of unknowns. Our implementation is made freely available under the GPL 3.0 license within the Gypsilab framework.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2202-m2021-0324}, url = {http://global-sci.org/intro/article_detail/jcm/22105.html} }
TY - JOUR T1 - A Fast Free Memory Method for an Efficient Computation of Convolution Kernels AU - Aussal , Matthieu AU - Bakry , Marc JO - Journal of Computational Mathematics VL - 6 SP - 1093 EP - 1116 PY - 2023 DA - 2023/11 SN - 41 DO - http://doi.org/10.4208/jcm.2202-m2021-0324 UR - https://global-sci.org/intro/article_detail/jcm/22105.html KW - Convolution product, Fast multipole method, Boundary integral equations, Open-source. AB -

We introduce the Fast Free Memory method (FFM), a new implementation of the Fast Multipole Method (FMM) for the evaluation of convolution products. The FFM aims at being easier to implement while maintaining a high level of performance, capable of handling industrially-sized problems. The FFM avoids the implementation of a recursive tree and is a kernel independent algorithm. We give the algorithm and the relevant complexity estimates. The quasi-linear complexity enables the evaluation of convolution products with up to one billion entries. We illustrate numerically the capacities of the FFM by solving Boundary Integral Equations problems featuring dozen of millions of unknowns. Our implementation is made freely available under the GPL 3.0 license within the Gypsilab framework.

Aussal , Matthieu and Bakry , Marc. (2023). A Fast Free Memory Method for an Efficient Computation of Convolution Kernels. Journal of Computational Mathematics. 41 (6). 1093-1116. doi:10.4208/jcm.2202-m2021-0324
Copy to clipboard
The citation has been copied to your clipboard