Reduced-Rank Approximations to the Far-Field Transform in the Gridded Fast Multipole Method

Area of Science:

• Computational electromagnetics
• Numerical analysis
• Applied mathematics

Background:

• The Fast Multipole Method (FMM) offers computational efficiency for large-scale problems.
• Transformations between plane-wave and pressure expansions are a computational bottleneck in FMM, especially for large finest-level groups.
• Existing methods like FFT convolution and reduced-rank approximations have limitations.

Purpose of the Study:

• To reduce the computational cost associated with transformations in the Fast Multipole Method (FMM).
• To improve the accuracy and efficiency of reduced-rank approximations for FMM operators.
• To investigate the combined use of Adaptive Cross Approximation (ACA) and Singular Value Decomposition (SVD) for FMM transformations.

Main Methods:

• Utilized adaptive cross approximation (ACA) to represent forward and adjoint far-field transformation operators in FMM.
• Applied a truncated Singular Value Decomposition (SVD) for recompressing ACA-approximated operators.
• Focused on transformations between plane-wave expansions and pressure distributions within the FMM framework.

Main Results:

• The combination of ACA with a reduced, truncated SVD significantly decreased approximation error.
• The proposed method achieved approximation error comparable to a full-scale truncated SVD.
• The computational efficiency of ACA matrix assembly was maintained without degradation.

Conclusions:

• A hybrid ACA-SVD approach effectively reduces FMM computational costs associated with complex transformations.
• This method provides a practical solution for improving FMM performance on large datasets.
• The findings offer a more efficient and accurate FMM implementation for computational electromagnetics.