Numerical differentiation
This PR will add functions to numerically compute derivatives of volume potentials.
Currently Existing Approach
- Near field come from pre-computed tables with derivatives of the kernel.
- Far field is obtained by taking derivatives of the local expansions.
Pros
- Given accurate pre-computation and high FMM order, the results are accurate.
Cons
- Pre-computation can be costly (
O(p^2)
times more expensive for taking up-top
-th order derivatives). - More table data to store in memory (consumes
O(p^2)
times more memory)$. - Derivatives of a kernel may have alternating signs near the target point, which can incur numerical cancellation errors.
Added Approach
-
Numerically take derivatives of the volume potential with three steps, by taking advantage of the fact that the box's directions are aligned with axes.
- Boxwise discrete Legendre transform (DLT).
- Multiply the coefficients with the differentiation matrix (Kronecker product of 1D matrices) for each box.
- Inverse DLT
Pros
- Light on pre-computation & storage.
-
O(N q^{2 dim} )
complexity (linear in the number of boxes), and trivially parallelizable.
Cons
- Loss of accuracy compared to the underlying potential (presumably worse than the existing approach).