×

Reordering and incomplete preconditioning in serial and parallel adaptive mesh refinement and coarsening flow solutions. (English) Zbl 1253.76090

Summary: The effects of reordering the unknowns on the convergence of incomplete factorization preconditioned Krylov subspace methods are investigated. Of particular interest is the resulting preconditioned iterative solver behavior when adaptive mesh refinement and coarsening (AMR/C) are utilized for serial or distributed parallel simulations. As representative schemes, we consider the familiar reverse Cuthill-McKee and quotient minimum degree algorithms applied with incomplete factorization preconditioners to CG and GMRES solvers. In the parallel distributed case, reordering is applied to local subdomains for block ILU preconditioning, and subdomains are repartitioned dynamically as mesh adaptation proceeds. Numerical studies for representative applications are conducted using the object-oriented AMR/C software system libMesh linked to the PETSc solver library. Serial tests demonstrate that global unknown reordering and incomplete factorization preconditioning can reduce the number of iterations and improve serial CPU time in AMR/C computations. Parallel experiments indicate that local reordering for subdomain block preconditioning associated with dynamic repartitioning because of AMR/C leads to an overall reduction in processing time.

MSC:

76M25 Other numerical methods (fluid mechanics) (MSC2010)
65M22 Numerical solution of discretized equations for initial value and initial-boundary value problems involving PDEs
65F08 Preconditioners for iterative methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Saad, Iterative Methods for Sparse Linear Systems (1996) · Zbl 1031.65047
[2] Balay S Brown J Buschelman K Eijkhout V Gropp WD Kaushik D Knepley MG McInnes LC Smith BF Zhang H PETSc Users Manual ANL-95/11 - Revision 3.1 2010
[3] Heroux MA Bartlett RA Howle VE Hoekstra RJ Hu JJ Kolda TG Lehoucq RB Long KR Pawlowski RP Phipps ET Salinger AG Thornquist HK Tuminaro RS Willenbring JM Williams A Stanley KS An overview of the Trilinos project ACM Press New York, NY, USA 2005 397 423 http://doi.acm.org/101145/10890141089021
[4] Hestenes, Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards 49 (6) pp 409– (1952) · Zbl 0048.09901 · doi:10.6028/jres.049.044
[5] Saad, GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 7 (3) pp 856– (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[6] van der Vorst, Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM Journal on Scientific and Statistical Computing 13 pp 631– (1986) · Zbl 0761.65023 · doi:10.1137/0913035
[7] Catabriga, Evaluating the LCD algorithm for solving linear systems of equations arising from implicit SUPG formulation of compressible flows, International Journal for Numerical Methods in Engineering 60 pp 1513– (2004) · Zbl 1060.76568 · doi:10.1002/nme.1012
[8] Dai, Study on semi-conjugate direction methods for non-symmetric systems, International Journal for Numerical Methods in Engineering 60 pp 1383– (2004) · Zbl 1078.65022 · doi:10.1002/nme.983
[9] Saad, Iterative solution of linear systems in the 20th century, Journal of Computational and Applied Mathematics 123 (1-2) pp 1– (2000) · Zbl 0965.65051 · doi:10.1016/S0377-0427(00)00412-X
[10] Cuthill, Proceedings of the 24th National Conference pp 157– (1969) · doi:10.1145/800195.805928
[11] Liu, Comparative analysis of the Cuthill-McKee and the reverse Cuthill-McKee ordering algorithms for sparse matrices, SIAM Journal on Numerical Analysis 13 (2) pp 198– (1976) · Zbl 0331.65022 · doi:10.1137/0713020
[12] Sloan, An algorithm for profile and wavefront reduction of sparse matrices, International Journal of Numerical Methods in Engineering 23 pp 239– (1986) · Zbl 0601.65027 · doi:10.1002/nme.1620230208
[13] Gibbs, An algorithm for reducing the bandwidth and profile of a sparse matrix, SIAM Journal of Numerical Analysis 13 (2) pp 236– (1976) · Zbl 0329.65024 · doi:10.1137/0713023
[14] George, The evolution of the minimum degree ordering algorithm, SIAM Review 31 pp 1– (1989) · Zbl 0671.65024 · doi:10.1137/1031001
[15] Lipton RJ Rose DJ Tarjan RE Generalized nested dissection 1977
[16] Benzi, Ordering for incomplete factorization preconditioning of nonsymmetric problems, SIAM Journal on Scientific Computing 20 (5) pp 1652– (1999) · Zbl 0940.65033 · doi:10.1137/S1064827597326845
[17] Duff, The effect of ordering on preconditioned conjugate gradient, BIT Numerical Methematics 29 pp 635– (1989) · Zbl 0687.65037 · doi:10.1007/BF01932738
[18] Dutto, The effect of reordering on preconditioned GMRES algorithm for solving the compressible Navier-Stokes equations, International Journal on Numerical Methods in Engineering 36 pp 457– (1993) · Zbl 0767.76026 · doi:10.1002/nme.1620360307
[19] Heniche, Efficient ILU preconditioning and inexact-newton-GMRES to solve the 2d steady shallow water equations, Communications in Numerical Methods in Engineering 17 (2) pp 69– (2001) · Zbl 0986.76040 · doi:10.1002/1099-0887(200102)17:2<69::AID-CNM388>3.0.CO;2-A
[20] Hou PS Nodal reordering strategies to improve preconditioning for finite element systems Master’s Thesis 2005
[21] Wille, The evolution of the minimum degree ordering algorithm, International Journal of Numerical Methods for Heat & Fluid Flow 14 pp 325– (2004) · Zbl 1084.76051 · doi:10.1108/09615530410517986
[22] Dutto, Parallelization of the ILU(0) preconditioner for CFD problems on shared-memory computers, International Journal for Numerical Methods in Fluids 30 pp 995– (1999) · Zbl 0970.76078 · doi:10.1002/(SICI)1097-0363(19990830)30:8<995::AID-FLD874>3.0.CO;2-K
[23] Ainsworth, A Posterori Error Estimation in Finite Element Analysis, Wiley-Interscience 2000 pp 3137– (2002)
[24] Bangerth, Adaptive Finite Element Methods for Differential Equations (2003)
[25] Kelly, A posteriori error analysis and adaptive processes in the finite element method: Part I error analysis, International Journal of Numerical Methods in Engineering 19 pp 1593– (1983) · Zbl 0534.65068 · doi:10.1002/nme.1620191103
[26] Zienkiewicz, A simple error estimator and adaptive procedure for practical engineering analysis, International Journal of Numerical Methods in Engineering 24 pp 337– (1987) · Zbl 0602.73063 · doi:10.1002/nme.1620240206
[27] Carey, A mesh refinement scheme for finite element computations, Computer Methods in Applied Mechanics and Engineering 7 (1) pp 93– (1976) · Zbl 0312.65076 · doi:10.1016/0045-7825(76)90007-4
[28] Stogner, libMesh: a C++ library for parallel adaptive mesh refinement/coarsening simulations, Journal Engineering with Computers 22 pp 237– (2006) · Zbl 05192775 · doi:10.1007/s00366-006-0049-3
[29] Devine, Zoltan data management services for parallel dynamic applications, Computing in Science and Engineering 4 (2) pp 90– (2002) · Zbl 05091837 · doi:10.1109/5992.988653
[30] Devine, Tinkertoy parallel programming: a case study with Zoltan, International Journal of Computational Science and Engineering 1 (2-4) pp 64– (2005) · doi:10.1504/IJCSE.2005.009692
[31] Carey V A posteriori error estimation for the finite element method via local averaging PhD Thesis 2005
[32] Bangerth, Adaptive Finite Element Methods for Differential Equations (2003) · doi:10.1007/978-3-0348-7605-6
[33] Eriksson, Adaptive Finite Elements (1996)
[34] Estep, Accounting for stability: a posteriori estimates based on residuals and variational analysis, Communications in Numerical Methods in Engineering 8 pp 15– (2002) · Zbl 0994.65097
[35] Brooks, Streamline Upwind/Petrov-Galerkin formulations for convection dominated flows with particular emphasis on the incompressible Navier-Stokes equations, Computer Methods in Applied Mechanics and Engineering 32 pp 199– (1982) · Zbl 0497.76041 · doi:10.1016/0045-7825(82)90071-8
[36] Codina, The intrinsic time for the streamline upwind/Petrov-Galerkin formulation using quadratic elements, Computer Methods in Applied Mechanics and Engineering 94 pp 239– (1992) · Zbl 0748.76082 · doi:10.1016/0045-7825(92)90149-E
[37] Ladyzhenskaya, The Mathematical Theory of Viscous Incompressible Flows (1969) · Zbl 0184.52603
[38] Brezzi, On the existence, uniqueness and approximation of saddle-point problems arising from Lagrangian multipliers, Rev. Fr. Autom. Inf. Rech. Oper. Numer. Anal. pp 129– (1974) · Zbl 0338.90047
[39] Babuka, The finite element method with Lagrangian multipliers, Numerische Mathematik 20 pp 179– (1973) · Zbl 0258.65108 · doi:10.1007/BF01436561
[40] Carey, Finite Elements: Fluid Mechanics (1986) · Zbl 0653.76002
[41] deSampaio, Petrov-Galerkin solutions of the incompressible Navier-Stokes equations in primitive variables with adaptive remeshing, Computer Methods in Applied Mechanics and Engineering 106 pp 143– (1993) · Zbl 0783.76053 · doi:10.1016/0045-7825(93)90189-5
[42] Erturk, Numerical solutions 2-D steady incompressible driven cavity flow at high Reynolds numbers, International Journal of Numerical Methods in Fluids 48 pp 747– (2005) · Zbl 1071.76038 · doi:10.1002/fld.953
[43] Spotz, High-order compact scheme for the esteady stream-function vorticity equations, International Journal of Numerical Methods in Engineering 38 pp 3497– (1995) · Zbl 0836.76065 · doi:10.1002/nme.1620382008
[44] Ghia, High Re solutions for incompressible flow using Navier-Stokes equations and a multi-grid method, Journal of Computational Physics 48 pp 387– (1982) · Zbl 0511.76031 · doi:10.1016/0021-9991(82)90058-4
[45] Prabhakar, Spectral/hp penalty least-squares finite element formulation for the steady incompressible Navier-Stokes equations, Journal of Computational Physics 215 pp 274– (2006) · Zbl 1140.76369 · doi:10.1016/j.jcp.2005.10.033
[46] Elias, Stabilized edge-based finite element simulation of free-surface flows, International Journal in Numerical Methods in Fluids 54 pp 965– (2007) · Zbl 1258.76111 · doi:10.1002/fld.1475
[47] Peterson, Parallel adaptive solution of coupled Rayleigh-Bénard-Marangoni problems with Navier-slip, International Journal for Numerical Methods in Fluids 66 (4) pp 428– (2009) · Zbl 1328.76044 · doi:10.1002/fld.2264
[48] Osher, Level Set Methods and Dynamic Implicit Surfaces 153 (2000)
[49] LeVeque, High-resolution conservative algorithms for advection in incompressible flow, SIAM Journal on Numerical Analysis 33 pp 627– (1996) · Zbl 0852.76057 · doi:10.1137/0733033
[50] Kalro, Parallel iterative computational methods for 3D finite element flow simulations, Computer Assisted Mechanics and Engineering Sciences 5 pp 173– (1998) · Zbl 0952.76036
[51] Gropp, High-perfomance parallel implicit CFD, Parallel Computing 27 pp 337– (2001) · Zbl 0971.68191 · doi:10.1016/S0167-8191(00)00075-2
[52] Ahrens, the Visualization Handbook (2005)
[53] Shende, TAU: the TAU parallel performance system, International Journal of High Performance Computing Applications 20 (2) pp 287– (2006) · doi:10.1177/1094342006064482
[54] Griebel, Numerical Simulation in Fluid Dynamics - A Practical Introduction (1998) · Zbl 0945.76001 · doi:10.1137/1.9780898719703
[55] Behr, Stabilized finite element methods for the velocity-pressure-stress formulation of incompressible flows, Computer Methods in Applied Mechanics and Engineering 104 pp 3138– (1993) · Zbl 0771.76033 · doi:10.1016/0045-7825(93)90205-C
[56] Tezduyar, Modelling of fluidstructure interactions with the spacetime finite elements: solution techniques, International Journal for Numerical Methods in Fluids 54 pp 855– (2007) · Zbl 1144.74044 · doi:10.1002/fld.1430
[57] DeVahl Davis, Natural convection of air in a square cavity: a benchmark numerical solution, International Journal Numerical Methods in Fluids 3 (3) pp 249– (1983) · Zbl 0538.76075 · doi:10.1002/fld.1650030305
[58] Mayne, Natural convection of air in a square cavity: a benchmark numerical solution, International Journal of Numerical Methods for Heat and Fluid Flow 10 pp 598– (2000) · Zbl 0979.76049 · doi:10.1108/09615530010347187
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.