Open Access

PROCEEDINGS

A Directional Fast Algorithm for Oscillatory Kernels with Curvelet-Like Functions

Yanchuang Cao¹, Jun Liu¹, Dawei Chen^1,*

1 Institute of Applied Physics and Computational Mathematics, Beijing, 100094, China

* Corresponding Author: Dawei Chen. Email:

The International Conference on Computational & Experimental Engineering and Sciences 2023, 25(4), 1-1. https://doi.org/10.32604/icces.2023.09272

Abstract

Interactions of multiple points with oscillatory kernels are widely encountered in wave analysis. For large scale problems, its direct evaluation is prohibitive since the computational cost increases quadratically with the number of points.
Various fast algorithms have been constructed by exploiting specific properties of the kernel function. Early fast algorithms, such as the fast multipole method (FMM) and its variants, H2-matrix, adaptive cross approximation (ACA), wavelet-based method, etc., are generally developed for kernels that are asymptotically smooth when source points and target points are well separated. For oscillatory kernels, however, the asymptotic smoothness criteria is only satisfied when the oscillation is insignificant, thus these fast algorithms are only suitable for low frequency cases. Fortunately, later the directional low rank property of highly oscillatory kernels is found, based on which various directional fast algorithms that are suitable for wideband problems are proposed, include the directional FMM, dirH2-ACA, and directional algebraic FMM, etc. They may be viewed as the generalization of early low-frequency fast algorithms to high frequency cases.
In this work, a curvelet-based method is developed by generalizing wavelet-based method to high frequency cases. Multilevel curvelet-like functions are constructed as the transform of the original nodal basis. Then the system matrix in a new non-standard form is derived under the curvelet basis, which would be nearly optimally sparse due to the directional low rank property of the oscillatory kernel. Its sparsity is further enhanced via a-posteriori compression. Finally, its log-linear computational complexity with controllable accuracy is demonstrated by numerical results.
This work provides another highly efficient wideband fast algorithm for wave problems. Moreover, it gives an explicitly-sparse representation for the system matrix, which is expected to be beneficial for the development of fast direct solvers and efficient preconditioners.

---

Keywords

---