Application of determinant Maximization Programming to the SOR and Chebyshev Methods for Complex Linear Systems

Wai-Shing Luk

Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, N.T.
Hong Kong

Jan Janssen

Department of Computer Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A, B-3001 Heverlee
Belgium

Stefan Vandewalle

Department of Computer Science
Katholieke Universiteit Leuven
Celestijnenlaan 200A, B-3001 Heverlee
Belgium


Abstract

In the SOR and Chebyshev methods for solving complex linear systems, one crucial procedure is to find an ellipse that encloses the spectrum of a given complex matrix and gives the smallest convergence factor. For the Chebyshev method, the original Manteuffel's procedure requires the ellipse to be symmetric to the real axis, which is far from optimal for most complex matrices. Moreover, the procedure requires a combinatorial search for all possible ellipses. A new approach is proposed that approximates the optimal ellipse problem as a determinant maximization programming poblem with linear matrix inequality constraints. The approximated problem can be solved efficiently by the recently developed interior-point method. Moreover, both the SOR and Chebyshev cases can be handled in a unified manner in this approach.