Fast Algorithms for Digital Computation of Linear Canonical Transforms

Koc, Aykut
Öktem, Sevinç Figen
Ozaktas, Haldun M.
Kutay, M. Alper
Fast and accurate algorithms for digital computation of linear canonical transforms (LCTs) are discussed. Direct numerical integration takes O.N-2/time, where N is the number of samples. Designing fast and accurate algorithms that take O. N logN/time is of importance for practical utilization of LCTs. There are several approaches to designing fast algorithms. One approach is to decompose an arbitrary LCT into blocks, all of which have fast implementations, thus obtaining an overall fast algorithm. Another approach is to define a discrete LCT (DLCT), based on which a fast LCT (FLCT) is derived to efficiently compute LCTs. This strategy is similar to that employed for the Fourier transform, where one defines the discrete Fourier transform (DFT), which is then computed with the fast Fourier transform (FFT). A third, hybrid approach involves a DLCT but employs a decomposition-based method to compute it. Algorithms for two-dimensional and complex parametered LCTs are also discussed.


Digital computation of linear canonical transforms
Koc, Aykut; Ozaktas, Haldun M.; Candan, Çağatay; KUTAY, M. Alper (2008-06-01)
We deal with the problem of efficient and accurate digital computation of the samples of the linear canonical transform (LCT) of a function, from the samples of the original function. Two approaches are presented and compared. The first is based on decomposition of the LCT into chirp multiplication, Fourier transformation, and scaling operations. The second is based on decomposition of the LCT into a fractional Fourier transform followed by scaling and chirp multiplication. Both algorithms take similar to N...
Fixed-frequency slice computation of discrete Cohen's bilinear class of time-frequency representations
Ozgen, MT (2000-02-01)
This communication derives DFT-sample-based discrete formulas directly in the spectral-correlation domain for computing fixed-frequency slices of discrete Cohen's class members with reduced computational cost, both for one-dimensional and multidimensional (specifically two-dimensional (2-D)) finite-extent sequence cases. Frequency domain integral expressions that define discrete representations are discretized to obtain these discrete implementation formulas. 2-D ambiguity function domain kernels are chosen...
Efficient and Accurate Electromagnetic Optimizations Based on Approximate Forms of the Multilevel Fast Multipole Algorithm
Onol, Can; Karaosmanoglu, Bariscan; Ergül, Özgür Salih (2016-01-01)
We present electromagnetic optimizations by heuristic algorithms supported by approximate forms of the multilevel fast multipole algorithm (MLFMA). Optimizations of complex structures, such as antennas, are performed by considering each trial as an electromagnetic problem that can be analyzed via MLFMA and its approximate forms. A dynamic accuracy control is utilized in order to increase the efficiency of optimizations. Specifically, in the proposed scheme, the accuracy is used as a parameter of the optimiz...
Efficient Computation of Green's Functions for Multilayer Media in the Context of 5G Applications
Mittra, Raj; Özgün, Özlem; Li, Chao; Kuzuoğlu, Mustafa (2021-03-22)
This paper presents a novel method for effective computation of Sommerfeld integrals which arise in problems involving antennas or scatterers embedded in planar multilayered media. Sommerfeld integrals that need to be computed in the evaluation of spatial-domain Green's functions are often highly oscillatory and slowly decaying. For this reason, standard numerical integration methods are not efficient for such integrals, especially at millimeter waves. The main motivation of the proposed method is to comput...
On the Lagrange interpolation in multilevel fast multipole algorithm
Ergül, Özgür Salih (2006-07-14)
In this paper the Lagrange interpolation employed in the multilevel fast multipole algorithm (MLFMA) is considered as part of the efforts to obtain faster and more efficient solutions for large problems of computational electromagnetics. For the translation operator, this paper presents the choice of the parameters for optimal interpolation. Also, for the aggregation and disaggregation processes, the interpolation matrices are discussed and an efficient way of improving the accuracy by employing the poles a...
Citation Formats
A. Koc, S. F. Öktem, H. M. Ozaktas, and M. A. Kutay, “Fast Algorithms for Digital Computation of Linear Canonical Transforms,” LINEAR CANONICAL TRANSFORMS: THEORY AND APPLICATIONS, pp. 293–327, 2016, Accessed: 00, 2020. [Online]. Available: