A fast algorithm for computing matrix-vector products in the problem of function decomposition into Fourier series on a circle

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.