## 3 Algorithms for Toeplitz Matrix-Vector Multiplication
### Algorithm for \(N=4\)  
Let it be necessary to calculate the matrix-vector product of the following form:  
\[\begin{bmatrix}y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\end{bmatrix}=\begin{bmatrix}t_{3}&t_{2}&t_{1}&t_{0}\\ t_{4}&t_{3}&t_{2}&t_{1}\\ t_{5}&t_{4}&t_{3}&t_{2}\\ t_{6}&t_{5}&t_{4}&t_{3}\end{bmatrix}\begin{bmatrix}x_{0}\\ x_{1}\\ x_{2}\\ x_{3}\end{bmatrix}. \tag{6}\]  
The direct method of calculating this product requires 16 multiplications and 12 additions.  
**Proposition 2**.: _To calculate the product (6), no more than 9 multiplications are required._  
Proof.: Let us introduce some auxiliary matrices, pre- and postaddition matrices:  
\[\mathbf{P}_{4\times 6}^{(4)}=\begin{bmatrix}1&1&&\\ 1&&1&&\\ &&1&&1\\ &&1&1\end{bmatrix},\]  
\[\mathbf{P}_{6\times 9}^{(4)}=\mathbf{I}_{3}\otimes\mathbf{P}_{2\times 3^{ \prime}}^{(4)},\quad\mathbf{P}_{2\times 3}^{(4)}=\begin{bmatrix}1&1\\ &1&1\end{bmatrix},\]  
\[\mathbf{T}_{9\times 6}^{(4)}=\mathbf{I}_{3}\otimes\mathbf{T}_{3\times 2}^{(4)}, \quad\mathbf{T}_{3\times 2}^{(4)}=\begin{bmatrix}1&\\ 1&1\\ &1\end{bmatrix},\]  
Figure 1: Data flow diagram of the algorithm (5) for \(N=3\).  
\[\mathbf{T}_{6\times 4}^{(4)}=\begin{bmatrix}&1&\\ &&1\\ &1&\\ 1&&\\ &1&\end{bmatrix},\]  
and a diagonal matrix of multiplication factors \(\mathbf{D}_{9}^{(4)}\), in which the entries are the algebraic sums of entries of the Toeplitz matrix \(\mathbf{T}_{4}\):  
\[\mathbf{D}_{9}^{(4)}=\text{diag}\Big{(}\begin{array}{cccc}s_{0}^{(4)},&s_{1} ^{(4)},&\ldots&s_{8}^{(4)}\end{array}\Big{)}, \tag{7}\]  
\[s_{0}^{(4)}=w_{0}^{(4)}+w_{1}^{(4)},\quad s_{1}^{(4)}=-w_{0}^{(4)},\]  
\[s_{2}^{(4)}=t_{0}-t_{2}+w_{0}^{(4)},\quad s_{3}^{(4)}=t_{2}-t_{3},\quad s_{4}^ {(4)}=t_{3},\]  
\[s_{5}^{(4)}=t_{4}-t_{3},\quad s_{6}^{(4)}=-t_{4}+t_{6}+w_{2}^{(4)},\quad s_{7} ^{(4)}=-w_{2}^{(4)},\]  
\[s_{8}^{(4)}=-w_{1}^{(4)}+w_{2}^{(4)},\]  
where  
\[w_{0}^{(4)}=-t_{1}+t_{3},\quad w_{1}^{(4)}=t_{2}-t_{4},\quad w_{2}^{(4)}=t_{3 }-t_{5},\]  
and the sign \(\otimes^{\prime\prime}\) denotes the Kronecker product [49].  
Considering the matrices that have been introduced, expression (6) can be represented as follows:  
\[\mathbf{Y}_{4\times 1}=\mathbf{P}_{4\times 6}^{(4)}\mathbf{P}_{6\times 9}^{(4)} \mathbf{D}_{9}^{(4)}\mathbf{T}_{9\times 6}^{(4)}\mathbf{T}_{6\times 4}^{(4)} \mathbf{X}_{4\times 1}, \tag{8}\]  
where  
\[\begin{array}{l}\mathbf{X}_{4\times 1}=[x_{0},x_{1},x_{2},x_{3}]^{T},\\ \mathbf{Y}_{4\times 1}=[y_{0},y_{1},y_{2},y_{3}]^{T}.\end{array}\]  
It is easy to see that the multiplicative complexity of expression (8) is 9.  
The correctness of expression (8) is confirmed by the truth of the following expression:  
\[\mathbf{T}_{4}=\mathbf{P}_{4\times 6}^{(4)}\mathbf{P}_{6\times 9}^{(4)} \mathbf{D}_{9}^{(4)}\mathbf{T}_{9\times 6}^{(4)}\mathbf{T}_{6\times 4}^{(4)},\]  
where \(\mathbf{T}_{4}\) is a \(4\times 4\) Toeplitz matrix (1). Expression (8) defines a reduced multiplicative complexity algorithm for calculating the matrix-vector product with a fourth-order Toeplitz matrix.  
**Remark 2**.: _The proposed algorithm requires only 9 multiplications and 26 additions. This gives, relative to the direct method, a reduction of 7 multiplications at the cost of an additional 14 additions. Suppose the entries of the matrix \(\mathbf{D}_{9}^{(4)}\) (7) 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 15 additions, significantly reducing the computational requirements. Finally, we obtain a reduction in multiplications by 7 at the cost of 3 extra additions._  
Figure 2 shows a data flow diagram of the proposed algorithm.