article

Software concepts and numerical algorithms for a scalable adaptive parallel finite element method

Authors:

A. VoigtAuthors Info & Claims

Advances in Computational Mathematics, Volume 41, Issue 6

Pages 1145 - 1177

https://doi.org/10.1007/s10444-015-9405-4

Published: 01 December 2015 Publication History

Abstract

An efficient implementation of an adaptive finite element method on distributed memory systems requires an efficient linear solver. Most solver methods, which show scalability to a large number of processors make use of some geometric information of the mesh. This information has to be provided to the solver in an efficient and solver specific way. We introduce data structures and numerical algorithms which fulfill this task and allow in addition for an user-friendly implementation of a large class of linear solvers. The concepts and algorithms are demonstrated for global matrix solvers and domain decomposition methods for various problems in fluid dynamics, continuum mechanics and materials science. Weak and strong scaling is shown for up to 16.384 processors.

References

[1]

Aland, S., Lowengrub, J., Voigt, A.: Two-phase flow in complex geometries: a diffuse domain approach. CMES 57, 77---108 (2010)

[2]

Amestoy, P., Duff, I., L'Excellent, J., Koster, J.: A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM Journal on Matrix Analysis and Applications 23(1), 15---41 (2001)

Digital Library

[3]

Amestoy, P., Guermouche, A., L'Excellent, J.-Y., Pralet, S.: Hybrid scheduling for the parallel solution of linear systems. Parallel Comput. 32(2), 136---156 (2006)

Digital Library

[4]

Backofen, R., Barmak, K., Elder, K., Voigt, A.: Capturing the complex physics behind universal grain size distributions in thin metallic films. Acta Mater. 64, 72---77 (2014)

[5]

Backofen, R., Rätz, A., Voigt, A.: Nucleation and growth by a phase field crystal (PFC) model. Philos. Mag. Lett. 87(11), 813---820 (2007)

[6]

Balay, S., Brown, J., Buschelman, K., Eijkhout, V., Gropp, W. D., Kaushik, D., Knepley, M. G., McInnes, L. C., Smith, B. F., manual, H. Zhang. PETSc users: Technical Report ANL-95/11 - Revision 3.2. Argonne National Laboratory (2011)

[7]

Balay, S., Brown, J., Buschelman, K., Gropp, W.D., Kaushik, D., Knepley, M.G., McInnes, L.C., Smith, B.F., Zhang, H.: PETSc Web page. http://www.mcs.anl.gov/petsc (2011)

[8]

Bangerth, W., Burstedde, C., Heister, T., Kronbichler, M.: Algorithms and data structures for massively parallel generic adaptive finite element codes. ACM Trans. Math. Softw. 38(2), 14/1---14/28 (2012)

Digital Library

[9]

Bangerth, W., Hartmann, R., Kanschat, G.: Deal.II --- a general purpose object oriented finite element library. ACM Trans. Math. Softw. 33(4), 24/1---24/27 (2007)

Digital Library

[10]

Benzi, M., Golub, G. H., Liesen, J.: Numerical solution of saddle point problems. Acta Numerica 14, 1---137 (2005)

[11]

Burstedde, C., Ghattas, O., Gurnis, M., Isaac, T., Stadler, G., Warburton, T., Wilcox, L. C.: Extreme-scale AMR. In SC10: Proceedings of the International Conference for High Performance Computing, Networking, Storage, and Analysis. ACM/IEEE (2010)

[12]

Burstedde, C., Ghattas, O., Stadler, G., Tu, T., Wilcox, L. C.: Towards adaptive mesh pde simulations on petascale computers. In TeraGrid'08 (2008)

[13]

Burstedde, C., Wilcox, L. C., Ghattas, O.: p4est: Scalable algorithms for parallel adaptive mesh refinement on forests of octrees. SIAM J. Sci. Comput. 33(3), 1103---1133 (2011)

Digital Library

[14]

Davis, T.: Algorithm 832: Umfpack v4.3--an unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30(2), 196---199 (2004)

[15]

Davis, T.: A column pre-ordering strategy for the unsymmetric-pattern multifrontal method. ACM Trans. Math. Softw. 30(2), 165---195 (2004)

Digital Library

[16]

Dedner, A., Klöfkorn, R., Nolte, M., Ohlberger, M.: A generic interface for parallel and adaptive discretization schemes: abstraction principles and the dune-fem module. Computing 90, 165---196 (2010)

Digital Library

[17]

Dryja, M., Smith, B., Widlund, O.: Schwarz analysis of iterative substructuring algorithms for elliptic problems in three dimensions. SIAM J. Numer. Anal. 31(6), 1662---1694 (1994)

Digital Library

[18]

Elder, K. R., Katakowski, M., Haataja, M., Grant, M.: Modeling elasticity in crystal growth. Phys. Rev. Lett. 245701, 88 (2002)

[19]

Farhat, C., Lesoinne, M., LeTallec, P., Pierson, K., Rixen, D.: FETI-DP: a dual-primal unified FETI method-part I: A faster alternative to the two-level FETI method. Int. J. Numer. Methods Eng. 50(7), 1523---1544 (2001)

[20]

Farhat, C., Lesoinne, M., Pierson, K.: A scalable dual-primal domain decomposition method. Numerical Linear Algebra with Applications 7(7-8), 687---714 (2000)

[21]

Filippone, S., Colajanni, M.: PSBLAS: a library for parallel linear algebra computation on sparse matrices. ACM Trans. Math. Softw. 26(4), 527---550 (2000)

Digital Library

[22]

Golub, G., van Van Loan, C.: Matrix Computations. The Johns Hopkins University Press (1996)

[23]

Jansson, N., Hoffman, J., Jansson, J.: Framework for massively parallel adaptive finite element computational fluid dynamics on tetrahedral meshes. SIAM J. Sci. Comput. 34(1), 24---41 (2012)

Digital Library

[24]

Kay, D., Welford, R.: Efficient numerical solution of Cahn-Hilliard-Navier-Stokes fluids in 2D. SIAM J. Sci. Comput. 29(6), 2241---2257 (2007)

Digital Library

[25]

Kim, H., Lee, C., Park, E.: A FETI-DP formulation for the stokes problem without primal pressure components. SIAM J. Numer. Anal. 47(6), 4142---4162 (2010)

[26]

Kirk, B. S., Peterson, J. W., Stogner, R. H., Carey, G. F.: libMesh: A C++ Library for Parallel Adaptive Mesh Refinement/Coarsening Simulations. Engineering with Computers 22(3---4), 237---254 (2006)

[27]

Klawonn, A., Rheinbach, O.: Robust FETI-DP methods for heterogeneous three dimensional elasticity problems. Comput. Methods Appl. Mech. Eng. 196(8), 1400---1414 (2007)

[28]

Klawonn, A., Rheinbach, O.: Highly scalable parallel domain decomposition methods with an application to biomechanics. ZAMM 90(1), 5---32 (2010)

[29]

Klawonn, A., Widlund, O. B.: Dual-primal FETI methods for linear elasticity. Commun. Pur. Appl. Math. 59(11), 1523---1572 (2006)

[30]

Lesoinne, M.: A FETI-DP corner selection algorithm for three-dimensional problems. In: Proceedings of the 14th International Conference on Domain Decomposition Methods (2003)

[31]

Li, X., Lowengrub, J., Rätz, A., Voigt, A.: Solving PDEs in complex domains: a diffuse domain approach. Commun. Math. Sci. 7, 81---107 (2009)

[32]

Logg, A., Mardal, K.-A., Wells, G. N., et al.: Automated Solution of Differential Equations by the Finite Element Method. Springer (2012)

[33]

Mandel, J.: Iterative solvers by substructuring for the p-version finite element method. Comput. Methods Appl. Mech. Eng. 80(1-3), 117---128 (1990)

Digital Library

[34]

Mandel, J.: On block diagonal and schur complement preconditioning. Numer. Math. 58, 79---93 (1990)

Digital Library

[35]

Mandel, J.: Balancing domain decomposition. Commun. Numer. Methods Eng. 9(3), 233---241 (1993)

[36]

Mandel, J., Sousedík, B., Dohrmann, C.: Multispace and multilevel BDDC. Computing 83, 55---85 (2008)

Digital Library

[37]

T. P: Matthew. Domain Decomposition Methods for the Numerical Solution of Partial Differential Equations. Springer (2008)

[38]

Ribalta, A., Stoecker, C., Vey, S., Voigt, A.: AMDiS - adaptive multidimensional simulations: Parallel concepts. In Domain Decomposition Methods in Science and Engineering XVII, volume 60 of Lecture Notes in Computational Science and Engineering, pp. 615---621. Springer, Berlin Heidelberg (2008)

[39]

Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM (2003)

[40]

Silvester, D., Elman, H., Kay, D., Wathen, A.: Efficient preconditioning of the linearized navierâă¿¿stokes equations for incompressible flow. J. Comput. Appl. Math. 128(1-2), 261---279 (2001)

Digital Library

[41]

Stukowski, A.: OVITO Web page. http://www.ovito.orf (2010)

[42]

Stukowski, A.: Visualization and analysis of atomistic simulation date with OVITO-the open visualization tool. Model. Simul. Mater. Sci. Eng. 128, 261---279 (2010)

[43]

Trottenberg, U., Oosterlee, C. W., Schüller, A.: Multigrid: Basics, Parallelism and Adaptivity. Academic Press (2000)

[44]

Vejchodsk?, T., ¿olín, P., Zítka, M.: Modular hp-FEM system HERMES and its application to Maxwell's equations. Math. Comput. Simul. 76(1-3), 223---228 (2007)

Digital Library

[45]

Vey, S., Voigt, A.: AMDiS: adaptive multidimensional simulations. Comput. Vis. Sci. 10, 57---67 (2007)

Digital Library

[46]

¿ístek, J., Sousedík, B., Burda, P., Mandel, J., Novotn?, J.: Application of the parallel BDDC preconditioner to the Stokes flow. Computers and Fluids 46(1), 429---435 (2011)

[47]

Witkowski, T., Voigt, A.: A multi-mesh finite element method for Lagrange elements of arbitrary degree. J. Comput. Sci. 3, 420---428 (2012)

[48]

Xue, M., Jin, J.: Nonconformal FETI-DP methods for large-scale electromagnetic simulation. IEEE Trans. Antennas Propag. PP(99), 1 (2012)

Cited By

(2017)Distributed Newest Vertex BisectionJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.12.003104:C(1-11)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.12.003
Reuther SVoigt A(2016)Incompressible two-phase flows with an inextensible Newtonian fluid interfaceJournal of Computational Physics10.1016/j.jcp.2016.07.023322:C(850-858)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jcp.2016.07.023

Software concepts and numerical algorithms for a scalable adaptive parallel finite element method
1. Mathematics of computing
  1. Mathematical analysis
    1. Differential equations
    2. Numerical analysis
2. Theory of computation
  1. Models of computation
    1. Concurrency

Recommendations

A low-order discontinuous Petrov---Galerkin method for the Stokes equations

This paper introduces a low-order discontinuous Petrov-Galerkin (dPG) finite element method (FEM) for the Stokes equations. The ultra-weak formulation utilizes piecewise constant and affine ansatz functions and piecewise affine and discontinuous lowest-...
The Aggregated Unfitted Finite Element Method on Parallel Tree-Based Adaptive Meshes

In this work, we present an adaptive unfitted finite element scheme that combines the aggregated finite element method with parallel adaptive mesh refinement. We introduce a novel scalable distributed-memory implementation of the resulting scheme on ...
Local and parallel finite element algorithms for the time-dependent Oseen equations
Abstract
Based on two-grid discretizations, local and parallel finite element algorithms are proposed and analyzed for the time-dependent Oseen equations. Using conforming finite element pairs for the spatial discretization and backward Euler scheme for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Advances in Computational Mathematics

Advances in Computational Mathematics Volume 41, Issue 6

December 2015

246 pages

ISSN:1019-7168

Issue’s Table of Contents

Copyright © Copyright © 2015 Springer Science+Business Media New York.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 December 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

(2017)Distributed Newest Vertex BisectionJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.12.003104:C(1-11)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2016.12.003
Reuther SVoigt A(2016)Incompressible two-phase flows with an inextensible Newtonian fluid interfaceJournal of Computational Physics10.1016/j.jcp.2016.07.023322:C(850-858)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.jcp.2016.07.023

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents