Top

Computing

Published in:

01-12-2013

Adaptive-Multilevel BDDC and its parallel implementation

Authors: Bedřich Sousedík, Jakub Šístek, Jan Mandel

Published in: Computing | Issue 12/2013

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We combine the adaptive and multilevel approaches to the BDDC and formulate a method which allows an adaptive selection of constraints on each decomposition level. We also present a strategy for the solution of local eigenvalue problems in the adaptive algorithm using the LOBPCG method with a preconditioner based on standard components of the BDDC. The effectiveness of the method is illustrated on several engineering problems. It appears that the Adaptive-Multilevel BDDC algorithm is able to effectively detect troublesome parts on each decomposition level and improve convergence of the method. The developed open-source parallel implementation shows a good scalability as well as applicability to very large problems and core counts.

next article MPI + MPI: a new hybrid approach to parallel programming with MPI plus shared memory

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

http://www.math.cas.cz/~sistek/software/bddcml.html.

http://code.google.com/p/blopex.

Amestoy PR, Duff IS, L’Excellent JY (2000) Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput Methods Appl Mech Eng 184:501–520CrossRefMATH

Blaheta R, Jakl O, Starý J, Krečmer K (2009) The Schwarz domain decomposition method for analysis of geocomposites. In: Topping B, Neves LC, Barros R (eds) Proceedings of the twelfth international conference on civil, structural and environmental engineering computing. Civil-Comp Press, Stirlingshire

Brenner SC, Sung LY (2007) BDDC and FETI-DP without matrices or vectors. Comput Methods Appl Mech Eng 196(8):1429–1435MathSciNetCrossRefMATH

Brož J, Kruis J, (2009) An algorithm for corner nodes selection in the FETI-DP method. In: Enginnering mechanics 2009—CDROM [CD-ROM]. Institute of Theoretical and Applied Mechanics AS CR, Prague, pp 129–140

Cros JM (2003) A preconditioner for the Schur complement domain decomposition method. In: Herrera I, Keyes DE, Widlund OB (eds) Domain decomposition methods in science and engineering. In: 14th international conference on domain decomposition methods, Cocoyoc, Mexico, January 6–12, 2002. National Autonomous University of Mexico (UNAM), México (2003) , pp 373–380

Demmel JW (1997) Applied numerical linear algebra. Society for Industrial and Applied Mathematics (SIAM), Philadelphia

Dohrmann CR (2003) A preconditioner for substructuring based on constrained energy minimization. SIAM J Sci Comput 25(1):246–258MathSciNetCrossRefMATH

Farhat C, Lesoinne M, Pierson K (2000) A scalable dual-primal domain decomposition method. Numer Linear Algebra Appl 7:687–714MathSciNetCrossRefMATH

Fragakis Y, Papadrakakis M (2003) The mosaic of high performance domain decomposition methods for structural mechanics: formulation, interrelation and numerical efficiency of primal and dual methods. Comput Methods Appl Mech Eng 192:3799–3830CrossRefMATH

10.

Ipsen ICF, Meyer CD (1995) The angle between complementary subspaces. Am Math Monthly 102(10):904–911MathSciNetCrossRefMATH

11.

Karypis G, Kumar V (1998) METIS: a software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4.0. Technical report, Department of Computer Science, University of Minnesota. http://glaros.dtc.umn.edu/gkhome/views/metis

12.

Kim HH, Tu X (2009) A three-level BDDC algorithm for mortar discretizations. SIAM J Numer Anal 47(2):1576–1600. doi:10.1137/07069081X MathSciNetCrossRefMATH

13.

Klawonn A, Rheinbach O, Widlund OB (2008) An analysis of a FETI-DP algorithm on irregular subdomains in the plane. SIAM J Numer Anal 46(5):2484–2504. doi:10.1137/070688675 MathSciNetCrossRefMATH

14.

Klawonn A, Widlund OB (2006) Dual-primal FETI methods for linear elasticity. Commun Pure Appl Math 59(11):1523–1572MathSciNetCrossRefMATH

15.

Klawonn A, Widlund OB, Dryja M (2002) Dual-primal FETI methods for three-dimensional elliptic problems with heterogeneous coefficients. SIAM J Numer Anal 40(1):159–179MathSciNetCrossRefMATH

16.

Knyazev AV (2001) Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method. Copper Mountain conference, 2000. SIAM J Sci Comput 23(2):517–541

17.

Kruis J (2006) Domain decomposition methods for distributed computing. Saxe-Coburg Publications, Kippen

18.

Lesoinne M (2003) A FETI-DP corner selection algorithm for three-dimensional problems. In: Herrera I, Keyes DE, Widlund OB (eds) Domain decomposition methods in science and engineering. In: 14th international conference on domain decomposition methods, Cocoyoc, Mexico, January 6–12, 2002. National Autonomous University of Mexico (UNAM), México, pp 217–223. http://www.ddm.org

19.

Li J, Widlund OB (2006) FETI-DP, BDDC, and block Cholesky methods. Int J Numer Methods Eng 66(2):250–271MathSciNetCrossRefMATH

20.

Mandel J, Dohrmann CR (2003) Convergence of a balancing domain decomposition by constraints and energy minimization. Numer Linear Algebra Appl 10(7):639–659MathSciNetCrossRefMATH

21.

Mandel J, Dohrmann CR, Tezaur R (2005) An algebraic theory for primal and dual substructuring methods by constraints. Appl Numer Math 54(2):167–193MathSciNetCrossRefMATH

22.

Mandel J, Sousedík B (2006) Adaptive coarse space selection in the BDDC and the FETI-DP iterative substructuring methods: optimal face degrees of freedom. In: Widlund OB, Keyes DE (eds) Domain decomposition methods in science and engineering XVI. Lecture notes in computational science and engineering, vol 55. Springer, Berlin, pp 421–428CrossRef

23.

Mandel J, Sousedík B (2007) Adaptive selection of face coarse degrees of freedom in the BDDC and the FETI-DP iterative substructuring methods. Comput Methods Appl Mech Eng 196(8):1389–1399CrossRefMATH

24.

Mandel J, Sousedík B (2007) BDDC and FETI-DP under minimalist assumptions. Computing 81:269–280MathSciNetCrossRefMATH

25.

Mandel J, Sousedík B, Dohrmann CR (2007) On multilevel BDDC. Domain decomposition methods in science and engineering XVII. Lecture notes in computational science and engineering, vol 60, pp 287–294

26.

Mandel J, Sousedík B, Dohrmann CR (2008) Multispace and multilevel BDDC. Computing 83(2–3):55–85. doi:10.1007/s00607-008-0014-7 MathSciNetCrossRefMATH

27.

Mandel J, Sousedík B, Šístek J (2001) Adaptive BDDC in three dimensions. Math Comput Simul 82(10):1812–1831. doi:10.1016/j.matcom.2011.03.014 CrossRef

28.

Mandel J, Tezaur R (2001) On the convergence of a dual-primal substructuring method. Numer Math 88:543–558MathSciNetCrossRefMATH

29.

Pechstein C, Scheichl R (2008) Analysis of FETI methods for multiscale PDEs. Numer Math 111(2):293–333MathSciNetCrossRefMATH

30.

Pechstein C, Scheichl R (2011) Analysis of FETI methods for multiscale PDEs—Part II: interface variations. Numer Math 118(3):485–529MathSciNetCrossRefMATH

31.

Šístek J, Mandel J, Sousedík B (2012) Some practical aspects of parallel adaptive BDDC method. In: Brandts J, Chleboun J, Korotov S, Segeth K, Šístek J, Vejchodský T (eds) Proceedings of Applications of Mathematics 2012. Institute of Mathematics AS CR, pp 253–266

32.

Šístek J, Mandel J, Sousedík B, Burda P (2013) Parallel implementation of Multilevel BDDC. In: Proceedings of ENUMATH 2011. Springer, Berlin (to appear)

33.

Šístek J, Čertíková M, Burda P, Novotný J (2012) Face-based selection of corners in 3D substructuring. Math Comput Simul 82(10):1799–1811. doi:10.1016/j.matcom.2011.06.007 CrossRef

34.

Smith BF, Bjørstad PE, Gropp WD (1996) Domain decomposition: parallel multilevel methods for elliptic partial differential equations. Cambridge University Press, CambridgeMATH

35.

Sousedík B (2008) Comparison of some domain decomposition methods. Ph.D. thesis, Czech Technical University in Prague, Faculty of Civil Engineering, Department of Mathematics. http://mat.fsv.cvut.cz/doktorandi/files/BSthesisCZ.pdf. Retrieved December 2011

36.

Sousedík B (2010) Adaptive-Multilevel BDDC. Ph.D. thesis, University of Colorado Denver, Department of Mathematical and Statistical Sciences

37.

Sousedík B (2011) Nested BDDC for a saddle-point problem. submitted to Numerische Mathematik. http://arxiv.org/abs/1109.0580

38.

Sousedík B, Mandel J (2008) On the equivalence of primal and dual substructuring preconditioners. Electron Trans Numer Anal 31:384–402. http://etna.mcs.kent.edu/vol.31.2008/pp384-402.dir/pp384-402.html. Retrieved December 2011

39.

Sousedík B, Mandel J (2011) On Adaptive-Multilevel BDDC. In: Huang Y, Kornhuber R, Widlund O, Xu J (eds) Domain decomposition methods in science and engineering XIX. Lecture notes in computational science and engineering vol 78, Part 1. Springer, Berlin, pp 39–50. doi:10.1007/978-3-642-11304-8_4

40.

Toselli A, Widlund OB (2005) Domain decomposition methods—algorithms and theory. In: Springer series in computational mathematics, vol 34. Springer, Berlin

41.

Tu X (2007) Three-level BDDC in three dimensions. SIAM J Sci Comput 29(4):1759–1780. doi:10.1137/050629902 MathSciNetCrossRefMATH

42.

Tu X (2007) Three-level BDDC in two dimensions. Int J Numer Methods Eng 69(1):33–59. doi:10.1002/nme.1753 CrossRefMATH

43.

Tu X (2011) A three-level BDDC algorithm for a saddle point problem. Numer Math 119(1):189–217. doi:10.1007/s00211-011-0375-2 MathSciNetCrossRefMATH

44.

Widlund OB (2009) Accomodating irregular subdomains in domain decomposition theory. In: Bercovier M, Gander M, Kornhuber R, Widlund O (eds) Domain decomposition methods in science and engineering XVIII. Proceedings of 18th international conference on domain decomposition. Jerusalem, Israel, January 2008. Lecture notes in computational science and engineering, vol 70. Springer, Berlin

Title: Adaptive-Multilevel BDDC and its parallel implementation
Authors: Bedřich Sousedík
Jakub Šístek
Jan Mandel
Publication date: 01-12-2013
Publisher: Springer Vienna
Published in: Computing / Issue 12/2013
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-013-0293-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Premium Partner