English

FMMA

任意次元の変数 $x_i$, $y_j$ と任意の関数 $f$ について、

$$c_i = \sum_{j} w_j f(x_i, y_j)$$

を高速に計算するためのライブラリ

インストール

C++

cmakeを用いた場合、以下のようにしてインストール出来る

cmake -B build
cmake --build build
cmake --install build

BLASを用いて高速化する場合は、build時に

cmake -B build -DFMMA_USE_BLAS=ON

とする

Python

pip を用いてインストール可能

pip install pyfmma

もしくは

pip install git+https://github.com/fockl/FMMA.git

cmakeを用いてより詳しく条件を設定したい場合は

cmake -B build
cmake --build build

をした後 python 側で

import build.pyfmma

をする

使い方

C++の場合、

fmma::FMMA<double, 3> fmma;
fmma.set_fn([](auto x, auto y){return 1.0/(x[0]-y[0]);}); 
fmma.set_solver_type("fmm");
fmma.solve(target, source_weight, source, ans);

のようにして使用する

詳しくはtutorial参照

現在はsolverとしてexact, nrnmm, tree, fmmが実装済み

$O(n(x)) = O(n(y)) = O(N)$の時の計算量は以下の通り：

type	computatoin cost
exact	$O(N^2)$
nrnmm	$O(N\sqrt{N})$
tree	$O(N\log{N})$
fmm	$O(N)$

ベンチマーク結果

github-actions を用いたベンチマーク結果：

1次元の場合:

2次元の場合:

参考文献

• W. Fong and E. Darve. The black-box fast multipole method. Journal of Computational Physics, 228 (2009).

FMMA(English)

FMMA is a library to calculate fastly

$$c_i = \sum_{j} w_j f(x_i, y_j)$$

for arbitrary function $f$ and variables $x_i$, $y_j$ in arbitrary dimension.

Benchmark results using github-actions are follows :

1D:

2D:

Install(English)

C++

You can install this library as follows if cmake is used:

cmake -B build
cmake --build build
cmake --install build

If BLAS is required, define an argument like:

cmake -B build -DFMMA_USE_BLAS=ON

Python

You can install via pip

pip install pyfmma

or

pip install git+https://github.com/fockl/FMMA.git

If you want to set details with using cmake,

cmake -B build
cmake --build build

and in python

import build.pyfmma

Usage(English)

In C++, you can use FMMA as

fmma::FMMA<double, 3> fmma;
fmma.set_fn([](auto x, auto y){return 1.0/(x[0]-y[0]);}); 
fmma.set_solver_type("fmm");
fmma.solve(target, source_weight, source, ans);

For more details, see tutorials

exact, nrnmm, tree, fmm are now implemented as solver.

when $O(n(x)) = O(n(y)) = O(N)$, the computational cost are as follows:

type	computatoin cost
exact	$O(N^2)$
nrnmm	$O(N\sqrt{N})$
tree	$O(N\log{N})$
fmm	$O(N)$

Benchmark results

Benchmark results using github-actions are as follows:

1D:

2D:

References

• W. Fong and E. Darve. The black-box fast multipole method. Journal of Computational Physics, 228 (2009).