講演情報
[U02-P07]A Fast Direct Solver for Nonuniform Discrete Fourier Transform of Type 3★Invited Papers
*Yingzhou Li1 (1.Fudan University)
キーワード：
Fourier Transform、Radon Transform、Butterfly
Nonuniform discrete Fourier transform (NUDFT) and its inverse are widely used in various fields of scientific computing. In this talk, we introduce a novel fast direct inversion method for type 3 NUDFT. The proposed method approximates the type 3 NUDFT matrix as a product of a type 2 NUDFT matrix and an HSS matrix, where the type 2 NUDFT matrix is further decomposed as the product of an HSS matrix and uniform DFT matrix. Based on the decomposition of the type 3 NUDFT matrix, both matrix forward application and backward inversion could be accomplished in quasi-linear complexity. Our fast backward inversion can serve as a fast direct solver or as an efficient preconditioner. Additionally, we provide an error bound for the approximation under specific sample distributions. Numerical results are presented to verify the relevant theoretical properties and demonstrate the efficiency of the proposed methods.