## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=6\)  
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}\\ y_{5}\end{bmatrix}=\begin{bmatrix}t_{5}&t_{4}&t_{3}&t_{2}&t_{1}&t_{0}\\ t_{6}&t_{5}&t_{4}&t_{3}&t_{2}&t_{1}\\ t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&t_{2}\\ t_{8}&t_{7}&t_{6}&t_{5}&t_{4}&t_{3}&x_{3}\\ t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&t_{4}\\ t_{10}&t_{9}&t_{8}&t_{7}&t_{6}&t_{5}&x_{5}\end{bmatrix}. \tag{12}\]  
Figure 3: Data flow diagram of the algorithm (11) for \(N=5\).  
The direct method of calculating this product requires 36 multiplications and 30 additions.  
**Proposition 4**.: _To calculate the product (12), no more than 18 multiplications are required._  
Proof.: Let us introduce auxiliary matrices:  
\[\mathbf{P}_{6\times 9}^{(6)}=\begin{bmatrix}\mathbf{0}_{3}&\mathbf{I}_{3}&\mathbf{I }_{3}\\ \mathbf{I}_{3}&\mathbf{I}_{3}&\mathbf{0}_{3}\end{bmatrix},\quad\mathbf{P}_{9 \times 18}^{(6)}=\mathbf{I}_{3}\otimes\mathbf{P}_{3\times 6}^{(3)},\]  
and  
\[\mathbf{T}_{18\times 9}^{(6)}=\mathbf{I}_{3}\otimes\mathbf{T}_{6\times 3}^{(3)},\]  
\[\mathbf{D}_{18}^{(6)}=\text{diag}\Big{(}s_{0}^{(6)},\;\;s_{1}^{(6)},\;\;\ldots,\;\;s_{17}^{(6)}\Big{)}, \tag{13}\]  
\[s_{0}^{(6)}=w_{0}^{(6)},\;\;\;s_{1}^{(6)}=t_{10}-w_{0}^{(6)}+w_{2}^{(6)},\]  
\[s_{2}^{(6)}=-t_{6}+t_{9},\;\;\;s_{3}^{(6)}=t_{4}+w_{0}^{(6)}+w_{2}^{(6)},\]  
\[s_{4}^{(6)}=-t_{4}+t_{7},\;\;\;s_{5}^{(6)}=-t_{8}+w_{3}^{(6)}-w_{4}^{(6)},\; \;\;s_{6}^{(6)}=t_{5},\]  
\[s_{7}^{(6)}=-w_{3}^{(6)},\;\;\;s_{8}^{(6)}=t_{6},\;\;\;s_{9}^{(6)}=-t_{4}+t_{5 }-t_{6},\]  
\[s_{10}^{(6)}=t_{4},\;\;\;s_{11}^{(6)}=-w_{5}^{(6)},\;\;\;s_{12}^{(6)}=w_{6}^{( 6)},\]  
\[s_{13}^{(6)}=-t_{2}-w_{4}^{(6)}+w_{3}^{(6)},\;\;\;s_{14}^{(6)}=t_{3}-t_{6},\]  
\[s_{15}^{(6)}=-t_{1}+t_{6}-w_{4}^{(6)}+w_{6}^{(6)},\;\;\;s_{16}^{(6)}=t_{1}-t_{ 4},\]  
\[s_{17}^{(6)}=t_{0}-t_{1}-t_{2}+w_{5}^{(6)},\]  
where  
\[w_{0}^{(6)}=-t_{5}+t_{8},\;\;\;w_{1}^{(6)}=t_{6}-t_{7},\]  
\[w_{2}^{(6)}=-t_{9}+w_{1}^{(6)},\;\;\;w_{3}^{(6)}=t_{5}+w_{1}^{(6)},\;\;\;w_{4 }^{(6)}=t_{3}-t_{4},\]  
\[w_{5}^{(6)}=t_{5}+w_{4}^{(6)},\;\;\;\;w_{6}^{(6)}=t_{2}-t_{5}.\]  
Taking into account the introduced matrix constructions, expression (12) can be written in the following form:  
\[\mathbf{Y}_{6\times 1}=\mathbf{P}_{6\times 9}^{(6)}\mathbf{P}_{9\times 18}^{(6)} \mathbf{D}_{18}^{(6)}\mathbf{T}_{18\times 9}^{(6)}\mathbf{T}_{9\times 6}^{(6)} \mathbf{X}_{6\times 1}, \tag{14}\]  
where  
\[\mathbf{X}_{6\times 1}=[x_{0},x_{1},x_{2},x_{3},x_{4},x_{5}]^{T},\]  
\[\mathbf{Y}_{6\times 1}=[y_{0},y_{2},y_{3},y_{3},y_{4},y_{5}]^{T}.\]  
It is easy to see that the multiplicative complexity of calculating expression (14) is 18.  
The correctness of expression (14) can be checked by a simple substitution:  
\[\mathbf{T}_{6}=\mathbf{P}_{6\times 9}^{(6)}\mathbf{P}_{9\times 18}^{(6)} \mathbf{D}_{18}^{(6)}\mathbf{T}_{18\times 9}^{(6)}\mathbf{T}_{9\times 6^{\prime}}^{(6)},\]  
where \(\mathbf{T}_{6}\) is a \(6\times 6\) Toeplitz matrix. Expression (14) defines a reduced multiplicative complexity algorithm for calculating the matrix-vector product with a sixth-order Toeplitz matrix.  
**Remark 4**: _The proposed algorithm (14) requires only 18 multiplications and 75 additions. Suppose the entries of the matrix \(\mathbf{D}_{18}^{(6)}\) (13) are constant values that can be precomputed and stored in the memory of a calculator. In that case, the implementation of the algorithm can be accomplished with only 33 additions, significantly reducing the computational requirements. Thus, the proposed algorithm (14) applied to the calculation of the matrix-vector product (12) reduces 18 multiplications at the expense of 3 extra additions compared to the direct method._  
Figure 4 shows a data flow diagram of the proposed algorithm.