## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=5\)  
Let it be necessary to calculate the matrix-vector product of the following form:  
\[\begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4}\end{bmatrix}=\begin{bmatrix}t_{4}&t_{3}&t_{2}&t_{1}&t_{0}\\ t_{5}&t_{4}&t_{3}&t_{2}&t_{1}\\ t_{6}&t_{5}&t_{4}&t_{3}&t_{2}\\ t_{7}&t_{6}&t_{5}&t_{4}&t_{3}\\ t_{8}&t_{7}&t_{6}&t_{5}&t_{4}\end{bmatrix}\begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{bmatrix}. \tag{9}\]  
The direct method of calculating this product requires 25 multiplications and 20 additions.  
**Proposition 3**.: _To calculate the product (9), no more than 14 multiplications are required._  
Proof.: Let us introduce some auxiliary matrices, pre- and postaddition matrices:  
\[\mathbf{P}_{11\times 14}^{(5)}=\mathbf{I}_{4}\oplus\mathbf{I}_{3} \otimes\mathbf{P}_{2\times 3}^{(4)}\oplus 1,\] \[\mathbf{T}_{14\times 11}^{(5)}=\mathbf{I}_{4}\oplus\mathbf{I}_{3} \otimes\mathbf{T}_{3\times 2}^{(4)}\oplus 1,\] \[\mathbf{T}_{11\times 5}^{(5)}=\begin{bmatrix}1&&&&\\ 1&&&1\\ 1&1&&&\\ &1&&1&\\ &1&&&1\\ &&1&&&\\ &&&1&\\ &&&&1\\ 1&&&1&\\ \end{bmatrix},\]  
and a diagonal matrix of multiplication factors:  
\[\mathbf{D}_{14}^{(5)}=\text{diag}\Big{(}s_{0}^{(5)},\;\;s_{1}^{(5)},\;\;\ldots, \;\;s_{13}^{(5)}\Big{)}, \tag{10}\]  
\[s_{0}^{(5)}=-t_{4}-t_{7}+t_{8}+w_{3}^{(5)},\;\;\;s_{1}^{(5)}=t_{4},\;\;\;s_{2} ^{(5)}=t_{6},\]  
\[s_{3}^{(5)}=t_{7},\;\;\;s_{4}^{(5)}=w_{0}^{(5)},\;\;\;s_{5}^{(5)}=t_{3},\;\;\; s_{6}^{(5)}=w_{2}^{(5)},\]  
\[s_{7}^{(5)}=t_{6}-t_{5}-t_{4}+t_{3}-t_{7},\;\;\;s_{8}^{(5)}=t_{5}-t_{3},\]  
\[s_{9}^{(5)}=t_{4}-w_{2}^{(5)}+w_{3}^{(5)},\;\;\;s_{10}^{(5)}=t_{2}-t_{5}+w_{1} ^{(5)},\]  
\[s_{11}^{(5)}=t_{1}-t_{3},\;\;\;s_{12}^{(5)}=t_{0}-t_{2}+w_{1}^{(5)},\;\;\;s_{1 3}^{(5)}=t_{5},\]  
Figure 2: Data flow diagram of the algorithm (8) for \(N=4\).  
where \[w_{0}^{(5)}=-t_{3}+t_{4}, w_{1}^{(5)}=-t_{1}-w_{0}^{(5)}, w_{2}^{(5)}=t_{2}-t_{3},\] \[w_{3}^{(5)}=-t_{5}-t_{6},\]  
and the sign \(\oplus^{\prime\prime}\) denotes the direct sum of matrices [50].  
Considering the matrix constructions introduced earlier, expression (9) can be reformulated as follows:  
\[\mathbf{Y}_{5\times 1}=\mathbf{P}_{5\times 1}^{(5)}\mathbf{P}_{11\times 14}^{(5) }\mathbf{D}_{14}^{(5)}\mathbf{T}_{14\times 11}^{(5)}\mathbf{T}_{11\times 5}^{(5)} \mathbf{X}_{5\times 1}, \tag{11}\]  
where  
\[\begin{array}{l}\mathbf{X}_{5\times 1}=[x_{0},x_{1},x_{2},x_{3},x_{4}]^{T}, \\ \mathbf{Y}_{5\times 1}=[y_{0},y_{2},y_{3},y_{3},y_{4}]^{T}.\end{array}\]  
It is easy to see that the multiplicative complexity of computing expression (11) is 14. The correctness of expression (11) is confirmed by the truth of the following expression:  
\[\mathbf{T}_{5}=\mathbf{P}_{5\times 11}^{(5)}\mathbf{P}_{11\times 14}^{(5)} \mathbf{D}_{14}^{(5)}\mathbf{T}_{14\times 11}^{(5)}\mathbf{T}_{11\times 5}^{(5)},\]  
where \(\mathbf{T}_{5}\) is a \(5\times 5\) Toeplitz matrix. Expression (11) defines a reduced multiplicative complexity algorithm for calculating the matrix-vector product with a fifth-order Toeplitz matrix.  
**Remark 3**.: _The proposed algorithm requires only 14 multiplications and 45 additions. This gives, relative to the direct method, a reduction of 11 multiplications at the cost of an additional 25 additions. When the entries of the matrix \(\mathbf{D}_{14}^{(5)}\) (10) are constant numbers that can be precalculated and stored in the calculator's memory, the implementation of the algorithm (11) requires only 27 additions, effectively reducing the computational complexity. Finally, we obtain a reduction in multiplications by 11 at the cost of 7 extra additions._  
Figure 3 shows a data flow diagram of the proposed algorithm.