ANALYSIS AND DATA PROCESSING SYSTEMS
Print ISSN: 2782-2001
Online ISSN: 2782-215X
A significant interest lies in the development and exploration of the potential application of fast algorithms for computing matrix-vector products in the context of transforms on the circle, which will substantially improve the efficiency of calculating Zernike moments. This paper presents an efficient method for compressing transform matrices for Zernike functions based on the Fast Discrete Fourier Transform (FDFT) algorithm and the extra-component method. The proposed approach enables efficient multiplication of the initial transform matrix by a vector using FDFT, significantly reducing the computational complexity of the overall method. It is assumed that matrix compression is performed only once during the preparatory stage, while the number of vectors to be transformed is sufficiently large for the computational costs of this stage to be negligible. This approach reduces the computation time of the matrix-vector product during the processing stage by eliminating matrix elements with magnitudes close to zero. The preparatory stage will require performing of the order of operations, while the computational stage will involve performing arithmetic operations, which is significantly less than the estimate for the direct method of calculating the matrix-vector product. Computational experiments demonstrate the stability, accuracy, and efficiency of the procedures, which makes it possible to substantially reduce the computation time by several orders of magnitude compared to direct matrix-vector multiplication for the current problem of decomposing functions into series according to the Zernike basis.
Zelenchuk Nikita A.
Terekhov Andrew Valeryevich
1. Cooley J., Tukey J. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 1965, vol. 19 (90), pp. 297–301.
2. Zernike F., Stratton F.J.M. Diffraction theory of the knife-edge test and its improved form, the phase-contrast method. Monthly Notices of the Royal Astronomical Society, 1934, vol. 94 (5), pp. 377–384.
3. Noll R.J. Zernike polynomials and atmospheric turbulence. Journal of the Optical Society of America, 1976, vol. 66 (3), pp. 207–211.
4. Terekhov A.V. An extra-component method for evaluating fast matrix-vector multiplication with special functions. Numerical Algorithms, 2022, vol. 92, pp. 2189–2217.
5. Born M., Wolf E. Principles of optics. New York, Pergamon Press, 1983. 854 p.
6. Bezdidko S.N. The use of Zernike polynomials in optics. Soviet Journal of Optical Technology, 1974, vol. 41, pp. 425–429.
7. Niu K., Tian C. Zernike polynomials and their applications. Journal of Optics, 2022, vol. 24 (12), p. 123001. DOI: 10.1088/2040-8986/ac9e08.
8. Bastani N., Vard A., Jabalameli M., Bastani V. A theoretical comparison among recursive algorithms for fast computation of Zernike moments using the concept of time complexity. American Journal of Computational Mathematics, 2021, vol. 11, pp. 304–326.
9. Kintner E.C. A recurrence relation for calculating the Zernike polynomials. Optica Acta: International Journal of Optics, 1976, vol. 23 (6), pp. 499–500. DOI: 10.1080/713819279.
10. Deng A., Wei C., Gwo C.-Y. Stable, fast computation of high-order Zernike moments using a recursive method. Pattern Recognition, 2016, vol. 56, pp. 16–25. DOI: 10.1016/j.patcog.2016.02.014.
11. Prata A., Rusch W.V.T. Algorithm for computation of Zernike polynomials expansion coefficients. Applied Optics, 1989, vol. 28 (4), pp. 749–754. DOI: 10.1364/AO.28.000749.
12. Chong C.-W., Paramesran R., Mukundan R. A comparative analysis of algorithms for fast computation of Zernike moments. Pattern Recognition, 2003, vol. 36, pp. 731–742.
13. Krylov V.I. Priblizhennoe vychislenie integralov [Approximate calculation of integrals]. Moscow, Fizmatgiz Publ., 1959. 328 p.
14. Angot A. Matematika dlya elektro- i radioinzhenerov [Mathematics for electrical and radio engineers]. Moscow, Nauka Publ., 1965. 780 p. (In Russian).
15. Suetin P.K. Klassicheskie ortogonal'nye mnogochleny [Classical orthogonal polynomials]. 2nd ed., rev. Moscow, Nauka Publ., 1979. 416 p.
Zelenchuk N.A., Terekhov A.V. Bystryi algoritm vychisleniya matrichno-vektornykh proizvedenii v zadache razlozheniya funktsii v ryady Fur'e na kruge [A fast algorithm for computing matrix-vector products in the problem of function decomposition into Fourier series on a circle]. Sistemy analiza i obrabotki dannykh = Analysis and Data Processing Systems, 2024, no. 4 (96), pp. 21–34. DOI: 10.17212/2782-2001-2024-4-21-34.
