zbMATH — the first resource for mathematics

A robust adaptive algebraic multigrid linear solver for structural mechanics. (English) Zbl 1441.74302
Summary: The numerical simulation of structural mechanics applications via finite elements usually requires the solution of large-size linear systems, especially when accurate results are sought for derived variables, like stress or deformation fields. Such a task represents the most time-consuming kernel, and motivates the development of robust and efficient linear solvers for these applications. On the one hand, direct solvers are robust and easy to use, but their computational complexity in the best scenario is superlinear, which limits applicability according to the problem size. On the other hand, iterative solvers, in particular those based on algebraic multigrid (AMG) preconditioners, can reach up to linear complexity, but require more knowledge from the user for an efficient setup, and convergence is not always guaranteed, especially in ill-conditioned problems. In this work, we present a novel AMG method specifically tailored for ill-conditioned structural problems. It is characterized by an adaptive factored sparse approximate inverse (aFSAI) method as smoother, an improved least-squared based prolongation (DPLS) and a method for uncovering the near-null space that takes advantage of an already existing approximation. The resulting linear solver has been applied in the solution of challenging linear systems arising from real-world linear elastic structural problems. Numerical experiments prove the efficiency and robustness of the method and show how, in several cases, the proposed algorithm outperforms state-of-the-art AMG linear solvers. Even more important, the results show how the proposed method gives good results even assuming a default setup, making it fully adoptable also for non-expert users and commercial software.

74S99 Numerical and other methods in solid mechanics
65F10 Iterative numerical methods for linear systems
74B05 Classical linear elasticity
Full Text: DOI
[1] Li, J.; Saharan, A.; Koric, S.; Ostoja-Starzewski, M., Elastic-plastic transition in three-dimensional random materials: massively parallel simulations, fractal morphogenesis and scaling functions, Phil. Mag., 92, 22, 2733-2758 (2012)
[2] Pavarino, L.; Scacchi, S.; Zampini, S., Newton-Krylov-BDDC solvers for nonlinear cardiac mechanics, Comput. Methods Appl. Mech. Engrg., 295, 562-580 (2015) · Zbl 1423.74913
[3] Zhang, X.; Oate, E.; Torres, S. A.G.; Bleyer, J.; Krabbenhoft, K., A unified Lagrangian formulation for solid and fluid dynamics and its possibility for modelling submarine landslides and their consequences, Comput. Methods Appl. Mech. Engrg., 343, 314-338 (2019)
[4] Dialami, N.; Chiumenti, M.; Cervera, M.; Agelet de Saracibar, C., Challenges in thermo-mechanical analysis of friction stir welding processes, Arch. Comput. Methods Eng., 24, 1, 189-225 (2017) · Zbl 1360.74044
[5] Wang, G.; Wang, Y.; Lu, W.; Yu, M.; Wang, C., Deterministic 3D seismic damage analysis of Guandi concrete gravity dam: A case study, Eng. Struct., 148, 263-276 (2017)
[6] Koric, S.; Gupta, A., Sparse matrix factorization in the implicit finite element method on petascale architecture, Comput. Methods Appl. Mech. Engrg., 302, 281-292 (2016) · Zbl 1425.65062
[7] Cotton, R.; Pearce, C.; Young, P.; Kota, N.; Leung, A.; Bagchi, A.; Qidwai, S., Development of a geometrically accurate and adaptable finite element head model for impact simulation: the naval research laboratory – simpleware head model, Comput. Methods Biomech. Biomed. Eng., 19, 1, 101-113 (2016)
[8] Hasegawa, M.; Adachi, T.; Takano-Yamamoto, T., Computer simulation of orthodontic tooth movement using CT image-based voxel finite element models with the level set method, Comput. Methods Biomech. Biomed. Eng., 19, 5, 474-483 (2016)
[9] Truster, T. J.; Masud, A., A unified mixture formulation for density and volumetric growth of multi-constituent solids in tissue engineering, Comput. Methods Appl. Mech. Engrg., 314, 222-268 (2017)
[10] Zhang, C.; Li, N.; Wang, W.; Binienda, W. K.; Fang, H., Progressive damage simulation of triaxially braided composite using a 3D meso-scale finite element model, Compos. Struct., 125, 104-116 (2015)
[11] Zhou, R.; Song, Z.; Lu, Y., 3D mesoscale finite element modelling of concrete, Comput. Struct., 192, 96-113 (2017)
[12] Mazzucco, G.; D’Antino, T.; Pellegrino, C.; Salomoni, V., Three-dimensional finite element modeling of inorganic-matrix composite materials using a mesoscale approach, Composites B, 143, 75-85 (2018)
[13] Palkovic, S. D.; Kupwade-Patil, K.; Yip, S.; Büyüköztürk, O., Random field finite element models with cohesive-frictional interactions of a hardened cement paste microstructure, J. Mech. Phys. Solids, 119, 349-368 (2018)
[14] Barazzetti, L.; Banfi, F.; Brumana, R.; Gusmeroli, G.; Oreni, D.; Previtali, M.; Roncoroni, F.; Schiantarelli, G., BIM from laser clouds and finite element analysis: combining structural analysis and geometric complexity, ISPRS - Int. Arch. Photogrammetry, Remote Sens. Spatial Inf. Sci., XL-5/W4, 345-350 (2015)
[15] Schneider, K.; Klusemann, B.; Bargmann, S., Automatic three-dimensional geometry and mesh generation of periodic representative volume elements for matrix-inclusion composites, Adv. Eng. Softw., 99, 177-188 (2016)
[16] Youssef, S.; Maire, E.; Gaertner, R., Finite element modelling of the actual structure of cellular materials determined by X-ray tomography, Acta Mater., 53, 3, 719-730 (2005)
[17] Huang, Y.; Yang, Z.; Ren, W.; Liu, G.; Zhang, C., 3D meso-scale fracture modelling and validation of concrete based on in-situ X-ray computed tomography images using damage plasticity model, Int. J. Solids Struct., 67-68, 340-352 (2015)
[18] Sencu, R.; Yang, Z.; Wang, Y.; Withers, P.; Rau, C.; Parson, A.; Soutis, C., Generation of micro-scale finite element models from synchrotron x-ray CT images for multidirectional carbon fibre reinforced composites, Composites A, 91, 85-95 (2016)
[19] Wu, L.; Xiao, X.; Wen, Y.; Zhang, J., Three-dimensional finite element study on stress generation in synchrotron X-ray tomography reconstructed nickel-manganese-cobalt based half cell, J. Power Sources, 336, 8-18 (2016)
[20] Bikas, H.; Stavropoulos, P.; Chryssolouris, G., Additive manufacturing methods and modelling approaches: a critical review, Int. J. Adv. Manuf. Technol., 83, 1, 389-405 (2016)
[21] Chen, Q.; Guillemot, G.; Gandin, C.-A.; Bellet, M., Three-dimensional finite element thermomechanical modeling of additive manufacturing by selective laser melting for ceramic materials, Addit. Manuf., 16, 124-137 (2017)
[22] Gouge, M.; Michaleris, P.; Denlinger, E.; Irwin, J., Chapter 2 - the finite element method for the thermo-mechanical modeling of additive manufacturing processes, (Gouge, M.; Michaleris, P., Thermo-Mechanical Modeling of Addit. Manuf. (2018), Butterworth-Heinemann), 19-38
[23] Saad, Y., ILUT: a dual threshold incomplete LU factorization, Numer. Linear Algebr., 1, 4, 387-402 (1994) · Zbl 0838.65026
[24] Lin, C.; Mor, J., Incomplete cholesky factorizations with limited memory, SIAM J. Sci. Comput., 21, 1, 24-45 (1999) · Zbl 0941.65033
[25] Benzi, M., Preconditioning techniques for large linear systems: A survey, J. Comput. Phys., 182, 2, 418-477 (2002), URL http://www.sciencedirect.com/science/article/pii/S0021999102971767 · Zbl 1015.65018
[26] Benzi, M.; Meyer, C. D.; Tůma, M., A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17, 5, 1135-1149 (1996), URL https://doi.org/10.1137/S106482759427142 · Zbl 0856.65019
[27] Tang, W., Toward an effective sparse approximate inverse preconditioner, SIAM J. Matrix Anal. Appl., 20, 4, 970-986 (1999), URL https://doi.org/10.1137/S0895479897320071 · Zbl 0937.65056
[28] Huckle, T., Factorized sparse approximate inverses for preconditioning, J. Supercomput., 25, 109-117 (2003), URL https://doi.org/10.1137/S0895479897320071 · Zbl 1027.65056
[29] Janna, C.; Ferronato, M.; Sartoretto, F.; Gambolati, G., FSAIPACK: A software package for high-performance factored sparse approximate inverse preconditioning, ACM Trans. Math. Software, 41, 2, 10:1-10:26 (2015), URL http://doi.acm.org/10.1145/2629475 · Zbl 1369.65052
[30] Dolean, V.; Jolivet, P.; Nataf, F., An Introduction to Domain Decomposition Methods: Algorithms, Theory and Parallel Implementation (2015), SIAM, URL https://hal.inria.fr/cel-01100932v3/document · Zbl 1364.65277
[31] Zampini, S., PCBDDC: A class of robust dual-primal methods in PETSc, SIAM J. Sci. Comput., 38, 5, S282-S306 (2016), URL https://doi.org/10.1137/15M1025785 · Zbl 1352.65632
[32] Badia, S.; Martín, A. F.; Principe, J., Multilevel balancing domain decomposition at extreme scales, SIAM J. Sci. Comput., 38, 1, C22-C52 (2016), URL https://doi.org/10.1137/15M1013511 · Zbl 1334.65217
[33] Li, R.; Saad, Y., Low-rank correction methods for algebraic domain decomposition preconditioners, SIAM J. Matrix Anal. Appl., 38, 3, 807-828 (2017), URL https://doi.org/10.1137/16M110486X · Zbl 1371.65029
[34] Stüben, K., Algebraic multigrid (AMG): Experiences and comparisons, Appl. Math. Comput., 13, 3-4, 419-451 (1983), URL http://dx.doi.org/10.1016/0096-3003(83)90023-1 · Zbl 0533.65064
[35] Brandt, A., Algebraic multigrid theory: The symmetric Case, Appl. Math. Comput., 19, 1-4, 23-56 (1986), URL http://dx.doi.org/10.1016/0096-3003(86)90095-0 · Zbl 0616.65037
[36] Vaněk, P., Acceleration of convergence of a two-level algorithm by smoothing transfer operator, Appl. Math. (Prague), 37, 265-274 (1992), URL https://eudml.org/doc/15715 · Zbl 0773.65021
[37] Vaněk, P.; Mandel, J.; Brezina, M., Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems, Computing, 56, 3, 179-196 (1996), URL https://doi.org/10.1007/BF02238511 · Zbl 0851.65087
[38] Brezina, M.; Cleary, A. J.; Falgout, R. D.; Henson, V. E.; Jones, J. E.; Manteuffel, T. A.; McCormick, S. F.; Ruge, J. W., Algebraic multigrid based on element interpolation (AMGe), SIAM J. Sci. Comput., 22, 5, 1570-1592 (2001), URL https://doi.org/10.1137/S1064827598344303 · Zbl 0991.65133
[39] Henson, V. E.; Vassilevski, P. S., Element-free AMGe: General algorithms for computing interpolation weights in AMG, SIAM J. Sci. Comput., 23, 2, 629-650 (2001), URL https://doi.org/10.1137/S1064827500372997 · Zbl 0992.65141
[40] Chartier, T.; Falgout, R. D.; Henson, V. E.; Jones, J.; Manteuffel, T.; McCormick, S.; Ruge, J.; Vassilevski, P. S., Spectral AMGe \(( \rho\) amge), SIAM J. Sci. Comput., 25, 1, 1-26 (2003), URL https://doi.org/10.1137/S106482750139892X · Zbl 1057.65096
[41] Brezina, M.; Falgout, R.; MacLachlan, S.; Manteuffel, T.; McCormick, S.; Ruge, J., Adaptive smoothed aggregation \(( \alpha\) sa) multigrid, SIAM Rev., 47, 2, 317-346 (2005), URL https://doi.org/10.1137/050626272 · Zbl 1075.65042
[42] Brandt, A.; Brannick, J.; Kahl, K.; Livshits, I., Bootstrap AMG, SIAM J. Sci. Comput., 33, 2, 612-632 (2011), URL https://doi.org/10.1137/090752973 · Zbl 1227.65120
[43] Brandt, A.; Brannick, J.; Kahl, K.; Livshits, I., Bootstrap algebraic multigrid: Status report, open problems, and outlook, Numer. Math.: Theory Methods Appl., 8, 1, 112135 (2015), URL https://doi.org/10.4208/nmtma.2015.w06si · Zbl 1340.65289
[44] D’ambra, P.; Filippone, S.; Vassilevski, P. S., Bootcmatch: A software package for bootstrap AMG based on graph weighted matching, ACM Trans. Math. Software, 44, 4, 39:1-39:25 (2018), URL http://doi.acm.org/10.1145/3190647 · Zbl 07003064
[45] Xu, J.; Zikatanov, L., Algebraic multigrid methods, Acta Numer., 26, 591721 (2017), URL http://dx.doi.org/10.1017/S0962492917000083
[46] Yoo, J., Multigrid for the Galerkin least squares method in linear elasticity, J. Math. Anal. Appl., 286, 1, 326-339 (2003), URL http://www.sciencedirect.com/science/article/pii/S0022247X0300516X · Zbl 1160.74420
[47] Griebel, M.; Oeltz, D.; Schweitzer, M., An algebraic multigrid method for linear elasticity, SIAM J. Sci. Comput., 25, 2, 385-407 (2003) · Zbl 1163.65336
[48] Baker, A. H.; Kolev, T. V.; Yang, U. M., Improving algebraic multigrid interpolation operators for linear elasticity problems, Numer. Linear Algebr., 17, 2-3, 495-517 (2010), URL https://doi.org/10.1002/nla.688 · Zbl 1240.74027
[49] Paludetto Magri, V.; Franceschini, A.; Janna, C., A novel algebraic multigrid approach based on adaptive smoothing and prolongation for ill-conditioned systems, SIAM J. Sci. Comput., 41, 1, A190-A219 (2019) · Zbl 1433.65069
[50] Falgout, R. D.; Yang, U. M., Hypre: A library of high performance preconditioners, (Proceedings of the International Conference on Computational Science-Part III. Proceedings of the International Conference on Computational Science-Part III, ICCS ’02 (2002), Springer-Verlag: Springer-Verlag Berlin, Heidelberg), 632-641, URL http://dl.acm.org/citation.cfm?id=645459.653635 · Zbl 1056.65046
[52] Adams, M.; Brezina, M.; Hu, J.; Tuminaro, R., Parallel multigrid smoothing: polynomial versus Gaussseidel, J. Comput. Phys., 188, 2, 593-610 (2003), URL http://dx.doi.org/10.1016/S0021-9991(03)00194-3 · Zbl 1022.65030
[53] Baker, A.; Falgout, R.; Kolev, T.; Yang, U., Multigrid smoothers for ultraparallel computing, SIAM J. Sci. Comput., 33, 5, 2864-2887 (2011) · Zbl 1237.65032
[54] Vaněk, P.; Brezina, M.; Mandel, J., Convergence of algebraic multigrid based on smoothed aggregation, Nummath., 88, 3, 559-579 (2001) · Zbl 0992.65139
[55] Adams, M., Evaluation of three unstructured multigrid methods on 3D finite element problems in solid mechanics, Internat. J. Numer. Methods Engrg., 55, 5, 519-534 (2002) · Zbl 1076.74547
[56] Farhat, C.; Roux, F.-X., A method of finite element tearing and interconnecting and its parallel solution algorithm, Internat. J. Numer. Methods Engrg., 32, 6, 1205-1227 (1991), URL https://onlinelibrary.wiley.com/doi/abs/10.1002/nme.1620320604 · Zbl 0758.65075
[57] Xu, J.; Zou, J., Some nonoverlapping domain decomposition methods, SIAM Rev., 40, 4, 857-914 (1998) · Zbl 0913.65115
[58] Farhat, C.; Pierson, K.; Lesoinne, M., The second generation FETI methods and their application to the parallel solution of large-scale linear and geometrically non-linear structural analysis problems, Comput. Methods Appl. Mech. Engrg., 184, 2, 333-374 (2000) · Zbl 0981.74064
[59] Frank, J.; Vuik, C., On the construction of deflation-based preconditioners, SIAM J. Sci. Comput., 23, 2, 442-462 (2001) · Zbl 0997.65072
[60] Jonsthovel, T.; van Gijzen, M. B.; Vuik, C.; Scarpas, A., On the use of rigid body modes in the deflated preconditioned conjugate gradient method, SIAM J. Sci. Comput., 35, 1, B207-B225 (2013), URL https://doi.org/10.1137/100803651 · Zbl 1372.74017
[61] Baggio, R.; Franceschini, A.; Spiezia, N.; Janna, C., Rigid body modes deflation of the preconditioned conjugate gradient in the solution of discretized structural problems, Comput. Struct., 185, 15-26 (2017)
[62] Longsine, D.; McCormick, S., Simultaneous rayleigh-quotient minimization methods for \(A x = \lambda B x\), Linear Algebra Appl., 34, 195-234 (1980), URL http://www.sciencedirect.com/science/article/pii/0024379580901664 · Zbl 0475.65021
[63] Bergamaschi, L.; Martnez, Á.; Pini, G., Parallel preconditioned conjugate gradient optimization of the Rayleigh quotient for the solution of sparse eigenproblems, Appl. Math. Comput., 175, 2, 1694-1715 (2006), URL http://www.sciencedirect.com/science/article/pii/S0096300305007320 · Zbl 1093.65036
[64] Bergamaschi, L.; Martínez, Á.; Pini, G., Parallel Rayleigh quotient optimization with FSAI-based preconditioning, J. Appl. Math., 2012 (2012) · Zbl 1244.65043
[65] Ferronato, M.; Janna, C.; Pini, G., Efficient parallel solution to large-size sparse eigenproblems with block FSAI preconditioning, Numer. Linear Algebr., 19, 5, 797-815 (2012) · Zbl 1274.65106
[66] Yang, U. M., Parallel algebraic multigrid methods — High performance preconditioners, (Numerical Solution of Partial Differential Equations on Parallel Computers (2006), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 209-236, URL https://doi.org/10.1007/3-540-31619-1_6 · Zbl 1097.65125
[67] Livne, O. E.; Brandt, A., Lean algebraic multigrid (LAMG): Fast graph Laplacian linear solver, SIAM J. Sci. Comput., 34, 4, B499-B522 (2012), URL https://doi.org/10.1137/110843563 · Zbl 1253.65045
[68] Golub, G.; Van Loan, C., (Matrix Computations. Matrix Computations, Johns Hopkins Studies in the Mathematical Sciences (2013), Johns Hopkins University Press), URL https://books.google.it/books?id=X5YfsuCWpxMC
[69] Falgout, R. D.; Schroder, J. B., Non-Galerkin coarse grids for algebraic multigrid, SIAM J. Sci. Comput., 36, 3, C309-C334 (2014) · Zbl 1297.65035
[70] Fontanella, C.; Matteoli, S.; Carniel, E.; Wilhjelm, J.; Virga, A.; Corvi, A.; Natali, A., Investigation on the load-displacement curves of a human healthy heel pad: In vivo compression data compared to numerical results, Med. Eng. Phys., 34, 9, 1253-1259 (2012), URL http://www.sciencedirect.com/science/article/pii/S1350453311003274
[72] Logg, A.; Wells, G. N., DOLFIN: Automated finite element computing, ACM Trans. Math. Software, 37, 2, 20:1-20:28 (2010), URL http://doi.acm.org/10.1145/1731022.1731030 · Zbl 1364.65254
[73] Mazzucco, G.; Pomaro, B.; Salomoni, V.; Majorana, C., Numerical modelling of ellipsoidal inclusions, Constr. Build. Mater., 167, 317-324 (2018), URL http://www.sciencedirect.com/science/article/pii/S0950061818301843
[74] Koric, S.; Lu, Q.; Guleryuz, E., Evaluation of massively parallel linear sparse solvers on unstructured finite element meshes, Comput. Struct., 141, 19-25 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.