An adaptive Chebyshev iterative method

V. T. Zhukov ; N. D. Novikova ; O. B. Feodoritova

Matematičeskoe modelirovanie, Tome 30 (2018) no. 10, pp. 67-85.

Résumé

For the numerical solution of a boundary-value problem of three-dimensional elliptic equations an adaptive Chebyshev iterative method is constructed. In this adaptive method, the unknown lower bound of the spectrum of the discrete operator is refined in the additional cycle of the iterative method; the upper bound of the spectrum is taken to be its estimate by the Gershgorin theorem. Such procedure ensures the convergence of the constructed adaptive method with computational costs close to the costs of the Chebyshev method, which uses the exact boundaries of the spectrum of the discrete operator.

Détail

Mots-clés : elliptic equations
Keywords: Chebyshev polynomials, adaptive method.

Bibliographie

[1] V.T. Zhukov, N.D. Novikova, O.B. Feodoritova, “Multigrid method for anisotropic diffusion equations based on adaptive Chebyshev smoothers”, Mathematical Models and Computer Simulations, 7:2 (2015), 117–127

[2] V.T. Zhukov, N.D. Novikova, O.B. Feodoritova, “Multigrid method for elliptic equations with anisotropic discontinuous coefficients”, Computational Mathematics and Mathematical Physics, 55:7 (2015), 1150–1163

[3] V.T. Zhukov, N.D. Novikova, O.B. Feodoritova, “On the solution of evolution equations based on multigrid and explicit iterative methods”, Computational Mathematics and Mathematical Physics, 55:8 (2015), 1276–1289

[4] V.T. Zhukov, M.M. Krasnov, N.D. Novikova, O.B. Feodoritova, “Algebraicheskii mnogosetochnyi metod s adaptivnymi sglazhivateliami na osnove mnogochlenov Chebysheva”, IPM im. M.V. Keldysha RAN, 2016, 113, 32 pp. | DOI

[5] A.H. Baker, R.D. Falgout, T. Gamblin, T.V. Kolev, M. Schulz, U.M. Yang, “Scaling Algebraic Multigrid Solvers: On the Road to Exascale”, Competence in High Performance Computing 2010, Springer, Berlin–Heidelberg, 2011, 215–226

[6] A. Baker, R. Falgout, T. Kolev, U. Yang, “Multigrid smoothers for ultra-parallel computing”, SIAM J. Sci. Comput., 33:5 (2011), 2864–2887

[7] F.R. Gantmakher, Teoriya matrits, Nauka, M., 1966, 576 pp.; F.R. Gantmacher, The Theory of Matrices, AMS Chelsea Publishing; Reprinted by American Mathematical Society, 2000, 660 pp.

[8] A.A. Samarskii, E.S. Nikolaev, Metody resheniya setochnykh uravnenii, Nauka, M., 1978, 592 pp.; A.A. Samarskii, E.S. Nikolaev, Numerical Methods for Grid Equations, v. 1, Direct Methods, Birkhauser Verlag, Basel–Boston–Berlin, 1989, 242 pp.; v. 2, Iterative Methods, 502 pp.

[9] P.L. Chebyshev, Voprosy o naimen'shih velichinah, svyazannye s priblizhennym predstavleniem funkcij, v. 1, Sochineniya, SPb., 1899, 705–710

[10] A.S. Shvedov, V.T. Zhukov, “Explicit iterative difference schemes for parabolic equations”, Russian J. Numer. Anal. Math. Modeling, 13:2 (1998), 133–148

[11] L.F. Richardson, “The approximate arithmetical solution by finite differences of physical problems involving differential equations with an application to the stresses in a masonry dam”, Roy. Soc. Philos. Trans. A, 210 (1910), 307–357

[12] M.K. Gavurin, “Primenenie polinomov nailuchshego priblizheniia k uluchsheniiu skhodimosti iterativnykh protsessov”, UMN, 5:3(37) (1950), 156–160

[13] D. Flanders, G. Shortley, “Numerical determination of fundamental modes”, Appl. Phys., 21:12 (1950), 1326–1332

[14] G.H. Shortley, “Use of Tschebyscheff-polynomial operators in the solution of boundary value problems”, J. Appl. Phys., 24 (1953), 392–396.

[15] D.M. Young, “On Richardson's method for solving linear systems with positive definite matrices”, Math. Phys., 32:4 (1954), 243–255

[16] V.I. Lebedev, S.A. Finogenov, “O poriadke vybora iteratsionnykh parametrov v chebyshevskom tsiklicheskom metode”, Zh. vychisl. mat. i mat. fiz. матем., 11:2 (1971), 425–438

[17] E.S. Nikolaev, A.A. Samarskii, “Vybor iteratsionnykh parametrov v metode Richardsona”, Zh. vychisl. matem. i matem. fiz., 12:4 (1972), 960–973

[18] Yuan' Chzhao-din, Nekotorye raznostnye skhemy resheniya pervoj kraevoj zadachi dlya linejnyh differencial'nyh uravnenij s chastnymi proizvodnymi, Diss. na soisk. uchenoj stepeni kand. fiz.-mat. nauk, MGU, M., 1958

[19] Yuan' Chzhao-din, “Nekotorye raznostnye skhemy chislennogo resheniya differencial'nogo uravneniya parabolicheskogo tipa”, Matem. sbornik, 50 (92):4 (1960), 391–422

[20] Yuan' Chzhao-din, “Ob ustojchivosti raznostnyh skhem dlya resheniya differencial'nyh uravnenij parabolicheskogo tipa”, DAN SSSR, 117:4 (1957), 578–581

[21] V.K. Saul'ev, Integrirovanie uravnenij parabolicheskogo tipa metodom setok, ed. Lyusternik L. A., Fizmatgiz, M., 1960, 324 pp.

[22] L.A. Lyusternik, “Zamechaniya k chislennomu resheniyu kraevyh zadach uravneniya Laplasa i vychisleniyu sobstvennyh znachenij metodom setok”, Tr. Matem. in-ta im. V.A. Steklova, 20 (1947), 49–64

[23] N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov, Chislennye metody, Nauka, M., 1987, 600 pp.

[24] J. Demmel, Applied Numerical Linear Algebra, SIAM, 1997, 431 pp.

[25] R. Eymard, G. Henry, R. Herbin, F. Hubert, R. Klofkorn, G. Manzini, 3D Benchmark on Discretization Schemes for Anisotropic Diffusion Problems on General Grids, , 2011 hal-00580549

[26] V.T. Zhukov, N.D. Novikova, O.B. Feodoritova, “Adaptivnyj chebyshevskij algoritm”, Preprint IPM im. M.V. Keldysha RAN, 2017, 32 pp.