Skip to content

Numerical differentiation

Xiaoyu Wei requested to merge numerical-differentiation into master

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-to p-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.

    1. Boxwise discrete Legendre transform (DLT).
    2. Multiply the coefficients with the differentiation matrix (Kronecker product of 1D matrices) for each box.
    3. 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).

Merge request reports

Loading