Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/76159
Type: Artigo de periódico
Title: A new class of preconditioners for large-scale linear systems from interior point methods for linear programming
Author: Oliveira, ARL
Sorensen, DC
Abstract: A new class of preconditioners for the iterative solution of the linear systems arising from interior point methods is proposed. For many of these methods, the linear systems are symmetric and indefinite. The system can be reduced to a system of normal equations which is positive definite. We show that all preconditioners for the normal equations system have an equivalent for the augmented system while the opposite is not true. The new class of preconditioners works better near a solution of the linear programming problem when the matrices are highly ill conditioned. The preconditioned system can be reduced to a positive definite one. The techniques developed for a competitive implementation are rather sophisticated since the subset of columns is not known a priori. The new preconditioner applied to the conjugate gradient method compares favorably with the Cholesky factorization approach on large-scale problems whose Cholesky factorization contains too many nonzero entries. (C) 2004 Elsevier Inc. All rights reserved.
Subject: linear programming
interior point methods
preconditioning
augmented system
Country: EUA
Editor: Elsevier Science Inc
Rights: fechado
Identifier DOI: 10.1016/j.laa.2004.08.019
Date Issue: 2005
Appears in Collections:Artigos e Materiais de Revistas Científicas - Unicamp

Files in This Item:
File Description SizeFormat 
WOS000225181600001.pdf284.02 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.