AINVk: a Class of Approximate Inverse Preconditioners based on Krylov-subspace methods, for Large Indefinite Linear Systems
Giovanni Fasano (fasanounive.it)
Abstract: We propose a class of preconditioners for symmetric linear systems arising from numerical analysis and nonconvex optimization frameworks. Our preconditioners are specifically suited for large indefinite linear systems and may be obtained as by-product of Krylov-subspace solvers, as well as by applying L-BFGS updates. Moreover, our proposal is also suited for the solution of a sequence of linear systems, say Ax=b_i or A_ix=b_i, where respectively the right-hand side changes or the system matrix slightly changes, too. Each preconditioner in our class is identified by setting the values of a pair of parameters and a scaling matrix, which are user-dependent, and may be chosen according to the structure of the problem in hand. We provide theoretical properties of our preconditioners, discussing the relation with the proposals by Gratton et al.'11, Morales et al.'00. In particular, we show that our preconditioners both shift some eigenvalues of the indefinite system matrix to +/-1, and are able to control the condition number of the preconditioned matrix. We study some structural properties of our class of preconditioners, and report the results on a comparative numerical experience with LMP preconditioners in Gratton et al.'11. The experience is carried on first considering some relevant linear systems proposed in the literature. Then, we embed our preconditioners within a linesearch-based truncated Newton method, where sequences of linear systems (namely Newton's equations), are required to be solved. We perform an extensive numerical testing over the entire large scale unconstrained optimization test set of CUTEr collection.
Keywords: Preconditioners, large indefinite linear systems, large scale nonconvex optimization, Krylov-subspace methods
Category 1: Nonlinear Optimization
Category 2: Nonlinear Optimization (Unconstrained Optimization)
Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization)
Citation: G. Fasano, M. Roma, "A class of preconditioners for large indefinite linear systems, as by-product of Krylov subspace methods: Part I", ,Working Paper n. 4/2011, June 2011, Dept. of Management, Venice, ISSN: 2239-2734. G. Fasano, M. Roma, "A class of preconditioners for large indefinite linear systems, as by-product of Krylov subspace methods: Part II", ,Working Paper n. 5/2011, June 2011, Dept. of Management, Venice, ISSN: 2239-2734.
Entry Submitted: 05/22/2012
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|