Digital Signal Processing (DSP)-Oriented Reduced-Complexity Algorithms for Calculating Matrix–Vector Products with Small-Order Toeplitz Matrices

Abstract

Toeplitz matrix–vector products are used in many digital signal processing applications. Direct methods for calculating such products require N2 multiplications and N(N−1) additions, where N denotes the order of the Toeplitz matrix. In the case of large matrices, this operation becomes especially time intensive. However, matrix–vector products with small-order Toeplitz matrices are of particular interest because small matrices often serve as kernels in modern digital signal processing algorithms. Perhaps reducing the number of arithmetic operations when calculating matrix–vector products in the case of small Toeplitz matrices gives less effect than of large ones, but this problem exists, and it needs to be solved. The traditional way to calculate such products is to use the fast Fourier transform algorithm. However, in the case of small-order matrices, it is advisable to use direct factorization of Toeplitz matrices, which leads to a reduction in arithmetic complexity. In this paper, we propose a set of reduced-complexity algorithms for calculating matrix–vector products with Toeplitz matrices of order N=3,4,5,6,7,8,9. The main emphasis will be on reducing multiplicative complexity since multiplication in most cases is more time-consuming than addition. This paper also provides assessments of the implementation of the developed algorithms on FPGAs.

Keywords

• Toeplitz matrix
• matrix–vector product
• multiplication complexity