×

On conjugate gradient type methods and polynomial preconditioners for a class of complex non-Hermitian matrices. (English) Zbl 0702.65034

The author presents a detailed study, with the emphasis on practical aspects, of conjugate gradient type methods for arbitrary complex matrices of the form \(A=e^{i\theta}(T+i\sigma I)\), T Hermitian matrix, \(\sigma\) and \(\theta\) real. Three approaches based on a minimal residual property, a Galerkin condition and an Euclidean error minimization are considered. In particular it is shown how SYMMLQ and MINRES can be extended to numerically stable implementations of all three approaches and derive error bounds for all three methods.
Also it is shown how the special shift structure of A can be preserved by using polynomial preconditioning, and results on the optimal choice of the polynomial preconditioner are given. Finally, some numerical experiments for matrices arising from finite difference approximations to the complex Helmholtz equation with constant coefficients are reported.
Reviewer: P.Narain

MSC:

65F10 Iterative numerical methods for linear systems
65N22 Numerical solution of discretized equations for boundary value problems involving PDEs
35J05 Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Ashby, S.F., Manteuffel, T.A., Saylor, P.E.: A taxonomy for conjugate gradient methods. Preprint UCRL-98508, Lawrence Livermore National Laboratory, March 1988 · Zbl 0723.65018
[2] Barbour, I.M., Behilil, N.-E., Gibbs, P.E., Rafiq, M., Moriarty, K.J.M., Schierholz, G.: Updating fermions with the Lanzos method. J. Comput. Phys.68, 227-236 (1987) · Zbl 0609.65004 · doi:10.1016/0021-9991(87)90053-2
[3] Bayliss, A., Goldstein, C.I., Turkel, E.: The numerical solution of the Helmoholtz equation for wave propagation problems in underwater acoustics. Comp. Maths. Appl.11, 655-665 (1985) · Zbl 0596.76092 · doi:10.1016/0898-1221(85)90162-2
[4] Carlson, B.C., Todd, J.: Zolotarev’s first problem ? the best approximation by polynomials of degree ?n?2 tox n?n ?x n?1 in [?1,1]. Aequationes Math.26, 1-33 (1983) · Zbl 0535.41029 · doi:10.1007/BF02189661
[5] Chandra, R.: Conjugate gradient methods for partial differential equations. Ph.D. Thesis, Computer Science Department, Research Report 129, Yale University, January 1978
[6] Concus, P., Golub, G.H.: A generalized conjugate gradient method for nonsymmetric systems of linear equations. In: Glowingski, R., Lions, J.L. (eds.) Computing methods in applied sciences and engineering, pp. 56-65. Lecture Notes in Economics and Mathematical Systems, Vol. 134. Berlin Heidelberg New York: Springer 1976 · Zbl 0344.65020
[7] Concus, P., Golub, G.H., O’Leary, D.P.: A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations. In: Bunch, J.R., Rose, D.J. (eds.) Sparse matrix computations, pp. 309-332. New York: Academic Press 1976
[8] Delfour, M., Fortin, M., Payre, G.: Finite-differences solutions of a non-linear Schrödinger equation. J. Comput. Phys.44, 277-288 (1981) · Zbl 0477.65086 · doi:10.1016/0021-9991(81)90052-8
[9] Duffin, R., Schaeffer, A.C.: Some properties of functions of exponential type. Bull. Am. Math. Soc.44, 236-240 (1938) · Zbl 0018.40901 · doi:10.1090/S0002-9904-1938-06725-0
[10] Eiermann, M., Li, X., Varga, R.S.: On hybrid semiiteratives methods. SIAM J. Numer. Anal.26, 152-168 (1989) · Zbl 0669.65020 · doi:10.1137/0726009
[11] Eisenstat, S.C., Elman, H.C., Schultz, M.H.: Variationals iterative methods for non-symmetric systems of linear equations SIAM J. Numer. Anal.20, 345-357 (1983) · Zbl 0524.65019 · doi:10.1137/0720023
[12] Elmore, W.C., Heald, M.A.: Physics of waves. New York: McGraw-Hill 1969
[13] Faber, V., Manteuffel, T.: Necessary and sufficient conditions for the existence of a conjugate gradient method. SIAM J. Numer. Anal.21, 352-362 (1984) · Zbl 0546.65010 · doi:10.1137/0721026
[14] Faber, V., Manteuffel, T.: Orthogonal error methods. SIAM J. Numer. Anal.24, 170-187 (1987) · Zbl 0613.65030 · doi:10.1137/0724014
[15] Fischer, B., Freund, R.: On the constrained Chebyshev approximation problem on ellipses. J. Approx. Theory, to appear (1990) · Zbl 0728.41023
[16] Fletcher, R.: Conjugate gradient methods for indefinite systems. In: Watson, G.A. (ed.) Numerical Analysis Dundee 1975, pp. 73-89. Lecture Notes in Mathematics, Vol. 506. Berlin Heidelberg New York: Springer 1976
[17] Fridman, V.M.: The method of minimum iterations with minimum errors for a system of linear algebraic equations with a symmetrical matrix. USSR Comput. Math. and Math. Phys.2, 362-363 (1963) · Zbl 0136.12702 · doi:10.1016/0041-5553(63)90412-9
[18] Freund, R.: Über einige cg-ähnliche Verfahren zur Lösung linearers Gleichungssysteme. Doctoral Thesis, Universität Würzburg, F.R. of Germany May, 1983 · Zbl 0531.65017
[19] Freund, R., Ruscheweyh, St.: On a class of Chebyshev approximation problems which arise in connection with a conjugate gradient type method. Numer. Math.48, 525-542 (1986) · Zbl 0611.65016 · doi:10.1007/BF01389449
[20] Goldstein, C.I.: Multigrid preconditioners applied to three-dimensional parabolic equation type models. In: Lee, D., Sternberg, R.L., Schultz, M.H. (eds.) Computational acoustics: wave propagation, pp. 57-74. Amsterdam: North-Holland 1988
[21] Golub, G.H., Van Loan, C.F.: Matrix computatiom. Baltimore: The Johns Hopkins University Press 1983 · Zbl 0559.65011
[22] Golub, G.H., Varga, R.S.: Chebyshev semi-iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods. Numer. Math.3, 147-168 (1961) · Zbl 0099.10903 · doi:10.1007/BF01386013
[23] Hestenes, M.R., Stiefel, E.: Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bur. Stand.49, 409-436 (1952) · Zbl 0048.09901
[24] Householder, A.S.: The theory of matrices in numerical analysis. New York: Blaisdell 1964 · Zbl 0161.12101
[25] Johnson, O.G., Micchelli, C.A., Paul, G.: Polynomial preconditioners for conjugate gradient calculations. SIAM J. Numer. Anal.20, 362-376 (1983) · Zbl 0563.65020 · doi:10.1137/0720025
[26] Joubert, W.D., Young, D.M.: Necessary and sufficient conditions for the simplification of generalized conjugate-gradient algorithms. Linear Algebra Appl.88/89, 449-485 (1987) · Zbl 0632.65030 · doi:10.1016/0024-3795(87)90120-0
[27] Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integrals operators. J. Res. Natl. Bur. Stand.45, 255-282 (1950)
[28] Marfurt, K.J.: Finite element modeling of elastodynamic and electromagnetic wave propagation for geophysical exploration. In: Glowinski, R., Lions, J.L. (eds.) Computing methods in applied sciences and engineering VII, pp. 517-547. Amsterdam: North Holland 1986 · Zbl 0705.73248
[29] Meinardus, G.: Approximation of functions: Theory and numerical methods. Berlin Heidelberg New York: Springer 1967 · Zbl 0152.15202
[30] 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
[31] Peterson, A.F., Mittra, R.: Method of conjugate gradients for the numerical solution of large-body electromagnetic scattering problems. J. Opt. Soc. Am. A2, 971-977 (1985) · doi:10.1364/JOSAA.2.000971
[32] Pierce, A.D.: Acoustics: An introduction to its physical principles and applications. New York: McGraw-Hill 1981
[33] Rapoport, D.: A nonlinear Lanczos algorithm and the stationary Navier-Stokes equation. Ph.D. Thesis, Department of Mathematics, New York University, October 1978
[34] Rutishauser, H.: Theory of gradient methods. In: Refined iterative methods for computation of the solution and the eigenvalues of self-adjoint boundary value problems, pp. 24-49. Mitteilungen aus dem Institut für Angewandte Mathematik an der ETH Zürich, Vol. 8. Basel: Birkhäuser 1959
[35] Saad, Y.: Krylov subspace methods on supercomputers. SIAM J. Sci. Stat. Comput.10, 1200-1232 (1989) · Zbl 0693.65028 · doi:10.1137/0910073
[36] Saad, Y., Schultz, M.H.: Conjugate gradient-like algorithm for solving nonsymmetric linear systems. Math. Comput.44, 417-424 (1985) · Zbl 0566.65019 · doi:10.1090/S0025-5718-1985-0777273-9
[37] Schultz, M.H., Lee, D., Jackson, K.R.: Application of the Yale sparse technique to solve the 3-dimensional parabolic wave equation. In: Scully-Power. P.D., Lee, D. (eds.) Recent progress in the development and application of the parabolic equation. Naval Underwater Systems Center, Technical Document 7145, May 1984
[38] Sidi, A.: Extrapolation vs. projection methods for linear systems of equations. J. Comput. Appl. Math.22, 71-88 (1988) · Zbl 0646.65031 · doi:10.1016/0377-0427(88)90289-0
[39] Stoer, J.: Solution of large linear systems of equations by conjugate gradient type methods. In: Bachem, A., Grötschel, M., Korte, B. (eds.) Mathematical programming ? The state of the art, pp 540-565. Berlin Heidelberg New York Tokyo: Springer 1983
[40] Stoer, J., Freund, R.: On the solution of large indefinite systems of linear equations by conjugate gradient algorithms In: Glowinski, R., Lions, J.L. (eds.) Computing methods in applied sciences and engineering V, pp 35-53. Amsterdam: North Holland 1982 · Zbl 0499.65018
[41] Szyld, D.B.: A two-level iterative method for large sparse generalized eigen value calculations. Ph.D. Thesis, Department of Mathematics, New York University, October 1983
[42] Szyld, D.B., Widlund, O.: Applications of conjugate gradient type methods to eigenvalue calculations. In: Vichnevetsky, R., Stepleman, R.S. (eds.) Advances in computer methods for partial differential equations III, pp. 167-173. New Brunswick: IMACS 1979
[43] Trummer, M.: An efficient implementation of a conformal mapping method based on the Szegö kernel. SIAM J. Numer. Anal.23, 853-872 (1986) · Zbl 0596.30013 · doi:10.1137/0723055
[44] Widlund, O.: A Lanczos method for a class of nonsymmetric systems of linear equations. SIAM J. Numer. Anal.15, 801-812 (1978) · Zbl 0398.65030 · doi:10.1137/0715053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.