Abstract: It is known that the product Axof a large scale Hermitian Toeplitz matrix Aand a vector xcan be computed effectively by using the Fast Fourier Transform(FFT).In this paper,based on the fact that an Her-mitian Toeplitz matrix Acan be reduced into a real Toeplitz-plus-Hankel matrix(A=T+H)by a unitarysimilarity transformation(the unitary matrix is U=1/√2(I-iJ), we develop a more efficient algorithm thatonly O(n)complex arithmetics are included for computing the product Ax by employing the DCT and DST.

Key words: Hermitian Toeplitz matri, x Matrix-vector multiplication,  , DCT, DST, Real operation