Refined spectral estimates for preconditioned saddle point linear systems in a non-standard inner product

Abstract

Linear systems in saddle point form arise in a wide variety of applications including fluid dynamics, elasticity and constrained optimization problems. Indefinite preconditioners lead to effective strategies for solving these systems. Short term iterative methods such as conjugate gradients can be employed if an inner product is determined that makes the preconditioned coefficient matrix symmetric and positive definite with respect to that inner product. We present new detailed spectral estimates for such preconditioned problems that improve our understanding of the expected behavior of indefinite preconditioners when applied to real problems. References

• S. F. Ashby, T. A. Manteuffel, P. E. Saylor. A Taxonomy for Conjugate Gradients Methods. SIAM J. on Numer. Anal., 27:1542--1568, 1990. doi:10.1137/0727091
• O. Axelsson. Solution of linear systems of equations: iterative methods. In V. A. Barker, editor, Sparse matrix techniques, 572 of Lecture notes in Mathematics, pp. 1--51. Springer, 1997.
• B. Beckermann and A. B. J. Kuijlaars. Superlinear Convergence of Conjugate Gradients. SIAM J. Numer. Anal., 39:300--329, 2001. doi:10.1137/S0036142999363188
• M. Benzi, G. H. Golub and J. Liesen, Numerical Solution of Saddle Point Problems. Acta Numerica, 14:1--137, 2005. doi:10.1017/S0962492904000212
• J. Boyle, M. D. Mihajlovic, and J. A. Scott. HSL_MI20: an efficient AMG preconditioner for finite element problems in 3D. Int. J. Numer. Meth. Engng., 82:64--98, 2010. doi:10.1002/nme.2758
• J. H. Bramble and J. E. Pasciak. A preconditioning technique for indefinite systems resulting from mixed approximations of elliptic problems. Math. Comp., 50:1--17, 1988. doi:10.1090/S0025-5718-1988-0917816-8
• H. S. Dollar, N. I. M. Gould, M. Stoll and A. J. Wathen. Preconditioning saddle-point systems with applications in optimization. SIAM J. Sci. Comput., 32:249--270, 2010. doi:10.1137/080727129
• V. Faber, T. A. Manteffel. Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method. SIAM J. Numer. Anal., 21:352-362, 1984. doi:10.1137/0721026
• R. Herzog and E. Sachs. Preconditioned conjugate gradient method for optimal control problems with control and state constraints, SIAM J. Matrix Anal. Appl., 31: 2291--2317, 2010. doi:10.1137/090779127
• W. D. Joubert and D. M. Young. Necessary and Sufficient Conditions for the Simplification of Generalized Conjugate-Gradients Algorithms. Linear Algebra Appl., 88/89:449-485, 1987. doi:10.1016/0024-3795(87)90120-0
• C. Keller, N. I. M. Gould, and A. J. Wathen. Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21:1300--1317, 2000. doi:10.1137/S0895479899351805
• L. Luksan and J. Vlcek. Indefinitely preconditioned inexact Newton method for large sparse equality constrained non-linear programming problems, Numer. Linear Algebra Appl., 5:219--247, 1998. doi:10.1002/(SICI)1099-1506(199805/06)5:3<219::AID-NLA134>3.0.CO;2-7
• MathWorks, Matlab 7, September 2004. http://www.mathworks.com.au/
• J. Pestana and J. A. Wathen. Combination preconditioning of saddle point systems for positive definiteness, Numer. Linear Algebra Appl., 2012. doi:10.1002/nla.1843
• M. Rozloznik and V. Simoncini. Krylov subspace methods for saddle point problem with indefinite preconditioning. SIAM J. Matrix Anal. Appl., 24(2):368--391, 2002. doi:10.1137/S0895479800375540
• J. W. Ruge and K. Stuben. Algebraic Multigrid, in Multigrid Methods, Frontiers Appl. Math., SIAM, Philadelphia, 1987.
• J. Schoberl and W. Zulehner. Symmetric Indefinite Preconditioners for Saddle Point Problems with Applications to PDE-Constrained Optimization Problems. SIAM J. Matrix Anal. Appl., 29:752--773, 2007. doi:10.1137/060660977
• M. Stoll and A. J. Wathen. Combination preconditioning and the Bramble-Pasciak\(^+\) preconditioner. SIAM J. Matrix Anal. Appl., 30:582--608, 2008. doi:10.1137/070688961
• H. S. Thorne. Distributed Control and Constraint Preconditioners. Comput. and Fluids, 46:461--466, 2011. doi:10.1016/j.compfluid.2011.01.019