Abstract
Complex valued linear algebraic systems arise in many important applications. We present analytical and extensive numerical comparisons of some available numerical solution methods. It is advocated, in particular for large scale ill-conditioned problems, to rewrite the complex-valued system in real valued form leading to a two-by-two block system of particular form, for which it is shown that a very efficient and robust preconditioned iterative solution method can be constructed. Alternatively, in many cases it turns out that a simple preconditioner in the form of the sum of the real and the imaginary part of the matrix also works well but involves complex arithmetic.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
van Rienen, U.: Numerical methods in computational electrodynamics. Linear systems in practical applications. Springer–Verlag, Berlin Heidelberg (2001)
Kormann, K.: Efficient and reliable simulation of quantum molecular dynamics. Ph.D. Thesis, Uppsala University. http://uu.diva-portal.org/smash/record.jsf?pid=diva2:549981
Novikov, S., Manakov, S.V., Pitaevskiĭ, L.P., Zakharov, V.E.: Theory of Solitons. The Inverse Scattering Method. Translated from Russian. Contemporary Soviet Mathematics. Consultants Bureau [Plenum], New York (1984)
Butcher, J.C.: Integration processes based on Radau quadrature formulas. Math. Comp. 18, 233–244 (1964)
Axelsson, O.: On the efficiency of a class of A–stable methods. BIT 14, 279–287 (1974)
Day, D., Heroux, M.A.: Solving complex-valued linear systems via equivalent real formulations. SIAM J. Sci. Comput. 23, 480–498 (2001)
Benzi, M., Bertaccini, D.: Block preconditioning of real–valued iterative algorithms for complex linear systems. SIAM J. Numer. Anal. 28, 598–618 (2008)
Giovangiglia, V., Grailleb, B.: Projected iterative algorithms for complex symmetric systems arising in magnetized multicomponent transport. Linear Algebra Appl. 430, 1404–1422 (2009)
Howle, V.E., Vavasis, S.A.: An iterative method for solving complex-symmetric systems arising in electrical power modeling. SIAM J. Matrix Anal. Appl. 26, 1150–1178 (2005)
Bai, Z.-Z., Benzi, M., Chen, F., Wang, Z.-Q.: Preconditioned MHSS iteration methods for a class of block two-by-two linear systems with applications to distributed control problems. IMA J. Numer. Anal. 33, 343–369 (2013)
Axelsson, O., Kucherov, A.: Real valued iterative methods for solving complex symmetric linear systems. Numer. Linear Algebra Appl. 7, 197–218 (2000)
Saad, Y., Schultz, M.H.: GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, 856–869 (1986). doi:10.1137/0907058
Saad, Y.: A flexible inner-outer preconditioned GMRES algorithm. SIAM, J. Sci. Comp. 14, 461–469 (1993)
Axelsson, O., Vassilevski, P.S.: A black box generalized conjugate gradient solver with inner iterations and variable–step preconditioning. SIAM J. Matrix Anal. Appl. 12, 625–644 (1991)
Vassilevski, P.S.: Multilevel Block Factorization Preconditioners: Matrix-Based Analysis and Algorithms for Solving Finite Element Equations. Springer, New York (2008)
Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl. 24, 603–626 (2003)
Bai, Z.-Z., Golub, G.H., Ng, M.K.: On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations. Numer. Linear Algebra Appl. 14, 319–335 (2007)
Bai, Z.-Z., Benzi, M., Chen, F.: Modified HSS iteration methods for a class of complex symmetric linear systems. Computing 87, 93–111 (2010)
Bai, Z.-Z., Benzi, M., Chen, F.: On preconditioned MHSS iteration methods for complex symmetric linear systems. Numer. Algoritm. 56, 297–317 (2011)
Axelsson, O., Bai, Z.-Z., Qiu, S.-X.: A class of nested iteration schemes for linear systems with a coefficient matrix with a dominant positive definite symmetric part. Numer. Algoritm. 35, 351–372 (2004)
Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edn. SIAM, Philadelphia (1994)
Freund, R.W.: Conjugate gradient–type methods for linear systems with complex symmetric coefficient matrices. SIAM J. Sci. Statist. Comput. 13, 425–448 (1992)
van der Vorst, H., Melissen, J.: A Petrov–Galerkin type method for solving Ax = b where A is symmetric complex. IEEE Trans. Magn. 26, 706–708 (1990)
Freund, R.W., Nachtigal, N.M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems. Numer. Math. 60, 315–339 (1991)
Freund, R.W.: A transpose-free quasi-minimum residual algorithm for non-Hermitian linear systems. SIAM J. Sci. Comput. 14, 470–482 (1993)
Pearson, J.W., Wathen, A.J.: A new approximation of the Schur complement in preconditioners for PDE-constrained optimization. Numer. Linear Algebra Appl. 19, 816–829 (2012)
Axelsson, O.: Iterative Solution Methods. Cambridge University Press, Cambridge (1994)
Axelsson, O., Boyanova, P., Kronbichler, M., Neytcheva, M., Wu, X.: Numerical and computational efficiency of solvers for two-phase problems. Comput. Math. Appl. (2012). Published on line at doi:10.1016/j.camva.2012.05.020
Kormann, K., Larsson, E.: An RBF-Galerkin Approach to the Time-Dependent Schrödinger Equation. Department of Information Technology, Uppsala University, TR 2012–024 (2012)
The University of Florida Sparse Matrix Collection, maintained by T. Davis and Y. Hu, http://www.cise.ufl.edu/research/sparse/matrices/
Notay, Y.: AGMG software and documentation; see http://homepages.ulb.ac.be/~ynotay/AGMG
Napov, A., Notay, Y.: An algebraic multigrid method with guaranteed convergence rate. SIAM J. Sci. Comput. 34, A1079–A1109 (2012)
Notay, Y.: Aggregation-based algebraic multigrid for convection-diffusion equations. SIAM J. Sci. Comput. 34, A2288–A2316 (2012)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Axelsson, O., Neytcheva, M. & Ahmad, B. A comparison of iterative methods to solve complex valued linear algebraic systems. Numer Algor 66, 811–841 (2014). https://doi.org/10.1007/s11075-013-9764-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-013-9764-1