zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Lanczos-type variants of the COCR method for complex nonsymmetric linear systems. (English) Zbl 1173.65316
Summary: Motivated by the celebrated extending applications of the well-established Complex Biconjugate Gradient (CBiCG) method to deal with large three-dimensional electromagnetic scattering problems by M. D. Pocock and S. P. Walker [IEEE Trans. Antennas Propagat. 45, No. 1, 140–146 (1997)], three Lanczos-type variants of the recently introduced Conjugate A-Orthogonal Conjugate Residual (COCR) method by T. Sogabe and S.-L. Zhang [J. Comput. Appl. Math. 199, No. 2, 297–303 (2007; Zbl 1108.65028)] are explored for the solution of complex nonsymmetric linear systems. The first two can be respectively considered as mathematically equivalent but numerically improved popularizing versions of the BiCR and CRS methods for complex systems presented in T. Sogabe’s Ph.D. Dissertation [Extensions of the conjugate residual method, University of Tokyo (2006)]. And the last one is somewhat new and is a stabilized and more smoothly converging variant of the first two in some circumstances. The presented algorithms are with the hope of obtaining smoother and, hopefully, faster convergence behavior in comparison with the CBiCG method as well as its two corresponding variants. This motivation is demonstrated by numerical experiments performed on some selective matrices borrowed from the sparse matrix collection of the University of Florida by Davis.

MSC:
65F10Iterative methods for linear systems
Software:
SparseMatrix; CGS
References:
[1]Pocock, M. D.; Walker, S. P.: The complex bi-conjugate gradient solver applied to large electromagnetic scattering problems, computational costs, and cost scalings, IEEE trans. Antennas propagat. 45, 140-146 (1997)
[2]Sogabe, T.; Zhang, S. -L.: A COCR method for solving complex symmetric linear systems, J. comput. Appl. math. 199, 297-303 (2007) · Zbl 1108.65028 · doi:10.1016/j.cam.2005.07.032
[3]Dongarra, J.; Sullivan, F.: Guest editors’ introduction to the top 10 algorithms, Comput. sci. Eng. 2, No. 1, 22-23 (2000)
[4]Hestenes, M. R.; Stiefel, E. L.: Methods of conjugate gradients for solving linear systems, J. res. Nat. bureau standards 49, 409-436 (1952) · Zbl 0048.09901
[5]Lanczos, C.: Solution of systems of linear equations by minized itertions, J. res. Nat. bureau standards 49, 33-53 (1952)
[6]Brezinski, C.: Padé type approximation and general orthogonal polynomials, (1980)
[7]Simoncini, V.; Szyld, D. B.: Recent computational developments in Krylov subspace methods for linear systems, Numer. linear algebra appl. 14, 1-59 (2007) · Zbl 1199.65112 · doi:10.1002/nla.499
[8]Fletcher, R.: Conjugate gradient methods for indefinite systems, Lecture notes in mathematics 506 (1976) · Zbl 0326.65033
[9]D.A.H. Jacobs, The Exploitation of Sparsity by Iterative Methods, Sparse Matrices and their Uses, I.S. Duff, Springer, 1981, pp. 191 – 222. · Zbl 0469.65016
[10]Jacobs, D. A. H.: A generalization of the conjugate gradient method to solve complex systems, IMA J. Numer. anal. 6, 447-452 (1986) · Zbl 0614.65028 · doi:10.1093/imanum/6.4.447
[11]Sarkar, T. K.: On the application of the generalized biconjugate gradient method, J. electromagnet. Waves appl. 1, 223-242 (1987)
[12]Markham, G.: Conjugate gradient type methods for indefinite, asymmetric, and complex systems, IMA J. Numer. anal. 10, 155-170 (1990) · Zbl 0702.65032 · doi:10.1093/imanum/10.2.155
[13]Smith, C. F.; Peterson, A. F.; Mittra, R.: The biconjugate gradient method for electromagnetic scatterings, IEEE trans. Antennas propagat. 38, 938-940 (1990)
[14]Joly, P.; Meurant, G.: Complex conjugate gradient methods, Numer. algo. 4, 379-406 (1993) · Zbl 0780.65021 · doi:10.1007/BF02145754
[15]P. Joly, Méthode de gradient conjugué, Publications du Laboratoire d’Analyse Numérique Université Pierre et Marie Curie, Paris, 1984.
[16]Sonneveld, P.: CGS a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. stat. Comput. 10, 36-52 (1989) · Zbl 0666.65029 · doi:10.1137/0910004
[17]M. Clemens, T. Weiland, Iterative methods for the solution of very large complex-symmetric linear systems of equations in electromagnetics, in: T.A. Manteuffel, S.F. McCormick (Eds.), Eleventh Copper Mountain Conference on Iterative Methods, Part 2, 1996.
[18]Van Der Vorst, H. A.; Melissen, J. B. M.: A Petrov – Galerkin type method for solving ax=b, where A is symmetric complex, IEEE trans. Mag. 26, 706-708 (1990)
[19]Cullum, J.; Kerner, W.; Willoughby, R. A.: A generalized nonsymmetric Lanczos procedure, Comput. phys. Commu. 53, 19-48 (1989) · Zbl 0798.65050 · doi:10.1016/0010-4655(89)90146-X
[20]Cullum, J.; Willoughby, R. A.: Lanczos algorithms for large symmetric eigenvalue computations, Classics in applied mathematics 41 (1985)
[21]Clemens, M.; Weiland, T.: Comparison of Krylov-type methods for complex linear systems applied to high-voltage problems, IEEE trans. Mag. 5, 3335-3338 (1998)
[22]Liang Li, Ting-Zhu Huang, Yan-Fei Jing, Application of the incomplete Cholesky factorization preconditioned conjugated orthogonal conjugate gradient algorithm to the vector FEM for 3-D electromagnetic scattering problems, Comput. Phys. Commun., submitted for publication.
[23]Weiss, R.: Parameter-free iterative linear solvers, Mathematical research 97 (1996) · Zbl 0858.65031
[24]R. Weiss, Convergence behavior of generalized conjugate gradient method, Ph.D. Dissertation, University of Karlsruhe, 1990. · Zbl 0738.90074
[25]Weiss, R.: Properties of generalized conjugate gradient methods, J. numer. Linear algebra appl. 1, 45-63 (1994) · Zbl 0816.65013 · doi:10.1002/nla.1680010106
[26]Saad, Y.: Iterative methods for sparse linear systems, (1996) · Zbl 1031.65047
[27]Gutknecht, Martin H.; Rozloz&breve, Miroslav; Ník: A framework for generalized conjugate gradient methods – with special emphasis on contributions by Rűdiger Weiss, Appl. numer. Math. 41, 7-22 (2002)
[28]W. Schönauer, The efficient solution of large linear systems, resulting from the fdm for 3-d PDE’s, on vector computers, in: Proceedings of the 1st International colloquium on vector and parallel computing in Scientific Applications, Paris, March 1983, 1983.
[29]B. Hendrickson, R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations, Technical Report SAND92-1460, UC-405, Sandia National Laboratories, Albuquerque, NM, 1992.
[30]Brezinski, C.; Redivo-Zaglia, M.: Hybrid procedures for solving systems of linear equations, Numer. math. 67, 1-19 (1994) · Zbl 0797.65023 · doi:10.1007/s002110050015
[31]Zhou, L.; Walker, H. F.: Residual smoothing techniques for iterative methods, SIAM J. Sci. comput. 15, 297-312 (1994) · Zbl 0802.65041 · doi:10.1137/0915021
[32]R. Weiss, A theoretical overview of Krylov subspace methods, in: W. Schönauer, R. Weiss (Eds.), Special Issue on Iterative Methods for Linear Systems Applied Numerical Methods, 1995, pp. 33 – 56.
[33]Freund, R. W.; Nachtigal, N. M.: QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. math. 60, 315-339 (1991) · Zbl 0754.65034 · doi:10.1007/BF01385726
[34]Gutknecht, Martin H.; Rozloz&breve, Miroslav; Ník: Residual smoothing techniques: do they improve the limiting accuracy of iterative solvers?, Bit 41, 086-114 (2001)
[35]Gutknecht, Martin H.; Rozloz&breve, Miroslav; Ník: By how much can residual minization accelerate the convergence of orthogonal residual methods?, Numer. algo. 27, 189-213 (2001)
[36]Paige, C. C.; Saunders, M. A.: Solution of sparse indefinite systems of linear equations, SIAM J. Numer. anal. 12, 617-629 (1975) · Zbl 0319.65025 · doi:10.1137/0712047
[37]Freund, R. W.: A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. comput. 14, 470-482 (1993) · Zbl 0781.65022 · doi:10.1137/0914029
[38]Brown, P. N.: A therical comparison of the arnoldi and GMRES algorithms, SIAM J. Sci. statist. Comput. 12, 58-78 (1991) · Zbl 0719.65022 · doi:10.1137/0912003
[39]Walker, H. F.: Residual smoothing and peak/plateau behavior in Krylov subspace methods, Appl. numer. Math. 19, 279-286 (1995) · Zbl 0855.65023 · doi:10.1016/0168-9274(95)00087-9
[40]Cullum, J.: Peaks, plateaus, numerical instabilities in a Galerkin/minimal residual pair of methods for solving ax=b, Appl. numer. Math. 19, 255-278 (1995) · Zbl 0855.65022 · doi:10.1016/0168-9274(95)00086-0
[41]Cullum, J.; Greenbaum, A.: Relations between Galerkin and norm-minimizing iterative methods for solving linear systems, SIAM J. Matrix anal. Appl. 17, 223-247 (1996) · Zbl 0855.65021 · doi:10.1137/S0895479893246765
[42]H. Sadok, Analysis of the convergence of the minimal and the orthogonal residual methods, Reprint, 1997.
[43]Eiermann, M.; Ernst, O.: Geometric aspects in the theory of Krylov space methods, Acta numer. 10, 251-312 (2001) · Zbl 1105.65328 · doi:10.1017/S0962492901000046
[44]Stiefel, E.: Relaxationsmethoden bester strategie zur lösung linearer gleichungssysteme, Comment. math. Helv. 29, 157-179 (1955) · Zbl 0066.36703 · doi:10.1007/BF02564277
[45]Van Der Vorst, H. A.: Iterative Krylov methods for large linear systems, (2003)
[46]Sogabe, T.; Sugihara, M.; Zhang, S. -L.: An extension of the conjugate residual method to nonsymmetric linear systems, J. comput. Appl. math. 226, 103-113 (2009) · Zbl 1170.65026 · doi:10.1016/j.cam.2008.05.018
[47]T. Sogabe, Extensions of the conjugate residual method, Ph.D. Dissertation, University of Tokyo, 2006.
[48]Van Der Vorst, H. A.: Bi-CGSTAB: a fast and smoothly converging variant of bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. stat. Comput. 13, 631-644 (1992) · Zbl 0761.65023 · doi:10.1137/0913035
[49]Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. res. Nat. bureau standards 45, 255-281 (1950)
[50]Parlett, B.; Taylor, D.; Liu, Z. -S.: A look-ahead Lanczos algorithm for unsymmetric matrices, Math. comput. 44, 105-124 (1985) · Zbl 0564.65022 · doi:10.2307/2007796
[51]Parlett, B.: Reduction to tridiagonal form and minimal realizations, SIAM J. Matrix anal. Appl. 13, 567-593 (1992) · Zbl 0754.65040 · doi:10.1137/0613036
[52]Freund, R.; Gutknecht, M. H.; Nachtigal, N.: An implementation of the look-ahead Lanczos algorithm for non-Hermitian matrices, SIAM J. Sci. stat. Comput. 14, 137-158 (1993) · Zbl 0770.65022 · doi:10.1137/0914009
[53]Gutknecht, M. H.: Lanczos-type solvers for nonsymmetric linear systems of equations, Acta numer. 6, 271-397 (1997) · Zbl 0888.65030
[54]Day, D.: An efficient implementation of the nonsymmetric Lanczos algorithms, SIAM J. Matrix anal. Appl. 18, 566-589 (1997)
[55]Barrett, R.; Berry, M. W.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; Van Der Vorst, H. A.: Templates for the solution of linear systems: building blocks for iterative methods, (1994)
[56]Sleijpen, G. L. G.; Van Der Vorst, H. A.: An overview of approaches for the stable computation of hybrid bicg method, Appl. numer. Math. 19, 235-254 (1995) · Zbl 0856.65022 · doi:10.1016/0168-9274(95)00085-2
[57]Gutknecht, M. H.: Variants of bicgstab for matrices with complex spectrum, SIAM J. Sci. comput. 14, 1020-1033 (1993) · Zbl 0837.65031 · doi:10.1137/0914062
[58]Sleijpen, G. L. G.; Fokkema, D. R.: BiCGSTAB(l) for linear equations involving unsymmetric matrices with complex spectrum, Electron. trans. Numer. anal. 1, 11-32 (1993) · Zbl 0820.65016 · doi:emis:journals/ETNA/vol.1.1993/
[59]Saad, Y.; Schultz, M. H.: GMRES: a generalized minimal residual algorithm for solving a nonsymmetric linear systems, SIAM J. Sci. stat. Comput. 7, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[60]Benzi, M.: Preconditioning techniques for large linear systems: a survey, J. comput. Phys. 182, 418-477 (2002) · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[61]Davis, T.: The university of Florida sparse matrix collection, NA digest 97, No. 23 (1997)
[62]Van Der Vorst, H. A.: The convergence behavior of preconditioned CG and CG-S in the presence of rounding errors, Lecture notes math. 1457, 126-136 (1990) · Zbl 0714.65034
[63]Saad, Y.; Van Der Vorst, H. A.: Iterative solution of linear systems in the 20th century, J. comput. Appl. math. 123, 1-33 (2000) · Zbl 0965.65051 · doi:10.1016/S0377-0427(00)00412-X
[64]M.H. Gutknecht, Residual smoothing for Krylov space solvers: does it help at all? in: Seminar for Applied Mathematics, ETH Zurich, lt;http://www.sam.math.ethz.ch/ mhggt;.