  When solving linear systems with nonsymmetric Toeplitz or multilevel Toeplitz
matrices using Krylov subspace methods, the coefficient matrix may be
symmetrized. The preconditioned MINRES method can then be applied to this
symmetrized system, which allows rigorous upper bounds on the number of MINRES
iterations to be obtained. However, effective preconditioners for symmetrized
(multilevel) Toeplitz matrices are lacking. Here, we propose novel ideal
preconditioners, and investigate the spectra of the preconditioned matrices. We
show how these preconditioners can be approximated and demonstrate their
effectiveness via numerical experiments.
