Summary
The modern design of industrial structures leads to very complex simulations characterized by nonlinearities, high heterogeneities, tortuous geometries... Whatever the modelization may be, such an analysis leads to the solution to a family of large ill-conditioned linear systems. In this paper we study strategies to efficiently solve to linear system based on non-overlapping domain decomposition methods. We present a review of most employed approaches and their strong connection. We outline their mechanical interpretations as well as the practical issues when willing to implement and use them. Numerical properties are illustrated by various assessments from academic to industrial problems. An hybrid approach, mainly designed for multifield problems, is also introduced as it provides a general framework of such approaches.
Similar content being viewed by others
References
Yves Achdou and Yuri A. Kuznetsov (1995). Substructuring preconditioners for finite element methods on nonmatching grids.East-West J. Numer. Math.,3(1), 1–28.
Yves Achdou, Yvon Maday and Olof B. Widlund (1996). Méthode itérative de sousstructuration pour les éléments avec joints.C.R. Acad. Sci. Paris,I(322), 185–190.
Mickael Barboteu, Pierre Alart and Marina Vidrascu (2001). A domain decomposition strategy for nonclassical frictional multicontact problems.Comp. Meth. App. Mech. Eng.,190, 4785–4803.
Richard Barrett, Michael Berry, Tony F. Chan, James Demmel, June Donato, Jack Dongarra, Victor Eijkhout, Roldan Pozo, Charles Romine and Henk Van der Vorst (1994).Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM.
T. Belytschko, Y. Krongauz, D. Organ, M. Fleming and P. Krysl (1996). Meshless methods: An overview and recent developments.Computer Methods in Applied Mechanics and Engineering,139, 3–47.
C. Bernardi, Y. Maday and T. Patera (1989). A new non conforming approach to domain decomposition: the Mortar Element Method. In: H. Brezis and J.L. Lious, editors,Nonlinear Partial Differential Equations and their Applications. Pitman, London.
M. Bhardwaj, D. Day, C. Farhat, M. Lesoinne, K. Pierson and D. Rixen (2000). Application of the FETI method to ASCI problems: Scalability results on a thousand-processor and discussion of highly heterogeneous problems.Int. J. Num. Meth. Eng.,47(1–3), 513–536.
J. E. Bolander and N. Sukumar (2005). Irregular lattice model for quasistatic crack propagation.Phys. Rev. B, 71.
Piotr Breikopt and Antonio Huerta (Eds.) (2002).Meshfree and particle based approaches in computational Mechanics, Volume 11 ofREEF special release. Hermes.
Suzanne Brenner (2005). Lower bounds in domain decomposition. InProceedings of the 16th international conference on domain decomposition methods.
F. Brezzi and L.D. Marini (1993). A three-field domain decomposition method. InProceedings of the Sixth International Conference on Domain Decomposition Methods, pp. 27–34.
M. Cross, C. Walshaw and M.C. Everett (1995). A parallelisable algorithm for optimising unstructured mesh partitions. Technical Report, School of Mathematics, Statistics & Scientific Computing, University of Greenwich, London.
X-C Cai and David Keyes. Nonlinearly preconditioned inexact newton algorithms.SIAM J. Sci. Comp., 2002.
A. Chapman and Y. Saad (1997). Deflated and augmented Krylov subspace techniques.Numer. Linear Algebra Appl..
P.G. Ciarlet (1979).The finite element method for elliptic problems. North Holland.
J. Salençon (1988).Mécanique des milieux continus. Ecole polytechnique. Ellipses, 1988.
R. Craig and M. Bampton. Coupling of substructures for dynamic analysis.AIAA Journal,6, 1313–1319.
Philippe Cresta, Olivier Allix, Christian Rey and Stéphane Guinard (2005). Comparison of multiscale and parallel nonlinear strategies based on domain decomposition for post buckling analysis.Comp. Meth. App. Mech. Eng.,196(8), 1436–1446.
Jean-Michel Cros (2002). A preconditioner for the schur complement domain decomposition method. In Herrera, Keyes and Widlund (Eds.),Proceedings of the 14 th International Conference on Domain Decomposition Methods, pp. 373–380.
G.A. D'Addetta, E. Ramm, S. Diebels and W. Ehlers (2004). A particle center based homogenization strategy for granular assemblies.Int. J. for Computer-Aided Engineering,21(2–4), 360–383.
A. de La Bourdonnaye, C. Farhat, A. Macedo, F. Magoules and F-X. Roux (1998).Adrances in Computational Mechanics with High Performance Computing. Chapter A method of finite element tearing and interconnecting for the Helmholtz problem, pp. 41–54. Civil-Comp Press, Edinburgh, United Kingdom.
Arnaud Delaplace (2005). Fine description of fracture by using discrete particle model. InProceedings of ICF 11-11th International Conference on Fracture.
Clarck Dohrmann (2003). A preconditioner for substructuring based on constrained energy minimization.SIAM J. Sci. Comp.,25(1), 246–258.
Victorita Dolean, F. Nataf and Gerd Rapin (2005). New constructions of domain decomposition methods for systems of PDEs.C. R. Acad. Sci. Paris,340(1), 693–696.
Z. Dostal (1988). Conjugate gradient method with preconditioning by projector.Int. J. Comput. Math.,23, 315–323.
Zdenek Dostal, David Horak and Dan Stefanica (2005). An overview of scalable feti-dp algorithms for variational inequalities. InProceedings of the 16th Conference on Domain Decomposition Methods.
D. Dureisseix and C. Farhat (2001). A numerically scalable domain decomposition method for the solution of frictionless contact problems.Internat. J. Num. Meth. Engng.,50(12), 2643–2666.
Georges Duvant (1990).Mécanique des milieux continus. Masson.
J. Erhel, K. Burrage and B. Pohl (1996). Restarted GMRes preconditioned by deflation.J. Comput. Appl. Math.,69, 303–318.
Justine Erhel and F. Guyomarc'h (2000). An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems.SIAM J. Matrix Anal. Appl.,21(4), 1279–1299.
C. Farhat (1992). A saddle-point principle domain decomposition method for the solution of solid mechanics problems. In D. Keyes, T.F. Chan, G.A. Meurant, J.S. Scroggs, and R.G. Voigt, editors,Domain Decomposition Methods for Partial Differential Equations, pp. 271–292.
C. Farhat, P.-S. Chen and F.-X. Roux (1998). The two-level FETI method-Part II: Extension to shell problems, parallel implementation and performance results.J. Comput. Meth. Appl. Mech. Eng.,155, 153–180.
C. Farhat and M. Géradin (1996). On the computation of the null space and generalized invers of large matrix, and the zero energy modes of a structure. Technical Report CU-CAS-96-15, Center for aerospace structures, May.
C. Farhat, M. Lesoinne, P. LeTallec, K. Pierson and D. Rixen (2001). FETI-DP: a dual-primal unified FETI method-part i: a faster alternative to the two-level FETI method.Int. J. Num. Meth. Eng.,50, (7), 1523–1544.
C. Farhat, M. Lesoinne and K. Pierson (2000). A scalable dual-primal domain decomposition method.Numer. Linear Algebra Appl.,7 (7–8), 687–714.
C. Farhat, A. Macedo and M. Lesoinne (2000). A two-level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems.Numerische Mathematik,85, 283–308.
C. Farhat, A. Macedo and R. Tezaur (1999). FETI-H: a scalable domaine decomposition method for high frequency exterior Helmholtz problems. InDomain decomposition methods in science and engineering. Domain decomposition press.
C. Farhat and J. Mandel (1998). The two-level FETI method for static and dynamic plate problems-part I: An optimal iterative solver for biharmonic systems.J. Comput. Meth. Appl. Mech. Eng.,155, 129–152.
C. Farhat, J. Mandel and F.X. Roux (1994). Optimal convergence properties of the FETI domain decomposition method.Comput. Meth. Appl. Mech. Eng.,115, 365–385.
C. Farhat, K. Pierson and M. Lesoinne (2000). The second generation FETI methods and their application to the parallel solution of large-scale linear and geometrically non-linear structural analysis problems.J. Comput. Meth. Appl. Mech. Eng.,184(2–4), 333–374
C. Farhat and F.-X. Roux (1991). A method of finite tearing and interconnecting and its parallel solution algorithm.Int. J. Num. Meth. Eng.,32, 1205–1227.
C. Farhat and F.-X. Roux (1994). The dual Schur complement method with well-posed local Neumann problems.Contemporary Mathematics,157, 193–201.
C. Farhat and F. X. Roux (1994). Implicit parallel processing in structural mechanics.Computational Mechanics Advances,2(1), 1–124. North-Holland.
C. Farhat and H. D. Simon (1993). Top/domdec—a software tool for mesh partitioning and parallel processing. Technical Report, NASA Ames.
Frédéric Feyel (1998).Application du calcul parallèle aux modèles à grand nombre de variables internes. Thèse de doctorat, Ecole Nationale Supérieure des Mines de Paris.
Frédéric Feyel (2005).Quelques multi-problèmes en mécanique des matériaux et structures. Habilitation à diriger des recherches, Université Pierre et Marie Curie.
Michel Fortin and Roland Glowinski (1982).Méthodes de lagrangien augmenté—applications à la résolution numérique de problèmes aux limites. Dunod.
Yannis Fragakis and Manolis Papadrakakis (2002). A unified framework for formulating domain decomposition methods in structural mechanics. Technical report, Institute of Structural Analysis and Seismic Research, National Technical University of Athens.
Yannis Fragakis and Manolis Papadrakakis (2003). The mosaic of high-performance domain decomposition methods for structural mechanics—part i: Formulation, interrelation and numerical efficiency of primal and dual methods.Comput. Meth. Appl. Mec. Eng.,192(35–36), 3799–3830.
Yannis Fragakis and Manolis Papadrakakis (2004). The mosaic of high-performance domain decomposition methods for structural mechanics—part ii: Formulation enhancements, multiple right-hand sides and implicit dynamics.Comput. Meth. Appl. Mec. Eng.,193(42–44), 4611–4662.
V. Frayssé, L. Girand and H. Kharraz-Aroussi (1998). On the influence of the orthogonalization scheme on the parallel performance of GMRes. Technical Report, CERFACS.
Norbert Germain, Jacques Besson and Frédéric Feyel (2005). Méthodes de calcul non local: Application aux structures composites. InActes du 7ème colloque national en calcul des structures, Giens.
P. Germain (1986).Mécanique. Ecole polytechnique. Ellipses.
R. Glowinski and P. Le Tallec (1990). Augmented lagrangian interpretation of the nonoverlapping Schwartz alternating method. InThird International Symposium on Domain Decomposition Methods for Partial Differential Equations pp. 224–231.
P. Goldfeld (2002). Balancing Neumann-Neumann for (in)compressible linear elasticity and (generalized) Stokes—parallel implementation. InProceedings of the 14 th International Conference on Domain Decomposition Method, pp. 209–216.
P. Gosselet, V. Chiaruttini, C. Rey and F. Feyel (2003). Une approche hybride de décomposition de domaine pour les problèmes multiphysiques: application à la poroélasticité. InActes du Sixième Colloque National en Calcul de Structures, Volume 2, pp. 297–304.
P. Gosselet, Vincent Chiaruttini, C. Rey and F. Feyel (2004). A monolithic strategy based on an hybrid domain decomposition method for multiphysic problems application to poroelasticity.Revue Européenne des Élements Finis,13, 523–534.
P. Gosselet and C. Rey (2002). On a selective reuse of krylov subspaces in newton-krylov approaches for nonlinear elasticity. InProceedings of the 14 th Conference on Domain Decomposition Methods, pp. 419–426.
P. Gosselet, C. Rey, P. Dasset and F. Léné (2002). A domain decomposition method for quasi incompressible formulations with discontinuous pressure field.Revue Européenne des Élements Finis,11, 363–377.
P. Gosselet, C. Rey and D. Rixen (2003). On the initial estimate of interface forces in FETI methods.Comput. Meth. Appl. Mech. Engrg.,192, 2749–2764.
Pierre Gosselet (2003).Méthodes de décomposition de domaine et méthodes d'accélération pour les problèmes multichamp en mécanique non-linéaire. PhD thesis, Université P. et M. Curie.
George Karypis and Vipin Kumar (1998). Multilevel algorithms for multi-constraint graph partitioning. Technical report, University of Minnesota, Department of Computer Science.
A. Klawonn, O. Rheinbach and O.B. Widlund (2005). Some computational results for dualprimal feti methods for three dimensional elliptic problems.Lect. Notes Comput. Sci. Eng.,40, 361–368.
A. Klawonn and O.B. Widlund (1999). Dual and dual-primal FETI methods for elliptic problems with discontinuous coefficients. InProceedings of the 12th International Conference on Domain Decomposition Methods, Chiba, Japan, October. Submitted.
A. Klawonn and O.B. Widlund (2001). FETI and Neumann-Neumann iterative substructuring methods: connections and new results.Comm. pure and appl. math., LIV, 0057–0090.
P. Ladevèze (1999).Nonlinear Computational Structural Mechanics—New Approaches and Non-Incremental Methods of Calculation. Springer Verlag.
P. Ladevèze, O. Loiseau and D. Dureisseix (2001). A micro-macro and parallel computational strategy for highly heterogeneous structures.Int. J. Num. Meth. Engng.,52, 121–138.
P. Ladevèze, D. Néron and P. Gosselet, P. (2006). On a mixed and multiscale domain decomposition method.Comput. Meth. in Appl. Mech. Engng.,196 (8), 1526–1540.
Michel Lesoinne and Kendall Pierson (1999). FETI-DP: An efficient, scalable, and unified Dual-Primal FETI method. InDomain Decomposition Methods in Sciences and Engineering, pp. 421–428.
Jing Li (2002). A dual-primal feti method for solving stokes/navier-stokes equations. InProceedings of the 14 th International Conference on Domain Decomposition Method, pp. 225–233.
F.J. Lingen (2000). Efficient Gram-Semidt orthonormalisation on parallel computers.Com. Numer. Meth. Engng.,16, 57–66.
JL. Lious, Y. Maday and G. Turinici (2001). Résolution d'edp par un schéma en temps pararéel.C. R. Acad. Sci. Paris,333 (1), 1–6.
Gui-Rong Liu and Yuan-Tong Gu (2005).An Introduction to Meshfree Methods and Their Programming. Springer.
J. Mandel (1993). Balancing domain decomposition.Comm. Appl. Num. Meth. Engng.,9, 233–241.
J. Mandel and M. Brezina (1996). Balancing domain decomposition for problems with large jumps in coefficients.Math. Comp.,65(216), 1387–1401.
J. Mandel and R. Tezaur (1996). Convergence of a substructuring method with Lagrange multipliers.Numerische Mathematik,73, 473–487.
J. Mandel and R. Tezaur (2000). On the convergence of a dual-primal substructuring method. UCD/CCM Report 150, Center for Computational Mathematics, University of Colorado at Denver, April. To appear in Numer. Math.
Northwest Numerics (2001).Z-set developper manual.
Northwest Numeries (2001).Z-set user manual.
A. Nouy (2003).Une stratégie de calcul multiéchelle avec homogénéisation en temps et en espace pour le calcul de structures fortement hétérogènes. PhD thesis, ENS de Cachan.
K.C. Park, M.R. Justino, and C.A. Felippa (1997). An algebraically partitioned FETI method for parallel structural analysis: algorithm description.Int. J. Num. Meth. Eng.,40(15), 2717–2737.
K.C. Park, M.R. Justino, and C.A. Felippa (1997) An algebraically partitioned FETI method for parallel structural analysis: performance evaluation.Int. J. Num. Meth. Eng.,40(15), 2739–2758.
Rodrigo Paz and Mario Storti (2005). An interface strip preconditioner for domain decomposition methods: application to hydrologyInt. J. Numer. Meth. Engng.,62, 1873–1894.
C. Rey and P. Gosselet (2003). Solution to large nonlinear systems: acceleration strategies based on domain decomposition and reuse of krylov subspaces. InProceedings of the 6t h ESAFORM conference on material forming.
C. Rey and F. Léné (1998). Reuse of krylov spaces in the solution of large-scale non linear elasticity problems. InDomain Decomposition Methods in Sciences and Engineering, pp. 465–471.
C. Rey and F. Risler (1998). A Rayleigh-Ritz preconditioner for the iterative solution to large scale nonlinear problems.Numerical Algorithms,17, 279–311.
Franck Risler and Christian Rey (2000). Iterative accelerating algorithms with Krylov subspaces for the solution to large-scale nonlinear problems.Numerical Algorithms,23, 1–30.
Frank Risler and Christian Rey (1998). On the reuse of Ritz vectors for the solution to nonlinear elasticity problems by domain decomposition methods. InDD10 Proceedings, Contemporary Mathematics, Volume 218, pp. 334–340.
D. Rixen (1997).Substructuring and dual methods in structural analysis. PhD thesis University of Liège, Belgique.
D. Rixen (2004). A dual craig-bampton method for dynamic substructuring.J. Comput. Appl. Math. 168, 383–391.
D. Rixen and C. Farhat (1999). A simple and efficient extension of a class of substructure based preconditioners to heterogeneous structural mechanics problems.Int. J. Num. Meth. Eng.,44(4), 489–516.
D. Rixen, C. Farhat, R. Tezaur and J. Mandel (1999). Theoretical comparison of the FETI and algebraically partitioned FETI methods, and performance comparisons with a direct sparse solver.Int. J. Num. Meth. Eng.,46(4), 501–534.
Daniel Rixen (2002). Extended preconditioners for the feti method applied to constrained problems.Int. Journal for Numerical Methods in Engineering,54(1), 1–26.
F.-X. Roux (1997), Parallel implementation of direct solution strategies for the coarse grig solvers in 2-level FETI method. Technical report, ONERA, Paris, France.
Y. Saad (1997). Analysis of augmented Krylov subspace methods.SIAM J. Matrix Anal. Appl.,18(2), 435–449.
Y. Saad (2000).Iterative methods for sparse linear systems. PWS Publishing Company, 3rd edition.
Y. Saad and M.H. Schultz (1986). GMRes: a generalized minimal residual algorithm for solving nonsymmetric linear systems.SIAM J. Sci. Comput.,7, 856–869.
Youssef Saad (1987). On the Lanczos method for solving symmetric linear systems with several right hand sides.Math. Comp.,48, 651–662.
L. Series, F. Feyel and F.-X. Roux (2003). Une méthode de décomposition de domaine avec deux multiplicateurs de Lagrange. InActes du 16eme Congrès Français de Mécanique.
L. Series, F. Feyel and F.-X. Roux (2003). Une méthode de décomposition de domaine avec deux multiplicateurs de Lagrange, application au calcul des structures, cas du contact. InActes du Sixième Colloque National en Calcul des Structures, Volume III, pp. 373–380.
D. Stefanica and A. Klawonn (1999). The FETI method for mortar finite elements. InProceedings of 11th International Conference on Domain Decomposition Methods, pp. 121–129.
P. Le Tallec (1994). Domain-decomposition methods in computational mechanics.Computational Mechanics Advances,1(2), 121–220. North-Holland.
P. Le Tallec, J. Mandel and M. Vidrascu (1998). A Neumann-Neumann domain decomposition algorithm for solving plate and shell problems.SIAM. J. Num. Ana.,35(2), 836–867, April.
P. Le Tallec, Y.-H. De Roeck and M. Vidrascu (1991). Domain-decomposition methods for large linearly elliptic three dimensional problems.J. Comp. Appl. Math.,34, 93–117. Elsevier Science Publishers, Amsterdam.
P. Le Tallec and M. Vidrascu (1993). Méthodes de décomposition de domaines en calcul de structures. InActes du Premier Colloque National en Calcul des Structures, Volume, I, pp. 33–49.
P. Le Tallec and M. Vidrascu (1996). Generalized Neumann-Neumann preconditioners for iterative substructuring. InProceedings of the Ninth Conference on Domain Decomposition, June Bergen. to appear.
A. van der Sluis and H. can der Vorst (1986). The rate of convergence of conjugate gradients. Numer. Math.,48, 543–560.
Pieter Wesseling (2004).An Introduction to Multigrid Methods. R.T. Edwards, Inc.
O.C. Zienkiewicz and R.L. Taylor (1989).The finite element method. Mc Graw-Hill Book Compagny.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gosselet, P., Rey, C. Non-overlapping domain decomposition methods in structural mechanics. Arch Computat Methods Eng 13, 515 (2006). https://doi.org/10.1007/BF02905857
Received:
DOI: https://doi.org/10.1007/BF02905857