The re-discovery of the fast Fourier transform algorithm

The discovery of the fast Fourier transform (FFT) algorithm and the subsequent development of algorithmic and numerical methods based on it have had an enormous impact on the ability of computers to process digital representations of signals, or functions. At first, the FFT was regarded as entirely new. However, attention and wide publicity led to an unfolding of its pre-electronic computer history going back to Gauss. The present paper describes the author's own involvement and experience with the FFT algorithm.The author is grateful for permission from the Association for Computing Machinery to allow the present paper to bear some similarity with the paper,How the FFT Gained Acceptance, ref. [28]     

Nonelectroactive recognition: Monitoring of perphenazine by its subsecond adsorption on an Au microelectrode by the fast fourier transform continuous cyclic voltammetric technique (FFTCCV)

A novel method for determining perphenazine in flow-injection systems has been developed in this work. The method was successfully applied for fast determination of perphenazine in its pharmaceutical formulations. Being very simple, precise, accurate, time-saving, and economical, this method has many advantages compared to all of the previously reported methods. Some investigations were also performed to find the effects of various parameters on the sensitivity of the proposed method. The conditions responsible for the performance were a pH value of 2, a scan rate value of 30 V/s, an accumulation potential of 500 mV, and an accumulation time of 0.8 s. Some of the advantages of the proposed method are as follows: the removal of oxygen from the test solution is not required anymore, the detection limit of the method is subnanomolar, and finally, the method is fast enough to determine such compounds in a wide variety of chromatographic methods. We also introduce a special computer-based numerical method to calculate the analyte signal and noise reduction. After subtraction of the background current from noise, the electrode response was calculated based on partial and total charge exchanges at the electrode surface. The integration range of currents was set for all the potential scan ranges, including oxidation and reduction of the Au surface electrode, to obtain a sensitive determination. The waveform potential was continuously applied on an Au disk microelectrode (a radius of 12.5 μm). The detention limit of the method for perphenazine was 15 pg/ml. For eight runs, the relative standard deviation of the method at 1.1 × 10⁻⁸ M was 2.1%. Published in Russian in Elektrokhimiya, 2008, Vol. 44, No. 9, pp. 1093–1102. The text was submitted by the authors in English.     

Discussion about the DCT/FFT phase-unwrapping algorithm for interferometric applications

After discussing Schofield's fast Fourier transform (FFT) algorithm, a (weighted) discrete-cosine-transform-based (DCT-based) phase-unwrapping (PU) algorithm is described. The algorithm could unwrap some high-phase-variation map which the FFT algorithm could not solve. Although the DCT algorithm is derived from Schofield's FFT PU algorithm, unlike FFT, it avoids the mirroring operation in implementing the boundary conditions so that it has higher efficiency in PU. Furthermore, in order to improve the reliability and noise robustness, we introduce the phase derivative variance (PDV) quality weight extracted from quality map into the DCT algorithm. The unwrapped results of both the computer-simulated and interferometric synthetic aperture radar (IFSAR) data demonstrate that the (weighted) DCT PU algorithm is generally effective, especially in dealing with the high-phase-variation and/or irregular-phase-distribution maps.     

加速器噪声对远红外FEL振荡器影响的模拟研究

采用FEL一维脉冲模型，针对中国原子能研究院的远红外FEL振荡器，模拟研究了加速器噪声对FEL的影响。对电子束微脉冲的时间晃动和能量波动所引起的光功率波动及光谱中心晃动进行了模拟计算，在计算中还分别考虑了噪声频率、振幅的大小产生的直接影响以及腔失谐的间接影响。     

A note on the solution of not balanced banded Toeplitz systems

A direct algorithm is presented for the solution of linear systems having banded Toeplitz coefficient matrix with unbalanced bandwidths. It is derived from the cyclic reduction algorithm, it makes use of techniques based on the displacement rank and it relies on the Morrison–Sherman–Woodbury formula. The algorithm always equals and sometimes outperforms the already known direct ones in terms of asymptotic computational cost. The case where the coefficient matrix is a block banded block Toeplitz matrix in block Hessenberg form is analyzed as well. The algorithm is numerically stable if applied to M‐matrices that are point diagonally dominant by columns. Copyright © 2007 John Wiley & Sons, Ltd.     

Spectral accuracy in fast Ewald-based methods for particle simulations

A spectrally accurate fast method for electrostatic calculations under periodic boundary conditions is presented. We follow the established framework of FFT-based Ewald summation, but obtain a method with an important decoupling of errors: it is shown, for the proposed method, that the error due to frequency domain truncation can be separated from the approximation error added by the fast method. This has the significance that the truncation of the underlying Ewald sum prescribes the size of the grid used in the FFT-based fast method, which clearly is the minimal grid. Both errors are of exponential-squared order, and the latter can be controlled independently of the grid size. We compare numerically to the established SPME method by Essmann et al. and see that the memory required can be reduced by orders of magnitude. We also benchmark efficiency (i.e. error as a function of computing time) against the SPME method, which indicates that our method is competitive. Analytical error estimates are proven and used to select parameters with a great degree of reliability and ease.     

An efficient pseudo‐spectral Legendre–Galerkin method for solving a nonlinear partial integro‐differential equation arising in population dynamics

The pseudo‐spectral Legendre–Galerkin method (PS‐LGM) is applied to solve a nonlinear partial integro‐differential equation arising in population dynamics. This equation is a competition model in which similar individuals are competing for the same resources. It is a kind of reaction–diffusion equation with integral term corresponding to nonlocal consumption of resources. The proposed method is based on the Legendre–Galerkin formulation for the linear terms and interpolation operator at the Chebyshev–Gauss–Lobatto (CGL) points for the nonlinear terms. Also, the integral term, which is a kind of convolution, is directly computed by a fast and accurate method based on CGL interpolation operator, and thus, the use of any quadrature formula in its computation is avoided. The main difference of the PS‐LGM presented in the current paper with the classic LGM is in treating the nonlinear terms and imposing boundary conditions. Indeed, in the PS‐LGM, the nonlinear terms are efficiently handled using the CGL points, and also the boundary conditions are imposed strongly as collocation methods. Combination of the PS‐LGM with a semi‐implicit time integration method such as second‐order backward differentiation formula and Adams‐Bashforth method leads to reducing the complexity of computations and obtaining a linear algebraic system of equations with banded coefficient matrix. The desired equation is considered on one and two‐dimensional spatial domains. Efficiency, accuracy, and convergence of the proposed method are demonstrated numerically in both cases. Copyright © 2012 John Wiley & Sons, Ltd.     

基于GPU和分块技术的巨幅影像快速傅里叶变换算法研究(英文)

快速傅里叶变换(FFT)是遥感影像处理的基础方法,随着高光谱、高空间和高时间分辨率遥感影像获取能力的提升,如何利用快速傅里叶变换技术快速有效地处理巨幅遥感影像是当前遥感影像处理技术中的重要环节和研究热点。傅里叶变换算法FFT是基本的图像处理算法之一,该算法可进行遥感影像的条带噪声去除、影像压缩和影像配准处理等多种用途。CUFFT函数库是NVIDIA公司提供的基于GPU的FFT算法库,FFTW是由MIT科学实验室计算机组在PC平台上开发的基于CPU的FFT算法,是目前在基于CPU的运行速度最快的FFT算法函数库,这两种实现共有的问题是当可用内存或显存的容量小于图像容量时,就会出现内存或显存溢出。针对这种问题,提出了一种基于GPU和分块技术的巨幅遥感影像快速傅里叶变换(huge remote fast Fourier transform,HRFFT)算法。通过对CUDA的CUFFT函数库中的FFT算法进行改进,解决了巨幅图像内存或显存溢出的问题,并结合HJ-1A卫星的CCD影像,通过实验与其他算法进行了对比,证明了该方法的合理性。在实际应用中,利用本文提出的HRFFT算法,改善了影像处理的效果,提高了遥感影像的质量,同时加快了影像处理的速度,节省了计算时间,取得了较好的效果。     

基于JASMIN框架的FFT并行解法器及其应用

为解决并行应用程序使用FFTW(Fastest Fourier Transform in the West)并行软件包所面临的计算规模难以扩展、数据结构变动大、实现不同数据结构间通信难度大、接口不确定等问题,在JASMIN框架内设计实现FFT并行解法器.该解法器封装了数据分布存储、数据通信等并行计算细节,通过重新分布存储数据,调用一维FFT变换实现高维FFT的并行计算,并提供规范接口,支撑用户简便地实现FFT的并行计算.数值测试表明,该解法器具有很好的并行性能.该解法器已应用于激光等离子体成丝不稳定性的数值模拟并行程序,它在2048个处理器上的并行效率可达80%以上.     

基于傅里叶变换光谱技术的Zoom-FFT算法研究

在分析经典的Zoom-FFT算法基础上,提出一种基于傅里叶变换光谱技术的Zoom-FFT算法,用matlab仿真常规FFT算法和Zoom-FFT算法,对不同采样步长的干涉条纹进行数据处理,通过反演出的光谱曲线图和原始光谱曲线图可以看出:采样步长小于20 m时,FFT和Zoom-FFT算法都可以反演出光谱;而当采样步长大于20 m且小于33.3 m时,FFT算法未能反演出光谱,而Zoom-FFT算法仍然可以反演出光谱。