×

Krylov-subspace recycling via the POD-augmented conjugate-gradient method. (English) Zbl 1348.15005

Summary: This work presents a new Krylov-subspace-recycling method for efficiently solving sequences of linear systems of equations characterized by varying right-hand sides and symmetric-positive-definite matrices. As opposed to typical truncation strategies used in recycling such as deflation, we propose a truncation method inspired by goal-oriented proper orthogonal decomposition (POD) from model reduction. This idea is based on the observation that model reduction aims to compute a low-dimensional subspace that contains an accurate solution; as such, we expect the proposed method to generate a low-dimensional subspace that is well suited for computing solutions that can satisfy inexact tolerances. In particular, we propose specific goal-oriented POD “ingredients” that align the optimality properties of POD with the objective of Krylov-subspace recycling. To compute solutions in the resulting “augmented” POD subspace, we propose a hybrid direct/iterative three-stage method that leverages (1) the optimal ordering of POD basis vectors, and (2) well-conditioned reduced matrices. Numerical experiments performed on solid-mechanics problems highlight the benefits of the proposed method over existing approaches for Krylov-subspace recycling.

MSC:

15A12 Conditioning of matrices
15A18 Eigenvalues, singular values, and eigenvectors
65F10 Iterative numerical methods for linear systems
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F50 Computational methods for sparse matrices

Software:

Adagio; SIERRA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Bishop, J. Emery, R. Field, C. Weinberger, and D. Littlewood, {\it Direct numerical simulations in solid mechanics for understanding the macroscale effects of microscale material variability}, Comput. Methods Appl. Mech. Engrg., 287 (2015), pp. 262-289. · Zbl 1423.74692
[2] K. Carlberg and C. Farhat, {\it A compact proper orthogonal decomposition basis for optimization-oriented reduced-order models}, in 12th AIAA/ISSMO Multidisciplinary Analysis and Optimization Conference, Victoria, Canada, 2008, AIAA paper 2008-5964. · Zbl 1235.74352
[3] K. Carlberg and C. Farhat, {\it An adaptive POD-Krylov reduced-order model for structural optimization}, in 8th World Congress on Structural and Multidisciplinary Optimization, Lisbon, Portugal, 2009.
[4] K. Carlberg and C. Farhat, {\it A low-cost, goal-oriented “compact proper orthogonal decomposition” basis for model reduction of static systems}, Internat. J. Numer. Methods Engrg., 86 (2011), pp. 381-402. · Zbl 1235.74352
[5] K. Carlberg, C. Farhat, J. Cortial, and D. Amsallem, {\it The GNAT method for nonlinear model reduction: Effective implementation and application to computational fluid dynamics and turbulent flows}, J. Comput. Phys., 242 (2013), pp. 623-647. · Zbl 1299.76180
[6] K. Carlberg, R. Tuminaro, and P. Boggs, {\it Preserving Lagrangian structure in nonlinear model reduction with application to structural dynamics}, SIAM J. Sci. Comput., 37 (2015), pp. B153-B184, http://dx.doi.org/10.1137/140959602 doi:10.1137/140959602. · Zbl 1320.65193
[7] A. Chapman and Y. Saad, {\it Deflated and augmented Krylov subspace techniques}, Numer. Linear Algebra Appl., 4 (1997), pp. 43-66. · Zbl 0889.65028
[8] C. Davis and W. Kahan, {\it Some new bounds on perturbation of subspaces}, Bull. Amer. Math. Soc., 75 (1969), pp. 863-868. · Zbl 0175.43204
[9] C. Davis and W. Kahan, {\it The rotation of eigenvectors by a perturbation. III}, SIAM J. Numer. Anal., 7 (1970), pp. 1-46, http://dx.doi.org/10.1137/0707001 doi:10.1137/0707001. · Zbl 0198.47201
[10] E. De Sturler, {\it Truncation strategies for optimal Krylov subspace methods}, SIAM J. Numer. Anal., 36 (1999), pp. 864-889, http://dx.doi.org/10.1137/S0036142997315950 doi:10.1137/S0036142997315950. · Zbl 0960.65031
[11] H. Edwards, A. Williams, G. Sjaardema, D. Baur, and W. Cochran, {\it SIERRA toolkit computational mesh conceptual model}, Sandia National Laboratories SAND Series, SAND, 1192 (2010), p. 2010.
[12] S. Eisenstat and I. Ipsen, {\it Relative perturbation techniques for singular value problems}, SIAM J. Numer. Anal., 32 (1995), pp. 1972-1988, http://dx.doi.org/10.1137/0732088 doi:10.1137/0732088. · Zbl 0837.65039
[13] S. Eisenstat and H. Walker, {\it Choosing the forcing terms in an inexact Newton method}, SIAM J. Sci. Comput., 17 (1996), pp. 16-32, http://dx.doi.org/10.1137/0917003 doi:10.1137/0917003. · Zbl 0845.65021
[14] J. Erhel and F. Guyomarc’h, {\it An augmented conjugate gradient method for solving consecutive symmetric positive definite linear systems}, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1279-1299, http://dx.doi.org/10.1137/S0895479897330194 doi:10.1137/S0895479897330194. · Zbl 0966.65031
[15] C. Farhat, {\it Optimizing substructuring methods for repeated right hand sides, scalable parallel coarse solvers, and global/local analysis}, in Domain-Based Parallelism and Problem Decomposition Methods in Computational Science and Engineering, D. Keyes, Y. Saad, and D. G. Truhlar, eds., SIAM, Philadelphia, 1995, pp. 141-160, http://dx.doi.org/10.1137/1.9781611971507.ch9 doi:10.1137/1.9781611971507.ch9. · Zbl 0836.73067
[16] C. Farhat, L. Crivelli, and F. X. Roux, {\it Extending substructure based iterative solvers to multiple load and repeated analyses}, Comput. Methods Appl. Mech. Engrg., 117 (1994), pp. 195-209. · Zbl 0851.73059
[17] C. Farhat, K. Pierson, and M. Lesoinne, {\it 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 (2000), pp. 333-374. · Zbl 0981.74064
[18] P. Holmes, J. Lumley, and G. Berkooz, {\it Turbulence, Coherent Structures, Dynamical Systems and Symmetry}, Cambridge University Press, Cambridge, UK, 1996. · Zbl 0890.76001
[19] I. Ipsen, {\it Absolute and relative perturbation bounds for invariant subspaces of matrices}, Linear Algebra Appl., 309 (2000), pp. 45-56. · Zbl 0949.15025
[20] I. Ipsen, {\it An overview of relative sin \(Θ\) theorems for invariant subspaces of complex matrices}, J. Comput. Appl. Math., 123 (2000), pp. 131-153. · Zbl 0964.65039
[21] I. Ipsen, {\it A note on unifying absolute and relative perturbation bounds}, Linear Algebra Appl., 358 (2003), pp. 239-253. · Zbl 1028.15016
[22] S. Lall, P. Krysl, and J. Marsden, {\it Structure-preserving model reduction for mechanical systems}, Phys. D, 184 (2003), pp. 304-318. · Zbl 1041.70011
[23] J. A. Mitchell, A. S. Gullerud, W. M. Scherzinger, R. Koteras, and V. L. Porter, {\it Adagio: Non-linear Quasi-static Structural Response Using the SIERRA Framework}, https://cfwebprod.sandia.gov/cfdocs/CompResearch/docs/SAND2001-1603A.pdf, 2001.
[24] R. Morgan, {\it Computing interior eigenvalues of large matrices}, Linear Algebra Appl., 154 (1991), pp. 289-309. · Zbl 0734.65029
[25] R. Morgan, {\it GMRES with deflated restarting}, SIAM J. Sci. Comput., 24 (2002), pp. 20-37, http://dx.doi.org/10.1137/S1064827599364659 doi:10.1137/S1064827599364659. · Zbl 1018.65042
[26] B. Noack, P. Papas, and P. Monkewitz, {\it The need for a pressure-term representation in empirical Galerkin models of incompressible shear flows}, J. Fluid Mech., 523 (2005), pp. 339-365. · Zbl 1065.76102
[27] D. P. O’Leary, {\it The block conjugate gradient algorithm and related methods}, Linear Algebra Appl., 29 (1980), pp. 293-322. · Zbl 0426.65011
[28] M. Parks, E. De Sturler, G. Mackey, D. Johnson, and S. Maiti, {\it Recycling Krylov subspaces for sequences of linear systems}, SIAM J. Sci. Comput., 28 (2006), pp. 1651-1674, http://dx.doi.org/10.1137/040607277 doi:10.1137/040607277. · Zbl 1123.65022
[29] M. Rathinam and L. R. Petzold, {\it A new look at proper orthogonal decomposition}, SIAM J. Numer. Anal., 41 (2003), pp. 1893-1925, http://dx.doi.org/10.1137/S0036142901389049 doi:10.1137/S0036142901389049. · Zbl 1053.65106
[30] C. Rey, {\it Developpement d’algorithmes paralleles de resolution en calcul non-lineaire de structures heterogenes: Application au cas d’une butee acier-elastomere}, Ph.D. thesis, Laboratoire de Modelisation et Mecanique des Structures, University of Paris VI, Paris, France, 1994.
[31] C. Rey and F. Risler, {\it A Rayleigh-Ritz preconditioner for the iterative solution to large scale nonlinear problems}, Numer. Algorithms, 17 (1998), pp. 279-311. · Zbl 0908.65034
[32] F. Risler and C. Rey, {\it Iterative accelerating algorithms with Krylov subspaces for the solution to large-scale nonlinear problems}, Numer. Algorithms, 23 (2000), pp. 1-30. · Zbl 0951.65047
[33] F. X. Roux, {\it Parallel implementation of a domain decomposition method for non-linear elasticity}, in Domain-Based Parallelism and Problem Decomposition Methods in Computational Science and Engineering, D. Keyes, Y. Saad, and D. G. Truhlar, eds., SIAM, Philadelphia, 1995, pp. 161-175, http://dx.doi.org/10.1137/1.9781611971507.ch10 doi:10.1137/1.9781611971507.ch10. · Zbl 0836.73074
[34] Y. Saad, {\it On the Lanczos method for solving symmetric linear systems with several right-hand sides}, Math. Comp., 48 (1987), pp. 651-662. · Zbl 0615.65038
[35] Y. Saad, {\it Analysis of augmented Krylov subspace methods}, SIAM J. Matrix Anal. Appl., 18 (1997), pp. 435-449, http://dx.doi.org/10.1137/S0895479895294289 doi:10.1137/S0895479895294289. · Zbl 0871.65026
[36] Y. Saad, {\it Iterative Methods for Sparse Linear Systems}, 2nd ed., SIAM, Philadelphia, 2003. · Zbl 1031.65046
[37] Y. Saad, M. Yeung, J. Erhel, and F. Guyomarc’h, {\it A deflated version of the conjugate gradient algorithm}, SIAM J. Sci. Comput., 21 (2000), pp. 1909-1926, http://dx.doi.org/10.1137/S1064829598339761 doi:10.1137/S1064829598339761. · Zbl 0955.65021
[38] O. San and T. Iliescu, {\it Proper Orthogonal Decomposition Closure Models for Fluid Flows: Burgers Equation}, preprint, http://arxiv.org/abs/1308.3276 arXiv:1308.3276 [physics.flu-dyn], 2013. · Zbl 1463.65245
[39] S. Sirisup and G. Karniadakis, {\it A spectral viscosity method for correcting the long-term behavior of pod models}, J. Comput. Phys., 194 (2004), pp. 92-116. · Zbl 1136.76412
[40] L. Sirovich, {\it Turbulence and the dynamics of coherent structures. I: Coherent structures}, Quart. Appl. Math., 45 (1987), pp. 561-571. · Zbl 0676.76047
[41] L. Sirovich, {\it Turbulence and the dynamics of coherent structures. III: Dynamics and scaling}, Quart. Appl. Math., 45 (1987), pp. 583-590. · Zbl 0676.76047
[42] Z. Wang, I. Akhtar, J. Borggaard, and T. Iliescu, {\it Proper orthogonal decomposition closure models for turbulent flows: A numerical comparison}, Comput. Methods Appl. Mech. Engrg., 237 (2012), pp. 10-26. · Zbl 1253.76050
[43] D. Watkins, {\it The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods}, SIAM, Philadelphia, 2007. · Zbl 1142.65038
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.