Total and selective reuse of Krylov subspaces for the resolution of sequences of nonlinear structural problems. (English) Zbl 1352.65105
Summary: This paper deals with the definition and optimization of augmentation spaces for faster convergence of the conjugate gradient method in the resolution of sequences of linear systems. Using advanced convergence results from the literature, we present a procedure on the basis of a selection of relevant approximations of the eigenspaces for extracting, selecting and reusing information from the Krylov subspaces generated by previous solutions in order to accelerate the current iteration. Assessments of the method are proposed in the cases of both linear and nonlinear structural problems.
MSC:
| 65F10 | Iterative numerical methods for linear systems |
References:
| [1] | SaadY. Iterative Methods for Sparse Linear Systems, (2nd edn). SIAM: Philadelphia, USA, 2003. · Zbl 1031.65046 |
| [2] | KlawonnA, WidlundO. FETI and Neumann-Neumann iterative substructuring methods: connections and new results. Communications on Pure and Applied Mathematics2001; LIV:0057-0090. · Zbl 1023.65120 |
| [3] | GosseletP, ReyC. Non‐overlapping domain decomposition methods in structural mechanics. Archives of Computational Methods in Engineering2007; 13(4):515-572. · Zbl 1171.74041 |
| [4] | GosseletP, ReyC, RixenD. On the initial estimate of interface forces in FETI methods. Computer Methods in Applied Mechanics and Engineering2003; 192:2749-2764. · Zbl 1054.74728 |
| [5] | DostalZ. Conjugate gradient method with preconditioning by projector. International Journal of Computer Mathematics1988; 23:315-323. · Zbl 0668.65034 |
| [6] | SaadY. Analysis of augmented Krylov subspace methods. SIAM Journal on Matrix Analysis and Applications1997; 18(2):435-449. · Zbl 0871.65026 |
| [7] | ChapmanA, SaadY. Deflated and augmented Krylov subspace techniques. Numerical Linear Algebra with Applications1997; 4(1):43-66. · Zbl 0889.65028 |
| [8] | AliagaJI, BoleyDL, FreundRW, HernándezV. A Lanczos‐type method for multiple starting vectors. Mathematics of Computation2000; 69:1577-1601. · Zbl 0953.65018 |
| [9] | FarhatC, RouxFX. Implicit parallel processing in structural mechanics. Computational Mechanics Advances1994; 2(1):1-124. North‐Holland. · Zbl 0805.73062 |
| [10] | MandelJ, BrezinaM. Balancing domain decomposition for problems with large jumps in coefficients. Mathematics of Computation1996; 65(216):1387-1401. · Zbl 0853.65129 |
| [11] | FarhatC, MandelJ. The two‐level FETI method for static and dynamic plate problems ‐ part I: an optimal iterative solver for biharmonic systems. Computer Methods in Applied Mechanics and Engineering1998; 155:129-152. · Zbl 0964.74062 |
| [12] | FarhatC, ChenPS, RouxFX. The two‐level FETI method ‐ part II: extension to shell problems. parallel implementation and performance results. Computer Methods in Applied Mechanics and Engineering1998; 155:153-180. · Zbl 1040.74513 |
| [13] | Le TallecP, MandelJ, VidrascuM. A Neumann-Neumann domain decomposition algorithm for solving plate and shell problems. SIAM Journal on Numerical Analysis1998; 35(2):836-867. · Zbl 0917.73071 |
| [14] | GosseletP, RixenD, ReyC. A domain decomposition strategy to efficiently solve structures containing repeated patterns. International Journal for Numerical Methods in Engineering2009; 78(7):828-842. · Zbl 1183.74277 |
| [15] | MorganRB. A restarted GMRes method augmented with eigenvectors. SIAM Journal on Matrix Analysis and Applications1995; 16:1154-1171. · Zbl 0836.65050 |
| [16] | ErhelJ, BurrageK, PohlB. Restarted GMRes preconditioned by deflation. Journal of Computational and Applied Mathematics1996; 69:303-318. · Zbl 0854.65025 |
| [17] | BakerAH, DennisJM, JessupER. On improving linear solver performance: a block variant of GMRes. SIAM Journal on Scientific Computing2006; 27(5):1608-1626. · Zbl 1099.65029 |
| [18] | FarhatC, CrivelliL, RouxFX. Extending substructure based iterative solvers to multiple load and repeated analyses. Computer Methods in Applied Mechanics and Engineering1994; 117:195-209. · Zbl 0851.73059 |
| [19] | SaadY, YeungM, ErhelJ, Guyomarc’hF. A deflated version of the conjugate gradient algorithm. SIAM Journal on Scientific Computing2000; 21(5):1909-1926. · Zbl 0955.65021 |
| [20] | ErhelJ, Guyomarc’hF. An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems. SIAM Journal on Matrix Analysis and Applications2000; 21(4):1279-1299. · Zbl 0966.65031 |
| [21] | TangJ, NabbenR, VuikC, ErlanggaY. Theoretical and numerical comparison of various projection methods derived from deflation, domain decomposition and multigrid methods. Reports of the Department of Applied Mathematical Analysis 07‐04, Delft University of Technology, 2007. |
| [22] | SimonciniV, SzyldD. Recent computational developments in Krylov subspace methods for linear systems. Numerical Linear Algebra with Applications2007; 14(1):1-59. · Zbl 1199.65112 |
| [23] | CarprauxJ, GodunovS, KuznetsovS. Stability of the Krylov bases and subspaces. Technical Report 2296, INRIA, 1994. |
| [24] | ReyC, RislerF. A Rayleigh-Ritz preconditioner for the iterative solution to large scale nonlinear problems. Numerical Algorithms1998; 17:279-311. · Zbl 0908.65034 |
| [25] | GosseletP, ReyC. On a selective reuse of Krylov subspaces in Newton-Krylov approaches for nonlinear elasticity. Proceedings of the 14^th Conference on Domain Decomposition Methods, Cocoyoc, Mexico, 2002; 419-426. |
| [26] | ParksM, De SturlerE, MackeyG, JohnsonD, MaitiS. Recycling Krylov subspaces for sequences of linear systems. SIAM Journal on Scientific Computing2006; 28(5):1651-1674. · Zbl 1123.65022 |
| [27] | WangS, De SturlerE, PaulinoG. Large‐scale topology optimization using preconditioner Krylov subspace methods with recycling. International Journal for Numerical Methods in Engineering2007; 69(12):2441-2468. · Zbl 1194.74265 |
| [28] | ReyC. An acceleration technique for the solution of non‐linear elasticity problems by domain decomposition. Comptes Rendus de l’Académie des Sciences1996; 322(8):601-606. · Zbl 0923.73077 |
| [29] | RislerF, ReyC. Iterative accelerating algorithms with Krylov subspaces for the solution to large‐scale nonlinear problems. Numerical Algorithms2000; 23:1-30. · Zbl 0951.65047 |
| [30] | van der SluisA, van der VorstH. The rate of convergence of conjugate gradients. Numerische Mathematik1986; 48:543-560. · Zbl 0596.65015 |
| [31] | GosseletP, ReyC, DassetP, LénéF. A domain decomposition method for quasi incompressible formulations with discontinuous pressure field. Revue Européenne des Élements Finis2002; 11:363-377. · Zbl 1120.74859 |
| [32] | LénéF, ReyC. Some strategies to compute elastomeric lamified composite structures. Composite Structures2001; 54:231-241. |
| [33] | MeyerM, MatthiesHG. Efficient model reduction in non‐linear dynamics using the Karhunen-Loeve expansion and dual‐weighted‐residual methods. Computational Mechanics2003; 31(1‐2):179-191. · Zbl 1038.74559 |
| [34] | RyckelynckD, ChinestaF, CuetoE, AmmarA. On the a priori model reduction: Overview and recent developments. Archives of Computational Methods in Engineering2006; 13:91-128. · Zbl 1142.76462 |
| [35] | NouyA. A generalized spectral decomposition technique to solve a class of linear stochastic partial differential equations. Computer Methods in Applied Mechanics and Engineering2007; 196(45‐48):4521-4537. · Zbl 1173.80311 |
| [36] | FreundR. Krylov‐subspace methods for reduced‐order modeling in circuit simulation. Journal of Computational and Applied Mathematics2000; 123(1‐2):395-421. · Zbl 0964.65082 |
| [37] | FreundR. Model reduction methods based on Krylov subspaces. Acta Numerica2003; 12:267-319. · Zbl 1046.65021 |
| [38] | HeresP, DeschrijverD, SchildersW, DhaeneT. Combining Krylov subspace methods and identification‐based methods for model order reduction. International Journal of Numerical Modelling : Electronic Networks, Devices and Fields2007; 20(6):271-282. · Zbl 1128.93314 |
| [39] | LingenFJ. Efficient Gram-Schmidt orthonormalisation on parallel computers. Communication in Numerical Methods in Engineering2000; 16:57-66. · Zbl 0958.65048 |
| [40] | FarhatC, PiersonK, LesoinneM. The second generation FETI methods and their application to the parallel solution of large‐scale linear and geometrically non‐linear structural analysis problems. Computer Methods in Applied Mechanics and Engineering2000; 184(2‐4):333-374. · Zbl 0981.74064 |
| [41] | MandelJ. Balancing domain decomposition. Communication in Numerical Methods in Engineering1993; 9:233-241. · Zbl 0796.65126 |
| [42] | KilmerME, de SturlerE. Recycling subspace information for diffuse optical tomography. SIAM Journal on Scientific Computing2006; 27(6):2140-2166. · Zbl 1103.65036 |
| [43] | NotayY. On the convergence rate of the conjugate gradients in presence of rounding errors. Numerische Mathematik1993; 65:301-317. · Zbl 0791.65016 |
| [44] | AxelssonO, LindskogG. On the rate of convergence of the preconditioned conjugate gradient method. Numerische Mathematik1986; 48:499-523. · Zbl 0564.65017 |
| [45] | SaadY. Numerical Methods for Large Eigenvalue Problems, revised edn., Classics in Applied Mathematics, Vol. 66. SIAM: Philadelphia, USA, 2011. · Zbl 1242.65068 |
| [46] | JiaZ, StewartGW. On the convergence of the Ritz values, Ritz vectors and refined Ritz vectors, Technical Report 99‐08, Institute of Advanced Computer Studies, Technical Report 3896, Department of Computer Science, University of Maryland at College Park, 1999. |
| [47] | JiaZ. The convergence of harmonic Ritz values, harmonic Ritz vectors and refined harmonic Ritz vectors. Mathematics of Computation2004; 74(251):1441-1456. · Zbl 1072.65051 |
| [48] | MolinariN, BonaldiC, DaurèsJ. Multiple temporal cluster detection. Biometrics2001; 57:577-583. · Zbl 1209.62315 |
| [49] | Northwest Numerics. Z‐set user manual, 2001. |
| [50] | KarypisG, KumarV. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing1998; 20(1):359-392. · Zbl 0915.68129 |
| [51] | PaigeC. Approximate solutions and eigenvalue bounds from Krylov subspaces. Numerical Linear Algebra with Applications1995; 2(2):115-133. · Zbl 0831.65036 |
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.
