Symmetric centrosymmetric matrix-vector multiplication (Q1593669)

The multiplication of an arbitary vector by a symmetric matrix on a sequential machine requires, in general, \(2n^2\) floating-point operations. In this paper, a method for the multiplication of an arbitrary vector by a symmetric centrosymmetric matrix with \(\frac 54n^2+O(n)\) flops is presented. As the inverse of a symmetric Toeplitz matrix is symmetric centrosymmetric, combining this method with \textit{W. F. Trench}'s algorithm [J. SIAM 12, 515-522 (1964; Zbl 0131.36002)] yields a method for solving Toeplitz systems with the same complexity as \textit{N. Levinson}'s algorithm [J. Math. Phys. 25, 261-278 (1947)].