摘要
In this paper, we propose a fast algorithm for computing the DGFT (Discrete Generalized Fourier Transforms) on hexagon domains [6], based on the geometric properties of the domain. Our fast algorithm (FDGFT) reduces the computation complexity of DGFT from O(N4) to O(N2 log N). In particulary, for N =2^P23^P34^P45^P56^P6, the floating point computation working amount equals to(17/2P2 + 16p3 + 135/8p4 + 2424/25p5 + 201/2P6)3N^2. Numerical examples are given to access our analysis.
In this paper, we propose a fast algorithm for computing the DGFT (Discrete Generalized Fourier Transforms) on hexagon domains [6], based on the geometric properties of the domain. Our fast algorithm (FDGFT) reduces the computation complexity of DGFT from O(N4) to O(N2logN). In particulary, for N = 2P23P34P45P56P6, the floating point computation working amount equals to (17/2P-2 + 16p3 + 135/8P4 + 2424/25p5 + 201/2p6)3N2. Numerical examples are given to access our analysis.
出处
《计算数学》
CSCD
北大核心
2004年第3期351-366,共16页
Mathematica Numerica Sinica
基金
国家重点基础研究项目(G19990328)
国家基金委项目(60173021)资助
