×

A new preconditioner update strategy for the solution of sequences of linear systems in structural mechanics: application to saddle point problems in elasticity. (English) Zbl 1398.65047

Summary: Many applications in structural mechanics require the numerical solution of sequences of linear systems typically issued from a finite element discretization of the governing equations on fine meshes. The method of Lagrange multipliers is often used to take into account mechanical constraints. The resulting matrices then exhibit a saddle point structure and the iterative solution of such preconditioned linear systems is considered as challenging. A popular strategy is then to combine preconditioning and deflation to yield an efficient method. We propose an alternative that is applicable to the general case and not only to matrices with a saddle point structure. In this approach, we consider to update an existing algebraic or application-based preconditioner, using specific available information exploiting the knowledge of an approximate invariant subspace or of matrix-vector products. The resulting preconditioner has the form of a limited memory quasi-Newton matrix and requires a small number of linearly independent vectors. Numerical experiments performed on three large-scale applications in elasticity highlight the relevance of the new approach. We show that the proposed method outperforms the deflation method when considering sequences of linear systems with varying matrices.

MSC:

65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
65F50 Computational methods for sparse matrices
65F08 Preconditioners for iterative methods
65-02 Research exposition (monographs, survey articles) pertaining to numerical analysis

Software:

KryPy; MUMPS; JDQZ; JDQR; tn
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Amestoy PR, Duff IS, L’Excellent J-Y (2000) Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput Methods Appl Mech Eng 184:501-520 · Zbl 0956.65017 · doi:10.1016/S0045-7825(99)00242-X
[2] Amestoy PR, Duff IS, L’Excellent J-Y, Koster J (2001) A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J Matrix Anal Appl 23(1):15-41 · Zbl 0992.65018 · doi:10.1137/S0895479899358194
[3] Amestoy PR, Guermouche A, L’Excellent JY, Pralet S (2006) Hybrid scheduling for the parallel solution of linear systems. Parallel Comput 32(2):136-156 · doi:10.1016/j.parco.2005.07.004
[4] Baglama J, Calvetti D, Golub G, Reichel L (1998) Adaptively preconditioned GMRES algorithms. SIAM J Sci Comput 20:243-269 · Zbl 0954.65026 · doi:10.1137/S1064827596305258
[5] Bai Z, Demmel J, Dongarra J, Ruhe A, van der Vorst HA (2000) Templates for the solution of algebraic eigenvalue problems: a practical guide, vol 11. SIAM, Philadelphia · Zbl 0965.65058 · doi:10.1137/1.9780898719581
[6] Bargellini R (2011) Elasto-visco-plastic modeling with isotropic hardening in large deformations. Technical Report, EDF R&D, AMA R5.03.21 · Zbl 1205.65143
[7] Bellavia S, Bertaccini D, Morini B (2011) Nonsymmetric preconditioner updates in Newton-Krylov methods for nonlinear systems. SIAM J Sci Comput 33(5):2595-2619 · Zbl 1232.65049 · doi:10.1137/100789786
[8] Bellavia S, Morini B, Porcelli M (2014) New updates of incomplete LU factorizations and applications to large nonlinear systems. Optim Methods Softw 29:321-340 · Zbl 1285.90064 · doi:10.1080/10556788.2012.762517
[9] Benzi M (2002) Preconditioning techniques for large linear systems: a survey. J Comput Phys 182(2):418-477 · Zbl 1015.65018 · doi:10.1006/jcph.2002.7176
[10] Benzi M, Golub GH, Liesen J (2005) Numerical solution of saddle point problems. Acta Numer 14(1):1-137 · Zbl 1115.65034 · doi:10.1017/S0962492904000212
[11] Bonet J, Wood RD (1997) Nonlinear continuum mechanics for finite element analysis. Cambridge University Press, Cambridge · Zbl 0891.73001
[12] Broyden CG (1969) A new method of solving nonlinear simultaneous equations. Comput J 12(1):94-99 · Zbl 0164.45101 · doi:10.1093/comjnl/12.1.94
[13] Carpentieri B, Duff IS, Giraud L (2003) A class of spectral two-level preconditioners. SIAM J Sci Comput 25(2):749-765 · Zbl 1048.65043 · doi:10.1137/S1064827502408591
[14] Chapman A, Saad Y (1997) Deflated and augmented Krylov subspace techniques. Numer Linear Algebra Appl 4(1):43-66 · Zbl 0889.65028 · doi:10.1002/(SICI)1099-1506(199701/02)4:1<43::AID-NLA99>3.0.CO;2-Z
[15] Dostál Z (1988) Conjugate gradient method with preconditioning by projector. Int J Comput Math 23(3):315-323 · Zbl 0668.65034 · doi:10.1080/00207168808803625
[16] Duintjer Tebbens J, Tuma M (2007) Efficient preconditioning of sequences of nonsymmetric linear systems. SIAM J Sci Comput 29(5):1918-1941 · Zbl 1155.65036 · doi:10.1137/06066151X
[17] Duintjer Tebbens J, Tuma M (2010) Preconditioner updates for solving sequences of linear systems in matrix-free environment. Numer Linear Algebra Appl 17:997-1019 · Zbl 1240.65092 · doi:10.1002/nla.695
[18] Eirola T, Nevanlinna O (1989) Accelerating with rank-one updates. Linear Algebra Appl 121:511-520 · Zbl 0683.65018 · doi:10.1016/0024-3795(89)90719-2
[19] Elman HC, Silvester DJ, Wathen AJ (2014) Finite elements and fast iterative solvers: with applications in incompressible fluid dynamics, 2nd edn. Oxford University Press, Oxford · Zbl 1304.76002 · doi:10.1093/acprof:oso/9780199678792.001.0001
[20] Erlangga Y, Nabben R (2008) Deflation and balancing preconditioners for Krylov subspace methods applied to nonsymmetric matrices. SIAM J Matrix Anal Appl 30(2):684-699 · Zbl 1163.65014 · doi:10.1137/060678257
[21] Gaul A (2014) Recycling Krylov subspace methods for sequences of linear systems : analysis and applications. Ph.D. thesis, TU Berlin, Germany · Zbl 1103.65036
[22] Gaul A, Gutknecht MH, Liesen J, Nabben R (2013) A framework for deflated and augmented Krylov subspace methods. SIAM J Matrix Anal Appl 34(2):495-518 · Zbl 1273.65049 · doi:10.1137/110820713
[23] Gaul A, Schlömer N (2015) Preconditioned recycling Krylov subspace methods for self-adjoint problems. Electron Trans Numer Anal 44:522-547 · Zbl 1327.65059
[24] Giraud L, Gratton S, Martin E (2007) Incremental spectral preconditioners for sequences of linear systems. Appl Numer Math 57:1164-1180 · Zbl 1123.65031 · doi:10.1016/j.apnum.2007.01.005
[25] Golub GH, Greif C (2003) On solving block-structured indefinite linear systems. SIAM J Sci Comput 24(6):2076-2092 · Zbl 1036.65033 · doi:10.1137/S1064827500375096
[26] Gosselet P, Rey C, Pebrel J (2013) Total and selective reuse of Krylov subspaces for the resolution of sequences of nonlinear structural problems. Int J Numer Methods Eng 94(1):60-83 · Zbl 1352.65105 · doi:10.1002/nme.4441
[27] Gratton S, Mercier S, Tardieu N, Vasseur X (2016) Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics. Numer Linear Algebra Appl 23(5):865-887 · Zbl 1413.65041 · doi:10.1002/nla.2058
[28] Gratton S, Sartenaer A, Tshimanga J (2011) On a class of limited memory preconditioners for large scale linear systems with multiple right-hand sides. SIAM J Opt 21(3):912-935 · Zbl 1273.65044 · doi:10.1137/08074008
[29] Gutknecht MH (2012) Spectral deflation in Krylov solvers: a theory of coordinate space based methods. Electron Trans Numer Anal 39:156-185 · Zbl 1285.65021
[30] Gutknecht MH (2014) Deflated and augmented Krylov subspace methods: a framework for deflated BiCG and related solvers. SIAM J Matrix Anal Appl 35:1444-1466 · Zbl 1316.65041 · doi:10.1137/130923087
[31] Ipsen ICF (2001) A note on preconditioning nonsymmetric matrices. SIAM J Sci Comput 23(3):10501-1051 · Zbl 0998.65049 · doi:10.1137/S1064827500377435
[32] Jönsthövel TB, Van Gijzen MB, MacLachlan S, Vuik C, Scarpas A (2012) Comparison of the deflated conjugate gradient method and algebraic multigrid for composite materials. Comput Mech 50:321-333 · Zbl 1398.74345 · doi:10.1007/s00466-011-0661-y
[33] Jönsthövel TB, Van Gijzen MB, Vuik C, Scarpas A (2013) On the use of rigid body modes in the deflated preconditioned conjugate gradient method. SIAM J Sci Comput 35:B207-B225 · Zbl 1372.74017 · doi:10.1137/100803651
[34] Kelley CT (2003) Solving nonlinear equations with Newton’s method, vol 1. SIAM, Philadelphia · Zbl 1031.65069 · doi:10.1137/1.9780898718898
[35] Kharchenko S, Yeremin A (1995) Eigenvalue translation based preconditioners for the GMRES(k) method. Numer Linear Algebra Appl 2:51-77 · Zbl 0829.65036 · doi:10.1002/nla.1680020105
[36] Kilmer M, de Sturler E (2006) Recycling subspace information for diffuse optical tomography. SIAM J Sci Comput 27(6):2140-2166 · Zbl 1103.65036 · doi:10.1137/040610271
[37] Liesen J, Strakoš Z (2013) Krylov subspace methods principles and analysis. Oxford University Press, Oxford · Zbl 1263.65034
[38] Mercier S (2015) Fast nonlinear solvers in solid mechanics. Ph.D. thesis, University of Toulouse, Toulouse, France, http://thesesups.ups-tlse.fr/3000/1/2015TOU30305.pdf · Zbl 1036.65033
[39] Meyer CD (2000) Matrix analysis and applied linear algebra. SIAM, Philadelphia · doi:10.1137/1.9780898719512
[40] Michel-Ponnelle S (2013) Modeling of the pretension cables. Technical report, EDF R&D, AMA R7.01.02 · Zbl 0954.65026
[41] Morales JL, Nocedal J (2000) Automatic preconditioning by limited memory quasi-Newton updating. SIAM J Opt 10(4):1079-1096 · Zbl 1020.65019 · doi:10.1137/S1052623497327854
[42] Nash S (1984) Newton-type minimization via the Lanczos method. SIAM J Numer Anal 21:770-778 · Zbl 0558.65041 · doi:10.1137/0721052
[43] Nečas J, Hlavácek I (1980) Mathematical theory of elastic and elastoplastic bodies. Elsevier, Amsterdam · Zbl 0448.73009
[44] Nicolaides RA (1987) Deflation of conjugate gradients with applications to boundary value problems. SIAM J Numer Anal 24(2):355-365 · Zbl 0624.65028 · doi:10.1137/0724027
[45] Nocedal J, Wright SJ (1999) Numerical optimization. Springer series in operations research and financial engineering. Springer, Berlin
[46] Notay Y (2014) A new analysis of block preconditioners for saddle point problems. SIAM J Matrix Anal Appl 35(1):143-173 · Zbl 1297.65034 · doi:10.1137/130911962
[47] O’Leary DP, Yeremin A (1994) The linear algebra of block quasi-Newton algorithms. Linear Algebra Appl 212(213):153-168 · Zbl 0861.65044 · doi:10.1016/0024-3795(94)90401-4
[48] Olshanskii MA, Tyrtyshnikov EE (2014) Iterative methods for linear systems: theory and applications. SIAM, Philadelphia · Zbl 1320.65050 · doi:10.1137/1.9781611973464
[49] Paige CC, Parlett BN, van der Vorst HA (1995) Approximate solutions and eigenvalue bounds from Krylov subspaces. Numer Linear Algebra Appl 2:115-134 · Zbl 0831.65036 · doi:10.1002/nla.1680020205
[50] Parks M, de Sturler E, Mackey G, Johnson D, Maiti S (2006) Recycling Krylov subspaces for sequences of linear systems. SIAM J Sci Comput 28(5):1651-1674 · Zbl 1123.65022 · doi:10.1137/040607277
[51] Pestana J, Wathen AJ (2015) Natural preconditioning and iterative methods for saddle point systems. SIAM Rev 57(1):71-91 · Zbl 1338.65078 · doi:10.1137/130934921
[52] Proix JM (2013) Elasto-visco-plastic modeling of Chaboche-type. Technical Report, EDF R&D, AMA R5.03.04
[53] Rey C, Risler F (1998) A Rayleigh-Ritz preconditioner for the iterative solution to large scale nonlinear problems. Numer Algorithms 17:279-311 · Zbl 0908.65034 · doi:10.1023/A:1016680306741
[54] Risler F, Rey C (1998) On the reuse of Ritz vectors for the solution to nonlinear elasticity problems by domain decomposition methods. Contemp Math 218:334-340 · Zbl 0914.73078 · doi:10.1090/conm/218/03026
[55] Saad Y (2003) Iterative methods for sparse linear systems. SIAM, Philadelphia · Zbl 1031.65046 · doi:10.1137/1.9780898718003
[56] Saad Y, Schultz MH (1986) GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J Sci Stat Comput 7(3):856-869 · Zbl 0599.65018 · doi:10.1137/0907058
[57] Saad Y, Yeung M, Erhel J, Guyomarc’h F (2000) A deflated version of the conjugate gradient algorithm. SIAM J Sci Comput 21(5):1909-1926 · Zbl 0955.65021 · doi:10.1137/S1064829598339761
[58] Schnabel RB (1983) Quasi-Newton methods using multiple secant equations. Technical report, Technical report CU-CS-247-83, Department of Computer Sciences, University of Colorado, Boulder, CO
[59] Shewchuk J (2002) What is a good linear finite element ? Interpolation, conditioning, anisotropy, and quality measures, University of California at Berkeley, unpublished preprint · Zbl 1285.90064
[60] Simoncini V, Szyld DB (2007) Recent computational developments in Krylov subspace methods for linear systems. Numer Linear Algebra Appl 14(1):1-59 · Zbl 1199.65112 · doi:10.1002/nla.499
[61] Soodhalter KM, Szyld DB, Xue F (2014) Krylov subspace recycling for sequences of shifted linear systems. Appl Numer Math 81:105-118 · Zbl 1291.65108 · doi:10.1016/j.apnum.2014.02.006
[62] Tang JM, MacLachlan SP, Nabben R, Vuik C (2010) A comparison of two-level preconditioners based on multigrid and deflation. SIAM J Matrix Anal Appl 31(4):1715-1739 · Zbl 1205.65143 · doi:10.1137/08072084X
[63] Tardieu N, Cheignon E (2012) A Newton-Krylov method for solid mechanics. Eur J Comput Mech 21(3-6):374-384 · Zbl 1348.74342
[64] Toselli A, Widlund O (2005) Domain decomposition methods: algorithms and theory. Springer, Berlin · Zbl 1069.65138 · doi:10.1007/b137868
[65] van der Vorst HA (2003) Iterative Krylov methods for large linear systems. Cambridge University Press, Cambridge · Zbl 1023.65027 · doi:10.1017/CBO9780511615115
[66] Vassilevski PS (2008) Multilevel block factorization preconditioners: matrix-based analysis and algorithms for solving finite element equations. Springer, New-York · Zbl 1170.65001
[67] Wang S, de Sturler E, Paulino G (2007) Large-scale topology optimization using preconditioned Krylov subspace methods with recycling. Int J Numer Methods Eng 69(12):2441-2468 · Zbl 1194.74265 · doi:10.1002/nme.1798
[68] Wathen AJ (2015) Preconditioning. Acta Numer 24:329-376 · Zbl 1316.65039 · doi:10.1017/S0962492915000021
[69] Yang UM (1995) A family of preconditioned iterative solvers for sparse linear systems. Ph.D. thesis, University of Illinois at Urbana-Champaign · Zbl 0855.65024
[70] Yang UM, Gallivan KA (1995) A new family of preconditioned iterative solvers for nonsymmetric linear systems. Appl Num Math 19(3):287-317 · Zbl 0855.65024 · doi:10.1016/0168-9274(95)00088-7
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.