Library Subscription: Guest
Begell Digital Portal Begell Digital Library eBooks Journals References & Proceedings Research Collections
International Journal for Multiscale Computational Engineering
IF: 1.016 5-Year IF: 1.194 SJR: 0.452 SNIP: 0.68 CiteScore™: 1.18

ISSN Print: 1543-1649
ISSN Online: 1940-4352

International Journal for Multiscale Computational Engineering

DOI: 10.1615/IntJMultCompEng.2013006012
pages 633-654


Haim Waisman
Department of Civil Engineering and Engineering Mechanics, Columbia University, New York, New York 10027, USA
Luc Berger-Vergiat
Department of Civil Engineering & Engineering Mechanics, Columbia University, New York 10027, USA


Application of an algebraic multigrid (AMG) solver to linear systems arising from fracture problems modeled by extended finite elements (XFEM) will often result in poor convergence. This is due to coarsening operators in AMG that disregard the discontinuous enrichment functions and automatically coarsen across cracks. To overcome the AMG coarsening limitation, we propose a multiplicative-Schwarz domain decomposition preconditioner to the generalized minimum residual method. In this approach the domain is decomposed into one uncracked subdomain and multiple cracked subdomains. A cracked subdomain is the domain containing the crack and its enrichment functions and the uncracked subdomain contains the rest of the domain with a one-element-layer overlap between the two. Within the preconditioning scheme, one AMG V-cycle is applied to the uncracked subdomain to obtain an approximate solution while the cracked subdomains (often much smaller compared to the uncracked part) are solved concurrently by a direct solver, thus resolving the error from the discontinuous fields exactly. Hence any black box AMG solver can be used for XFEM, and the need for development of special coarsening procedures that handle enriched degrees of freedom can be avoided. We consider multiple propagating cracks and develop an algorithm that adaptively updates the subdomains, following the cracks. This adaptive scheme can be obtained directly from level set values which are updated with crack growth or from close neighbor search algorithms. The level set update scheme is fast but does not guarantee tight subdomains, while a neighbor search is slower but gives optimal subdomains. The preconditioner is tested on structured and unstructured meshes with multiple propagating cracks and shows convergence rates that are significantly better than a brute force application of AMG to the entire domain.


  1. Achtert, E., Böhm, C., Kröger, P., Kunath, P., Pryakhin, A., and Renz, M., Efficient reverse k-nearest neighbor search in arbitrary metric spaces. DOI: 10.1145/1142473.1142531

  2. Anderson, T., Fracture Mechanics: Fundamentals and Applications.

  3. Banks-Sills, L. and Sherman, D., Comparison of methods for calculating stress intensity factors with quarter-point elements. DOI: 10.1007/BF00019788

  4. Belytschko, T. and Black, T., Elastic crack growth in finite elements with minimal remeshing. DOI: 10.1002/(SICI)1097-0207(19990620)45:5<601::AID-NME598>3.0.CO;2-S

  5. Berchtold, S., Ertl, B., Keim, D. A., Kriegel, H. P., and Seidl, T., Fast nearest neighbor search in high-dimensional space. DOI: 10.1109/ICDE.1998.655779

  6. Berger-Vergiat, L., Waisman, H., Hiriyur, B., Tuminaro, R., and Keyes, D., Inexact Schwarz-algebraic multigrid preconditioners for crack problems modeled by extended finite element methods. DOI: 10.1002/nme.3318

  7. Brandt, A., Multi-level adaptive solutions to boundary-value problems. DOI: 10.1090/S0025-5718-1977-0431719-X

  8. Briggs, W. L., Henson, V. E., and McCormick, S. F., A Multigrid Tutorial.

  9. Broberg, K., Crack-growth criteria and non-linear fracture mechanics. DOI: 10.1016/0022-5096(71)90008-1

  10. Bui, H. D., Charras, T., and Cheissoux, J., M&#233;canique de la Rupture: M&#233;thodes Num&#233;riques Pour L&#8216;ing&#233;nieur.

  11. Chan, S., Tuba, I., and Wilson, W., On the finite element method in linear fracture mechanics. DOI: 10.1016/0013-7944(70)90026-3

  12. Decker, R., Source Book on Maraging Steels.

  13. Duarte, C. A., Babu&#353;ka, I., and Oden, J. T., Generalized finite element methods for three-dimensional structural mechanics problems. DOI: 10.1016/S0045-7949(99)00211-4

  14. Erdogan, F. and Sih, G. C., On the crack extension in plate under plane loading and transverse shear. DOI: 10.1115/1.3656897

  15. Fan, R. and Fish, J., The <i>rs</i>-method for material failure simulations. DOI: 10.1002/nme.2134

  16. Farhat, C., Mandel, J., and Roux, F. X., Optimal convergence properties of the FETI domain decomposition method. DOI: 10.1016/0045-7825(94)90068-X

  17. Farhat, C. and Roux, F. X., A method of finite element tearing and interconnecting and its parallel solution algorithm. DOI: 10.1002/nme.1620320604

  18. Fish, J., The <i>s</i>-version of the finite element method. DOI: 10.1016/0045-7949(92)90287-A

  19. Fish, J. and Markolefas, S., Adaptive <i>s</i>-method for linear elastostatics. DOI: 10.1016/0045-7825(93)90032-S

  20. Gee, M.W., Hu, J. J., and Tuminaro, R. S., A new smoothed aggregation multigrid method for anisotropic problems. DOI: 10.1002/nla.593

  21. Goodman, J. E. and O&#8216;Rourke, J., Handbook of Discrete and Computational Geometry. DOI: 10.1201/9781420035315

  22. Gosz, M., Dolbow, J., and Moran, B., Domain integral formulation for stress intensity factor computation along curved threedimensional interface cracks. DOI: 10.1016/S0020-7683(97)00132-7

  23. Gosz, M. and Moran, B., An interaction energy integral method for computation of mixed-mode stress intensity factors along non-planar crack fronts in three dimensions. DOI: 10.1016/S0013-7944(01)00080-7

  24. Gravouil, A., Rannou, J., and Ba&#239;etto, M.-C., A local multi-grid X-FEM approach for 3D fatigue crack growth. DOI: 10.1007/s12289-008-0212-z

  25. Heroux, M. A., Bartlett, R. A., Howle, V. E., Hoekstra, R. J., Hu, J., Kolda, T. G., Lehoucq, R. B., Long, K. R., Pawlowski, R. P., Phipps, E. T., Salinger, A. G., Thornquist, H. K., Tuminaro, R. S., Willenbring, J. M., Williams, A., and Stanley, K. S., An overview of the Trilinos project. DOI: 10.1145/1089014.1089021

  26. Hiriyur, B., Tuminaro, R., Waisman, H., Boman, E., and Keyes, D., A quasi-algebraic multigrid approach to fracture problems based on the extended finite element method. DOI: 10.1137/110819913

  27. Hughes, T. J. R., The Finite Element Method: Linear Static And Dynamic Finite Element Analysis.

  28. Kishimoto, K., Aoki, S., and Sakata, M., On the path independent integral-&#309;. DOI: 10.1016/0013-7944(80)90015-6

  29. Krauthgamer, R. and Lee, J., The black-box complexity of nearest-neighbor search. DOI: 10.1016/j.tcs.2005.09.017

  30. Li, F. Z., Shih, C. F., and Needleman, A., A comparison of methods for calculating energy release rates. DOI: 10.1016/0013-7944(85)90029-3

  31. Liu, X. Y., Xiao, Q. Z., and Karihaloo, B. L., XFEM for direct evaluation of mixed mode SIFs in homogeneous and bi-materials. DOI: 10.1002/nme.906

  32. Menk, A. and Bordas, S. P. A., A robust preconditioning technique for the extended finite element method. DOI: 10.1002/nme.3032

  33. Mo&#235;s, N., Dolbow, J., and Belytschko, T., A finite element method for crack growth without remeshing. DOI: 10.1002/(SICI)1097-0207(19990910)46:1<131::AID-NME726>3.0.CO;2-J

  34. Mo&#235;s, N., Gravouil, A., and Belytschko, T., Non-planar 3D crack growth by the extended finite element and level sets&mdash;Part I: Mechanical model. DOI: 10.1002/nme.429

  35. Munjiza, A. A., The Combined Finite-Discrete Element Method. DOI: 10.1002/0470020180

  36. Nagashima, T., Omoto, Y., and Tani, S., Stress intensity factor analysis of interface cracks using X-FEM. DOI: 10.1002/nme.604

  37. Nuismer, R. J., An energy release rate criterion for mixed mode fracture. DOI: 10.1007/BF00038891

  38. Olson, L. N., Schroder, J. B., and Tuminaro, R. S., A general interpolation strategy for algebraic multigrid using energy minimization. DOI: 10.1137/100803031

  39. Oosterlee, C.W. and Washio, T., On the use of multigrid as a preconditioner.

  40. Osher, S. and Sethian, J. A., Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations. DOI: 10.1016/0021-9991(88)90002-2

  41. Parks, D. M., A stiffness derivative finite element technique for determination of crack tip stress intensity factors. DOI: 10.1007/BF00155252

  42. Parsons, I. D. and Hall, J. F., The multigrid method in solid mechanics: Part I&mdash;algorithm description and behaviour. DOI: 10.1002/nme.1620290404

  43. Parsons, I. D. and Hall, J. F., The multigrid method in solid mechanics: Part II&mdash;practical applications. DOI: 10.1002/nme.1620290405

  44. Passieux, J. C., Gravouil, A., Rh&#233;thor&#233;, J., and Baietto, M. C., Direct estimation of generalised stress intensity factors using threescale concurrent multigrid X-FEM. DOI: 10.1002/nme.3037

  45. Pommier, S., Gravouil, A., Mo&#235;s, N., and Combescure, A., Extended Finite Element Method for Crack Propagation. DOI: 10.1002/9781118622650

  46. Rannou, J., Gravouil, A., and Baietto-Dubourg, M. C., A local multigrid X-FEM strategy for 3-D crack propagation. DOI: 10.1002/nme.2427

  47. Rice, J. R., A path independent integral and the approximate analysis of strain concentration by notches and cracks. DOI: 10.1115/1.3601206

  48. Rybicki, E. and Kanninen, M., A finite element calculation of stress intensity factors by a modified crack closure integral. DOI: 10.1016/0013-7944(77)90013-3

  49. Saad, Y. and Schultz, M. H., GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems. DOI: 10.1137/0907058

  50. Sethian, J. A., Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision, and Materials Science.

  51. Shih, C. F., Lorenzi, H. G., and German, M. D., Crack extension modeling with singular quadratic isoparametric elements. DOI: 10.1007/BF00034654

  52. Sih, G. C., Strain-energy-density factor applied to mixed mode crack problems. DOI: 10.1007/BF00035493

  53. Smith, B. F., Bjorstad, P., and Gropp, W., Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations.

  54. Sukumar, N., Chopp, D. L., Mo&#235;s, N., and Belytschko, T., Modeling holes and inclusions by level sets in the extended finite element method. DOI: 10.1016/S0045-7825(01)00215-8

  55. Toselli, A. and Widlund, O., Domain Decomposition Methods &#8211; Algorithms and Theory. DOI: 10.1007/b137868

  56. Tuminaro, R. S., Parallel smoothed aggregation multigrid: aggregation strategies on massively parallel machines.

  57. Tuminaro, R. S. and Tong, C., Parallel smoothed aggregation multigrid: Aggregation strategies on massively parallel machines. DOI: 10.1109/SC.2000.10008

  58. Van&#283;k, P., Mandel, J., and Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. DOI: 10.1007/BF02238511

  59. Waisman, H., An analytical stiffness derivative extended finite element technique for extraction of crack tip strain energy release rates. DOI: 10.1016/j.engfracmech.2010.08.015

  60. Waisman, H., Fish, J., Tuminaro, R. S., and Shadid, J., The Generalized Global Basis (GGB) method. DOI: 10.1002/nme.1107

  61. Waisman, H., Fish, J., Tuminaro, R. S., and Shadid, J., Acceleration of the Generalized Global Basis (GGB) method for nonlinear problems. DOI: 10.1016/

  62. Williams, J. G. and Ewing, P. D., Fracture under complex stress, the angled crack problem. DOI: 10.1007/BF00962967

  63. Williams, M. L., On the stress distribution at the base of a stationary crack.

  64. Wyart, E., Duflot, M., Coulon, D., Martiny, P., Pardoen, T., and Remacle, J.-F., A substructured FE-shell/XFE-3D method for crack analysis in thin-walled structures. DOI: 10.1002/nme.2029

  65. Wyart, E., Duflot, M., Coulon, D., Martiny, P., Pardoen, T., Remacle, J.-F., and Lani, F., Substructuring FE-XFE approaches applied to three-dimensional crack propagation. DOI: 10.1016/

  66. Xu, J. and Zikatanov, L. T., On Multigrid Methods for Generalized Finite Element Methods. DOI: 10.1007/978-3-642-56103-0_28

  67. Zamani, A., Gracie, R., and Eslami, R., Cohesive and non-cohesive fracture by higher-order enrichment of xfem. DOI: 10.1002/nme.3329

Articles with similar content:

International Journal for Multiscale Computational Engineering, Vol.12, 2014, issue 3
Youming Wang, Yongqing Fan, Qing Wu
International Journal for Multiscale Computational Engineering, Vol.11, 2013, issue 5
Omer San, Anne E. Staples
Olivier F. Balima
Adaptive Multiwavelet-Hierarchical Method for Multiscale Computation
International Journal for Multiscale Computational Engineering, Vol.8, 2010, issue 4
Youming Wang, Zhengjia He, Xuefeng Chen
International Journal for Multiscale Computational Engineering, Vol.11, 2013, issue 6
Mirmohammadreza Kabiri, Franck J. Vernerey