## 3 Algorithms for Toeplitz Matrix-Vector Multiplication  
### Algorithm for \(N=3\)  
Let it be necessary to calculate the matrix-vector product of the following form:  
\[ \begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\end{bmatrix} = \begin{bmatrix}t_{2}&t_{1}&t_{0}\\ t_{3}&t_{2}&t_{1}\\ t_{4}&t_{3}&t_{2}\end{bmatrix}\begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\end{bmatrix} . \tag{3}\]  
The direct method of calculating the base matrix-vector product (3) requires 9 multiplications and 6 additions. **Proposition 1**. : _To calculate the product (3), no more than 6 multiplications are required._  
Proof. : Let us introduce auxiliary matrices: the matrix \(\mathbf{P}_{3\times 6}^{(3)}\) with the final summation operations performed to obtain the \(\mathbf{Y}_{3\times 1}\) signals and the matrix \(\mathbf{T}_{6\times 3}^{(3)}\) with the initial summation operations to prepare the corresponding signals to be multiplied by the diagonal matrix \(\mathbf{D}_{6}^{(3)}\), in which the entries are the algebraic sums of entries of the Toeplitz matrix \(\mathbf{T}_{3}\). In this paper, in matrices containing summation, such as \(\mathbf{P}_{3\times 6}^{(3)}\) and \(\mathbf{T}_{6\times 3}^{(3)}\), all zeros are omitted to improve readability. \[\mathbf{P}_{3\times 6}^{(3)}= \begin{bmatrix}1&&&1&1\\ &&1&1&1\\ 1&1&1&&&\end{bmatrix} ,\]  
\[\mathbf{T}_{6\times 3}^{(3)}= \begin{bmatrix}1&&1\\ 1&&\\ 1&1&\\ &1&\\ &1&1\\ &&1\end{bmatrix} ,\]  
and  
\[\mathbf{D}_{6}^{(3)}=\text{diag}\Big{(} \begin{array}{cccc}s_{0}^{(3)},&s_{1 }^{(3)},&\ldots,&s_{5}^{(3)}\end{array} \Big{)}, \tag{4}\]  
\[s_{0}^{(3)}=t_{2},\quad s_{1}^{(3)}=-t_{2}-t_{3}+t_{4},\]  
\[s_{2}^{(3)}=t_{3},\quad s_{3}^{(3)}=-t_{1}+t_{2}-t_{3},\]  
\[s_{4}^{(3)}=t_{1},\quad s_{5}^{(3)}=t_{0}-t_{1}-t_{2}.\]  
Taking into account the introduced matrix constructions, expression (2) can be written in the following form:  
\[\mathbf{Y}_{3\times 1}=\mathbf{P}_{3\times 6}^{(3)}\mathbf{D}_{6}^{(3)}\mathbf{ T}_{6\times 3}^{(3)}\mathbf{X}_{3\times 1}, \tag{5}\]  
where  
\[\mathbf{X}_{3\times 1}=[x_{0},x_{1},x_{2}]^{T},\quad\mathbf{Y}_{3\times 1}=[y_{ 0},y_{1},y_{2}]^{T}.\]  
It is easy to see that the multiplicative complexity of calculating expression (5) is 6. The correctness of expression (5) is confirmed by the truth of the expression  
\[\mathbf{T}_{3}=\mathbf{P}_{3\times 6}^{(3)}\mathbf{D}_{6}^{(3)}\mathbf{T}_{6 \times 3}^{(3)},\]  
where \(\mathbf{T}_{3}\) is a \(3\times 3\) Toeplitz matrix (1). Expression (5) defines a reduced multiplicative complexity algorithm for calculating the matrix-vector product with a third-order Toeplitz matrix. **Remark 1**. : _The proposed algorithm (5) requires only 6 multiplications and 15 additions. In a number of practical applications, the entries of the Toeplitz matrix, i.e., \(t_{0},t_{1},\ldots,t_{4}\), are constant numbers. Then, the entries of the matrix \(\mathbf{D}_{6}^{(3)}\) (4) can be calculated in advance and stored in the calculator's memory. For this case, the number of additions in the algorithm is reduced to 9. Thus, the proposed algorithm (5) applied to the calculation of the matrix-vector product (3) reduces 3 multiplication at the expense of 3 extra additions compared to the direct method._  
Figure 1 shows the data flow diagram of the proposed algorithm (5). The initial and final additions follow from the matrices \(\mathbf{P}_{3\times 6}^{(3)}\) and \(\mathbf{T}_{3\times 6}^{(3)}\). The coefficients \(s_{i}\) are derived from the entries \(s_{i}^{(3)}\) of the matrix \(\mathbf{D}_{6}^{(3)}\). For simplicity, superscripts on variables are omitted in all figures, as it is self-evident which variable is referenced in each case. This paper presents data flow diagrams in a left-to-right orientation, where straightforward lines within the illustrations represent data transfer operations. Circles in these diagrams represent multiplication operations, with the respective numerical factors inscribed inside. Points of convergence, marked with a bold dot, indicate summation.