###### Abstract  
Toeplitz matrix-vector products are used in many digital signal processing applications. Direct methods for calculating such products require \(N^{2}\) 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.  
Toeplitz matrix; matrix-vector product; multiplication complexity 2024202452  
on embedding such a matrix in a \(2N\times 2N\) circulant matrix and calculating the matrix-vector product with the resulting matrix. Therefore, Toeplitz matrix-vector multiplication can be calculated as the product of a circulant matrix by a vector. This product can be computed using fast Fourier transform (FFT) algorithms [43]. These algorithms lead to data redundancy and require \(O(NlogN)\) operations [44]. However, this approach involves rather complicated housekeeping and a relatively large number of multiplications and additions. What is more, these operations are performed on complex numbers.  
Alternative efficient algorithms for multiplying a Toeplitz/Hankel matrix by a vector not based on FFT were discussed in [45, 46]. Both of these methods, based on the Karatsuba multiplication method [47], have a computational complexity of \(O(N^{log2})\) multiplications and use only real arithmetic. One way or another, well-known publications mainly describe general approaches to rationalizing the computations of Toeplitz matrix-vector products and practically do not consider examples of constructing such algorithms for specific \(N\). At the same time, developing such algorithms for specific \(N\) is of independent interest since such algorithms can be used as building blocks, contributing to unification in designing more complex algorithms.  
In this article, we propose and describe in detail new rationalized algorithms for matrix-vector multiplication for Toeplitz matrices of orders \(N=3,4,5,6,7,8,9\), which minimize the multiplication complexity compared to the conventional direct method, at the cost of some increase in additions. We emphasize that the reduced-complexity algorithm for the product of a matrix and a vector with a Toeplitz matrix for \(N=2\) is well-known in the literature and therefore is not considered here.  
The remainder of this paper is organized as follows. Section 2 explains the preliminary information about Toeplitz matrices. Section 3 describes the proposed algorithms for orders from \(N=3\) to \(N=9\). Section 4 evaluates our algorithms in terms of computational cost. Section 5 concludes this paper.