More Web Proxy on the site http://driver.im/

research-article

Multilevel Balancing Domain Decomposition by Constraints Deluxe Algorithms with Adaptive Coarse Spaces for Flow in Porous Media

Authors:

Stefano Zampini,

Xuemin TuAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 39, Issue 4

Pages A1389 - A1415

https://doi.org/10.1137/16M1080653

Published: 01 January 2017 Publication History

Abstract

Multilevel balancing domain decomposition by constraints (BDDC) deluxe algorithms are developed for the saddle point problems arising from mixed formulations of Darcy flow in porous media. In addition to the standard no-net-flux constraints on each face, adaptive primal constraints obtained from the solutions of local generalized eigenvalue problems are included to control the condition number. Special deluxe scaling and local generalized eigenvalue problems are designed in order to make sure that these additional primal variables lie in a benign subspace in which the preconditioned operator is positive definite. The current multilevel theory for BDDC methods for porous media flow is complemented with an efficient algorithm for the computation of the so-called malign part of the solution, which is needed to make sure the rest of the solution can be obtained using the conjugate gradient iterates lying in the benign subspace. We also propose a new technique, based on the Sherman--Morrison formula, that lets us preserve the complexity of the subdomain local solvers. Condition number estimates are provided under certain standard assumptions. Extensive numerical experiments confirm the theoretical estimates; additional numerical results prove the effectiveness of the method with higher order elements and high-contrast problems from real-world applications.

References

[1]

P. R. Amestoy, I. S. Duff, J.-Y. L'Excellent, and J. Koster, A fully asynchronous multifrontal solver using distributed dynamic scheduling, SIAM J. Matrix Anal. Appl., 23 (2001), pp. 15--41.

[2]

W. N. Anderson, Jr., and R. J. Duffin, Series and parallel addition of matrices, J. Math. Anal. Appl., 26 (1969), pp. 576--594.

[3]

D. N. Arnold, D. Boffi, and R. S. Falk, Quadrilateral $H({div})$ finite elements, SIAM J. Numer. Anal., 42 (2005), pp. 2429--2451.

[4]

S. Balay, S. Abhyankar, M. F. Adams, J. Brown, P. Brune, K. Buschelman, L. Dalcin, V. Eijkhout, W. D. Gropp, D. Kaushik, M. G. Knepley, L. C. McInnes, K. Rupp, B. F. Smith, S. Zampini, and H. Zhang, PETSc Users Manual, Technical report ANL-95/11--Revision 3.6, Argonne National Laboratory, Argonne, IL, 2015.

[5]

L. Beira͂o da Veiga, L. F. Pavarino, S. Scacchi, O. B. Widlund, and S. Zampini, Isogeometric BDDC preconditioners with deluxe scaling, SIAM J. Sci. Comput., 36 (2014), pp. A1118--A1139.

[6]

L. Beira͂o da Veiga, L. F. Pavarino, S. Scacchi, O. B. Widlund, and S. Zampini, Adaptive selection of primal constraints for isogeometric BDDC deluxe preconditioners, SIAM J. Sci. Comput., 39 (2017), pp. A281--A302.

[7]

D. Boffi, F. BreAzzi, and M. Fortin, Mixed Finite Element Methods and Applications, Springer, Heidelberg, 2013.

[8]

J. G. Calvo and O. B. Widlund, An Adaptive Choice of Primal Constraints for BDDC Domain Decomposition Algorithms, Technical report TR2015-979, Courant Institute of Mathematical Sciences, New York, 2015.

[9]

Z. Chen, G. Huan, and Y. Ma, Computational Methods for Multiphase Flows in Porous Media, Comput. Sci. Eng., SIAM, Philadelphia, 2006.

[10]

C. R. Dohrman, A Substructuring Preconditioner for Nearly Incompressible Elasticity Problems, Technical report, SAND 2004-5393, Sandia National Laboratories, Albuquerque, New Mexico, 2004.

[11]

C. R. Dohrmann, A preconditioner for substructuring based on constrained energy minimization, SIAM J. Sci. Comput., 25 (2003), pp. 246--258.

[12]

C. R. Dohrmann, An approximate BDDC preconditioner, Numer. Linear Algebra Appl., 14 (2007), pp. 149--168.

[13]

C. R. Dohrmann and P. B. Bochev, A stabilized finite element method for the Stokes problem based on polynomial pressure projections, Internat. J. Numer. Methods Fluids, 46 (2004), pp. 183--201.

[14]

C. R. Dohrmann and O. B. Widlund, A BDDC algorithm with deluxe scaling for three-dimensional H(curl) problems, Comm. Pure Appl. Math., 69 (2016), pp. 745--770.

[15]

R. E. Ewing and J. Wang, Analysis of the Schwarz algorithm for mixed finite element methods, ESAIM Math. Model. Numer. Anal., 26 (1992), pp. 739--756.

[16]

R. S. Falk, P. Gatto, and P. Monk, Hexahedral $H(div)$ and $H(curl)$ finite elements, ESAIM Math. Model. Numer. Anal., 45 (2011), pp. 115--143.

[17]

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

[18]

V. Girault and P.-A. Raviart, Finite Element Methods for Navier-Stokes Equations. Springer, New York, 1986.

[19]

P. Goldfeld, Balancing Neumann-Neumann Preconditioners for the Mixed Formulation of Almost-Incompressible Linear Elasticity. Ph.D. thesis, New York University, Courant Institute of Mathematical Sciences, New York, 2003.

[20]

P. Hénon, P. Ramet, and J. Roman, PASTIX: A high-performance parallel direct solver for sparse symmetric positive definite systems, Parallel Comput., 28 (2002), pp. 301--321.

[21]

R. Ingram, M. F. Wheeler, and I. Yotov, A multipoint flux mixed finite element method on hexahedra, SIAM J. Numer. Anal., 48 (2010), pp. 1281--1312.

[22]

G. Karypis, METIS and ParMETIS, in Encyclopedia of Parallel Computing, D. Padua, ed., Springer, New York, 2011, pp. 1117--1124.

[23]

H. H. Kim, E. T. Chung, and J. Wang, BDDC and FETI-DP Algorithms with Adaptive Coarse Spaces for Three-Dimensional Elliptic Problems with Oscillatory and High Contrast Coefficients, preprint, arXiv:1606.07560, 2016.

[24]

A. Klawonn, M. Kühn, and O. Rheinbach, Adaptive coarse spaces for FETI-DP in three dimensions, SIAM J. Sci. Comput., 38 (2016), pp. A2880--A2911.

[25]

A. Klawonn, P. Radtke, and O. Rheinbach, A comparison of adaptive coarse spaces for iterative substructuring in two dimensions, Electron. Trans. Numer. Anal., 45 (2016), pp. 75--106.

[26]

A. Klawonn and O. B. Widlund, Dual-primal FETI methods for linear elasticity, Comm. Pure Appl. Math., 59 (2006), pp. 1523--1572.

[27]

A. Kuzmin, M. Luisier, and O. Schenk, Fast methods for computing selected elements of the greens function in massively parallel nanoelectronic device simulations, in Euro-Par 2013 Parallel Processing, F. Wolf, B. Mohr, and D. Mey, ed., Lecture Notes in Comput. Sci. 8097, Springer, Berlin, 2013, pp. 533--544.

[28]

M. la Cour Christensen, U. Villa, A. P. Engsig-Karup, and P. S. Vassilevski, Numerical multilevel upscaling for incompressible flow in reservoir simulation: An element-based algebraic multigrid (AMGe) approach, SIAM J. Sci. Comput., 39 (2017), pp. B102--B137.

[29]

J. Li and X. Tu, A nonoverlapping domain decomposition method for incompressible Stokes equations with continuous pressures, SIAM J. Numer. Anal., 51 (2013), pp. 1235--1253.

[30]

J. Li and O. B. Widlund, BDDC algorithms for incompressible Stokes equations, SIAM J. Numer. Anal., 44 (2006), pp. 2432--2455.

[31]

J. Li and O. B. Widlund, FETI-DP, BDDC, and block Cholesky methods, Internat. J. Numer. Methods Engrg., 66 (2006), pp. 250--271.

[32]

A. Logg, K.-A. Mardal, G. N. Wells, Automated Solution of Differential Equations by the Finite Element Method, Springer, Heidelberg, 2012.

[33]

A. Logg and G. N. Wells, Dolfin: Automated finite element computing, ACM Trans. Math. Softw., 37 (2010), 20.

[34]

J. Mandel, C. R. Dohrmann, and R. Tezaur, An algebraic theory for primal and dual substructuring methods by constraints, Appl. Numer. Math., 54 (2005), pp. 167--193.

[35]

J. Mandel and B. Sousedík, Adaptive selection of face coarse degrees of freedom in the BDDC and the FETI-DP iterative substructuring methods, Comput. Methods Appl. Mech. Engrg., 196 (2007), pp. 1389--1399.

[36]

J. Mandel, B. Sousedík, and C. R. Dohrmann, Multispace and multilevel BDDC, Computing, 83 (2008), pp. 55--85.

[37]

J. Mandel, B. Sousedík, and J. Šístek, Adaptive BDDC in three dimensions, Math. Comput. Simulation, 82 (2012), pp. 1812--1831.

[38]

T. P. Mathew, Domain Decomposition and Iterative Refinement Methods for Mixed Finite Element Discretisations of Elliptic Problems, Ph.D. thesis, New York University, Courant Institute of Mathematical Sciences, New York, 1989.

[39]

T. P. Mathew, Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems. I. Algorithms and numerical results, Numer. Math., 65 (1993), pp. 445--468.

[40]

T. P. Mathew, Schwarz alternating and iterative refinement methods for mixed formulations of elliptic problems. II. Convergence theory, Numer. Math., 65 (1993), pp. 469--492.

[41]

D.-S. Oh, O. B. Widlund, S. Zampini, and C. Dohrmann, BDDC algorithms with deluxe scaling and adaptive selection of primal constraints for Raviart-Thomas vector fields, Math. Comp., to appear, https://doi.org/10.1090/mcom/3254.

[42]

L. F. Pavarino and O. B. Widlund, Balancing Neumann-Neumann methods for incompressible Stokes equations, Comm. Pure Appl. Math., 55 (2002), pp. 302--335.

[43]

L. F. Pavarino, O. B. Widlund, and S. Zampini, BDDC preconditioners for spectral element discretizations of almost incompressible elasticity in three dimensions, SIAM J. Sci. Comput., 32 (2010), pp. 3604--3626.

[44]

C. Pechstein and C. R. Dohrmann, Modern Domain Decomposition Solvers: BDDC, Deluxe Scaling, and An Algebraic Approach, https://people.ricam.oeaw.ac.at/c.pechstein/pechstein-bddc2013.pdf (2013).

[45]

C. Pechstein and C. R. Dohrmann, A Unified Framework for Adaptive BDDC, http://www.ricam.oeaw.ac.at/files/reports/16/rep16-20.pdf (2016).

[46]

J. Šístek, J. Březina, and B. Sousedík, BDDC for mixed-hybrid formulation of flow in porous media with combined mesh dimensions, Numer. Linear Algebra Appl., 22 (2015), pp. 903--929.

[47]

B. Sousedík, Nested BDDC for a saddle-point problem, Numer. Math., 125 (2013), pp. 761--783.

[48]

B. Sousedík, J. Šístek, and J. Mandel, Adaptive-multilevel BDDC and its parallel implementation, Computing, 95 (2013), pp. 1087--1119.

[49]

SPE Comparative Solution Projects, http://www.spe.org/web/csp/datasets/set02.htm.

[50]

N. Spillane, V. Dolean, P. Hauret, F. Nataf, C. Pechstein, and R. Scheichl, Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps, Numer. Math., 126 (2013), pp. 741--770.

[51]

A. Toselli and O. B. Widlund, Domain decomposition methods---algorithms and theory, Springer Ser. Comput. Math. 34, Springer, Berlin, 2005.

[52]

X. Tu, A BDDC algorithm for a mixed formulation of flow in porous media, Electron. Trans. Numer. Anal., 20 (2005), pp. 164--179.

[53]

X. Tu, BDDC Domain Decomposition Algorithms: Methods with Three Levels and for Flow in Porous Media. Ph.D. thesis, New York University, Courant Institute of Mathematical Sciences, New York, 2006.

[54]

X. Tu, A BDDC algorithm for flow in porous media with a hybrid finite element discretization, Electron. Trans. Numer. Anal., 26 (2007), pp. 146--160.

[55]

X. Tu, Three-level BDDC in three dimensions, SIAM J. Sci. Comput., 29 (2007), pp. 1759--1780.

[56]

X. Tu, Three-level BDDC in two dimensions, Internat. J. Numer. Methods Engrg., 69 (2007), pp. 33--59.

[57]

X. Tu, A three-level BDDC algorithm for a saddle point problem, Numer. Math., 119 (2011), pp. 189--217.

[58]

X. Tu and J. Li, A unified dual-primal finite element tearing and interconnecting approach for incompressible Stokes equations, Internat. J, Numer. Methods Engrg., 94 (2013), pp. 128--149.

[59]

X. Tu and J. Li, A FETI-DP type domain decomposition algorithm for three-dimensional incompressible Stokes equations, SIAM J. Numer. Anal., 53 (2015), pp. 720--742.

[60]

M. F. Wheeler, G. Xue, and I. Yotov, A multiscale mortar multipoint flux mixed finite element method, ESAIM Math. Model. Numer. Anal., 46 (2012), pp. 759--796.

[61]

O. B. Widlund and C. R. Dohrmann, BDDC deluxe domain decomposition, in Domain Decomposition Methods in Science and Engineering XXII, Lecture Notes Comput. Sci. Eng. 104, Springer, Cham, Switzerland, 2016, pp. 93--103.

[62]

B. I. Wohlmuth, A. Toselli, and O. B. Widlund, An iterative substructuring method for Raviart--Thomas vector fields in three dimensions, SIAM J. Numer. Anal., 37 (2000), pp. 1657--1676.

[63]

S. Zampini, PCBDDC: A class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput., 38 (2016), pp. S282--S306.

[64]

S. Zampini, Adaptive BDDC deluxe methods for H(curl), in Domain Decomposition Methods in Science and Engineering XXIII, C.-O. Lee, X.-C. Cai, D. E. Keyes, H. H. Kim, A. Klawonn, E.-J. Park, and O. B. Widlund, ed., Springer, Cham, Switerland, 2017, pp. 285--292.

[65]

S. Zampini and D. E. Keyes, On the robustness and prospects of adaptive BDDC methods for finite element discretizations of elliptic PDEs with high-contrast coefficients, In Proceedings of the Platform for Advanced Scientific Computing Conference, PASC '16, ACM, New York, 2016, 6.

Cited By

Ciaramella GVanzan T(2022)Substructured two-grid and multi-grid domain decomposition methodsNumerical Algorithms10.1007/s11075-022-01268-091:1(413-448)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11075-022-01268-0
Ciaramella GVanzan T(2022)Spectral Coarse Spaces for the Substructured Parallel Schwarz MethodJournal of Scientific Computing10.1007/s10915-022-01840-991:3Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10915-022-01840-9

Recommendations

Low-Rank Correction Methods for Algebraic Domain Decomposition Preconditioners

This paper presents a parallel preconditioning method for distributed sparse linear systems, based on an approximate inverse of the original matrix, that adopts a general framework of distributed sparse matrices and exploits domain ...
A Balancing Domain Decomposition by Constraints Deluxe Method for Reissner--Mindlin Plates with Falk--Tu Elements

The Reissner--Mindlin plate models thin plates. The condition numbers of finite element approximations of these plate models increase very rapidly as the thickness of the plate goes to 0. A balancing domain decomposition by constraints (BDDC) deluxe method is ...
A Unified Analysis of Balancing Domain Decomposition by Constraints for Discontinuous Galerkin Discretizations

The BDDC algorithm is extended to a large class of discontinuous Galerkin (DG) discretizations of second order elliptic problems. An estimate of $C(1+\log(H/h))^2$ is obtained for the condition number of the preconditioned system where $C$ is a constant ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 39, Issue 4

DOI:10.1137/sjoce3.39.4

Issue’s Table of Contents

© 2017, Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2017

Author Tags

Author Tags

Qualifiers

Research-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 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ciaramella GVanzan T(2022)Substructured two-grid and multi-grid domain decomposition methodsNumerical Algorithms10.1007/s11075-022-01268-091:1(413-448)Online publication date: 1-Sep-2022
https://dl.acm.org/doi/10.1007/s11075-022-01268-0
Ciaramella GVanzan T(2022)Spectral Coarse Spaces for the Substructured Parallel Schwarz MethodJournal of Scientific Computing10.1007/s10915-022-01840-991:3Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10915-022-01840-9

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents