Real valued iterative methods for solving complex symmetric linear systems. (English) Zbl 1051.65025

Axelsson, Owe; Kucherov, Andrey

Numer. Linear Algebra Appl. 7, No. 4, 197-218 (2000).

The paper deals with iterative methods for solving complex symmetric linear systems. A new reduction of complex linear systems to systems the solution of which needs only real arithmetic and a real-valued (RV) preconditioned iterative solution method is proposed. The preconditioning is based on the Schur complement reduction. If the reduction is exact, the condition number of the preconditioned matrix is bounded from above by 2. Applications of the method are discussed and results of numerical experiments are demonstrated by a few examples.
The introduction of the paper is devoted to a motivation of the approach in solving matrix polynomial equations. Basic possibilities how to avoid the use of complex arithmetic are shown and the motivation for this task is explained. A short description of standard possible approaches like the algorithms CSYM, QMR and CGNE is given. The ideas of the new transformation are provided in the introduction as well.
Most of the theory of the paper concerning the transformation is given in section 2. A detailed derivation of the approach parametrized by one or two parameters is given, the resulting algorithm for solving complex symmetric systems is presented, and a theoretical conclusions concerning the condition number of the preconditioned matrix are derived. Later, the whole process of application of the method to solving matrix polynomial equations is described.
The third section is devoted to applications to solving systems of ordinary differential equations. The use of time-stepping integration schemes based on Padé approximation for solving parabolic and hyperbolic problems are considered as well.
The last section of the paper is devoted to numerical experiments. The proposed RV method is compared with the complex symmetric QMR method for two types of problems: systems with a complex diagonal shift and some parabolic complex systems arising in integration schemes based on Padé approximations. The presented problems are two-dimensional with the dimensions of linear systems from 10000 up to 250000. The crucial task, solving the system with the block arising in preconditioning is based on a direct solver from the symmetric Yale Sparse Matrix Package (YSMP) and two variants of its use are proposed. The results of the new approach compare favourably with the purely iterative complex symmetric QMR approach. This is, of course, influenced by the fact that a great portion of the work in this implementation is done by the direct solver. The results could be probably even better in favour of the new approach if a contemporary direct solver would be used instead of an outdated code YSMP.

Reviewer: Miroslav Tůma (Praha)

MSC:

65F10	Iterative numerical methods for linear systems
65F50	Computational methods for sparse matrices

Keywords:

symmetric complex linear systems; Krylov subspace method; real-valued iterative methods; QMR method; Schur complement preconditioning; condition number; numerical experiments; matrix polynomial equations; Padé approximation

Software:

symrcm; YSMP

References:

[1]	Saad, SIAM Journal on Scientific and Statistical Computing 7 pp 856– (1986) · Zbl 0599.65018
[2]	Iterative Solution Methods Cambridge University Press: New York, 1994.
[3]	Axelsson, Numerische Mathematik 51 pp 209– (1987) · Zbl 0596.65014
[4]	Axelsson, Communications on Applied Analysis 1 pp 371– (1997)
[5]	Freund, SIAM Journal on Scientific and Statistical Computing 13 pp 425– (1992) · Zbl 0761.65018
[6]	Bunse-Gerstner, Linear Algebra and its Applications 287 pp 105– (1999) · Zbl 0941.65031
[7]	Jacobs, IMA Journal of Numerical Analysis 6 pp 447– (1986) · Zbl 0614.65028
[8]	Markham, IMA Journal of Numerical Analysis 10 pp 155– (1990) · Zbl 0702.65032
[9]	Joly, Numerical Algorithms 4 pp 379– (1993) · Zbl 0780.65021
[10]	Solution of shifted linear systems by quasi-minimal residual iterations. In Numerical Linear Algebra, (eds). W. de Gruyter 1993;101-121. · Zbl 0794.65028
[11]	The search for ?high-level? parallelism for iterative sparse linear system solvers. In Parallel Supercomputing: Methods, Algorithms and Applications, (ed). Wiley, 1989; 89-105.
[12]	Young, Applied Numerical Mathematics 10 pp 261– (1992) · Zbl 0756.65051
[13]	Datta, Linear Algebra and its Applications 154/156 pp 225– (1991) · Zbl 0734.65037
[14]	Frommer, SIAM Journal on Scientific Computing 19 pp 15– (1998) · Zbl 0912.65023
[15]	Freund, Numerische Mathematik 57 pp 285– (1990) · Zbl 0702.65034
[16]	On the computational complexity of some matrix iterative algorithms. Department of Computer Sciences, Chalmers University of Technology, Göteborg, Sweden, 1974.
[17]	Axelsson, BIT 14 pp 279– (1974) · Zbl 0289.65028
[18]	Kucherov, Sovietsky Mathematischeskoe Doklady 43 pp 377– (1991)
[19]	Numerical Methods in Computational Electrodynamics-Linear Systems in Practical Applications Springer Lecture Notes in Computational Science and Engineering, vol. 15, 2000, to be published.
[20]	Kucherov, Mathematical Modelling 3 pp 115– (1991)
[21]	Robust and efficient AC analysis of high-speed devices. In Proceedings of the 1992 Electron Device Meeting IEEE; 935-938.
[22]	Solving Ordinary Differential Equations-Part II. Stiff and Differential Algebraic Problems Springer-Verlag: Berlin, 1996. · Zbl 1192.65097
[23]	Eisenstat, International Journal for Numerical Methods in Engineering 18 pp 1145– (1982) · Zbl 0492.65012
[24]	Computer Solution of Large Sparse Positive Definite Systems Prentice-Hall: Englewood Cliffs, NJ, 1981.
[25]	Axelsson, Journal of Computational Physics 35 pp 284– (1980) · Zbl 0425.65056