Geodesic
Preconditioning by multilevel methods with locally modified grids
Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 9 (2006) no. 4, pp. 403-421.

Voir la notice de l'article provenant de la source Math-Net.Ru

Systems of grid equations that approximate elliptic boundary value problems on locally modified grids are considered. The triangulation, which approximates the boundary with second order of accuracy, is generated from an initial uniform triangulation by shifting nodes near the boundary according to special rules. This “locally modified” grid possesses several significant features: this triangulation has a regular structure, generation of the triangulation is rather fast, this construction allows the use of multilevel preconditioning (BPX-like) methods. The proposed iterative methods for solving grid elliptic boundary value problems are based on two approaches: the fictitious space method, i.e., reduction of the original problem to that in an auxiliary (fictitious) space, and the multilevel decomposition method, i.e., construction of preconditioners by decomposing functions on hierarchical grids. The convergence rate of the corresponding iterative process with the preconditioner obtained is independent of the mesh size. The construction of the grid and the preconditioning operator for the three-dimensional problem can be done in the same manner. 
@article{SJVM_2006_9_4_a7,
     author = {M. Jung and A. M. Matsokin and S. V. Nepomnyaschikh and Yu. A. Tkachov},
     title = {Preconditioning by multilevel methods with locally modified grids},
     journal = {Sibirskij \v{z}urnal vy\v{c}islitelʹnoj matematiki},
     pages = {403--421},
     publisher = {mathdoc},
     volume = {9},
     number = {4},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SJVM_2006_9_4_a7/}
}
TY  - JOUR
AU  - M. Jung
AU  - A. M. Matsokin
AU  - S. V. Nepomnyaschikh
AU  - Yu. A. Tkachov
TI  - Preconditioning by multilevel methods with locally modified grids
JO  - Sibirskij žurnal vyčislitelʹnoj matematiki
PY  - 2006
SP  - 403
EP  - 421
VL  - 9
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SJVM_2006_9_4_a7/
LA  - en
ID  - SJVM_2006_9_4_a7
ER  - 
%0 Journal Article
%A M. Jung
%A A. M. Matsokin
%A S. V. Nepomnyaschikh
%A Yu. A. Tkachov
%T Preconditioning by multilevel methods with locally modified grids
%J Sibirskij žurnal vyčislitelʹnoj matematiki
%D 2006
%P 403-421
%V 9
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SJVM_2006_9_4_a7/
%G en
%F SJVM_2006_9_4_a7
M. Jung; A. M. Matsokin; S. V. Nepomnyaschikh; Yu. A. Tkachov. Preconditioning by multilevel methods with locally modified grids. Sibirskij žurnal vyčislitelʹnoj matematiki, Tome 9 (2006) no. 4, pp. 403-421. http://geodesic.mathdoc.fr/item/SJVM_2006_9_4_a7/

[1] Aubin J.-P., Approximation of Elliptic Boundary-Value Problems, Wiley-Interscience, New York etc., 1972 | MR | Zbl

[2] Bank R. E., Xu J., “The hierarchical basis multigrid method and incomplete LU decomposition”, Domain decomposition methods in scientific and engineering computing, Contemporary Mathematics, 180, eds. D. E. Keyes, J. Xu, 1994, 163–173 | MR | Zbl

[3] Bespalov A. N., Finogenov S. A., Kuznetsov Yu. A., Supalov A. V., Lipnikov K. N., Generation of three-dimensional locally fitted meshes. Algorithms and software, Moscow-Jyväskylä report series, Laboratory of Scientific Computing, Department of Mathematics, University of Jyväskylä, Finland, Jyväskylä, 1993

[4] Bornemann F. A., Yserentant H., “A basic norm equivalence for the theory of multilevel methods”, Numer. Math., 64 (1993), 455–476 | DOI | MR | Zbl

[5] Bramble J. H., Pasciak J. E., Xu J., “Parallel multilevel preconditioners”, Math. Comput., 55:191 (1990), 1–22 | DOI | MR | Zbl

[6] Brandt A., “Multi-level adaptive solutions to boundary value problems”, Math. Comput., 31 (1977), 333–390 | DOI | MR | Zbl

[7] Chan T. F., Smith B., Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes, CAM Report 93-42, Department of Mathematics, University of California, Los Angeles, 1993 | MR

[8] Ciarlet P., The Finite Element Method for Elliptic Problems, North-Holland, Amsterdam, 1978 | MR | Zbl

[9] Dyadechko V. G., Finogenov S. A., Iliash Yu. I., Tkhir A. V., Vassilevski Yu. V., Encient solving the Poisson equation: fictitious domains separable preconditioners on rectangular locally fitted meshes versus algebraic multigrid/fictitious space method on unstructured triangulations, Technical Report, Mathematical Institute A, Stuttgart University, Germany, 1996 | Zbl

[10] Fedorenko R. P., “Relaksacionnyj metod rešenija raznostnych elliptičeskich uravnenij”, ŽVMiMF, 1:3 (1961), 922–927 | MR | Zbl

[11] Finogenov S. A., Kuznetsov Yu. A., “Two-stage fictitious components method for solving the Dirichlet boundary value problem”, Sov. J. Numer. Anal. Math. Modelling, 3:4 (1988), 301–323 | MR | Zbl

[12] Hackbusch W., Ein iteratives Verfahren zur schnellen Auflösung elliptischer Randwertprobleme, Report 76-12, Universität Köln, Institut für Angewandte Mathematik, Köln, 1976

[13] Hackbusch W., Multi-Grid Methods and Applications, Springer Series in Computational Mathematics, 4, Springer, 1985 | MR | Zbl

[14] Iliash Yu. I., Kuznetsov Yu. A., Vassilevski Yu. V., On the application of fictitious domain and strengthened AMG methods for locally fitted 3D cartesian meshes to the potential flow problem on a massively parallel computer, Report No 9543, University of Nijmegen, Netherlands, 1995

[15] Kornhuber R., Yserentant H., “Multilevel methods for elliptic problems on domains not resolved by the coarse grid”, Domain decomposition methods in scientific and engineering computing, Contemporary Mathematics, 180, eds. D. E. Keyes and J. Xu, 1994, 49–60 | MR | Zbl

[16] Kuznetsov Yu., Finogenov S., Supalov A., Fictitious domain methods for 3D elliptic problems: algorithms and software within a parallel environment, Arbeitspapiere der GMD No 726, 1993

[17] Matsokin A. M., Automatization of the triangulation of domains with smooth boundary for solving equations of elliptic type, Preprint / VC SO RAN; 15, Novosibirsk, 1975 (In Russian)

[18] Nepomnyaschikh S. V., “Fictitious space method on unstructured meshes”, East-West J. Numer. Math., 3:1 (1995), 71–79 | MR | Zbl

[19] Oganesyan L. A., Rivkind V. Ya., Rukhovets L. A., “Variational-dikerence methods for the solution of elliptic equations. Part I”, Dikerencialnye uravnenija i ikh primenenie, Trudy Sem. Inst. Fiz. i Mat. Akad. Nauk Litovskoi SSR, 8, Vilnius, 1974 (In Russian) | Zbl

[20] Oganesyan L. A., Rukhovets L. A., Variational-Dikerence Methods for the Solution of Elliptic Equations, Izd. Akad. Nauk Armianskoi SSR, Jerevan, 1979 (In Russian)

[21] Oswald P., Multilevel Finite Element Approximation: Theory and Applications, Teubner Skripten zur Numerik, B. G. Teubner, Stuttgart, 1994 | MR | Zbl

[22] Reid J. K., “On the construction and convergence of a finite-element solution of Laplace's equation”, J. Inst. Math. Applics, 9 (1972), 1–13 | DOI | MR | Zbl

[23] Tkachov Yu. A., Algorithm of automatic generation of the triangular meshes for two-dimensional domains with piecewise smooth boundary, Dep. VINITI, No 8335, Novosibirsk, 1986 (In Russian)

[24] Tkachov Yu. A., “Algorithm of automatic generation of the triangular meshes for two-dimensional domains with piecewise smooth boundary”, Mashinnaya grafika i ee primenenie, Novosibirsk, 1987 (In Russian)

[25] Xu J., “Iterative methods by space decomposition and subspace correction”, SIAM Review, 34:4 (1992), 581–613 | DOI | MR | Zbl

[26] Xu J., “The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids”, Computing, 56 (1996), 215–235 | DOI | MR | Zbl

[27] Yakovlev G. N., “On traces of piecewise-smooth surfaces of functions from the space $W$”, Mat. Sbornik, 74:4 (1967), 526–543 | MR | Zbl