Preconditioners for Krylov subspace methods: an overview. (English) Zbl 1541.65016
Summary: When simulating a mechanism from science or engineering, or an industrial process, one is frequently required to construct a mathematical model, and then resolve this model numerically. If accurate numerical solutions are necessary or desirable, this can involve solving large-scale systems of equations. One major class of solution methods is that of preconditioned iterative methods, involving preconditioners which are computationally cheap to apply while also capturing information contained in the linear system. In this article, we give a short survey of the field of preconditioning. We introduce a range of preconditioners for partial differential equations, followed by optimization problems, before discussing preconditioners constructed with less standard objectives in mind.
© 2020 The Authors. GAMM - Mitteilungen published by Wiley-VCH GmbH on behalf of Gesellschaft für Angewandte Mathematik und Mechanik.
© 2020 The Authors. GAMM - Mitteilungen published by Wiley-VCH GmbH on behalf of Gesellschaft für Angewandte Mathematik und Mechanik.
MSC:
| 65F08 | Preconditioners for iterative methods |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
iterative method; Krylov subspace method; optimization; partial differential equations; preconditioningReferences:
| [1] | I. S.Duff, A. M.Erisman, and J. K.Reid, Direct methods for sparse matrices, 2nd ed., Oxford University Press, Oxford, UK, 2017. · Zbl 1364.65067 |
| [2] | S.Bellavia, J.Gondzio, and B.Morini, A matrix‐free preconditioner for sparse symmetric positive definite systems and least‐squares problems, SIAM J. Sci. Comput.35 (2013), A192-A211. · Zbl 1264.65036 |
| [3] | A. V.Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput.23 (2001), 517-541. · Zbl 0992.65028 |
| [4] | M.Benzi, Preconditioning techniques for large linear systems: A survey, J. Comput. Phys.182 (2002), 418-477. · Zbl 1015.65018 |
| [5] | A. J.Wathen, Preconditioning, Acta Numer.24 (2015), 329-376. · Zbl 1316.65039 |
| [6] | D.Bertaccini and F.Durastante, Iterative methods and preconditioning for large and sparse linear systems with applications, CRC Press, Boca Raton, FL, 2018. · Zbl 1386.65001 |
| [7] | K.Chen, Matrix preconditioning techniques and applications, Cambridge University Press, Cambridge, MA, 2005. · Zbl 1079.65057 |
| [8] | O.Axelsson, A survey of preconditioned iterative methods for linear systems of algebraic equations, BIT Numer. Math.25 (1985), 166-187. · Zbl 0566.65017 |
| [9] | M.Benzi and A. J.Wathen, Some preconditioning techniques for saddle point problems, in Model Order Reduction: Theory, Research Aspects and Applications. Mathematics in Industry (The European Consortium for Mathematics in Industry), Vol 13, W. H. A.Schilders (ed.), H. A.vander Vorst (ed.), and J.Rommes (ed.), Eds., Springer‐Verlag, Berlin/Heidelberg, Germany, 2008, 195-211. · Zbl 1152.65425 |
| [10] | M. A.Olshanskii and E. E.Tyrtyshnikov, Iterative methods for linear systems: theory and applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2014. · Zbl 1320.65050 |
| [11] | G.Mele et al., Preconditioning for linear systems, Kindle Direct Publishing, 2020. |
| [12] | A. M.Turing, Rounding‐off errors in matrix processes, Q. J. Mech. Appl. Math.1 (1948), 287-308. · Zbl 0033.28501 |
| [13] | J. A.Meijerink and H. A.vander Vorst, An iterative solution method for linear systems of which the coefficient matrix is a symmetric M‐matrix, Math. Comput.31 (1977), 148-162. · Zbl 0349.65020 |
| [14] | A.Greenbaum, Iterative methods for solving linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997. · Zbl 0883.65022 |
| [15] | J.Liesen and Z.Strakoš, Krylov subspace methods: Principles and analysis, Oxford University Press, Oxford, UK, 2013. · Zbl 1263.65034 |
| [16] | Y.Saad, Iterative methods for sparse linear systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003. · Zbl 1002.65042 |
| [17] | M.Eiermann and O. G.Ernst, Geometric aspects of the theory of Krylov subspace methods, Acta Numer.10 (2001), 251-312. · Zbl 1105.65328 |
| [18] | J.Liesen and P.Tichý, Convergence analysis of Krylov subspace methods, GAMM‐Mitt.27 (2004), 153-173. · Zbl 1071.65041 |
| [19] | V.Simoncini and D. B.Szyld, Recent computational developments in Krylov subspace methods for linear systems, Numer. Linear Algebra Appl.14 (2007), 1-59. · Zbl 1199.65112 |
| [20] | A. N.Krylov, On the numerical solution of the equation by which the frequency of small oscillations is determined in technical problems, Izv. Akad. Nauk SSSR Ser. Fiz.‐Mat.4 (1931), 491-539. · JFM 57.1454.02 |
| [21] | M. R.Hestenes and E.Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Stand.49 (1952), 409-436. · Zbl 0048.09901 |
| [22] | C.Lanczos, An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand.45 (1950), 255-282. |
| [23] | C.Lanczos, Solution of systems of linear equations by minimized iterations, J. Res. Nat. Bur. Stand.49 (1952), 33-53. |
| [24] | J. K.Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equations, in Large Sparse Sets of Linear Equations, J. K.Reid (ed.), Ed., Academic Press, London and New York, 1971, 231-254. |
| [25] | M.Engeli et al., Refined iterative methods for computation of the solution and the eigenvalues of self‐adjoint boundary value problems, Birkhäuser, Basel, 1959. · Zbl 0089.12103 |
| [26] | C. C.Paige and M. A.Saunders, Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal.12 (1975), 617-629. · Zbl 0319.65025 |
| [27] | Y.Saad and M. H.Schultz, GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput.7 (1986), 856-869. · Zbl 0599.65018 |
| [28] | Y.Saad, Krylov subspace methods for solving large unsymmetric linear systems, Math. Comput.37 (1981), 105-126. · Zbl 0474.65019 |
| [29] | C. C.Paige and M. A.Saunders, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Softw.8 (1982), 43-71. · Zbl 0478.65016 |
| [30] | D. C.‐L.Fong and M.Saunders, LSMR: An iterative algorithm for sparse least‐squares problems, SIAM J. Sci. Comput.33 (2011), 2950-2971. · Zbl 1232.65052 |
| [31] | R. W.Freund and N. M.Nachtigal, QMR: A quasi‐minimal residual method for non‐Hermitian linear systems, Numer. Math.60 (1991), 315-339. · Zbl 0754.65034 |
| [32] | R.Fletcher, Conjugate gradient methods for indefinite systems. Lecture notes in mathematics, Vol 506, Springer‐Verlag, Berlin, Germany, 1976, 73-89. · Zbl 0326.65033 |
| [33] | H. A.vander Vorst, Bi‐CGSTAB: A fast and smoothly converging variant of Bi‐CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput.13 (1992), 631-644. · Zbl 0761.65023 |
| [34] | P.Wesseling and P.Sonneveld, Numerical experiments with a multiple grid and a preconditioned Lanczos type method. Lecture notes in mathematics, Vol 771, Springer‐Verlag, Berlin, Germany, 1980, 543-562. · Zbl 0421.65065 |
| [35] | P.Sonneveld and M. B.vanGijzen, IDR(s): A family of simple and fast algorithms for solving large nonsymmetric systems of linear equations, SIAM J. Sci. Comput.31 (2008), 1035-1062. · Zbl 1190.65053 |
| [36] | M.Embree, How descriptive are GMRES convergence bounds? Technical report NA‐99‐08, University of Oxford, Oxford, UK, 1999. |
| [37] | A.Greenbaum and Z.Strakoš, Matrices that generate the same Krylov residual spaces, in Recent Advances in Iterative Methods, G.Golub (ed.), M.Luskin (ed.), and A.Greenbaum (ed.), Eds., Springer, New York, 1994, 95-118. · Zbl 0803.65029 |
| [38] | M.Arioli, V.Pták, and Z.Strakoš, Krylov sequences of maximal length and convergence of GMRES, BIT Numer. Math.38 (1998), 636-643. · Zbl 0916.65031 |
| [39] | A.Greenbaum, V.Pták, and Z.Strakoš, Any nonincreasing convergence curve is possible for GMRES, SIAM J. Matrix Anal. Appl.17 (1996), 465-469. · Zbl 0857.65029 |
| [40] | G.Meurant and J.Duintjer Tebbens, The role eigenvalues play in forming GMRES residual norms with non‐normal matrices, Numer. Alg.68 (2015), 143-165. · Zbl 1312.65050 |
| [41] | D.Braess and P.Peisker, On the numerical solution of the biharmonic equation and the role of squaring matrices for preconditioning, IMA J. Numer. Anal.6 (1986), 393-404. · Zbl 0616.65108 |
| [42] | M.Arioli et al., Interplay between discretization and algebraic computation in adaptive numerical solution of elliptic PDE problems, GAMM‐Mitt.36 (2013), 102-129. · Zbl 1279.65130 |
| [43] | J.Papež, J.Liesen, and Z.Strakoš, Distribution of the discretization and algebraic error in numerical solution of partial differential equations, Linear Algebra Appl.449 (2014), 89-114. · Zbl 1302.65113 |
| [44] | M.Arioli, E. H.Georgoulis, and D.Loghin, Stopping criteria for adaptive finite element solvers, SIAM J. Sci. Comput.35 (2013), A1537-A1559. · Zbl 1276.65077 |
| [45] | M.Arioli, D.Loghin, and A. J.Wathen, Stopping criteria for iterations in finite element methods, Numer. Math.99 (2005), 381-410. · Zbl 1069.65124 |
| [46] | P.Jiránek, Z.Strakoš, and M.Vohralík, A posteriori error estimates including algebraic error and stopping criteria for iterative solvers, SIAM J. Sci. Comput.32 (2010), 1567-1590. · Zbl 1215.65168 |
| [47] | D. N.Arnold, R. S.Falk, and R.Winther, Preconditioning in H(div) and applications, Math. Comput.66 (1997), 957-984. · Zbl 0870.65112 |
| [48] | V.Faber, T. A.Manteuffel, and S. V.Parter, On the theory of equivalent operators and application to the numerical solution of uniformly elliptic partial differential equations, Adv. Appl. Math.11 (1990), 109-163. · Zbl 0718.65043 |
| [49] | A.Klawonn, Preconditioners for indefinite problems. PhD Thesis, Universität Münster, 1996. |
| [50] | P.Oswald, On function spaces related to finite element approximation theory, Z. Anal. Anwendungen9 (1990), 43-64. · Zbl 0703.41018 |
| [51] | P.Oswald, Norm equivalencies and multilevel Schwarz preconditioning for variational problems. Forschungsergebnisse Math/92/01, Friedrich Schiller Universität, Jena, Germany, 1992. |
| [52] | W.Zulehner, Nonstandard norms and robust estimates for saddle point problems, SIAM J. Matrix Anal. Appl.32 (2011), 536-560. · Zbl 1251.65078 |
| [53] | U.Rüde, Mathematical and computational techniques for multilevel adaptive methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1993. · Zbl 0857.65127 |
| [54] | J.Málek and Z.Strakoš, Preconditioning and the conjugate gradient method in the context of solving PDEs, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2015. · Zbl 1396.65002 |
| [55] | K.‐A.Mardal and R.Winther, Preconditioning discretizations of systems of partial differential equations, Numer. Linear Algebra Appl.18 (2011), 1-40. · Zbl 1249.65246 |
| [56] | J.Hrnčíř, I.Pultarová, and Z.Strakoš, Decomposition into subspaces preconditioning: Abstract framework, Numer. Alg.83 (2020), 57-98. · Zbl 1434.65259 |
| [57] | H.Yserentant, Hierarchical bases of finite‐element spaces in the discretization of nonsymmetric elliptic boundary value problems, Computing35 (1985), 39-49. · Zbl 0566.65080 |
| [58] | H.Yserentant, On the multi‐level splitting of finite element spaces, Numer. Math.49 (1986), 379-412. · Zbl 0608.65065 |
| [59] | J.Xu, Iterative methods by space decomposition and subspace correction, SIAM Rev.34 (1992), 581-613. · Zbl 0788.65037 |
| [60] | L.Ling and E. J.Kansa, A least‐squares preconditioner for radial basis functions collocation methods, Adv. Comput. Math.23 (2005), 31-54. · Zbl 1067.65136 |
| [61] | D.Brown et al., On approximate cardinal preconditioning methods for solving PDEs with radial basis functions, Eng. Anal. Bound. Elem.29 (2005), 343-353. · Zbl 1182.65174 |
| [62] | R. K.Beatson, J. B.Cherrie, and C. T.Mouat, Fast fitting of radial basis functions: Methods based on preconditioned GMRES iteration, Adv. Comput. Math.11 (1999), 253-270. · Zbl 0940.65011 |
| [63] | R. E.Bank, Marching algorithms for elliptic boundary value problems. II: The variable coefficient case, SIAM J. Numer. Anal.14 (1977), 950-970. · Zbl 0382.65052 |
| [64] | B. L.Buzbee, G. H.Golub, and C. W.Nielson, On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal.7 (1970), 627-656. · Zbl 0217.52902 |
| [65] | R. W.Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM12 (1965), 95-113. · Zbl 0139.10902 |
| [66] | D.Fischer et al., On Fourier-Toeplitz methods for separable elliptic problems, Math. Comput.28 (1974), 349-368. · Zbl 0277.65065 |
| [67] | T.Gergelits et al., Laplacian preconditioning of elliptic PDEs: Localization of the eigenvalues of the discretized operator, SIAM J. Numer. Anal.57 (2019), 1369-1394. · Zbl 1495.65212 |
| [68] | U.Trottenberg, C.Oosterlee, and A.Schüller, Multigrid, Academic Press, London, 2001. · Zbl 0976.65106 |
| [69] | R. P.Fedorenko, A relaxation method for solving elliptic difference equations, USSR Comput. Math. Math. Phys.1 (1962), 1092-1096. · Zbl 0163.39303 |
| [70] | R. P.Fedorenko, The speed of convergence of one iterative process, USSR Comput. Math. Math. Phys.4 (1964), 227-235. · Zbl 0148.39501 |
| [71] | A.Brandt, Multi‐level adaptive solutions to boundary‐value problems, Math. Comput.31 (1977), 333-390. · Zbl 0373.65054 |
| [72] | A.Brandt, S.McCormick, and J.Ruge, Algebraic multigrid (AMG) for automatic multigrid solutions with application to geodetic computations. Technical report, Institute for Computational Studies, Fort Collins, CO, 1982. |
| [73] | A.Brandt, S.McCormick, and J.Ruge, Algebraic multigrid (AMG) for sparse matrix equations, in Sparsity and Its Applications, D. J.Evans (ed.), Ed., Cambridge University Press, Cambridge, MA, 1985, 257-284. · Zbl 0548.65014 |
| [74] | A.Brandt, Algebraic multigrid theory: The symmetric case, Appl. Math. Comput.19 (1986), 23-56. · Zbl 0616.65037 |
| [75] | J. E.Dendy, Black box multigrid, J. Comput. Phys.48 (1982), 366-386. · Zbl 0495.65047 |
| [76] | J. W.Ruge and K.Stüben, Algebraic multigrid, in Multigrid Methods, S. F.McCormick (ed.), Ed., Society for Industrial and Applied Mathematics, Philadelphia, PA, 1987, 73-130. |
| [77] | P.Wesseling and C. W.Oosterlee, Geometric multigrid with applications to computational fluid dynamics, J. Comput. Appl. Math.128 (2001), 311-334. · Zbl 0989.76069 |
| [78] | J.Xu and L.Zikatanov, Algebraic multigrid methods, Acta Numer.26 (2017), 591-721. · Zbl 1378.65182 |
| [79] | W.Hackbusch, Multi‐Grid methods and applications, Springer‐Verlag, Berlin/Heidelberg, Germany, 1985. · Zbl 0585.65030 |
| [80] | P.Wesseling, An introduction to multigrid methods, John Wiley & Sons, New York, NY, 1992. · Zbl 0760.65092 |
| [81] | H. A.Schwarz, Über einen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschr. Naturf. Ges. Zürich.15 (1870), 272-286. |
| [82] | M.Dryja and O.Widlund, An additive variant of the Schwarz alternating method for the case of many subregions. Technical report 339, Department of Computer Science, New York University, New York, 1987. |
| [83] | M.Dryja and O. B.Widlund, Chapter 16 - Some domain decomposition algorithms for elliptic problems, in Iterative Methods for Large Linear Systems, D. R.Kincaid (ed.) and L. J.Hayes (ed.), Eds., Academic Press, San Diego, 1990, 273-291. |
| [84] | M.Benzi et al., Algebraic theory of multiplicative Schwarz methods, Numer. Math.89 (2001), 605-639. · Zbl 0991.65037 |
| [85] | A.Frommer and D. B.Szyld, An algebraic convergence theory for restricted additive Schwarz methods using weighted max norms, SIAM J. Numer. Anal.39 (2001), 463-479. · Zbl 1006.65031 |
| [86] | R. A.Nicolaides, Deflation of conjugate gradients with applications to boundary value problems, SIAM J. Numer. Anal.24 (1987), 355-365. · Zbl 0624.65028 |
| [87] | F.Nataf et al., A coarse space construction based on local Dirichlet‐to‐Neumann maps, SIAM J. Sci. Comput.33 (2011), 1623-1642. · Zbl 1230.65134 |
| [88] | N.Spillane et al., Abstract robust coarse spaces for systems of PDEs via generalized eigenproblems in the overlaps, Numer. Math.126 (2014), 741-770. · Zbl 1291.65109 |
| [89] | V.Dolean, P.Jolivet, and F.Nataf, An introduction to domain decomposition methods: Algorithms, theory, and parallel implementation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2015. · Zbl 1364.65277 |
| [90] | M. J.Gander, Schwarz methods over the course of time, Electron. Trans. Numer. Anal.31 (2008), 228-255. · Zbl 1171.65020 |
| [91] | W.Hackbusch, Iterative solution of large sparse systems of equations, Springer, New York, NY, 1994. · Zbl 0789.65017 |
| [92] | T. P. A.Mathew, Domain decomposition methods for the numerical solution of partial differential equations, Springer‐Verlag, Berlin/Heidelberg, Germany, 2008. · Zbl 1147.65101 |
| [93] | A.Quarteroni and A.Valli, Domain decomposition methods for partial differential equations, Oxford University Press, Oxford, UK, 1999. · Zbl 0931.65118 |
| [94] | B.Smith, P.Bjørstad, and W.Gropp, Domain decomposition: Parallel multilevel methods for elliptic partial differential equations, Cambridge University Press, Cambridge, MA, 1996. · Zbl 0857.65126 |
| [95] | A.Toselli and O.Widlund, Domain decomposition methods – algorithms and theory, Springer‐Verlag, Berlin/Heidelberg, Germany, 2005. · Zbl 1069.65138 |
| [96] | R. E.Bank, A comparison of two multilevel iterative methods for nonsymmetric and indefinite elliptic finite element equations, SIAM J. Numer. Anal.18 (1981), 724-743. · Zbl 0471.65074 |
| [97] | H.Calandra, S.Gratton, and X.Vasseur, A geometric multigrid preconditioner for the solution of the Helmholtz equation in three‐dimensional heterogeneous media on massively parallel computers, in Modern Solvers for Helmholtz Problems, D.Lahaye (ed.), J.Tang (ed.), and K.Vuik (ed.), Eds., Birkhäuser, Cham, 2017, 141-155. · Zbl 1364.86008 |
| [98] | H. C.Elman, O. G.Ernst, and D. P.O’Leary, A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations, SIAM J. Sci. Comput.23 (2001), 1291-1315. · Zbl 1004.65134 |
| [99] | E.Haber and S.MacLachlan, A fast method for the solution of the Helmholtz equation, J. Comput. Phys.230 (2011), 4403-4418. · Zbl 1220.65172 |
| [100] | M.Bollhöfer, M. J.Grote, and O.Schenk, Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media, SIAM J. Sci. Comput.31 (2009), 3781-3805. · Zbl 1203.65273 |
| [101] | X.‐C.Cai and O. B.Widlund, Domain decomposition algorithms for indefinite elliptic problems, SIAM J. Sci. Stat. Comput.13 (1992), 243-258. · Zbl 0746.65085 |
| [102] | M. J.Gander and H.Zhang, Domain decomposition methods for the Helmholtz equation: A numerical investigation, in Domain Decomposition Methods in Science and Engineering, Vol XX, R.Bank (ed.) et al., Eds., Springer‐Verlag, Berlin/Heidelberg, Germany, 2013, 215-222. |
| [103] | C.Farhat, A.Macedo, and M.Lesoinne, A two‐level domain decomposition method for the iterative solution of high frequency exterior Helmholtz problems, Numer. Math.85 (2000), 283-308. · Zbl 0965.65133 |
| [104] | J.‐D.Benamou and B.Desprès, A domain decomposition method for the Helmholtz equation and related optimal control problems, J. Comput. Phys.136 (1997), 68-82. · Zbl 0884.65118 |
| [105] | M. J.Gander, F.Magoulès, and F.Nataf, Optimized Schwarz methods without overlap for the Helmholtz equation, SIAM J. Sci. Comput.24 (2002), 38-60. · Zbl 1021.65061 |
| [106] | S.Kim, Parallel multidomain iterative algorithms for the Helmholtz wave equation, Appl. Numer. Math.17 (1995), 411-429. · Zbl 0838.65119 |
| [107] | A.Bayliss, C. I.Goldstein, and E.Turkel, An iterative method for the Helmholtz equation, J. Comput. Phys.49 (1983), 443-457. · Zbl 0524.65068 |
| [108] | A. L.Laird and M. B.Giles, Preconditioned iterative solution of the 2D Helmholtz equation. Technical report NA‐02‐12, University of Oxford, Oxford, UK, 2002. |
| [109] | M.Magolu Monga Made, R.Beauwens, and G.Warzée, Preconditioning of discrete Helmholtz operators perturbed by a diagonal complex matrix, Commun. Numer. Methods Eng.16 (2000), 801-817. · Zbl 0972.65031 |
| [110] | Y. A.Erlangga, C. W.Oosterlee, and C.Vuik, A novel multigrid based preconditioner for heterogeneous Helmholtz problems, SIAM J. Sci. Comput.27 (2006), 1471-1492. · Zbl 1095.65109 |
| [111] | A. H.Sheikh, D.Lahaye, and C.Vuik, On the convergence of shifted Laplace preconditioner combined with multilevel deflation, Numer. Linear Algebra Appl.20 (2013), 645-662. · Zbl 1313.65293 |
| [112] | P.‐H.Cocquet and M. J.Gander, How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?SIAM J. Sci. Comput.39 (2017), A438-A478. · Zbl 1365.65269 |
| [113] | M. J.Gander, I. G.Graham, and E. A.Spence, Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber‐independent convergence is guaranteed?Numer. Math.131 (2015), 567-614. · Zbl 1328.65238 |
| [114] | O.Axelsson, J.Karátson, and F.Magoulès, Superlinear convergence using block preconditioners for the real system formulation of complex Helmholtz equations, J. Comput. Appl. Math.340 (2018), 424-431. · Zbl 1432.65035 |
| [115] | M. J.Gander and F.Nataf, An incomplete LU preconditioner for problems in acoustics, J. Comput. Acoust.13 (2005), 455-476. · Zbl 1189.76362 |
| [116] | B.Engquist and L.Ying, Sweeping preconditioner for the Helmholtz equation: Moving perfectly matched layers, Multiscale Model. Simul.9 (2011), 686-710. · Zbl 1228.65234 |
| [117] | M. J.Gander and H.Zhang, A class of iterative solvers for the Helmholtz equation: Factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods, SIAM Rev.61 (2019), 3-76. · Zbl 1417.65216 |
| [118] | X.Liu et al., Solving the three‐dimensional high‐frequency Helmholtz equation using contour integration and polynomial preconditioning, SIAM J. Matrix Anal. Appl.41 (2020), 58-82. · Zbl 1434.65234 |
| [119] | Y. A.Erlangga, Advances in iterative methods and preconditioners for the Helmholtz equation, Arch. Comput. Methods Eng.15 (2008), 37-66. · Zbl 1158.65078 |
| [120] | O. G.Ernst and M. J.Gander, Why it is difficult to solve Helmholtz problems with classical iterative methods, in Numerical Analysis of Multiscale Problems, I. G.Graham (ed.) et al., Eds., Springer‐Verlag, Berlin/Heidelberg, Germany, 2012, 325-363. · Zbl 1248.65128 |
| [121] | L. N.Trefethen and M.Embree, Spectra and pseudospectra: The behavior of nonnormal matrices and operators, Princeton University Press, Princeton, NJ, 2005. · Zbl 1085.15009 |
| [122] | O.Axelsson and J.Karátson, Symmetric part preconditioning for the conjugate gradient method in Hilbert space, Numer. Funct. Anal. Optim.24 (2003), 455-474. · Zbl 1054.65055 |
| [123] | H. C.Elman and M. H.Schultz, Preconditioning by fast direct methods for nonself‐adjoint nonseparable elliptic equations, SIAM J. Numer. Anal.23 (1986), 44-57. · Zbl 0619.65093 |
| [124] | Z.‐Z.Bai, G. H.Golub, and M. K.Ng, Hermitian and skew‐Hermitian splitting methods for non‐Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl.24 (2003), 603-626. · Zbl 1036.65032 |
| [125] | D.Bertaccini et al., Preconditioned HSS methods for the solution of non‐Hermitian positive definite linear systems and applications to the discrete convection‐diffusion equation, Numer. Math.99 (2005), 441-484. · Zbl 1068.65041 |
| [126] | R. C. Y.Chin and T. A.Manteuffel, An analysis of block successive overrelaxation for a class of matrices with complex spectra, SIAM J. Numer. Anal.25 (1988), 564-585. · Zbl 0655.65060 |
| [127] | H. C.Elman and M. P.Chernesky, Ordering effects on relaxation methods applied to the discrete one‐dimensional convection‐diffusion equation, SIAM J. Numer. Anal.30 (1993), 1268-1290. · Zbl 0790.65027 |
| [128] | H. C.Elman, D. J.Silvester, and A. J.Wathen, Finite elements and fast iterative solvers with applications in incompressible fluid dynamics, 2nd ed., Oxford University Press, Oxford, UK, 2014. · Zbl 1304.76002 |
| [129] | H. C.Elman and G. H.Golub, Iterative methods for cyclically reduced non‐self‐adjoint linear systems. II, Math. Comput.56 (1991), 215-242. · Zbl 0716.65096 |
| [130] | H.Han et al., Analysis of flow directed iterations, J. Comput. Math.10 (1992), 57-76. · Zbl 0743.76075 |
| [131] | P. A.Farrell, Flow conforming iterative methods for convection dominated flows, IMACS Ann. Comput. Appl. Math.1 (1989), 681-686. |
| [132] | O.Axelsson and J.Karátson, Mesh independent superlinear PCG rates via compact‐equivalent operators, SIAM J. Numer. Anal.45 (2007), 1495-1516. · Zbl 1151.65081 |
| [133] | R. C. Y.Chin, T. A.Manteuffel, and J.dePillis, ADI as a preconditioning for solving the convection‐diffusion equation, SIAM J. Sci. Stat. Comput.5 (1984), 281-299. · Zbl 0549.65068 |
| [134] | E. L.Wachspress, Extended application of alternating direction implicit iteration model problem theory, J. Soc. Ind. Appl. Math.11 (1963), 994-1016. · Zbl 0244.65045 |
| [135] | D.Palitta and V.Simoncini, Matrix‐equation‐based strategies for convection-diffusion equations, BIT Numer. Math.56 (2016), 751-776. · Zbl 1341.65042 |
| [136] | W.Hackbusch, A sparse matrix arithmetic based on ℋ‐matrices. Part I: Introduction to ℋ‐matrices, Computing62 (1999), 89-108. · Zbl 0927.65063 |
| [137] | J.Bey and G.Wittum, Downwind numbering: Robust multigrid for convection‐diffusion problems, Appl. Numer. Math.23 (1997), 177-192. · Zbl 0879.65088 |
| [138] | W.Hackbusch and T.Probst, Downwind Gauß-Seidel smoothing for convection dominated problems, Numer. Linear Algebra Appl.4 (1997), 85-102. · Zbl 0889.65026 |
| [139] | W. A.Mulder, A new multigrid approach to convection problems, J. Comput. Phys.83 (1989), 303-323. · Zbl 0672.76087 |
| [140] | T.Washio and C. W.Oosterlee, Flexible multiple semicoarsening for three‐dimensional singularly perturbed problems, SIAM J. Sci. Comput.19 (1998), 1646-1666. · Zbl 0913.65110 |
| [141] | A.Brandt and I.Yavneh, On multigrid solution of high‐Reynolds incompressible entering flows, J. Comput. Phys.101 (1992), 151-164. · Zbl 0757.76033 |
| [142] | A.Ramage, A multigrid preconditioner for stabilised discretisations of advection‐diffusion problems, J. Comput. Appl. Math.110 (1999), 187-203. · Zbl 0939.65135 |
| [143] | M.Benzi and M. A.Olshanskii, An augmented Lagrangian‐based approach to the Oseen problem, SIAM J. Sci. Comput.28 (2006), 2095-2113. · Zbl 1126.76028 |
| [144] | P. E.Farrell, L.Mitchell, and F.Wechsung, An augmented Lagrangian preconditioner for the 3D stationary incompressible Navier-Stokes equations at high Reynolds number, SIAM J. Sci. Comput.41 (2019), A3073-A3096. · Zbl 1448.65261 |
| [145] | J.Boyle, M.Mihajlović, and J.Scott, HSL_MI20: An efficient AMG preconditioner for finite element problems in 3D, Int. J. Numer. Methods Eng.82 (2010), 64-98. · Zbl 1183.76799 |
| [146] | Y.Notay, Aggregation‐based algebraic multigrid for convection‐diffusion equations, SIAM J. Sci. Comput.34 (2012), A2288-A2316. · Zbl 1250.76139 |
| [147] | C.‐T.Wu and H. C.Elman, Analysis and comparison of geometric and algebraic multigrid for convection‐diffusion equations, SIAM J. Sci. Comput.28 (2006), 2208-2228. · Zbl 1133.65102 |
| [148] | V.Dolean, F.Nataf, and G.Rapin, Deriving a new domain decomposition method for the Stokes equations using the Smith factorization, Math. Comput.78 (2009), 789-814. · Zbl 1223.76045 |
| [149] | J.Pestana et al., Efficient block preconditioning for a C^1 finite element discretization of the Dirichlet biharmonic problem, SIAM J. Sci. Comput.38 (2016), A325-A345. |
| [150] | P.Farrell and J.Pestana, Block preconditioners for linear systems arising from multiscale collocation with compactly supported RBFs, Numer. Linear Algebra Appl.22 (2015), 731-747. · Zbl 1363.65042 |
| [151] | M.Benzi, G. H.Golub, and J.Liesen, Numerical solution of saddle point problems, Acta Numer.14 (2005), 1-137. · Zbl 1115.65034 |
| [152] | M.Benzi et al., A relaxed dimensional factorization preconditioner for the incompressible Navier-Stokes equations, J. Comput. Phys.230 (2011), 6185-6202. · Zbl 1419.76433 |
| [153] | M.Benzi et al., Parameter estimates for the relaxed dimensional factorization preconditioner and application to hemodynamics, Comput. Meth. Appl. Mech. Eng.300 (2016), 129-145. · Zbl 1423.76212 |
| [154] | M. F.Murphy, G. H.Golub, and A. J.Wathen, A note on preconditioning for indefinite linear systems, SIAM J. Sci. Comput.21 (2000), 1969-1972. · Zbl 0959.65063 |
| [155] | N.Bootland et al., Preconditioners for two‐phase incompressible Navier-Stokes flow, SIAM J. Sci. Comput.41 (2019), B843-B869. · Zbl 1421.76161 |
| [156] | H. C.Elman, Preconditioning for the steady‐state Navier-Stokes equations with low viscosity, SIAM J. Sci. Comput.20 (1999), 1299-1316. · Zbl 0935.76057 |
| [157] | H.Elman et al., Block preconditioners based on approximate commutators, SIAM J. Sci. Comput.27 (2006), 1651-1668. · Zbl 1100.65042 |
| [158] | T.Roy et al., A block preconditioner for non‐isothermal flow in porous media, J. Comput. Phys.395 (2019), 636-652. · Zbl 1452.65053 |
| [159] | J. A.White and R. I.Borja, Block‐preconditioned Newton-Krylov solvers for fully coupled flow and geomechanics, Comput. Geosci.15 (2011), 647-659. · Zbl 1367.76034 |
| [160] | Yu. A.Kuznetsov, Efficient iterative solvers for elliptic finite element problems on nonmatching grids, Russ. J. Numer. Anal. Math. Model.10 (1995), 187-211. · Zbl 0839.65031 |
| [161] | G. H.Golub and R. S.Varga, Chebyshev semi‐iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods: Part I, Numer. Math.3 (1961), 147-156. · Zbl 0099.10903 |
| [162] | G. H.Golub and R. S.Varga, Chebyshev semi‐iterative methods, successive overrelaxation iterative methods, and second order Richardson iterative methods: Part II, Numer. Math.3 (1961), 157-168. · Zbl 0099.10903 |
| [163] | A.Wathen and T.Rees, Chebyshev semi‐iteration in preconditioning for problems including the mass matrix, Electron. Trans. Numer. Anal.34 (2009), 125-135. · Zbl 1189.65065 |
| [164] | F. P.Ali Beik and M.Benzi, Iterative methods for double saddle point systems, SIAM J. Matrix Anal. Appl.39 (2018), 902-921. · Zbl 1391.65062 |
| [165] | G. N.Gatica and N.Heuer, A dual‐dual formulation for the coupling of mixed‐FEM and BEM in hyperelasticity, SIAM J. Numer. Anal.38 (2000), 380-400. · Zbl 0992.74068 |
| [166] | K.‐A.Mardal, B. F.Nielsen, and M.Nordaas, Robust preconditioners for PDE‐constrained optimization with limited observations, BIT Numer. Math.57 (2017), 405-431. · Zbl 1368.65099 |
| [167] | J.Sogn and W.Zulehner, Schur complement preconditioners for multiple saddle point problems of block tridiagonal form with application to optimization problems, IMA J. Numer. Anal.39 (2019), 1328-1359. · Zbl 1464.65032 |
| [168] | C.Powell and D.Silvester, Black‐box preconditioning for mixed formulation of self‐adjoint elliptic PDEs, in Challenges in Scientific Computing - CISC 2002, E.Bänsch (ed.), Ed., Springer‐Verlag, Berlin/Heidelberg, Germany, 2003, 268-285. · Zbl 1045.65106 |
| [169] | J.Sundnes et al., Multigrid block preconditioning for a coupled system of partial differential equations modeling the electrical activity in the heart, Comput. Methods Biomech. Biomed. Engin.5 (2002), 397-409. |
| [170] | D.Silvester and A.Wathen, Fast iterative solution of stabilised Stokes systems Part II: Using general block preconditioners, SIAM J. Numer. Anal.31 (1994), 1352-1367. · Zbl 0810.76044 |
| [171] | P. S.Vassilevski and U.Villa, A block‐diagonal algebraic multigrid preconditioner for the Brinkman problem, SIAM J. Sci. Comput.35 (2013), S3-S17. · Zbl 1282.65133 |
| [172] | B.Fischer et al., Minimum residual methods for augmented systems, BIT Numer. Math.38 (1998), 527-543. · Zbl 0914.65026 |
| [173] | J. W.Pearson, J.Pestana, and D. J.Silvester, Refined saddle‐point preconditioners for discretized Stokes problems, Numer. Math.138 (2018), 331-363. · Zbl 1408.76371 |
| [174] | R.Herzog, Dimensionally consistent preconditioning for saddle‐point problems, arXiv e‐prints. 2020: arXiv:2003.09478. · Zbl 1473.65028 |
| [175] | P. P.Grinevich and M. A.Olshanskii, An iterative method for the Stokes‐type problem with variable viscosity, SIAM J. Sci. Comput.31 (2009), 3959-3978. · Zbl 1410.76290 |
| [176] | S.Holmgren and K.Otto, Semicirculant preconditioners for first‐order partial differential equations, SIAM J. Sci. Comput.15 (1994), 385-407. · Zbl 0806.65032 |
| [177] | K.Otto, Analysis of preconditioners for hyperbolic partial differential equations, SIAM J. Numer. Anal.33 (1996), 2131-2165. · Zbl 0861.65072 |
| [178] | M. M.Meerschaert and C.Tadjeran, Finite difference approximations for fractional advection-dispersion flow equations, J. Comput. Appl. Math.172 (2004), 65-77. · Zbl 1126.76346 |
| [179] | M. M.Meerschaert and C.Tadjeran, Finite difference approximations for two‐sided space‐fractional partial differential equations, Appl. Numer. Math.56 (2006), 80-90. · Zbl 1086.65087 |
| [180] | G. H.Golub and C. F.vanLoan, Matrix computations, 4th ed., The John Hopkins University Press, Maryland, 2013. · Zbl 1268.65037 |
| [181] | U.Grenander and G.Szegő, Toeplitz forms and their applications, American Mathematical Society, New York, 1958. · Zbl 0080.09501 |
| [182] | E. E.Tyrtyshnikov, A unifying approach to some old and new theorems on distribution and clustering, Linear Algebra Appl.232 (1996), 1-43. · Zbl 0841.15006 |
| [183] | N. L.Zamarashkin and E. E.Tyrtyshnikov, Distribution of eigenvalues and singular values of Toeplitz matrices under weakened conditions on the generating function, Sb. Math.188 (1997), 1191-1201. · Zbl 0898.15007 |
| [184] | P.Tilli, A note on the spectral distribution of Toeplitz matrices, Linear Multilinear Algebra45 (1998), 147-159. · Zbl 0951.65033 |
| [185] | G.Strang, A proposal for Toeplitz matrix calculations, Stud. Appl. Math.74 (1986), 171-176. · Zbl 0621.65025 |
| [186] | J. A.Olkin, Linear and nonlinear deconvolution problems, PhD Thesis, Rice University, 1986. |
| [187] | T. F.Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Stat. Comput.9 (1988), 766-771. · Zbl 0646.65042 |
| [188] | E. E.Tyrtyshnikov, Optimal and superoptimal circulant preconditioners, SIAM J. Matrix Anal. Appl.13 (1992), 459-473. · Zbl 0774.65024 |
| [189] | D.Bini and P.Favati, On a matrix algebra related to the discrete Hartley transform, SIAM J. Matrix Anal. Appl.14 (1993), 500-507. · Zbl 0773.65029 |
| [190] | T.Huckle, Fast transforms for tridiagonal linear equations, BIT Numer. Math.34 (1994), 99-112. · Zbl 0815.65040 |
| [191] | R. H.Chan, Toeplitz preconditioners for Toeplitz systems with nonnegative generating functions, IMA J. Numer. Anal.11 (1991), 333-345. · Zbl 0737.65022 |
| [192] | R. H.Chan and P. T. P.Tang, Fast band‐Toeplitz preconditioners for Hermitian Toeplitz systems, SIAM J. Sci. Comput.15 (1994), 164-171. · Zbl 0797.65022 |
| [193] | G.Fiorentino and S.Serra, Multigrid methods for Toeplitz matrices, Calcolo28 (1991), 283-305. · Zbl 0778.65021 |
| [194] | R. H.Chan and M. K.Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev.38 (1996), 427-482. · Zbl 0863.65013 |
| [195] | R. H.‐F.Chan and X.‐Q.Jin, An introduction to iterative Toeplitz solvers, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2007. · Zbl 1146.65028 |
| [196] | M. K.Ng, Iterative methods for Toeplitz systems, Oxford University Press, Oxford, UK, 2004. · Zbl 1059.65031 |
| [197] | S.Serra Capizzano and E.Tyrtyshnikov, How to prove that a preconditioner cannot be superlinear, Math. Comput.72 (2003), 1305-1316. · Zbl 1021.15005 |
| [198] | S.Serra Capizzano and E.Tyrtyshnikov, Any circulant‐like preconditioner for multilevel matrices is not superlinear, SIAM J. Matrix Anal. Appl.21 (1999), 431-439. · Zbl 0952.65037 |
| [199] | A.Aricò and M.Donatelli, A V‐cycle multigrid for multilevel matrix algebras: Proof of optimality, Numer. Math.105 (2007), 511-547. · Zbl 1114.65033 |
| [200] | S.Serra, Spectral and computational analysis of block Toeplitz matrices having nonnegative definite matrix‐valued generating functions, BIT Numer. Math.39 (1999), 152-175. · Zbl 0917.65031 |
| [201] | C.Garoni and S.Serra‐Capizzano, Generalized locally Toeplitz sequences: Theory and applications, Volume I, Springer, New York, NY, 2017. · Zbl 1376.15002 |
| [202] | C.Garoni and S.Serra‐Capizzano, Generalized locally Toeplitz sequences: Theory and applications, Volume II, Springer, New York, NY, 2018. · Zbl 1448.47004 |
| [203] | M. J.Gander, 50 years of time parallel time integration, in Multiple Shooting and Time Domain Decomposition Methods, T.Carraro (ed.) et al., Eds., Springer, New York, NY, 2015, 69-113. · Zbl 1337.65127 |
| [204] | D.Palitta, Matrix equation techniques for certain evolutionary partial differential equations, arXiv e‐prints. 2019: arXiv:1908.11851. |
| [205] | E.McDonald, J.Pestana, and A.Wathen, Preconditioning and iterative solution of all‐at‐once systems for evolutionary partial differential equations, SIAM J. Sci. Comput.40 (2018), A1012-A1033. · Zbl 1392.65036 |
| [206] | A.Goddard and A.Wathen, A note on parallel preconditioning for all‐at‐once evolutionary PDEs, Electron. Trans. Numer. Anal.51 (2019), 135-150. · Zbl 1422.65232 |
| [207] | S.Güttel and J. W.Pearson, A rational deferred correction approach to parabolic optimal control problems, IMA J. Numer. Anal.38 (2018), 1861-1892. · Zbl 1462.65160 |
| [208] | M.Benzi, E.Haber, and L.Taralli, A preconditioning technique for a class of PDE‐constrained optimization problems, Adv. Comput. Math.35 (2011), 149-173. · Zbl 1293.65041 |
| [209] | M.Hinze, M.Köster, and S.Turek, A space‐time multigrid method for optimal flow control, Internat. Ser. Numer. Math, Vol 160, Springer, Basel, AG, 2012, 147-170. · Zbl 1356.49046 |
| [210] | M.Stoll and A.Wathen, All‐at‐once solution of time‐dependent PDE‐constrained optimization problems. Technical report NA‐10‐13, University of Oxford, Oxford, UK, 2010. |
| [211] | I. G.Graham and M. J.Hagger, Unstructured additive Schwarz-conjugate gradient method for elliptic problems with highly discontinuous coefficients, SIAM J. Sci. Comput.20 (1999), 2041-2066. · Zbl 0943.65147 |
| [212] | P.Bastian, M.Blatt, and R.Scheichl, Algebraic multigrid for discontinuous Galerkin discretizations of heterogeneous elliptic problems, Numer. Linear Algebra Appl.19 (2012), 367-388. · Zbl 1274.65313 |
| [213] | J.Kraus et al., Preconditioning heterogeneous H(div) problems by additive Schur complement approximation and applications, SIAM J. Sci. Comput.38 (2016), A875-A898. · Zbl 1380.65376 |
| [214] | A.Klawonn, O. B.Widlund, and M.Dryja, Dual‐primal FETI methods for three‐dimensional elliptic problems with heterogeneous coefficients, SIAM J. Numer. Anal.40 (2002), 159-179. · Zbl 1032.65031 |
| [215] | C. E.Powell and D.Silvester, Optimal preconditioning for Raviart-Thomas mixed formulation of second‐order elliptic problems, SIAM J. Matrix Anal. Appl.25 (2004), 718-738. · Zbl 1073.65128 |
| [216] | M. W.Benson, Iterative solution of large scale linear systems, Master’s Thesis, Lakehead University Thunder Bay, Ontario, 1973. |
| [217] | G.Alléon, M.Benzi, and L.Giraud, Sparse approximate inverse preconditioning for dense linear systems arising in computational electromagnetics, Numer. Alg.16 (1997), 1-15. · Zbl 0895.65017 |
| [218] | B.Carpentieri, I. S.Duff, and L.Giraud, Sparse pattern selection strategies for robust Frobenius‐norm minimization preconditioners in electromagnetism, Numer. Linear Algebra Appl.7 (2000), 667-685. · Zbl 1051.65050 |
| [219] | A.Franceschini et al., Recent advancements in preconditioning techniques for large size linear systems suited for High Performance Computing. Dolomites Res. Notes Approx.32 (2018), 11-22. · Zbl 1540.65107 |
| [220] | L.Giraud, J.Langou, and G.Sylvand, On the parallel solution of large industrial wave propagation problems, J. Comput. Acoust.14 (2006), 83-111. · Zbl 1198.78011 |
| [221] | L. Yu.Kolotilina and A. Yu.Yeremin, Factorized sparse approximate inverse preconditioning. I. Theory, SIAM J. Matrix Anal. Appl.14 (1993), 45-58. · Zbl 0767.65037 |
| [222] | M.Margonari and M.Bonnet, Fast multipole method applied to elastostatic BEM-FEM coupling, Comput. Struct.83 (2005), 700-717. |
| [223] | J. A.Sanz, M.Bonnet, and J.Dominguez, Fast multipole method applied to 3‐D frequency domain elastodynamics, Eng. Anal. Bound. Elem.32 (2008), 787-795. · Zbl 1244.74190 |
| [224] | M. J.Grote and T.Huckle, Parallel preconditioning with sparse approximate inverses, SIAM J. Sci. Comput.18 (1997), 838-853. · Zbl 0872.65031 |
| [225] | M.Benzi and M.Tůma, A sparse approximate inverse preconditioner for nonsymmetric linear systems, SIAM J. Sci. Comput.19 (1998), 968-994. · Zbl 0930.65027 |
| [226] | M.Benzi and M.Tůma, A comparative study of sparse approximate inverse preconditioners, Appl. Numer. Math.30 (1999), 305-340. · Zbl 0949.65043 |
| [227] | T.Huckle, Approximate sparsity patterns for the inverse of a matrix and preconditioning, Appl. Numer. Math.30 (1999), 291-303. · Zbl 0927.65045 |
| [228] | T. K.Huckle, Efficient computation of sparse approximate inverses, Numer. Linear Algebra Appl.5 (1998), 57-71. · Zbl 0937.65055 |
| [229] | C. H.Ahn et al., Numerical study of approximate inverse preconditioner for two‐dimensional engine inlet problems, Electromagnetics19 (1999), 131-146. |
| [230] | B.Carpentieri et al., Sparse symmetric preconditioners for dense linear systems in electromagnetism, Numer. Linear Algebra Appl.11 (2004), 753-771. · Zbl 1164.65340 |
| [231] | M.Wathen and C.Greif, A scalable approximate inverse block preconditioner for an incompressible magnetohydrodynamics model problem, SIAM J. Sci. Comput.42 (2020), B57-B79. · Zbl 1428.76177 |
| [232] | D. W.Peaceman and H. H.RachfordJr., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math.3 (1955), 28-41. · Zbl 0067.35801 |
| [233] | Z.Dostál, Conjugate gradient method with preconditioning by projector, Int. J. Comput. Math.23 (1988), 315-323. · Zbl 0668.65034 |
| [234] | A.Gaul et al., A framework for deflated and augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl.34 (2013), 495-518. · Zbl 1273.65049 |
| [235] | M.Bebendorf, Hierarchical matrices: A means to efficiently solve elliptic boundary value problems, Springer‐Verlag, Berlin/Heidelberg, Germany, 2008. · Zbl 1151.65090 |
| [236] | L.Grasedyck and W.Hackbusch, Construction and arithmetics of ℋ‐matrices, Computing70 (2003), 295-334. · Zbl 1030.65033 |
| [237] | W.Hackbusch, B.Khoromskij, and S. A.Sauter, On ℋ^2‐matrices, in Lectures on Applied Mathematics, H.‐J.Bungartz (ed.), R. H. W.Hoppe (ed.), and C.Zenger (ed.), Eds., Springer‐Verlag, Berlin/Heidelberg, Germany, 2000, 9-29. |
| [238] | S.Chandrasekaran et al., Some fast algorithms for sequentially semiseparable representations, SIAM J. Matrix Anal. Appl.27 (2005), 341-364. · Zbl 1091.65063 |
| [239] | L.Greengard and V.Rokhlin, A fast algorithm for particle simulations, J. Comput. Phys.73 (1987), 325-348. · Zbl 0629.65005 |
| [240] | K. L.Ho and L.Greengard, A fast direct solver for structured linear systems by recursive skeletonization, SIAM J. Sci. Comput.34 (2012), A2507-A2532. · Zbl 1259.65062 |
| [241] | S.Le Borne and L.Grasedyck, ℋ‐matrix preconditioners in convection‐dominated problems, SIAM J. Matrix Anal. Appl.27 (2006), 1172-1183. · Zbl 1102.65051 |
| [242] | H.Ibeid et al., Fast multipole preconditioners for sparse matrices arising from elliptic equations, Comput. Vis. Sci.18 (2018), 213-229. · Zbl 1398.65039 |
| [243] | R.Bridson and C.Greif, A multipreconditioned conjugate gradient algorithm, SIAM J. Matrix Anal. Appl.27 (2006), 1056-1068. · Zbl 1104.65027 |
| [244] | C.Greif, T.Rees, and D. B.Szyld, GMRES with multiple preconditioners, SeMA Journal74 (2017), 213-231. · Zbl 1383.65026 |
| [245] | T.Bakhos et al., Multipreconditioned GMRES for shifted systems, SIAM J. Sci. Comput.39 (2017), S222-S247. · Zbl 1392.65043 |
| [246] | N.Bootland, A.Wathen, Multipreconditioning with application to two‐phase incompressible Navier‐Stokes flow, arXiv e‐prints. 2020: arXiv:2005.07608. · Zbl 1470.65046 |
| [247] | J.Gondzio, Interior point methods 25 years later, Eur. J. Oper. Res.218 (2012), 587-601. · Zbl 1244.90007 |
| [248] | L.Bergamaschi, J.Gondzio, and G.Zilli, Preconditioning indefinite systems in interior point methods for optimization, Comput. Optim. Appl.28 (2004), 149-171. · Zbl 1056.90137 |
| [249] | P. E.Gill et al., Preconditioners for indefinite systems arising in optimization, SIAM J. Matrix Anal. Appl.13 (1992), 292-311. · Zbl 0749.65037 |
| [250] | A. R. L.Oliveira and D. C.Sorensen, A new class of preconditioners for large‐scale linear systems from interior point methods for linear programming, Linear Algebra Appl.394 (2005), 1-24. · Zbl 1071.65088 |
| [251] | L.Schork and J.Gondzio, Implementation of an interior point method with basis preconditioning. Math. Prog. Comp. (2020). https://doi.org/10.1007/s12532‐020‐00181‐8. · Zbl 1452.90217 · doi:10.1007/s12532‐020‐00181‐8 |
| [252] | T. A.Davis, Algorithm 832: UMFPACK V4.3-an unsymmetric‐pattern multifrontal method, ACM Trans. Math. Softw.30 (2004), 196-199. · Zbl 1072.65037 |
| [253] | X. S.Li, An overview of SuperLU: Algorithms, implementation, and user interface, ACM Trans. Math. Softw.31 (2005), 302-325. · Zbl 1136.65312 |
| [254] | M.Bollhöfer, A robust ILU with pivoting based on monitoring the growth of the inverse factors, Linear Algebra Appl.338 (2001), 201-218. · Zbl 0991.65028 |
| [255] | E.Chow and Y.Saad, Experimental study of ILU preconditioners for indefinite matrices, J. Comput. Appl. Math.86 (1997), 387-414. · Zbl 0891.65028 |
| [256] | M. T.Jones and P. E.Plassmann, An improved incomplete Cholesky factorization, ACM Trans. Math. Softw.21 (1995), 5-17. · Zbl 0886.65024 |
| [257] | Y.Notay, A multilevel block incomplete factorization preconditioning, Appl. Numer. Math.31 (1999), 209-225. · Zbl 0960.65053 |
| [258] | Y.Saad, ILUM: A multi‐elimination ILU preconditioner for general sparse matrices, SIAM J. Sci. Comput.17 (1996), 830-847. · Zbl 0858.65029 |
| [259] | S. C.Eisenstat, Efficient implementation of a class of preconditioned conjugate gradient methods, SIAM J. Sci. Stat. Comput.2 (1981), 1-4. · Zbl 0474.65020 |
| [260] | M.Benzi and M.Tůma, A robust incomplete factorization preconditioner for positive definite matrices, Numer. Linear Algebra Appl.10 (2003), 385-400. · Zbl 1071.65528 |
| [261] | R. E.Bank and C.Wagner, Multilevel ILU decomposition, Numer. Math.82 (1999), 543-576. · Zbl 0938.65063 |
| [262] | P. S.Vassilevski, Multilevel block factorization preconditioners: Matrix‐based analysis and algorithms for solving finite element equations, Springer‐Verlag, New York, NY, 2008. · Zbl 1170.65001 |
| [263] | J.‐S.Chai and K.‐C.Toh, Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming, Comput. Optim. Appl.36 (2007), 221-247. · Zbl 1148.90352 |
| [264] | J. C.Haws and C. D.Meyer, Preconditioning KKT systems. Technical report M&CT‐Tech‐01‐021, The Boeing Company, Seattle, WA, 2003. |
| [265] | O.Schenk, A.Wächter, and M.Weiser, Inertia‐revealing preconditioning for large‐scale nonconvex constrained optimization, SIAM J. Sci. Comput.31 (2008), 939-960. · Zbl 1194.35029 |
| [266] | N. I. M.Gould, M. E.Hribar, and J.Nocedal, On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput.23 (2001), 1376-1395. · Zbl 0999.65050 |
| [267] | C.Keller, N. I. M.Gould, and A. J.Wathen, Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl.21 (2000), 1300-1317. · Zbl 0960.65052 |
| [268] | L.Lukšan and J.Vlček, Indefinitely preconditioned inexact Newton method for large sparse equality constrained non‐linear programming problems, Numer. Linear Algebra Appl.5 (1998), 219-247. · Zbl 0937.65066 |
| [269] | N.Gould, D.Orban, and T.Rees, Projected Krylov methods for saddle‐point systems, SIAM J. Matrix Anal. Appl.35 (2014), 1329-1343. · Zbl 1312.65043 |
| [270] | H. S.Dollar et al., Implicit‐factorization preconditioning and iterative solvers for regularized saddle‐point systems, SIAM J. Matrix Anal. Appl.28 (2006), 170-189. · Zbl 1104.65310 |
| [271] | H. S.Dollar et al., Using constraint preconditioners with regularized saddle‐point problems, Comput. Optim. Appl.36 (2007), 249-270. · Zbl 1124.65033 |
| [272] | T.Rees and J.Scott, A comparative study of null‐space factorizations for sparse symmetric saddle point systems, Numer. Linear Algebra Appl.25 (2018), e2103. · Zbl 1424.65060 |
| [273] | C.Durazzi and V.Ruggiero, Indefinitely preconditioned conjugate gradient method for large sparse equality and inequality constrained quadratic problems, Numer. Linear Algebra Appl.10 (2003), 673-688. · Zbl 1071.65512 |
| [274] | L.Bergamaschi et al., Inexact constraint preconditioners for linear systems arising in interior point methods, Comput. Optim. Appl.36 (2007), 137-147. · Zbl 1148.90349 |
| [275] | N.Dyn and W. E.FergusonJr., The numerical solution of equality‐constrained quadratic programming problems, Math. Comput.41 (1983), 165-170. · Zbl 0527.49030 |
| [276] | A.Forsgren, P. E.Gill, and J. D.Griffin, Iterative solution of augmented systems arising in interior point methods, SIAM J. Optim.18 (2007), 666-690. · Zbl 1143.49024 |
| [277] | L.Lukšan, C.Matonoha, and J.Vlček, Interior‐point method for non‐linear non‐convex optimization, Numer. Linear Algebra Appl.11 (2004), 431-453. · Zbl 1164.90422 |
| [278] | M.Rozložník and V.Simoncini, Krylov subspace methods for saddle point problems with indefinite preconditioning, SIAM J. Matrix Anal. Appl.24 (2002), 368-391. · Zbl 1021.65016 |
| [279] | E.deSturler and J.Liesen, Block‐diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. Part I: Theory, SIAM J. Sci. Comput.26 (2005), 1598-1619. · Zbl 1078.65027 |
| [280] | J.Scott and M.Tůma, Improving the stability and robustness of incomplete symmetric indefinite factorization preconditioners, Numer. Linear Algebra Appl.24 (2017), e2099. · Zbl 1424.65022 |
| [281] | T.Rees, H. S.Dollar, and A. J.Wathen, Optimal solvers for PDE‐constrained optimization, SIAM J. Sci. Comput.32 (2010), 271-298. · Zbl 1208.49035 |
| [282] | M.Kočvara, D.Loghin, and J.Turner, Constraint interface preconditioning for topology optimization problems, SIAM J. Sci. Comput.38 (2016), A128-A145. · Zbl 06536062 |
| [283] | C.Greif and D.Schötzau, Preconditioners for saddle point linear systems with highly singular (1,1) blocks, Electron. Trans. Numer. Anal.22 (2006), 114-121. · Zbl 1112.65042 |
| [284] | C.Greif and D.Schötzau, Preconditioners for the discretized time‐harmonic Maxwell equations in mixed form, Numer. Linear Algebra Appl.14 (2007), 281-297. · Zbl 1199.78010 |
| [285] | G. H.Golub and C.Greif, On solving block‐structured indefinite linear systems, SIAM J. Sci. Comput.24 (2003), 2076-2092. · Zbl 1036.65033 |
| [286] | R.Fletcher, Practical methods of optimization, 2nd ed., John Wiley & Sons, Chichester, 1987. · Zbl 0905.65002 |
| [287] | M.Fortin and R.Glowinski, Augmented Lagrangian methods: Applications to the solution of numerical boundary‐value problems, Vol 15, North‐Holland, Amsterdam, Netherlands, 1983. · Zbl 0525.65045 |
| [288] | T.Rees and C.Greif, A preconditioner for linear systems arising from interior point optimization methods, SIAM J. Sci. Comput.29 (2007), 1992-2007. · Zbl 1155.65048 |
| [289] | B.Morini, V.Simoncini, and M.Tani, Spectral estimates for unreduced symmetric KKT systems arising from Interior Point methods, Numer. Linear Algebra Appl.23 (2016), 776-800. · Zbl 1413.65246 |
| [290] | Z.‐H.Cao, Augmentation block preconditioners for saddle point‐type matrices with singular (1,1) blocks, Numer. Linear Algebra Appl.15 (2008), 515-533. · Zbl 1212.65146 |
| [291] | S.‐Q.Shen, T.‐Z.Huang, and J.‐S.Zhang, Augmentation block triangular preconditioners for regularized saddle point problems, SIAM J. Matrix Anal. Appl.33 (2012), 721-741. · Zbl 1261.65033 |
| [292] | L.Bergamaschi et al., Quasi‐Newton preconditioners for the inexact Newton method, Electron. Trans. Numer. Anal.23 (2006), 76-87. · Zbl 1112.65045 |
| [293] | J. M.Martínez, A theory of secant preconditioners, Math. Comput.60 (1993), 681-698. · Zbl 0779.65034 |
| [294] | J. M.Martínez, An extension of the theory of secant preconditioners, J. Comput. Appl. Math.60 (1995), 115-125. · Zbl 0925.65092 |
| [295] | J. L.Morales and J.Nocedal, Automatic preconditioning by limited memory quasi‐Newton updating, SIAM J. Optim.10 (2000), 1079-1096. · Zbl 1020.65019 |
| [296] | S. G.Nash, Newton‐type minimization via the Lanczos method, SIAM J. Numer. Anal.21 (1984), 770-788. · Zbl 0558.65041 |
| [297] | D. P.O’Leary and A.Yeremin, The linear algebra of block quasi‐Newton updates, Linear Algebra Appl.212-213 (1994), 153-168. · Zbl 0861.65044 |
| [298] | L.Bergamaschi, R.Bru, and A.Martínez, Low‐rank update of preconditioners for the inexact Newton method with SPD Jacobian, Math. Comput. Model.54 (2011), 1863-1873. · Zbl 1235.65049 |
| [299] | J.Duintjer Tebbens and M.Tůma, Efficient preconditioning of sequences of nonsymmetric linear systems, SIAM J. Sci. Comput.29 (2007), 1918-1941. · Zbl 1155.65036 |
| [300] | J.Duintjer Tebbens and M.Tůma, Preconditioner updates for solving sequences of linear systems in matrix‐free environment, Numer. Linear Algebra Appl.17 (2010), 997-1019. · Zbl 1240.65092 |
| [301] | S.Bellavia et al., Updating constraint preconditioners for KKT systems in quadratic programming via low‐rank corrections, SIAM J. Optim.25 (2015), 1787-1808. · Zbl 1323.65064 |
| [302] | S.Bellavia et al., On the update of constraint preconditioners for regularized KKT systems, Comput. Optim. Appl.65 (2016), 339-360. · Zbl 1366.90153 |
| [303] | L.Bergamaschi et al., BFGS‐like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming, Numer. Linear Algebra Appl.25 (2018), e2144. · Zbl 1513.65176 |
| [304] | S.Gratton, A.Sartenaer, and J.Tshimanga, On a class of limited memory preconditioners for large scale linear systems with multiple right‐hand sides, SIAM J. Optim.21 (2011), 912-935. · Zbl 1273.65044 |
| [305] | M.Fisher et al., Low rank updates in preconditioning the saddle point systems arising from data assimilation problems, Optim. Method. Softw.33 (2018), 45-69. · Zbl 1398.90178 |
| [306] | S.Bellavia et al., Efficient preconditioner updates for shifted linear systems, SIAM J. Sci. Comput.33 (2011), 1785-1809. · Zbl 1236.65029 |
| [307] | M.Benzi and D.Bertaccini, Approximate inverse preconditioning for shifted linear systems, BIT Numer. Math.43 (2003), 231-244. · Zbl 1037.65043 |
| [308] | X.‐M.Gu et al., Restarted Hessenberg method for solving shifted nonsymmetric linear systems, J. Comput. Appl. Math.331 (2018), 166-177. · Zbl 1377.65042 |
| [309] | L.Bergamaschi, A survey of low‐rank updates of preconditioners for sequences of symmetric linear systems, Algorithms13 (2020), 100. |
| [310] | R.Bru et al., Preconditioned iterative methods for solving linear least squares problems, SIAM J. Sci. Comput.36 (2014), A2002-A2022. · Zbl 1303.65021 |
| [311] | GouldN., ScottJ.. The state‐of‐the‐art of preconditioners for sparse linear least‐squares problems. ACM Trans. Math. Softw. 2017;43:Art. 36. · Zbl 1380.65064 |
| [312] | ScottJ., TůmaM.. HSL_MI28: An efficient and robust limited‐memory incomplete Cholesky factorization code. ACM Trans. Math. Softw. 2014;40:Art. 24. · Zbl 1371.65031 |
| [313] | J.Scott and M.Tůma, On positive semidefinite modification schemes for incomplete Cholesky factorization, SIAM J. Sci. Comput.36 (2014), A609-A633. · Zbl 1298.65049 |
| [314] | J.Scott, On using Cholesky‐based factorizations and regularization for solving rank‐deficient sparse linear least‐squares problems, SIAM J. Sci. Comput.39 (2017), C319-C339. · Zbl 1372.65094 |
| [315] | Z.‐Z.Bai, I. S.Duff, and A. J.Wathen, A class of incomplete orthogonal factorization methods. I: Methods and theories, BIT Numer. Math.41 (2001), 53-70. · Zbl 0990.65038 |
| [316] | A. T.Papadopoulus, I. S.Duff, and A. J.Wathen, A class of incomplete orthogonal factorization methods. II: Implementation and results, BIT Numer. Math.45 (2005), 159-179. · Zbl 1080.65028 |
| [317] | A.Jennings and M. A.Ajiz, Incomplete methods for solving A^TAx = b, SIAM J. Sci. Stat. Comput.5 (1984), 978-987. · Zbl 0559.65013 |
| [318] | X.Wang, K. A.Gallivan, and R.Bramley, CIMGS: An incomplete orthogonal factorization preconditioner, SIAM J. Sci. Comput.18 (1997), 516-536. · Zbl 0871.65033 |
| [319] | N.Li and Y.Saad, MIQR: A multilevel incomplete QR preconditioner for large sparse least‐squares problems, SIAM J. Matrix Anal. Appl.28 (2006), 524-550. · Zbl 1113.65036 |
| [320] | M.Benzi and M.Tůma, A robust preconditioner with low memory requirements for large sparse least squares problems, SIAM J. Sci. Comput.25 (2003), 499-512. · Zbl 1042.65030 |
| [321] | J.Scott and M.Tůma, On signed incomplete Cholesky factorization preconditioners for saddle‐point systems, SIAM J. Sci. Comput.36 (2014), A2984-A3010. · Zbl 1310.65036 |
| [322] | GreifC., HeS., LiuP.. SYM‐ILDL: Incomplete LDL^T factorization of symmetric indefinite and skew‐symmetric matrices. ACM Trans. Math. Softw. 2017;44:Art. 1. · Zbl 1380.65061 |
| [323] | X.Cui and K.Hayami, Generalized approximate inverse preconditioners for least squares problems, Jpn. J. Ind. Appl. Math.26 (2009), 1-14. · Zbl 1171.65390 |
| [324] | X.Cui, K.Hayami, and J.‐F.Yin, Greville’s method for preconditioning least squares problems, Adv. Comput. Math.35 (2011), 243-269. · Zbl 1233.65027 |
| [325] | A.Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996. · Zbl 0847.65023 |
| [326] | A.Björck and J. Y.Yuan, Preconditioners for least squares problems by LU factorization, Electron. Trans. Numer. Anal.8 (1999), 26-35. · Zbl 0924.65034 |
| [327] | M.Arioli and I. S.Duff, Preconditioning linear least‐squares problems by identifying a basis matrix, SIAM J. Sci. Comput.37 (2015), S544-S561. · Zbl 1325.65041 |
| [328] | M.Benzi and M. K.Ng, Preconditioned iterative methods for weighted Toeplitz least squares problems, SIAM J. Matrix Anal. Appl.27 (2006), 1106-1124. · Zbl 1102.65050 |
| [329] | S.Börm and S.Le Borne, ℋ‐LU factorization in preconditioners for augmented Lagrangian and grad‐div stabilized saddle point systems, Int. J. Numer. Meth. Fl.68 (2012), 83-98. · Zbl 1426.76224 |
| [330] | Y. A.Erlangga, C.Vuik, and C. W.Oosterlee, Comparison of multigrid and incomplete LU shifted‐Laplace preconditioners for the inhomogeneous Helmholtz equation, Appl. Numer. Math.56 (2006), 648-666. · Zbl 1094.65041 |
| [331] | Z.‐Z.Bai, M. K.Ng, and Z.‐Q.Wang, Constraint preconditioners for symmetric indefinite matrices, SIAM J. Matrix Anal. Appl.31 (2009), 410-433. · Zbl 1195.65033 |
| [332] | P.Chidyagwai, S.Ladenheim, and D. B.Szyld, Constraint preconditioning for the coupled Stokes-Darcy system, SIAM J. Sci. Comput.38 (2016), A668-A690. · Zbl 1382.76162 |
| [333] | I.Perugia and V.Simoncini, Block‐diagonal and indefinite symmetric preconditioners for mixed finite element formulations, Numer. Linear Algebra Appl.7 (2000), 585-616. · Zbl 1051.65038 |
| [334] | M.Benzi, M. A.Olshanskii, and Z.Wang, Modified augmented Lagrangian preconditioners for the incompressible Navier-Stokes equations, Int. J. Numer. Meth. Fl.66 (2011), 486-508. · Zbl 1421.76152 |
| [335] | J. W.Pearson and A. J.Wathen, A new approximation of the Schur complement in preconditioners for PDE‐constrained optimization problems, Numer. Linear Algebra Appl.19 (2012), 816-829. · Zbl 1274.65187 |
| [336] | J.Schöberl and W.Zulehner, Symmetric indefinite preconditioners for saddle point problems with applications to PDE‐constrained optimization problems, SIAM J. Matrix Anal. Appl.29 (2007), 752-773. · Zbl 1154.65029 |
| [337] | J. Pearson, Fast iterative solvers for PDE‐constrained optimization problems, PhD Thesis, University of Oxford, 2013. |
| [338] | T.Rees and M.Stoll, Block‐triangular preconditioners for PDE‐constrained optimization, Numer. Linear Algebra Appl.17 (2010), 977-996. · Zbl 1240.65097 |
| [339] | W.Krendl, V.Simoncini, and W.Zulehner, Stability estimates and structural spectral properties of saddle point problems, Numer. Math.124 (2013), 183-213. · Zbl 1269.65032 |
| [340] | J. W.Pearson and A. J.Wathen, Fast iterative solvers for convection-diffusion control problems, Electron. Trans. Numer. Anal.40 (2013), 294-310. · Zbl 1287.49031 |
| [341] | J. W.Pearson, M.Stoll, and A. J.Wathen, Regularization‐robust preconditioners for time‐dependent PDE‐constrained optimization problems, SIAM J. Matrix Anal. Appl.33 (2012), 1126-1152. · Zbl 1263.65035 |
| [342] | Z.‐Z.Bai et al., Preconditioned MHSS iteration methods for a class of block two‐by‐two linear systems with applications to distributed control problems, IMA J. Numer. Anal.33 (2013), 343-369. · Zbl 1271.65100 |
| [343] | O.Axelsson, S.Farouq, and M.Neytcheva, Comparison of preconditioned Krylov subspace iteration methods for PDE‐constrained optimization problems: Poisson and convection-diffusion control, Numer. Alg.73 (2016), 631-663. · Zbl 1353.65059 |
| [344] | R.Herzog and E.Sachs, Preconditioned conjugate gradient method for optimal control problems with control and state constraints, SIAM J. Matrix Anal. Appl.31 (2010), 2291-2317. · Zbl 1209.49038 |
| [345] | R.Herzog and S.Mach, Preconditioned solution of state gradient constrained elliptic optimal control problems, SIAM J. Numer. Anal.54 (2016), 688-718. · Zbl 1335.49043 |
| [346] | J. W.Pearson and J.Gondzio, Fast interior point solution of quadratic programming problems arising from PDE‐constrained optimization problems, Numer. Math.137 (2017), 959-999. · Zbl 1379.65042 |
| [347] | J. W.Pearson, M.Stoll, and A. J.Wathen, Preconditioners for state constrained optimal control problems with Moreau-Yosida penalty function, Numer. Linear Algebra Appl.21 (2012), 81-97. · Zbl 1324.49026 |
| [348] | M.Porcelli, V.Simoncini, and M.Tani, Preconditioning of active‐set Newton methods for PDE‐constrained optimal control problems, SIAM J. Sci. Comput.37 (2015), S472-S502. · Zbl 1325.65066 |
| [349] | E.Haber and U. M.Ascher, Preconditioned all‐at‐once methods for large, sparse parameter estimation problems, Inverse Probl.17 (2001), 1847-1864. · Zbl 0995.65110 |
| [350] | J.Berns‐Müller, I. G.Graham, and A.Spence, Inexact inverse iteration for symmetric matrices, Linear Algebra Appl.416 (2006), 389-413. · Zbl 1101.65037 |
| [351] | G. H.Golub and Q.Ye, Inexact preconditioned conjugate gradient method with inner‐outer iteration, SIAM J. Sci. Comput.21 (1999), 1305-1320. · Zbl 0955.65022 |
| [352] | M. A.Freitag and A.Spence, Convergence theory for inexact inverse iteration applied to the generalised nonsymmetric eigenproblem, Electron. Trans. Numer. Anal.28 (2007), 40-64. · Zbl 1171.65025 |
| [353] | M. A.Freitag and A.Spence, Convergence of inexact inverse iteration with application to preconditioned iterative solves, BIT Numer. Math.47 (2007), 27-44. · Zbl 1121.65038 |
| [354] | V.Simoncini and L.Eldén, Inexact Rayleigh quotient‐type methods for eigenvalue computations, BIT Numer. Math.42 (2002), 159-182. · Zbl 1003.65033 |
| [355] | M. A.Freitag and A.Spence, A tuned preconditioner for inexact inverse iteration applied to Hermitian eigenvalue problems, IMA J. Numer. Anal.28 (2008), 522-551. · Zbl 1151.65030 |
| [356] | D. B.Szyld and F.Xue, Efficient preconditioned inner solves for inexact Rayleigh quotient iteration and their connections to the single‐vector Jacobi-Davidson method, SIAM J. Matrix Anal. Appl.32 (2011), 993-1018. · Zbl 1238.65028 |
| [357] | M.Robbé, M.Sadkane, and A.Spence, Inexact inverse subspace iteration with preconditioning applied to non‐Hermitian eigenvalue problems, SIAM J. Matrix Anal. Appl.31 (2009), 92-113. · Zbl 1269.65036 |
| [358] | M. A.Freitag and A.Spence, Shift‐invert Arnoldi’s method with preconditioned iterative solves, SIAM J. Matrix Anal. Appl.31 (2009), 942-969. · Zbl 1204.65034 |
| [359] | F.Xue and H. C.Elman, Fast inexact implicitly restarted Arnoldi method for generalized eigenvalue problems with spectral transformation, SIAM J. Matrix Anal. Appl.33 (2012), 433-459. · Zbl 1263.65041 |
| [360] | G. H.Golub and Q.Ye, An inverse free preconditioned Krylov subspace method for symmetric generalized eigenvalue problems, SIAM J. Sci. Comput.24 (2002), 312-334. · Zbl 1016.65017 |
| [361] | R. B.Morgan and D. S.Scott, Preconditioning the Lanczos algorithm for sparse symmetric eigenvalue problems, SIAM J. Sci. Comput.14 (1993), 585-593. · Zbl 0791.65022 |
| [362] | L.Wu, F.Xue, and A.Stathopoulos, TRPL+K: Thick‐restart preconditioned Lanczos+K method for large symmetric eigenvalue problems, SIAM J. Sci. Comput.41 (2019), A1013-A1040. · Zbl 1431.65047 |
| [363] | O.Taussky, The role of symmetric matrices in the study of general matrices, Linear Algebra Appl.5 (1972), 147-154. · Zbl 0238.15008 |
| [364] | S.Hon and A.Wathen, Circulant preconditioners for analytic functions of Toeplitz matrices, Numer. Alg.79 (2018), 1211-1230. · Zbl 1404.65015 |
| [365] | J.Pestana and A. J.Wathen, A preconditioned MINRES method for nonsymmetric Toeplitz matrices, SIAM J. Matrix Anal. Appl.36 (2015), 273-288. · Zbl 1315.65034 |
| [366] | J.Pestana, Preconditioners for symmetrized Toeplitz and multilevel Toeplitz matrices, SIAM J. Matrix Anal. Appl.40 (2019), 870-887. · Zbl 1420.65024 |
| [367] | P.Ferrari et al., The eigenvalue distribution of special 2‐by‐2 block matrix‐sequences with applications to the case of symmetrized Toeplitz structures, SIAM J. Matrix Anal. Appl.40 (2019), 1066-1086. · Zbl 1426.15041 |
| [368] | M.Mazza and J.Pestana, Spectral properties of flipped Toeplitz matrices and related preconditioning, BIT Numer. Math.59 (2019), 463-482. · Zbl 1417.15045 |
| [369] | J.Pestana, Nonstandard inner products and preconditioned iterative methods, PhD Thesis, University of Oxford, 2011. |
| [370] | A.Günnel, R.Herzog, and E.Sachs, A note on preconditioners and scalar products in Krylov subspace methods for self‐adjoint problems in Hilbert space, Electron. Trans. Numer. Anal.41 (2014), 13-20. · Zbl 1295.65062 |
| [371] | J. H.Bramble and J. E.Pasciak, A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems, Math. Comput.50 (1988), 1-17. · Zbl 0643.65017 |
| [372] | P.Krzyżanowski, On block preconditioners for saddle point problems with singular or indefinite (1,1) block, Numer. Linear Algebra Appl.18 (2011), 123-140. · Zbl 1249.65059 |
| [373] | P.Concus and G. H.Golub, A generalized conjugate gradient method for nonsymmetric systems of linear equations, Springer, New York, NY, 1976, 56-65. · Zbl 0344.65020 |
| [374] | O.Widlund, A Lanczos method for a class of nonsymmetric systems of linear equations, SIAM J. Numer. Anal.15 (1978), 801-812. · Zbl 0398.65030 |
| [375] | D.Calvetti, B.Lewis, and L.Reichel, On the regularizing properties of the GMRES method, Numer. Math.91 (2002), 605-625. · Zbl 1022.65044 |
| [376] | M.Hanke, On Lanczos based methods for the regularization of discrete ill‐posed problems, BIT Numer. Math.41 (2001), 1008-1018. |
| [377] | T. K.Jensen and P. C.Hansen, Iterative regularization with minimum‐residual methods, BIT Numer. Math.47 (2007), 103-120. · Zbl 1113.65037 |
| [378] | M.Hanke, J. G.Nagy, and R. J.Plemmons, Preconditioned iterative regularization for ill‐posed problems, in Numerical Linear Algebra, L.Reichel (ed.), A.Ruttan (ed.), and R. S.Varga (ed.), Eds., de Gruyter, Berlin, Germany, 1993, 141-164. · Zbl 0794.65039 |
| [379] | M.Hanke and J.Nagy, Inverse Toeplitz preconditioners for ill‐posed problems, Linear Algebra Appl.284 (1998), 137-156. · Zbl 0935.65037 |
| [380] | J. G.Nagy and K. M.Palmer, Steepest descent, CG, and iterative regularization of ill‐posed problems, BIT Numer. Math.43 (2003), 1003-1017. · Zbl 1045.65034 |
| [381] | L.Eldén and V.Simoncini, Solving ill‐posed linear systems with GMRES and a singular preconditioner, SIAM J. Matrix Anal. Appl.33 (2012), 1369-1394. · Zbl 1263.65033 |
| [382] | Z.Ranjbar and L.Eldén, Solving an ill‐posed Cauchy problem for a two‐dimensional parabolic PDE with variable coefficients using a preconditioned GMRES method, SIAM J. Sci. Comput.36 (2014), B868-B886. · Zbl 1332.65139 |
| [383] | J.Baglama and L.Reichel, Decomposition methods for large linear discrete ill‐posed problems, J. Comput. Appl. Math.198 (2007), 332-343. · Zbl 1106.65035 |
| [384] | S.Gazzola and J. G.Nagy, Generalized Arnoldi-Tikhonov method for sparse reconstruction, SIAM J. Sci. Comput.36 (2014), B225-B247. · Zbl 1296.65061 |
| [385] | P. C.Hansen and T. K.Jensen, Smoothing‐norm preconditioning for regularizing minimum‐residual methods, SIAM J. Matrix Anal. Appl.29 (2006), 1-14. · Zbl 1154.65028 |
| [386] | D.Calvetti, Preconditioned iterative methods for linear discrete ill‐posed problems from a Bayesian inversion perspective, J. Comput. Appl. Math.198 (2007), 378-395. · Zbl 1101.65043 |
| [387] | V.Rokhlin and M.Tygert, A fast randomized algorithm for overdetermined linear least‐squares regression, Proc. Natl. Acad. Sci.105 (2008), 13212-13217. · Zbl 1513.62144 |
| [388] | P.Drineas et al., Faster least squares approximation, Numer. Math.117 (2011), 219-249. · Zbl 1218.65037 |
| [389] | H.Avron, P.Maymounkov, and S.Toledo, Blendenpik: Supercharging LAPACK’s least‐squares solver, SIAM J. Sci. Comput.32 (2010), 1217-1236. · Zbl 1213.65069 |
| [390] | E. S.Coakley, V.Rokhlin, and M.Tygert, A fast randomized algorithm for orthogonal projection, SIAM J. Sci. Comput.33 (2011), 849-868. · Zbl 1368.65061 |
| [391] | X.Meng, M. A.Saunders, and M. W.Mahoney, LSRN: A parallel iterative solver for strongly over‐ or underdetermined systems, SIAM J. Sci. Comput.36 (2014), C95-C118. · Zbl 1298.65053 |
| [392] | J.Yang et al., Weighted SGD for ℓ_p regression with randomized preconditioning, J. Mach. Learn. Res.18 (2018), 1-43. · Zbl 1448.68381 |
| [393] | D.Calvetti and E.Somersalo, Priorconditioners for linear systems, Inverse Probl.21 (2005), 1397-1418. · Zbl 1087.65044 |
| [394] | D.Calvetti, D.McGivney, and E.Somersalo, Left and right preconditioning for electrical impedance tomography with structural information, Inverse Probl.28 (2012), 055015. · Zbl 1243.65133 |
| [395] | P.Hennig, Probabilistic interpretation of linear solvers, SIAM J. Optim.25 (2015), 234-260. · Zbl 1356.49042 |
| [396] | J.Cockayne et al., A Bayesian conjugate gradient method (with discussion), Bayesian Anal.14 (2019), 937-1012. · Zbl 1430.62024 |
| [397] | S.Bartels et al., Probabilistic linear solvers: A unifying view, Stat. Comput.29 (2019), 1249-1263. · Zbl 1435.62027 |
| [398] | L.Grasedyck, Hierarchical singular value decomposition of tensors, SIAM J. Matrix Anal. Appl.31 (2010), 2029-2054. · Zbl 1210.65090 |
| [399] | W.Hackbusch and S.Kühn, A new scheme for the tensor representation, J. Fourier Anal. Appl.15 (2009), 706-722. · Zbl 1188.15022 |
| [400] | I. V.Oseledets, Tensor‐train decomposition, SIAM J. Sci. Comput.33 (2011), 2295-2317. · Zbl 1232.15018 |
| [401] | I. V.Oseledets, Approximation of 2^d × 2^d matrices using tensor decomposition, SIAM J. Matrix Anal. Appl.31 (2010), 2130-2145. · Zbl 1200.15005 |
| [402] | E. E.Tyrtyshnikov, Tensor approximation of matrices generated by asymptotically smooth functions, Sbornik Math.194 (2003), 147-160. · Zbl 1067.65044 |
| [403] | D.Kressner and C.Tobler, Krylov subspace methods for linear systems with tensor product structure, SIAM J. Matrix Anal. Appl.31 (2010), 1688-1714. · Zbl 1208.65044 |
| [404] | D.Palitta and V.Simoncini, Optimality properties of Galerkin and Petrov-Galerkin methods for linear matrix equations, Vietnam J. Math. (2020). https://doi.org/10.1007/s10013‐020‐00390‐7. · Zbl 1466.65031 · doi:10.1007/s10013‐020‐00390‐7 |
| [405] | R.Andreev and C.Tobler, Multilevel preconditioning and low‐rank tensor iteration for space‐time simultaneous discretizations of parabolic PDEs, Numer. Linear Alg. Appl.22 (2015), 317-337. · Zbl 1363.65156 |
| [406] | T.Breiten, V.Simoncini, and M.Stoll, Low‐rank solvers for fractional differential equations, Electron. Trans. Numer. Anal.45 (2016), 107-132. · Zbl 1338.65071 |
| [407] | S. V.Dolgov, TT‐GMRES: Solution to a linear system in the structured tensor format, Russ. J. Numer. Anal. M.28 (2013), 149-172. · Zbl 1266.65050 |
| [408] | B. N.Khoromskij, Tensor‐structured preconditioners and approximate inverse of elliptic operators in ℝ^d, Constr. Approx.30 (2009), 599-620. · Zbl 1185.65051 |
| [409] | S.Dolgov and M.Stoll, Low‐rank solution to an optimization problem constrained by the Navier-Stokes equations, SIAM J. Sci. Comput.39 (2017), A255-A280. · Zbl 1381.76259 |
| [410] | M.Stoll and T.Breiten, A low‐rank in time approach to PDE‐constrained optimization, SIAM J. Sci. Comput.37 (2015), B1-B29. · Zbl 1330.65153 |
| [411] | S.Dolgov et al., Fast tensor product solvers for optimization problems with fractional differential equations as constraints, Appl. Math. Comput.273 (2016), 604-623. · Zbl 1410.49018 |
| [412] | G.Heidel, V.Khoromskaia, B. N.Khoromskij, V.Schulz, Tensor product method for fast solution of optimal control problems with fractional multidimensional Laplacian in constraints, arXiv e‐prints. 2020: arXiv:1809.01971. |
| [413] | E. C.Carson et al., The numerical stability analysis of pipelined conjugate gradient methods: Historical context and methodology, SIAM J. Sci. Comput.40 (2018), A3549-A3580. · Zbl 1416.65080 |
| [414] | J.Dongarra, M. A.Heroux, and P.Luszczek, High‐performance conjugate‐gradient benchmark: A new metric for ranking high‐performance computing systems, Int. J. High Perform. Comput. Appl.30 (2016), 3-10. |
| [415] | M.Hoemmen, Communication‐avoiding Krylov subspace methods, PhD Thesis, University of California, Berkeley, 2010. |
| [416] | H.Anzt et al., Efficiency of general Krylov methods on GPUs - An experimental study, in IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2016, 683-691. |
| [417] | V.Eijkhout, Introduction to high performance scientific computing, 2nd ed., Lulu Group International, 2015. |
| [418] | B.Bergen et al., A massively parallel multigrid method for finite elements, Comput. Sci. Eng.8 (2006), 56-62. |
| [419] | V. E.Henson and U. M.Yang, BoomerAMG: A parallel algebraic multigrid solver and preconditioner, Appl. Numer. Math.41 (2002), 155-177. · Zbl 0995.65128 |
| [420] | E.Chow, Parallel implementation and practical use of sparse approximate inverse preconditioners with a priori sparsity patterns, Int. J. High Perform. Comput. Appl.15 (2001), 56-74. |
| [421] | JannaC., FerronatoM., SartorettoF., GambolatiG.. FSAIPACK: A software package for high‐performance factored sparse approximate inverse preconditioning. ACM Trans. Math. Softw.. 2015;41:Art. 10. · Zbl 1369.65052 |
| [422] | S.Badia, A. F.Martín, and J.Principe, Multilevel balancing domain decomposition at extreme scales, SIAM J. Sci. Comput.38 (2016), C22-C52. · Zbl 1334.65217 |
| [423] | V. A. P.Magri et al., Multilevel approaches for FSAI preconditioning, Numer. Linear Algebra Appl.25 (2018), e2183. · Zbl 1513.65056 |
| [424] | M.Bernaschi et al., A dynamic pattern factored sparse approximate inverse preconditioner on graphics processing units, SIAM J. Sci. Comput.41 (2019), C139-C160. · Zbl 1420.65020 |
| [425] | E.Chow and A.Patel, Fine‐grained parallel incomplete LU factorization, SIAM J. Sci. Comput.37 (2015), C169-C193. · Zbl 1320.65048 |
| [426] | H.Anzt et al., Incomplete sparse approximate inverses for parallel preconditioning, Parallel Comput.71 (2018), 1-22. |
| [427] | H.Ibeid, R.Yokota, D.Keyes, A matrix‐free preconditioner for the Helmholtz equation based on the fast multipole method, arXiv e‐prints. 2016: arXiv:1608.02461. |
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.
