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.