|
|
|
“A Minimum-Phase LU Factorization Preconditioner for Toeplitz Matrices”
by Ta-Kang Ku and C.-C. Jay Kuo
February 1991
A new preconditioner is proposed for the solution of an N x N Toeplitz system TN x=b, where TN can be symmetric indefinite or nonsymmetric, by preconditioned iterative methods. The preconditioner FN is obtained based on factorizing the generating function T(z) into the product of two terms corresponding, respectively, to minimum-phase causal and anticausal systems and therefore called the minimum-phase LU (MPLU) factorization preconditioner. Due to the minimum-phase property, ||FN-1|| is bounded. For rational Toeplitz TN with generating function T(z) = A(z-1)/B(z-1) + C(z)/D(z), where A(z), B(z), C(z) and D(z) are polynomials of orders p1, q1, p2, and q2, we show that the eigenvalues of FN-1TN are repeated exactly at 1 except at most aF outliers, where aF depends on p1, q1, p2, q2 and the number w of the roots of T(z) = A(z-1) D(z) + B(z-1) C(z) outside the unit circle. A preconditioner KN in circulant form generalized from the symmetric case is also presented for comparison. The MPLU preconditioner FN performs better than circulant preconditioner KN in our numerical experiments.