{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T04:19:05Z","timestamp":1772252345622,"version":"3.50.1"},"reference-count":50,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,4,21]],"date-time":"2020-04-21T00:00:00Z","timestamp":1587427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The aim of this survey is to review some recent developments in devising efficient preconditioners for sequences of symmetric positive definite (SPD) linear systems      A k   x k  =  b k  , k = 1 , \u2026     arising in many scientific applications, such as discretization of transient Partial Differential Equations (PDEs), solution of eigenvalue problems, (Inexact) Newton methods applied to nonlinear systems, rational Krylov methods for computing a function of a matrix. In this paper, we will analyze a number of techniques of updating a given initial preconditioner by a low-rank matrix with the aim of improving the clustering of eigenvalues around 1, in order to speed-up the convergence of the Preconditioned Conjugate Gradient (PCG) method. We will also review some techniques to efficiently approximate the linearly independent vectors which constitute the low-rank corrections and whose choice is crucial for the effectiveness of the approach. Numerical results on real-life applications show that the performance of a given iterative solver can be very much enhanced by the use of low-rank updates.<\/jats:p>","DOI":"10.3390\/a13040100","type":"journal-article","created":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T04:15:13Z","timestamp":1587528913000},"page":"100","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Survey of Low-Rank Updates of Preconditioners for Sequences of Symmetric Linear Systems"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8273-9674","authenticated-orcid":false,"given":"Luca","family":"Bergamaschi","sequence":"first","affiliation":[{"name":"Department of Civil Environmental and Architectural Engineering, University of Padua, 35100 Padua, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,4,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1137\/0614004","article-title":"Factorized Sparse Approximate Inverse Preconditionings I. Theory","volume":"14","author":"Kolotilina","year":"1993","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1135","DOI":"10.1137\/S1064827594271421","article-title":"A Sparse Approximate Inverse Preconditioner for the Conjugate Gradient Method","volume":"17","author":"Benzi","year":"1996","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Elman, H.C., Silvester, D.J., and Wathen, A.J. (2014). Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics, Oxford University Press. [2nd ed.]. Numerical Mathematics and Scientific Computation.","DOI":"10.1093\/acprof:oso\/9780199678792.001.0001"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1137\/0724027","article-title":"Deflation of Conjugate Gradients with Applications to Boundary Value Problems","volume":"24","author":"Nicolaides","year":"1987","journal-title":"SIAM J. Numer. Anal."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1909","DOI":"10.1137\/S1064829598339761","article-title":"A deflated version of the conjugate gradient algorithm","volume":"21","author":"Saad","year":"2000","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1137\/S0895479893253975","article-title":"A Restarted GMRES method augmented with eigenvectors","volume":"16","author":"Morgan","year":"1995","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/j.cam.2017.09.047","article-title":"Restarted Hessenberg method for solving shifted nonsymmetric linear systems","volume":"331","author":"Gu","year":"2018","journal-title":"J. Comput. Appl. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1137\/S1064827502408591","article-title":"A class of spectral two-level preconditioners","volume":"25","author":"Carpentieri","year":"2003","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1164","DOI":"10.1016\/j.apnum.2007.01.005","article-title":"Incremental spectral preconditioners for sequences of linear systems","volume":"57","author":"Giraud","year":"2007","journal-title":"Appl. Numer. Math."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"1918","DOI":"10.1137\/06066151X","article-title":"Efficient Preconditioning of Sequences of Nonsymmetric Linear Systems","volume":"29","author":"Tebbens","year":"2007","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"997","DOI":"10.1002\/nla.695","article-title":"Preconditioner updates for solving sequences of linear systems in matrix-free environment","volume":"17","year":"2010","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1023\/A:1026089811044","article-title":"Approximate inverse preconditioning for shifted linear systems","volume":"43","author":"Benzi","year":"2003","journal-title":"BIT"},{"key":"ref_13","first-page":"49","article-title":"Efficient preconditioning for sequences of parametric complex symmetric linear systems","volume":"18","author":"Bertaccini","year":"2004","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1080\/00207168808803625","article-title":"Conjugate gradient method with preconditioning by projector","volume":"23","year":"1988","journal-title":"Int. J. Comput. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1002\/cnm.1630040202","article-title":"On the use of deflation to improve the convergence of conjugate gradient iteration","volume":"4","author":"Mansfield","year":"1988","journal-title":"Commun. Appl. Numer. Methods"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1137\/S1064827500373231","article-title":"On the Construction of Deflation-Based Preconditioners","volume":"23","author":"Frank","year":"2001","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_17","first-page":"156","article-title":"Spectral deflation in Krylov solvers: A theory of coordinate space based methods","volume":"39","author":"Gutknecht","year":"2012","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s10543-006-0100-1","article-title":"Convergence of inexact inverse iteration with application to preconditioned iterative solves","volume":"47","author":"Freitag","year":"2007","journal-title":"BIT Numer. Math."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1093\/imanum\/drm036","article-title":"A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems","volume":"28","author":"Freitag","year":"2008","journal-title":"IMA J. Numer. Anal."},{"key":"ref_20","first-page":"76","article-title":"Quasi-Newton preconditioners for the inexact Newton method","volume":"23","author":"Bergamaschi","year":"2006","journal-title":"Electron. Trans. Numer. Anal."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1863","DOI":"10.1016\/j.mcm.2010.11.064","article-title":"Low-Rank Update of Preconditioners for the Inexact Newton Method with SPD Jacobian","volume":"54","author":"Bergamaschi","year":"2011","journal-title":"Math. Comput. Model."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1080\/10556788.2014.908878","article-title":"Efficiently preconditioned Inexact Newton methods for large symmetric eigenvalue problems","volume":"30","author":"Bergamaschi","year":"2015","journal-title":"Optim. Methods Softw."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1933","DOI":"10.1016\/j.mcm.2012.01.013","article-title":"Low-rank Update of Preconditioners for the nonlinear Richard\u2019s Equation","volume":"57","author":"Bergamaschi","year":"2013","journal-title":"Math. Comput. Model."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/j.advengsoft.2010.10.011","article-title":"Quasi-Newton Acceleration of ILU Preconditioners for Nonlinear Two-Phase Flow Equations in Porous Media","volume":"46","author":"Bergamaschi","year":"2012","journal-title":"Adv. Eng. Softw."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1002\/nla.2032","article-title":"Tuned preconditioners for the eigensolution of large SPD matrices arising in engineering problems","volume":"23","year":"2016","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1137\/080716281","article-title":"Shift-invert Arnoldi\u2019s method with preconditioned iterative solves","volume":"31","author":"Freitag","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Bergamaschi, L., and Mart\u00ednez, A. (2017). Two-stage spectral preconditioners for iterative eigensolvers. Numer. Linear Algebra Appl., 24.","DOI":"10.1002\/nla.2084"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Bergamaschi, L., Mar\u00edn, J., and Mart\u00ednez, A. (2020). Compact Quasi-Newton preconditioners for SPD linear systems. arXiv.","DOI":"10.1002\/nla.2322"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1742","DOI":"10.1137\/040608246","article-title":"A comparison of deflation and the balancing preconditioner","volume":"27","author":"Nabben","year":"2006","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1137\/080712908","article-title":"Convergence analysis of iterative solvers in inexact Rayleigh quotient iteration","volume":"31","author":"Xue","year":"2009","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/nla.2144","article-title":"BFGS-like updates of constraint preconditioners for sequences of KKT linear systems","volume":"25","author":"Bergamaschi","year":"2018","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1002\/nla.2058","article-title":"Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics","volume":"23","author":"Gratton","year":"2016","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_33","unstructured":"Bergamaschi, L., Gondzio, J., Mart\u00ednez, A., Pearson, J., and Pougkakiotis, S. (2019). A New Preconditioning Approach for an Interior Point-Proximal Method of Multipliers for Linear and Convex Quadratic Programming. arXiv."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1002\/nme.1201","article-title":"Using spectral low rank preconditioners for large electromagnetic calculations","volume":"62","author":"Duff","year":"2005","journal-title":"Int. J. Numer. Methods Eng."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.cam.2018.01.022","article-title":"Spectral preconditioners for the efficient numerical solution of a continuous branched transport model","volume":"254","author":"Bergamaschi","year":"2019","journal-title":"J. Comput. Appl. Math."},{"key":"ref_36","unstructured":"Golub, G.H., and van Loan, C.F. (1991). Matrix Computation, Johns Hopkins University Press."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Saad, Y. (2003). Iterative Methods for Sparse Linear Systems, SIAM. [2nd ed.].","DOI":"10.1137\/1.9780898718003"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1137\/080725532","article-title":"Computing and deflating eigenvalues while solving multiple right-hand side linear systems with an application to quantum chromodynamics","volume":"32","author":"Stathopoulos","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Greenbaum, A. (1997). Iterative Methods for Solving Linear Systems, SIAM.","DOI":"10.1137\/1.9781611970937"},{"key":"ref_40","unstructured":"Embree, M. (1999). How Descriptive Are GMRES Convergence Bounds? Technical Report, Oxford University Computing Laboratory. Technical Report."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1137\/S1064827599364659","article-title":"GMRES with Deflated Restarting","volume":"24","author":"Morgan","year":"2002","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1023\/A:1026000105893","article-title":"Restarted Full Orthogonalization Method for Shifted Linear Systems","volume":"43","author":"Simoncini","year":"2003","journal-title":"BIT Numer. Math."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1785","DOI":"10.1137\/100803419","article-title":"Efficient preconditioner updates for shifted linear systems","volume":"33","author":"Bellavia","year":"2011","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"1643","DOI":"10.1016\/j.camwa.2014.03.005","article-title":"Efficient preconditioner updates for unsymmetric shifted linear systems","volume":"67","author":"Luo","year":"2014","journal-title":"Comput. Math. Appl."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/j.enggeo.2015.04.020","article-title":"Land subsidence due to groundwater withdrawal in the northern Beijing plain, China","volume":"193","author":"Zhu","year":"2015","journal-title":"Eng. Geol."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/S1064827500366124","article-title":"Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method","volume":"23","author":"Knyazev","year":"2001","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/(SICI)1099-1506(199703\/04)4:2<69::AID-NLA98>3.0.CO;2-F","article-title":"Asymptotic Convergence of Conjugate Gradient Methods for the Partial Symmetric Eigenproblem","volume":"4","author":"Bergamaschi","year":"1997","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1137\/S0895479894270427","article-title":"A Jacobi-Davidson method for Linear Eigenvalue Problems","volume":"17","author":"Sleijpen","year":"1996","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/nla.246","article-title":"Combination of Jacobi-Davidson and conjugate gradients for the partial symmetric eigenproblem","volume":"9","author":"Notay","year":"2002","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/978-3-030-04088-8_12","article-title":"Generalized Block Tuned preconditioners for SPD eigensolvers","volume":"30","author":"Bergamaschi","year":"2019","journal-title":"Springer INdAM Ser."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/100\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T13:45:07Z","timestamp":1760363107000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/4\/100"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,21]]},"references-count":50,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,4]]}},"alternative-id":["a13040100"],"URL":"https:\/\/doi.org\/10.3390\/a13040100","relation":{"has-preprint":[{"id-type":"doi","id":"10.20944\/preprints202003.0094.v1","asserted-by":"object"}]},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,21]]}}}