maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-1-39-63mais-425Research ArticleОригинальные статьиArticlesО комбинировании различных методов ускорения при итерационном решении уравнений с частными производными методом коллокаций и наименьших невязокOn Combining Different Acceleration Techniques at the Iterative Solution of PDEs by the Method of Collocations and Least Residualshttps://orcid.org/0000-0001-6761-7273ШапеевВасилий ПавловичShapeevVasily P.

доктор физ.-мат. наук, профессор, ул. Институтская, 4/1, г. Новосибирск, 630090;

ул. Пирогова, 2, г. Новосибирск, 630090

 

Doctor of physical and mathematical sciences, professor, 4/1 Institutskaya str., Novosibirsk 630090;

2, Pirogov str., Novosibirsk 630090

vshapeev@ngs.ruhttps://orcid.org/0000-0003-2753-8399ВорожцовЕвгений ВасильевичVorozhtsovEvgenii V.

доктор физ.-мат. наук, профессор, 

ул. Институтская, 4/1, г. Новосибирск, 630090 

Doctor of physical and mathematical sciences, professor,

4/1 Institutskaya str., Novosibirsk 630090

vorozh@itam.nsc.ruИнститут теоретической и прикладной механики им. С. А. Христиановича СО РАН; Новосибирский национальный исследовательский университетРоссияKhristianovich Institute of Theoretical and Applied Mechanics, Siberian Branch of the Russian Academy of Sciences; Novosibirsk National Research UniversityRussian FederationИнститут теоретической и прикладной механики им. С. А. Христиановича СО РАНРоссияKhristianovich Institute of Theoretical and Applied Mechanics, Siberian Branch of the Russian Academy of SciencesRussian Federation2017210220172413963Copyright © Шапеев В.П., Ворожцов Е.В., 20172017Шапеев В.П., Ворожцов Е.В.Shapeev V.P., Vorozhtsov E.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/425

Рассматривается проблема ускорения итерационного процесса численного решения методом коллокаций и наименьших невязок (КНН) краевых задач для уравнений с частными производными (PDE). Для решения этой проблемы впервые предложено комбинированно приме- нять одновременно три способа ускорения итерационного процесса: предобуславливатель, многосеточный алгоритм и коррекцию решения PDE на промежуточных итерациях в подпространстве Крылова. Исследовано влияние на итерационный процесс всех трех способов его ускорения как по отдельности, так и при их комбинировании. Показано, что каждый из указанных способов вносит свой вклад в количественный показатель ускорения итерационного процесса. При этом наибольший вклад дает применение алгоритма, использующего подпространства Крылова. Комбинированное применение одновременно всех трех способов ускорения итерационного процесса решения конкретных краевых задач позволило уменьшить время их решения на компьютере до 230 раз по сравнению со случаем, когда никакие способы ускорения не применялись. Исследован двухпараметрический предобуславливатель. Предложено находить оптимальные значения его параметров путем численного решения относительно нетрудоемкой задачи минимизации числа обусловленности модифицированной предобуславливателем системы линейных алгебраических уравнений, решаемой в методе КНН. Показано, что в многосеточном варианте метода КНН для существенного уменьшения времени решения краевой задачи достаточно ограничиться только простой операцией продолжения решения на многосеточном комплексе. Приводятся многочисленные примеры расчетов, демонстрирующие эффективность предлагаемых подходов к ускорению итерационных процессов решения краевых задач для двумерных уравнений Навье–Стокса. Указывается, что предложенная комбинация способов ускорения итерационных процессов может быть реализована также в рамках применения других численных методов решения PDE.

In the work, we consider the problem of accelerating the iteration process of the numerical solution of boundary-value problems for partial differential equations (PDE) by the method of collocations and least residuals (CLR). To solve this problem, it is proposed to combine simultaneously three techniques of the iteration process acceleration: the preconditioner, the multigrid algorithm, and the correction of the PDE solution at the intermediate iterations in the Krylov subspace. The influence of all three techniques of the iteration acceleration was investigated both individually for each technique and at their combination. Each of the above techniques is shown to make its contribution to the quantitative figure of iteration process speed-up. The algorithm which employs the Krylov subspaces makes the most significant contribution. The joint simultaneous application of all three techniques for accelerating the iterative solution of specific boundary-value problems enabled a reduction of the CPU time of their solution on computer by a factor of up to 230 in comparison with the case when no acceleration techniques were applied. A two-parameter preconditioner was investigated. It is proposed to find the optimal values of its parameters by the numerical solution of a computationally inexpensive problem of minimizing the condition number of the system of linear algebraic equations. The problem is solved by the CLR method and it is modified by the preconditioner. It is shown that it is sufficient to restrict oneself in the multigrid version of the CLR method only to a simple solution prolongation operation on the multigrid complex to reduce substantially the CPU time of the boundary-value problem solution.

Numerous computational examples are presented, which demonstrate the efficiency of the approaches proposed for accelerating the iterative processes of the numerical solution of the boundary-value problems for the two-dimensional Navier–Stokes equations. It is pointed out that the proposed combination of the techniques for accelerating the iteration processes may be also implemented within the framework of other numerical techniques for the solution of PDEs.

предобуславливаниеподпространства Крыловамногосеточные алгоритмыитерации Гаусса–Зейделяуравнения Навье–Стоксаметод коллокаций и наименьших невязокpreconditioningKrylov subspacesmultigridGauss–Seidel iterationsNavier–Stokes equationsthe method of collocations and least residualsReferencesEdwards W. S., Tuckerman L. S., Friesner R. A., Sorensen D. C., “Krylov methods for the incompressible Navier–Stokes equations”, J. Comput. Phys., 110 (1994), 82–102.Edwards W. S., Tuckerman L. S., Friesner R. A., Sorensen D. C., “Krylov methods for the incompressible Navier–Stokes equations”, J. Comput. Phys., 110 (1994), 82–102.Knoll D. A., Keyes D. E., “Jacobian-free Newton–Krylov methods: a survey of approaches and applications”, J. Comput. Phys., 193:2 (2004), 357–397.Knoll D. A., Keyes D. E., “Jacobian-free Newton–Krylov methods: a survey of approaches and applications”, J. Comput. Phys., 193:2 (2004), 357–397.Griffith B. E., “An accurate and efficient method for the incompressible Navier–Stokes equations using the projection method as a preconditioner”, J. Comput. Phys., 228:20 (2009), 7565–7595.Griffith B. E., “An accurate and efficient method for the incompressible Navier–Stokes equations using the projection method as a preconditioner”, J. Comput. Phys., 228:20 (2009), 7565–7595.Saad Y., Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, 1991.Saad Y., Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, 1991.Крылов А. Н., “О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем”, Изв. АН СССР, Отд. матем. и естеств. наук, 1931, № 4, 491–539.Krylov A. N., “O chislennom reshenii uravneniya, kotorym v tekhnicheskikh voprosakh opredelyayutsya chastoty malykh kolebaniy materialnykh sistem”, Izv. AN SSSR, Otd. matem. i estestv. nauk, 1931, № 4, 491–539, (in Russian).Слепцов А. Г., “Об ускорении сходимости линейных итераций II”, Моделирование в механике, 3(20):5 (1989), 118–125.Sleptsov A. G., “Ob uskorenii skhodimosti lineinykh iteratsiy II”, Modelirovanie v mekhanike, 3(20):5 (1989), 118–125, (in Russian).Федоренко Р. П.“О скорости сходимости одного итерационного процесса”, Ж. вычисл. матем. и матем. физ., 4:3 (1964), 559–564.Fedorenko R. P., “The speed of convergence of one iterative process”, USSR Comput. Math. and Math. Phys., 4:3 (1964), 227–235.Piquet J., Vasseur X., “A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier–Stokes solver”, Num. Algorithms, 24:4 (2000), 333–355.Piquet J., Vasseur X., “A nonstandard multigrid method with flexible multiple semicoarsening for the numerical solution of the pressure equation in a Navier–Stokes solver”, Num. Algorithms, 24:4 (2000), 333–355.Jothiprasad G., Mavriplis D. J., Caughey D. A., “Higher-order time integration schemes for the unsteady Navier–Stokes equations on unstructured meshes”, J. Comput. Phys., 191:2 (2003), 542–566.Jothiprasad G., Mavriplis D. J., Caughey D. A., “Higher-order time integration schemes for the unsteady Navier–Stokes equations on unstructured meshes”, J. Comput. Phys., 191:2 (2003), 542–566.Ge L., Sotiropoulos F., “A numerical method for solving the 3D unsteady incompressible Navier–Stokes equations in curvilinear domains with complex immersed boundaries”, J. Comput. Phys., 225:2 (2007), 1782–1809.Ge L., Sotiropoulos F., “A numerical method for solving the 3D unsteady incompressible Navier–Stokes equations in curvilinear domains with complex immersed boundaries”, J. Comput. Phys., 225:2 (2007), 1782–1809.Lucas P., van Zuijlen A. H., Bijl H., “Fast unsteady flow computations with a Jacobian-free Newton–Krylov algorithm”, J. Comput. Phys., 229:2 (2010), 9201–9215.Lucas P., van Zuijlen A. H., Bijl H., “Fast unsteady flow computations with a Jacobian-free Newton–Krylov algorithm”, J. Comput. Phys., 229:2 (2010), 9201–9215.Nasr-Azadani M. M., Meiburg E., “TURBINS: An immersed boundary, Navier–Stokes code for the simulation of gravity and turbidity currents interacting with complex topographies”, Comp. & Fluids, 45:1 (2011), 14–28.Nasr-Azadani M. M., Meiburg E., “TURBINS: An immersed boundary, Navier–Stokes code for the simulation of gravity and turbidity currents interacting with complex topographies”, Comp. & Fluids, 45:1 (2011), 14–28.Wang M., Chen L., “Multigrid methods for the stokes equations using distributive gaussseidel relaxations based on the least squares commutator”, J. Sci. Comput., 56:2 (2013), 409–431.Wang M., Chen L., “Multigrid methods for the stokes equations using distributive gaussseidel relaxations based on the least squares commutator”, J. Sci. Comput., 56:2 (2013), 409–431.Nickaeen M., Ouazzi A., Turek S., “Newton multigrid least-squares FEM for the V-V-P formulation of the Navier–Stokes equations”, J. Comput. Phys., 256 (2014), 416–427.Nickaeen M., Ouazzi A., Turek S., “Newton multigrid least-squares FEM for the V-V-P formulation of the Navier–Stokes equations”, J. Comput. Phys., 256 (2014), 416–427.Fairag F. A., Wathen A. J., “A block preconditioning technique for the streamfunctionvorticity formulation of the Navier–Stokes equations”, Num. Methods Partial Differential Equations, 28:3 (2012), 888–898.Fairag F. A., Wathen A. J., “A block preconditioning technique for the streamfunctionvorticity formulation of the Navier–Stokes equations”, Num. Methods Partial Differential Equations, 28:3 (2012), 888–898.Benzi M., Wang Z., “Analysis of augmented lagrangian-based preconditioners for the steady incompressible navier-stokes equations”, SIAM J. Sci. Comput., 33:5 (2011), 2761–2784.Benzi M., Wang Z., “Analysis of augmented lagrangian-based preconditioners for the steady incompressible navier-stokes equations”, SIAM J. Sci. Comput., 33:5 (2011), 2761–2784.Jiang B. N., Lin T. L., Povinelli L. A., “Large-scale computation of incompressible viscous flow by least-squares finite element method”, Comput. Meth. Appl. Mech. Engng., 114:3–4 (1994), 213–231.Jiang B. N., Lin T. L., Povinelli L. A., “Large-scale computation of incompressible viscous flow by least-squares finite element method”, Comput. Meth. Appl. Mech. Engng., 114:3–4 (1994), 213–231.Ramˇsak M., Skerget L., “A subdomain boundary element method for high-Reynolds ˇ laminar flow using stream function–vorticity formulation”, Int. J. Numer. Meth. Fluids, 46 (2004), 815–847.Ramˇsak M., Skerget L., “A subdomain boundary element method for high-Reynolds ˇ laminar flow using stream function–vorticity formulation”, Int. J. Numer. Meth. Fluids, 46 (2004), 815–847.Плясунова А. В., Слепцов А. Г., “Коллокационно-сеточный метод решения нелинейных параболических уравнений на подвижных сетках”, Моделирование в механике, 18:4 (1987), 116–137.Plyasunova A. V., Sleptsov A. G., “Kollokatsionno-setochnyi metod resheniya nelineinykh parabolicheskikh uravneniy na podvizhnykh setkakh”, Modelirovanie v mekhanike, 18:4 (1987), 116–137, (in Russian).Carey G. F., Jiang B. N., “Least-squares finite element method and preconditioned conjugate gradient solution”, Int. J. Numer. Methods in Engng., 24:7 (1987), 1283–1296.Carey G. F., Jiang B. N., “Least-squares finite element method and preconditioned conjugate gradient solution”, Int. J. Numer. Methods in Engng., 24:7 (1987), 1283–1296.Jiang B. N., The Least-Squares Finite Element Method: Theory and Applications in Computational Fluid Dynamics and Electromagnetics, Springer, Berlin, 1998.Jiang B. N., The Least-Squares Finite Element Method: Theory and Applications in Computational Fluid Dynamics and Electromagnetics, Springer, Berlin, 1998.Bochev P. B., Gunzburger M. D., “Finite element methods of least-squares type”, SIAM Rev., 40:4 (1998), 789–837.Bochev P. B., Gunzburger M. D., “Finite element methods of least-squares type”, SIAM Rev., 40:4 (1998), 789–837.Soares B. F., Garcia R. V., Pinto P. C., Romao E. C., “Interval study of convergence in the solution of 1D Burgers by least squares finite element method (LSFEM) + Newton linearization”, Scientific Research and Essays, 10:16 (2015), 522–530.Soares B. F., Garcia R. V., Pinto P. C., Romao E. C., “Interval study of convergence in the solution of 1D Burgers by least squares finite element method (LSFEM) + Newton linearization”, Scientific Research and Essays, 10:16 (2015), 522–530.Семин Л. Г., Слепцов А. Г. Шапеев В. П.,, “Метод коллокаций-наименьших квадратов для уравнений Стокса”, Вычисл. технологии, 1:2 (1996), 90–98.Semin L. G., Sleptsov A. G., Shapeev V. P., “Metod kollokatsiy-naimenshikh kvadratov dlya uravneniy Stoksa”, Vychislitelnye tekhnologii, 1:2 (1996), 90–98, (in Russian).Semin L., Shapeev V., “Constructing the numerical method for Navier–Stokes equations using computer algebra system”, LNCS, 3718, Springer, Heidelberg, 2005, 367–378.Semin L., Shapeev V., “Constructing the numerical method for Navier–Stokes equations using computer algebra system”, LNCS, 3718, Springer, Heidelberg, 2005, 367–378.Исаев В. И., Шапеев В. П., “Развитие метода коллокаций и наименьших квадратов”, Труды ИММ УрО РАН, 14:1 (2008), 41–60.Isaev V. I., Shapeev V. P., “Development of the collocations and least squares method”, Proc. Inst. Math. Mech., 261 (2008), 87–106.Исаев В. И., Шапеев В. П., Черепанов А. Н., “Численное моделирование лазерной сварки тонких металлических пластин с учетом конвекции в сварочной ванне”, 13:3 (2010), 451–466.Isaev V.I., Shapeev V. P., Cherepanov A. N., “Numerical simulation of laser welding of thin metallic plates taking into account convection in the welding pool”, Thermophysics and Aeromechanics, 13:3 (2010), 419–434.Исаев В. И., Шапеев В. П., “Метод коллокаций и наименьших квадратов повышенной точности для решения уравнений Навье–Стокса”, Докл. Академии наук, 442:4 (2012), 442–445.Isaev V. I., Shapeev V. P. “High-order accurate collocations and least squares method for solving the Navier–Stokes equations”, Dokl. Math., 85 (2012), 71–74.Слепцов А. Г., Шокин Ю. И., “Адаптивный проекционно-сеточный метод для эллиптических задач”, Ж. вычисл. матем. и матем. физ., 37:5 (1997), 572–586.Sleptsov A. G., Shokin Yu. I., “An adaptive grid-projection method for elliptic problems”, Comput. Math. Math. Phys., 37 (1997), 558–571.Беляев В. В., Шапеев В. П., “Метод коллокаций и наименьших квадратов на адаптивных сетках в области с криволинейной границей”, Вычислительные технологии, 5:4 (2000), 12–21.Belyaev V. V., Shapeev V. P., “Metod kollokaziy i naimen’shikh kvadratov na adaptivnykh setkakh v oblasti s krivolineinoi granitsei”, Vychislitelnye tekhnologii, 5:4 (2000), 12–21, (in Russian).]Shapeev V. P., Isaev V. I., Idimeshev S. V., “The collocations and least squares method: application to numerical solution of the Navier–Stokes equations”, CD-ROM Proc. 6th ECCOMAS, Sept. 2012, Vienna Univ. of Tech. ISBN: 978-3-9502481-9-7, 2012.Shapeev V. P., Isaev V. I., Idimeshev S. V., “The collocations and least squares method: application to numerical solution of the Navier–Stokes equations”, CD-ROM Proc. 6th ECCOMAS, Sept. 2012, Vienna Univ. of Tech. ISBN: 978-3-9502481-9-7, 2012.Shapeev V. P., Vorozhtsov E. V., “Symbolic-numeric implementation of the method of collocations and least squares for 3D Navier–Stokes equations”, LNCS, 7442, Springer, Heidelberg, 2012, 321–333.Shapeev V. P., Vorozhtsov E. V., “Symbolic-numeric implementation of the method of collocations and least squares for 3D Navier–Stokes equations”, LNCS, 7442, Springer, Heidelberg, 2012, 321–333.Шапеев В. П., Ворожцов Е. В., Исаев В. И., Идимешев С. В., “Метод коллокаций и наименьших невязок для трехмерных уравнений Навье–Стокса”, Вычислит. методы и программирование, 14 (2013), 306–322.Shapeev V. P., Vorozhtsov E. V., Isaev V. I., Idimeshev S. V., “Metod kollokatsiy i naimenshikh nevyazok dlya trekhmernykh uravneniy Navie–Stoksa”, Vychislitelnye metody i programmirovanie, 14 (2013), 306–322, (in Russian).]Shapeev V. P., Vorozhtsov E.V., “CAS application to the construction of the collocations and least residuals method for the solution of 3D Navier–Stokes equations”, LNCS, 8136, Springer, Heidelberg, 2013, 381–392.Shapeev V. P., Vorozhtsov E.V., “CAS application to the construction of the collocations and least residuals method for the solution of 3D Navier–Stokes equations”, LNCS, 8136, Springer, Heidelberg, 2013, 381–392.Shapeev V., “Collocation and least residuals method and its applications”, EPJ Web of Conferences, 108:01009 (2016).Shapeev V., “Collocation and least residuals method and its applications”, EPJ Web of Conferences, 108:01009 (2016).Исаев В. И., Шапеев В. П., “Варианты метода коллокаций и наименьших квадратов повышенной точности для численного решения уравнений Навье–Стокса”, Ж. вычисл. матем. и матем. физ., 50:10 (2010), 1758–1770.Isaev V. I., Shapeev V. P., “High-accuracy versions of the collocations and least squares method for the numerical solution of the Navier–Stokes equations”, Comput. Math. and Math. Phys., 50 (2010), 1670–1681.Botella O., Peyret R., “Benchmark spectral results on the lid-driven cavity flow”, Comput. Fluids, 27 (1998), 421–433.Botella O., Peyret R., “Benchmark spectral results on the lid-driven cavity flow”, Comput. Fluids, 27 (1998), 421–433.Shapeev A. V., Lin P., “An asymptotic fitting finite element method with exponential mesh refinement for accurate computation of corner eddies in viscous flows”, SIAM J. Sci. Comput., 31 (2009), 1874–1900.Shapeev A. V., Lin P., “An asymptotic fitting finite element method with exponential mesh refinement for accurate computation of corner eddies in viscous flows”, SIAM J. Sci. Comput., 31 (2009), 1874–1900.Голушко С. К., Идимешев С. В., Шапеев В. П., “Метод коллокаций и наименьших невязок в приложении к задачам механики изотропных пластин”, Вычислительные технологии, 18:6 (2013), 31–43.Golushko S. K., Idimeshev S. V., Shapeev V. P., “Metod kollokatsiy i naimenshikh nevyazok v prilozhenii k zadacham mekhaniki izotropnykh plastin”, Vychislitelnye tekhnologii, 18:6 (2013), 31–43, (in Russian).Голушко С. К., Идимешев С. В., Шапеев В. П., “Разработка и применение метода коллокаций и наименьших невязок к задачам механики анизотропных слоистых пластин”, Вычислительные технологии, 19:5 (2014), 24–36.Golushko S. K., Idimeshev S. V., Shapeev V. P., “Razrabotka i primenenie metoda kollokatsiy i naimenshikh nevyazok k zadacham mekhaniki anizotropnykh sloistykh plastin”, Vychislitelnye tekhnologii, 19:5 (2014), 24–36, (in Russian).Kharenko D., Padovani C., Pagni A., Pasquinelli G., Semin L., “Free longitudinal vibrations of bimodular beams: a comparative study”, Int. J. Structural Stability and Dynamics, 11:1 (2011), 23–56.Kharenko D., Padovani C., Pagni A., Pasquinelli G., Semin L., “Free longitudinal vibrations of bimodular beams: a comparative study”, Int. J. Structural Stability and Dynamics, 11:1 (2011), 23–56.Shapeev V. P., Vorozhtsov E. V., “CAS application to the construction of the collocations and least residuals method for the solution of the Burgers and Korteweg–de Vries–Burgers equations”, LNCS, 8660, Springer, Heidelberg, 2014, 432–446.Shapeev V. P., Vorozhtsov E. V., “CAS application to the construction of the collocations and least residuals method for the solution of the Burgers and Korteweg–de Vries–Burgers equations”, LNCS, 8660, Springer, Heidelberg, 2014, 432–446.Isaev V., Cherepanov A., Shapeev V., “Numerical study of heat modes of laser welding of dissimilar metals with an intermediate insert”, Int. J. Heat Mass Transfer, 99 (2016), 711–720.Isaev V., Cherepanov A., Shapeev V., “Numerical study of heat modes of laser welding of dissimilar metals with an intermediate insert”, Int. J. Heat Mass Transfer, 99 (2016), 711–720.Ворожцов Е. В., Шапеев В. П., “Об ускорении итерационных процессов решения краевых задач комбинированием методов Крылова и Федоренко”, Символ науки, 2015, № 10(2), 24–43.Vorozhtsov E. V., Shapeev V. P., “Ob uskorenii iteratsionnykh protsessov resheniya kraevykh zadach kombinirovaniem metodov Krylova i Fedorenko”, Simvol nauki, 2015, № 10(2), 24–43, (in Russian).Temam R., Navier–Stokes Equations: Theory and Numerical Analysis, AMS Chelsea Publishing, Providence, Rhode Island, 2001.Temam R., Navier–Stokes Equations: Theory and Numerical Analysis, AMS Chelsea Publishing, Providence, Rhode Island, 2001. [46] Isaev V. I.,Исаев В. И., Шапеев В. П., Еремин С. А., “Исследование свойств метода коллокации и наименьших квадратов решения краевых задач для уравнения Пуассона и уравнений Навье–Стокса”, Вычислительные технологии, 12:3 (2007), 1–19.Shapeev V. P., Eremin S. A., “Issledovanie svoistv metoda kollokatsii i naimenshikh kvadratov resheniya kraevykh zadach dlya uravneniya Puassona i uravneniy Navie–Stoksa”, Vychislitelnye tekhnologii, 12:3 (2007), 1–19, (in Russian).]Wolfram S., The Mathematica Book, 5th edn., Wolfram Media, Inc., Champaign, IL., 2003.Wolfram S., The Mathematica Book, 5th edn., Wolfram Media, Inc., Champaign, IL., 2003.Wesseling P., An Introduction to Multigrid Methods, John Wiley & Sons, Chichester, 1992.Wesseling P., An Introduction to Multigrid Methods, John Wiley & Sons, Chichester, 1992.

The authors declare that there are no conflicts of interest present.