СИСТЕМЫ АНАЛИЗА И ОБРАБОТКИ ДАННЫХ

Значительный интерес состоит в разработке и исследовании возможностей применения быстрых алгоритмов для вычисления матрично-векторных произведений в контексте преобразования на круге, что позволит существенно улучшить эффективность вычисления моментов Цернике. В статье рассмотрен эффективный способ сжатия матриц преобразования для функций Цернике на основе алгоритма быстрого дискретного преобразования Фурье (БДПФ) и метода экстракомпонент. Высокая производительность алгоритма достигается за счет перехода от исходной матрицы к матрице с разреженным портретом посредством специальной процедуры, реализованной на основе дискретного преобразования Фурье. Предполагается, что сжатие матрицы выполняется однократно на подготовительном этапе, тогда как количество преобразуемых векторов таково, что вычислительными затратами подготовительного этапа можно пренебречь. Такой подход сокращает время счета матрично-векторного произведения на вычислительном этапе вследствие исключения близких по модулю к нулю элементов сжатой матрицы. Разработанный алгоритм позволяет экономично умножать исходную матрицу преобразования на вектор с использованием БДПФ, что снижает оценку вычислительной трудоемкости метода в целом. Подготовительный этап потребует выполнения порядка операций, в то время как на вычислительном этапе необходимо выполнить арифметических действий, что значительно меньше оценки для прямого способа расчета матрично-векторного произведения. Результаты вычислительных экспериментов показали устойчивость, корректность

и быстродействие процедур, что позволяет сократить время вычислений на несколько порядков по сравнению с прямым умножением матрицы преобразования на вектор для решения задачи разложения функций в ряды по базису Цернике.

1. Cooley J., Tukey J. An algorithm for the machine calculation of complex Fourier series // Mathematics of Computation. – 1965. – Vol. 19 (90). – P. 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). – P. 377–384.

3. Noll R.J. Zernike polynomials and atmospheric turbulence // Journal of the Optical Society of America. – 1976. – Vol. 66 (3). – P. 207–211.

4. Terekhov A.V. An extra-component method for evaluating fast matrix-vector multiplication with special functions // Numerical Algorithms. – 2022. – Vol. 92. – P. 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. – P. 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. A theoretical comparison among recursive algorithms for fast computation of Zernike moments using the concept of time complexity / N. Bastani, A. Vard, M. Jabalameli, V. Bastani // American Journal of Computational Mathematics. – 2021. – Vol. 11. – P. 304–326.

9. Kintner E.C. A recurrence relation for calculating the Zernike polynomials // Optica Acta: International Journal of Optics. – 1976. – Vol. 23 (6). – P. 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. – P. 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). – P. 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. – P. 731–742.

13. Крылов В.И. Приближенное вычисление интегралов. – М.: Физматгиз, 1959. – 328 с.

14. Анго A. Математика для электро- и радиоинженеров / с предисл. Л. Де Бройля. – М.: Наука, 1965. – 780 с.

15. Суетин П.К. Классические ортогональные многочлены. – 2-е изд., доп. – М.: Наука, 1979. – 416 с.