Algorithms for Optics: Generalized version of the inverse fast Fourier transform is computationally efficient
The Fourier transform is a mathematical operation that allows one to determine, for example, the spatial-frequency components of an image—its inverse is straightforwardly called the inverse Fourier transform. Both of these operations are fundamental to optics and photonics. The fast Fourier transform (FFT), an algorithm that implements the Fourier transform in practical form, and its inverse algorithm, the IFFT, are used in myriad applications, from image compression to fiber-optic encoding, wavefront sensing, optical spectrum analysis, interferogram analysis, vibration control, spectroscopy, and many more.
In the example mentioned above of the close relation between a set of data and its Fourier transform, the line-spread function, which for a given lens is the cross-sectional intensity trace of the lens’ image of an infinitely thin bright straight line on a dark background, can be Fourier-transformed to produce the 1D modulation-transfer function (MTF), which is a plot that shows the ability of the lens to image spatial frequencies from zero on up.
The FFT algorithm was published in 1965. Four years later, researchers developed a more versatile, generalized version called the chirp z-transform (CZT), but a similar generalization of the IFFT algorithm has gone unsolved for 50 years. Now, Alexander Stoytchev and Vladimir Sukhoy, two researchers at Iowa State University (Ames, IA), have come up with the long-sought algorithm, called the inverse chirp z-transform (ICZT).1
Advantages for optical calculations
Like all algorithms, the ICZT is a step-by-step process that solves a problem. In this case, it maps the output of the CZT algorithm back to its input. The algorithm matches the computational complexity or speed of its counterpart, has been tested for numerical accuracy, and, unlike the IFFT, can be used with exponentially decaying or growing frequency components (see figure). This last point is important, as it can allow calculations to be done for near-field optical propagation that relies on evanescent electromagnetic waves.
Sukhoy says that the inverse algorithm is a harder problem than the original, forward algorithm and so “we needed better precision and more powerful computers to attack it.” He also says a key was seeing the algorithm within the mathematical framework of structured matrices. The accuracy of the ICZT algorithm was determined via automated testing.
The newly developed ICZT algorithm has so-called O(n log n) complexity, which matches the computational complexity of the existing CZT and IFFT algorithms—in other words, it is not more computationally complex, unlike earlier attempts to generalize the ICZT algorithm.
REFERENCE
1. V. Sukhoy and A. Stoytchev, Sci. Rep.(2019); https://doi.org/10.1038/s41598-019-50234-9.
John Wallace | Senior Technical Editor (1998-2022)
John Wallace was with Laser Focus World for nearly 25 years, retiring in late June 2022. He obtained a bachelor's degree in mechanical engineering and physics at Rutgers University and a master's in optical engineering at the University of Rochester. Before becoming an editor, John worked as an engineer at RCA, Exxon, Eastman Kodak, and GCA Corporation.