Инд. авторы:	Jung M., Matsokin A.M., Nepomnyaschikh S.V., Tkachov Y.A.
Заглавие:	Preconditioning by multilevel methods with locally modified grids
Библ. ссылка:	Jung M., Matsokin A.M., Nepomnyaschikh S.V., Tkachov Y.A. Preconditioning by multilevel methods with locally modified grids // Сибирский журнал вычислительной математики. - 2006. - Vol.9. - Iss. 4. - P.403-422. - ISSN 1560-7526.
Внешние системы:	РИНЦ: 9278548;
Реферат:	rus: В статье рассматриваются системы сеточных уравнений, аппроксимирующих эллиптические краевые задачи на локально модифицированных сетках. Предлагаются правила сдвига приграничных узлов равномерной триангуляции области для построения новой триангуляции, аппроксимирующей границу области со вторым порядком точности. Локально модифицированная сетка обладает следующими свойствами: она имеет регулярную структуру, процесс генерации сетки быстр, такая конструкция позволяет использовать многоуровневые переобусловливатели (аналогичные ВРХ методу). Предлагаемые итерационные методы решения сеточных эллиптических краевых задач основаны на двух подходах: методе фиктивного пространства, т. е. сведении исходной задачи к задаче во вспомогательном (фиктивном) пространстве и многоуровневом методе декомпозиции, т. е. построении переобусловливателей на основе разложений функций на иерархических сетках. Скорость сходимости итерационного процесса с соответствующим переобусловливателем не зависит от шага сетки. Построение сетки и переобусловливающего оператора для трехмерного случая осуществляется аналогичным образом. eng: 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.
Ключевые слова:	mesh generation; finite element method; эллиптические краевые задачи; multilevel methods; метод конечных элементов; генерация сетки; Elliptic boundary value problems;
Издано:	2006
Физ. характеристика:	с.403-422
Цитирование:	1. Юнг М., Мацокин A.M., Непомнящих С.В., Ткачев Ю.А. Методы многоуровневого переобуславливания на локально модифицированных сетках // Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. - Новосибирск, 2006. -Т. 9, № 4. -С. 403-421. 2. Jung M., Matsokin A.M., Nepomnyaschikh S.V. and Tkachov Yu.A. Preconditioning by multilevel methods with locally modified grids // Siberian J. of Numer. Mathematics / Sib. Branch of Russ. Acad, of Sci.-Novosibirsk, 2006. -Vol. 9, № 4.-P. 403-421. 3. Aubin J.-P. Approximation of Elliptic Boundary-Value Problems. - New York etc.: Wiley-Interscience, 1972. 4. Bank R.E., Xu J. The hierarchical basis multigrid method and incomplete LU decomposition // Contemporary Mathematics / Domain decomposition for PDEs. D.E. Keyes, J.Xu, eds.- 1994.-Vol. 180.-P. 163-174. 5. 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. -Finland, Jyväskylä: Laboratory of Scientific Computing, Department of Mathematics, University of Jyväskylä, 1993. - (Moscow-Jyväskylä report series). 6. Bornemann F.A., Yserentant H. A basic norm equivalence for the theory of multilevel methods // Numer. Math.-1993.-Vol. 64.-P. 455-476. 7. Bramble J.H., Pasciak J.E., Xu J. Parallel multilevel preconditioners // Math. Comput.- 1990.-Vol. 55, № 191.-P. 1-22. 8. Brandt A. Multi-level adaptive solutions to boundary value problems // Math. Comput.- 1977.-Vol. 31.-P. 333-390. 9. Chan T.F., Smith B. Domain decomposition and multigrid algorithms for elliptic problems on unstructured meshes. -Los Angeles: Department of Mathematics, University of California, 1993.-(CAM Report 93-42). 10. Ciarlet P. The Finite Element Method for Elliptic Problems. - Amsterdam: North-Holland, 1978. 11. Dyadechko V.G., Finogenov S.A., Iliash Yu.I., Tkhir A.V., Vassilevski Yu.V. Efficient solving the Poisson equation: fictitious domains&separable preconditioners on rectangular locally fitted meshes versus algebraic multigrid/fictitious space method on unstructured triangulations.- Germany: Mathematical Institute A, Stuttgart University, 1996.-(Technical Report). 12. Fedorenko R.P. Relaksacionnyj metod resenija raznostnych ellipticeskich uravnenij // ZVMiMF.-1961.-Vol. 1, № 3.-P. 922-927. 13. Finogenov S.A., Kuznetsov Yu.A. Two-stage fictitious components method for solving the Dirichlet boundary value problem // Sov. J. Numer. Anal. Math. Modelling. -1988. -Vol. 3, №4.-P. 301-323. 14. Hackbusch W. Ein iteratives Verfahren zur schnellen Auflosung elliptischer Randwertprob-leme. -Köln: Universität Köln, Institut für Angewandte Mathematik, 1976. - (Report 76-12). 15. Hackbusch W. Multi-Grid Methods and Applications // Springer Series in Computational Mathematics. -Berlin: Springer, 1985. -Vol. 4. 16. 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. - Netherlands: University of Nijmegen, 1995.-(Report № 9543). 17. Kornhuber R., Yserentant H. Multilevel methods for elliptic problems on domains not resolved by the coarse grid // Contemporary Mathematics / Domain decomposition for PDEs. D.E. Keyes and J. Xu, eds.-1994.-Vol. 180.-P. 49-60. 18. Kuznetsov Yu., Finogenov S., Supalov A. Fictitious domain methods for 3D elliptic problems: algorithms and software within a parallel environment / Arbeitspapiere der GMD № 726, GMD, 1993. 19. Matsokin A.M. Automatization of the triangulation of domains with smooth boundary for solving equations of elliptic type.--Novosibirsk, 1975.- (Preprint / VC SO RAN; 15. In Russian). 20. Nepomnyaschikh S.V. Fictitious space method on unstructured meshes // East-West J. Numer. Math.-1995. -Vol. 3, № 1. 21. Oganesyan L.A., Rivkind V.Ya., Rukhovets L.A. Variational-difference methods for the solution of elliptic equations. Part I. // Trudy Sem. Inst. Fiz. i Mat. Akad. Nauk Litovskoi SSR / Differencialnye uravnenija i ikh primenenie. - Vilnius.-1974. - Vol. 8. (In Russian). 22. Oganesyan L.A., Rukhovets L.A. Variational-Difference Methods for the Solution of Elliptic Equations. -Jerevan: Izd. Akad. Nauk Armianskoi SSR, 1979. (In Russian). 23. Oswald P. Multilevel Finite Element Approximation: Theory and Applications. -B.G. Teubner Stuttgart: Teubner Skripten zur Numerik, 1994. 24. Reid J.K. On the construction and convergence of a finite-element solution of Laplace`s equation // J. Inst. Math. Applics.-1972.-Vol. 9.-P. 1-13. 25. Tkachov Yu.A. Algorithm of automatic generation of the triangular meshes for two-dimensional domains with piecewise smooth boundary. - Novosibirsk, 1986. - Dep. VINITI, № 8335, (In Russian). 26. Tkachov Yu.A. Algorithm of automatic generation of the triangular meshes for two-dimensional domains with piecewise smooth boundary // Mashinnaya grafika i ее primenenie. - Novosibirsk, 1987. (In Russian). 27. Xu J. Iterative methods by space decomposition and subspace correction // SIAM Review.- 1992.-Vol. 34, № 4.-P. 581-613. 28. Xu J. The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids // Computing.-1996. -Vol. 56. -P. 215-235. 29. Yakovlev G.N. On traces of piecewise-smooth surfaces of functions from the space Wlp // Mat. Sbornik.-1967.-Vol. 74.-P. 526-543.