Previous |  Up |  Next

Article

Keywords:
conjugate gradient method; superlinear convergence; mesh independence; preconditioning operator
Summary:
A mesh independent bound is given for the superlinear convergence of the CGM for preconditioned self-adjoint linear elliptic problems using suitable equivalent operators. The results rely on K-condition numbers and related estimates for compact Hilbert-Schmidt operators in Hilbert space.
References:
[1] O.  Axelsson: Iterative Solution Methods. Cambridge University Press, Cambridge, 1994. MR 1276069 | Zbl 0813.15021
[2] O.  Axelsson, I.  Kaporin: On the sublinear and superlinear rate of convergence of conjugate gradient methods. Mathematical journey through analysis, matrix theory and scientific computation (Kent, OH, 1999). Numer. Algorithms 25 (2000), 1–22. DOI 10.1023/A:1016694031362 | MR 1827142
[3] O.  Axelsson, J.  Karátson: On the rate of convergence of the conjugate gradient method for linear operators in Hilbert space. Numer. Funct. Anal. Optmization 23 (2002), 285–302. DOI 10.1081/NFA-120006694 | MR 1914497
[4] O.  Axelsson, J. Karátson: Superlinearly convergent CG methods via equivalent preconditioning for nonsymmetric elliptic operators. Numer. Math. 99 (2004), 197–223, SpringerLink DOI: 10.1007/s00211-004-0557-2 (electronic). DOI 10.1007/s00211-004-0557-2 | MR 2107430
[5] R. E. Bank, D. J.  Rose: Marching algorithms for elliptic boundary value problems. I.  The constant coefficient case. SIAM J.  Numer. Anal. 14 (1977), 792–829. DOI 10.1137/0714055 | MR 0502000
[6] R. E.  Bank: Marching algorithms for elliptic boundary value problems. II.  The variable coefficient case. SIAM J.  Numer. Anal. 14 (1977), 950–970. DOI 10.1137/0714064 | MR 0502001 | Zbl 0382.65052
[7] B.  Beckermann, A. B. J.  Kuijlaars: Superlinear convergence of conjugate gradients. SIAM J.  Numer. Anal. 39 (2001), 300–329, Electronic. DOI 10.1137/S0036142999363188 | MR 1860727
[8] P.  Concus, G. H.  Golub: Use of fast direct methods for the efficient numerical solution of nonseparable elliptic equations. SIAM J.  Numer. Anal. 10 (1973), 1103–1120. DOI 10.1137/0710092 | MR 0341890
[9] J. W.  Daniel: The conjugate gradient method for linear and nonlinear operator equations. SIAM J.  Numer. Anal. 4 (1967), 10–26. DOI 10.1137/0704002 | MR 0217987 | Zbl 0154.40302
[10] H. C.  Elman, M. H. Schultz: Preconditioning by fast direct methods for nonself-adjoint nonseparable elliptic equations. SIAM J.  Numer. Anal. 23 (1986), 44–57. DOI 10.1137/0723004 | MR 0821905
[11] V.  Faber, T.  Manteuffel, and S. V.  Parter: On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations. Adv. Appl. Math. 11 (1990), 109–163. DOI 10.1016/0196-8858(90)90007-L | MR 1053227
[12] I.  Faragó, J.  Karátson: Numerical solution of nonlinear elliptic problems via preconditioning operators. Theory and applications. Advances in Computation, Vol.  11, NOVA Science Publishers, Huntington, 2002. MR 2106499
[13] Z.  Fortuna: Some convergence properties of the conjugate gradient method in Hilbert space. SIAM J.  Numer. Anal. 16 (1979), 380–384. DOI 10.1137/0716031 | MR 0530475 | Zbl 0414.65029
[14] I.  Gohberg, S. Goldberg, and M. A. Kaashoek: Classes of linear operators, Vol.  I. Operator Theory: Advances and Applications, Vol. 49, Birkhäuser-Verlag, Basel, 1990. MR 1130394
[15] R. M.  Hayes: Iterative methods of solving linear problems in Hilbert space. Natl. Bur. Stand.; Appl. Math. Ser. 39 (1954), 71–103. MR 0066563
[16] M. R.  Hestenes, E.  Stiefel: Methods of conjugate gradients for solving linear systems. J.  Res. Natl. Bur. Stand., Sect.  B 49 (1952), 409–436. DOI 10.6028/jres.049.044 | MR 0060307
[17] J. Kadlec: On the regularity of the solution of the Poisson problem on a domain with boundary locally similar to the boundary of a convex open set. Czechoslovak Math.  J. 14(89) (1964), 386–393. (Russian) MR 0170088 | Zbl 0166.37703
[18] J. Karátson, I. Faragó: Variable preconditioning via quasi-Newton methods for nonlinear problems in Hilbert space. SIAM J.  Numer. Anal. 41 (2003), 1242–1262. DOI 10.1137/S0036142901384277 | MR 2034879
[19] T.  Manteuffel, J. Otto: Optimal equivalent preconditioners. SIAM J.  Numer. Anal. 30 (1993), 790–812. DOI 10.1137/0730040 | MR 1220653
[20] J. W.  Neuberger: Sobolev gradients and differential equations. Lecture Notes in Math., No.  1670, Springer-Verlag, Berlin, 1997. MR 1624197 | Zbl 0935.35002
[21] T. Rossi, J.  Toivanen: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension. SIAM J.  Sci. Comput. 20 (1999), 1778–1793. DOI 10.1137/S1064827597317016 | MR 1694683
[22] T. Rossi, J.  Toivanen: Parallel fictitious domain method for a non-linear elliptic Neumann boundary value problem. Czech-US Workshop in Iterative Methods and Parallel Computing, Part  I (Milovy, 1997). Numer. Linear Algebra Appl. 6 (1999), 51–60. MR 1684652
[23] W.  Rudin: Functional Analysis. McGraw-Hill, New York, 1991. MR 1157815 | Zbl 0867.46001
[24] F.  Riesz, B. Sz.-Nagy: Vorlesungen über Funktionalanalysis. VEB Deutscher Verlag der Wissenschaften, Berlin, 1982. Zbl 0483.47001
[25] L. Simon, E. Baderko: Linear Partial Differential Equations of Second Order. Tankönyvkiadó, Budapest, 1983. (Hungarian)
[26] P. N.  Swarztrauber: The methods of cyclic reduction, Fourier analysis and the FACR  algorithm for the discrete solution of Poisson’s equation on a rectangle. SIAM Rev. 19 (1977), 490–501. DOI 10.1137/1019071 | MR 0438732 | Zbl 0358.65088
[27] Yu. V. Vorobyev: Methods of Moments in Applied Mathematics. Gordon and Breach, New York, 1965. MR 0184400 | Zbl 0196.47601
[28] R.  Winter: Some superlinear convergence results for the conjugate gradient method. SIAM J.  Numer. Anal. 17 (1980), 14–17. DOI 10.1137/0717002 | MR 0559456
Partner of
EuDML logo