On combining different acceleration techniques at the iterative solution of PDEs by the method of collocations and least residuals

V. P. Shapeev ; E. V. Vorozhtsov

Modelirovanie i analiz informacionnyh sistem, Tome 24 (2017) no. 1, pp. 39-63.

Résumé

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.

Détail

Keywords: preconditioning, Krylov subspaces, multigrid, Gauss–Seidel iterations, Navier–Stokes equations, the method of collocations and least residuals.

Bibliographie

[1] 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 | DOI | MR | Zbl

[2] 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 | DOI | MR | Zbl

[3] 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 | DOI | MR | Zbl

[4] Saad Y., Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, 1991 | MR

[5] 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, no. 4, 491–539 (in Russian)

[6] Sleptsov A. G., “Ob uskorenii skhodimosti lineinykh iteratsiy II”, Modelirovanie v mekhanike, 3(20):5 (1989), 118–125 (in Russian) | MR | Zbl

[7] Fedorenko R. P., “The speed of convergence of one iterative process”, USSR Comput. Math. and Math. Phys., 4:3 (1964), 227–235 | DOI | MR

[8] 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 | DOI | MR | Zbl

[9] 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 | DOI | Zbl

[10] 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 | DOI | MR | Zbl

[11] 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 | DOI | Zbl

[12] 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 | DOI | MR | Zbl

[13] Wang M., Chen L., “Multigrid methods for the stokes equations using distributive gauss-seidel relaxations based on the least squares commutator”, J. Sci. Comput., 56:2 (2013), 409–431 | DOI | MR | Zbl

[14] 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 | DOI | MR | Zbl

[15] Fairag F. A., Wathen A. J., “A block preconditioning technique for the streamfunction-vorticity formulation of the Navier–Stokes equations”, Num. Methods Partial Differential Equations, 28:3 (2012), 888–898 | DOI | MR

[16] 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 | DOI | MR | Zbl

[17] 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 | DOI

[18] Ramšak M., Škerget 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 | DOI | Zbl

[19] 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) | MR | Zbl

[20] 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 | DOI | MR

[21] Jiang B. N., The Least-Squares Finite Element Method: Theory and Applications in Computational Fluid Dynamics and Electromagnetics, Springer, Berlin, 1998 | MR

[22] Bochev P. B., Gunzburger M. D., “Finite element methods of least-squares type”, SIAM Rev., 40:4 (1998), 789–837 | DOI | MR | Zbl

[23] 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 | DOI

[24] 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) | MR | Zbl

[25] Semin L., Shapeev V., “Constructing the numerical method for Navier–Stokes equations using computer algebra system”, LNCS, 3718, Springer, Heidelberg, 2005, 367–378 | MR | Zbl

[26] Isaev V. I., Shapeev V. P., “Development of the collocations and least squares method”, Proc. Inst. Math. Mech., 261 (2008), 87–106 | MR

[27] 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 | DOI

[28] 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 | DOI | MR | Zbl

[29] Sleptsov A. G., Shokin Yu. I., “An adaptive grid-projection method for elliptic problems”, Comput. Math. Math. Phys., 37 (1997), 558–571 | MR | Zbl

[30] 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) | MR

[31] Shapeev V. P., Isaev V. I., Idimeshev S. V., “The collocations and least squares method: application to numerical solution of the Navier–Stokes equations”, Proc. 6th ECCOMAS (Sept. 2012), Vienna Univ. of Tech., 2012 (CD-ROM)

[32] 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 | Zbl

[33] 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)

[34] 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 | Zbl

[35] Shapeev V., “Collocation and least residuals method and its applications”, EPJ Web of Conferences, 108:01009 (2016)

[36] 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 | DOI | MR | Zbl

[37] Botella O., Peyret R., “Benchmark spectral results on the lid-driven cavity flow”, Comput. Fluids, 27 (1998), 421–433 | DOI | Zbl

[38] 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 | DOI | MR | Zbl

[39] 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)

[40] 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) | Zbl

[41] 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 | DOI | MR | Zbl

[42] 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 | Zbl

[43] 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 | DOI

[44] Vorozhtsov E. V., Shapeev V. P., “Ob uskorenii iteratsionnykh protsessov resheniya kraevykh zadach kombinirovaniem metodov Krylova i Fedorenko”, Simvol nauki, 2015, no. 10(2), 24–43 (in Russian)

[45] Temam R., Navier–Stokes Equations: Theory and Numerical Analysis, AMS Chelsea Publishing, Providence, Rhode Island, 2001 | MR | Zbl

[46] Isaev V. I., 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)

[47] Wolfram S., The Mathematica Book, 5th edn., Wolfram Media, Inc., Champaign, IL., 2003 | MR

[48] Wesseling P., An Introduction to Multigrid Methods, John Wiley Sons, Chichester, 1992 | MR | Zbl