×

Efficient nonlinear solvers for Laplace-Beltrami smoothing of three-dimensional unstructured grids. (English) Zbl 1142.65455

Summary: The Laplace-Beltrami system of nonlinear, elliptic, partial differential equations has utility in the generation of computational grids on complex and highly curved geometry. Discretization of this system using the finite-element method accommodates unstructured grids, but generates a large, sparse, ill-conditioned system of nonlinear discrete equations. The use of the Laplace-Beltrami approach, particularly in large-scale applications, has been limited by the scalability and efficiency of solvers. This paper addresses this limitation by developing two nonlinear solvers based on the Jacobian-Free Newton-Krylov (JFNK) methodology. A key feature of these methods is that the Jacobian is not formed explicitly for use by the underlying linear solver. Iterative linear solvers such as the Generalized Minimal RESidual (GMRES) method do not technically require the stand-alone Jacobian; instead its action on a vector is approximated through two nonlinear function evaluations. The preconditioning required by GMRES is also discussed. Two different preconditioners are developed, both of which employ existing Algebraic Multigrid (AMG) methods. Further, the most efficient preconditioner, overall, for the problems considered is based on a Picard linearization. Numerical examples demonstrate that these solvers are significantly faster than a standard Newton-Krylov approach; a speedup factor of approximately 26 was obtained for the Picard preconditioner on the largest grids studied here. In addition, these JFNK solvers exhibit good algorithmic scaling with increasing grid size.

MSC:

65N50 Mesh generation, refinement, and adaptive methods for boundary value problems involving PDEs

Software:

CUBIT; NITSOL; ML; BPKit; PCG; LAMG; hypre
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Thompson, J. F.; Warsi, Z. U.A.; Mastin, C. W., Numerical Grid Generation: Foundations and Applications (1985), Elsevier: Elsevier New York · Zbl 0598.65086
[2] Hansen, G. A.; Douglass, R. W.; Zardecki, A., Mesh Enhancement: Selected Elliptic Methods, Foundations and Applications (2005), Imperial College Press: Imperial College Press London · Zbl 1079.65119
[3] Khamayseh, A.; Mastin, C. W., Computational conformal mapping for surface grid generation, J. Comput. Phys., 123, 394-401 (1996) · Zbl 0851.65079
[4] Liseikin, V. D., Grid Generation Methods (1999), Springer: Springer Berlin, Heidelberg, New York · Zbl 0949.65098
[5] Liseikin, V. D., A Computational Differential Geometry Approach to Grid Generation (2004), Springer: Springer Berlin, Heidelberg, New York · Zbl 1076.65083
[6] Hansen, G.; Zardecki, A.; Greening, D.; Bos, R., A finite element method for unstructured grid smoothing, J. Comput. Phys., 194, 2, 611-631 (2004) · Zbl 1039.65086
[7] Hansen, G.; Zardecki, A.; Greening, D.; Bos, R., A finite element method for three-dimensional unstructured grid smoothing, J. Comput. Phys., 202, 1, 281-297 (2005) · Zbl 1061.65133
[8] Brackbill, J. U.; Saltzman, J. S., Adaptive zoning for singular problems in two dimensions, J. Comput. Phys., 46, 342-368 (1982) · Zbl 0489.76007
[9] Brackbill, J. U., An adaptive grid with directional control, J. Comput. Phys., 108, 38-50 (1993) · Zbl 0832.65132
[10] Cao, W.; Huang, W.; Russell, R. D., An \(r\)-adaptive finite element method based upon moving mesh PDEs, J. Comput. Phys., 149, 221-244 (1999) · Zbl 0923.65062
[11] Chacon, L.; Lapenta, G., A fully implicit, nonlinear adaptive grid strategy, J. Comput. Phys., 212, 703-717 (2006) · Zbl 1083.65110
[12] Frey, W. H.; Field, D. A., Mesh relaxation. a new technique for improving triangulations, Int. J. Numer. Methods Eng., 31, 6, 1121-1133 (1991) · Zbl 0825.73812
[13] L. Freitag, P. Knupp, Tetrahedral element shape optimization via the Jacobian determinant and condition number, in: Proceedings of the 8th International Meshing Roundtable, Lake Tahoe, California, 1999, pp. 247-258; L. Freitag, P. Knupp, Tetrahedral element shape optimization via the Jacobian determinant and condition number, in: Proceedings of the 8th International Meshing Roundtable, Lake Tahoe, California, 1999, pp. 247-258
[14] Freitag, L.; Plassmann, P., Local optimization-based simplicial mesh untangling and improvement, Int. J. Numer. Methods Eng., 49, 1-2, 109-125 (2000) · Zbl 0962.65098
[15] Knoll, D. A.; Keyes, D. E., Jacobian-free Newton-Krylov methods: A survey of approaches and applications, J. Comput. Phys., 193, 2, 357-397 (2004) · Zbl 1036.65045
[16] Kelly, C. T., Iterative methods for linear and nonlinear equations, (Frontiers in Applied Mathematics (1995), SIAM: SIAM Philadelphia, PA)
[17] Knoll, D. A.; Rider, W. J.; Olson, G. L., An efficient nonlinear solution method for non-equilibrium radiation diffusion, J. Quant. Spect. Rad. Tran., 63, 1, 15-29 (1999)
[18] Rider, W. J.; Knoll, D. A.; Olson, G. L., A multigrid Newton-Krylov method for multimaterial equilibrium radiation diffusion, J. Comput. Phys., 152, 1, 164-191 (1999) · Zbl 0944.85002
[19] Briggs, W. L.; Henson, V. E.; McCormick, S. F., A Multigrid Tutorial (2000), SIAM Books: SIAM Books Philadelphia · Zbl 0958.65128
[20] Trottenberg, U.; Oosterlee, C.; Schüller, A., Multigrid (2001), Academic Press
[21] Codd, A. L.; Manteuffel, T. A.; McCormick, S. F.; Ruge, J. W., Multilevel first-order system least squares for elliptic grid generation, SIAM J. Numer. Anal., 41, 6, 2210-2232 (2003) · Zbl 1130.65317
[22] Spekreijse, S. P., Elliptic grid generation based on Laplace equations and algebraic transformations, J. Comput. Phys., 118, 38-61 (1995) · Zbl 0823.65120
[23] Brandt, A.; McCormick, S. F.; Ruge, J. W., Algebraic multigrid (AMG) for sparse matrix equations, (Evans, D. J., Sparsity and its Applications (1984), Cambridge University Press: Cambridge University Press Cambridge), 257-284 · Zbl 0548.65014
[24] Ruge, J. W.; Stüben, K., Algebraic multigrid (AMG), (McCormick, S. F., Multigrid Methods. Multigrid Methods, Frontiers in Applied Mathematics, vol. 3 (1987), SIAM: SIAM Philadelphia, PA), 73-130
[25] Stüben, K., A review of algebraic multigrid, J. Comput. Appl. Math., 128, 1-2, 281-309 (2001) · Zbl 0979.65111
[26] W.D. Joubert, G.F. Carey, N.A. Berner, A. Kalhan, H. Kohli, A. Lorber, R.T. Mclay, Y. Schen, PCG Reference Manual: A Package for the Iterative Solution of Large Sparse Linear Systems on Parallel Computers Version 1.0, Los Alamos National Laboratory, Los Alamos, NM, 1994; W.D. Joubert, G.F. Carey, N.A. Berner, A. Kalhan, H. Kohli, A. Lorber, R.T. Mclay, Y. Schen, PCG Reference Manual: A Package for the Iterative Solution of Large Sparse Linear Systems on Parallel Computers Version 1.0, Los Alamos National Laboratory, Los Alamos, NM, 1994
[27] Center for Applied Scientific Computing (CASC), Lawrence Livermore National Laboratory, Hypre high performance preconditioners User’s Manual, software version 1.9.0b edition, February 2005; Center for Applied Scientific Computing (CASC), Lawrence Livermore National Laboratory, Hypre high performance preconditioners User’s Manual, software version 1.9.0b edition, February 2005
[28] W.D. Joubert, LAMG: Los Alamos Algebraic Multigrid Code User’s Manual, A Parallel Software Library for the Solution of Systems of Linear Equations Using Algebraic Multigrid Methods, LA-UR 05-4041 edition, June 2005; W.D. Joubert, LAMG: Los Alamos Algebraic Multigrid Code User’s Manual, A Parallel Software Library for the Solution of Systems of Linear Equations Using Algebraic Multigrid Methods, LA-UR 05-4041 edition, June 2005
[29] Knupp, P.; Steinberg, S., The Fundamentals of Grid Generation (1993), CRC Press: CRC Press Boca Raton, FL
[30] Khamayseh, A.; Hansen, G., Quasi-orthogonal grids with impedance matching, SIAM J. Sci. Comput., 22, 4, 1220-1237 (2000) · Zbl 0979.65108
[31] Saad, Y., Iterative Methods for Sparse Linear Systems, The PWS Series in Computer Science (1995), PWS Publishing Company: PWS Publishing Company Boston, MA · Zbl 1002.65042
[32] Pernice, M.; Walker, H. F., NITSOL: A Newton iterative solver for nonlinear systems, SIAM J. Sci. Comp., 19, 1, 302-318 (1998) · Zbl 0916.65049
[33] Knoll, D. A.; Rider, W. J., Multigrid preconditioned Newton-Krylov method, SIAM J. Sci. Comp., 21, 2, 691-710 (1999) · Zbl 0952.65102
[34] M. Sala, M.W. Gee, J.J. Hu, R.S. Tuminaro, Ml 4.0 smoothed aggregation user’s guide, Tech. Rep. SAND2004-4819, Computational Math & Algorithms Department, Sandia National Laboratories, Albuquerque, NM, August 2005; M. Sala, M.W. Gee, J.J. Hu, R.S. Tuminaro, Ml 4.0 smoothed aggregation user’s guide, Tech. Rep. SAND2004-4819, Computational Math & Algorithms Department, Sandia National Laboratories, Albuquerque, NM, August 2005
[35] W. Joubert, J. Cullum, Scalable algebraic multigrid on 3500 processors, Tech. Rep. LA-UR 05-4129, Continuum Dynamics Group, Los Alamos National Laboratory, Los Alamos, NM, 2005; W. Joubert, J. Cullum, Scalable algebraic multigrid on 3500 processors, Tech. Rep. LA-UR 05-4129, Continuum Dynamics Group, Los Alamos National Laboratory, Los Alamos, NM, 2005 · Zbl 1112.65027
[36] Chow, E.; Heroux, M. A., Object-oriented framework for block preconditioning, ACM Trans. Math. Softw., 24, 2, 159-183 (1998) · Zbl 0930.65052
[37] S.J. Owen (Project Lead), Cubit: Geometry and mesh generation toolkit. URL: http://cubit.sandia.gov; S.J. Owen (Project Lead), Cubit: Geometry and mesh generation toolkit. URL: http://cubit.sandia.gov
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.