The generalized superoptimal preconditioner

For any given nn-by-nn matrix AA, a specific circulant preconditioner tF(A)tF(A) introduced by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459–473] is defined to be the solution ofminC‖I-C-1A‖Fover all nn-by-nn nonsingular circulant matrices CC. The preconditioner tF(A)tF(A), called the superoptimal circulant preconditioner, has been proved to be a good preconditioner for a large class of structured systems. In this paper, we study this preconditioner in the general case by using the Moore-Penrose inverse. We give a formula for the superoptimal preconditioner and discuss the stability properties of this preconditioner. A spectral relation between the optimal and superoptimal preconditioned matrices in the general case is also given.