期刊
LINEAR ALGEBRA AND ITS APPLICATIONS
卷 394, 期 -, 页码 1-24出版社
ELSEVIER SCIENCE INC
DOI: 10.1016/j.laa.2004.08.019
关键词
linear programming; interior point methods; preconditioning; augmented system
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据