Interior-Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints
25
Citation
33
Reference
10
Related Paper
Citation Trend
Keywords:
Solver
Interior point method
Iterated function
A new preconditioner for symmetric positive definite systems is proposed, analyzed, and tested. The preconditioner, compressed incomplete modified Gram--Schmidt (CIMGS), is based on an incomplete orthogonal factorization. CIMGS is robust both theoretically and empirically, existing (in exact arithmetic) for any full rank matrix. Numerically it is more robust than an incomplete Cholesky factorization preconditioner (IC) and a complete Cholesky factorization of the normal equations. Theoretical results show that the CIMGS factorization has better backward error properties than complete Cholesky factorization. For symmetric positive definite M-matrices, CIMGS induces a regular splitting and better estimates the complete Cholesky factor as the set of dropped positions gets smaller. CIMGS lies between complete Cholesky factorization and incomplete Cholesky factorization in its approximation properties. These theoretical properties usually hold numerically, even when the matrix is not an M-matrix. When the drop set satisfies a mild and easily verified (or enforced) property, the upper triangular factor CIMGS generates is the same as that generated by incomplete Cholesky factorization. This allows the existence of the IC factorization to be guaranteed, based solely on the target sparsity pattern.
Minimum degree algorithm
Dixon's factorization method
Matrix (chemical analysis)
Cite
Citations (50)
Interior point method
Cite
Citations (56)
A practical out-of-core Cholesky factorization scheme is introduced that is based on reorganizations of the matrix data structure during the factorization. It is applicable to the factorization of both dense and sparse matrices. The scheme can be regarded as a simple extension of the conventional in-core sparse factorization method. It is highly adaptive in the sense that it will run successfully in a range of storage sizes. Experimental results on some large sparse practical problems are provided; they show significant reduction in storage requirement for Cholesky factors with little increase (and sometimes decrease) in execution time.
Minimum degree algorithm
Matrix (chemical analysis)
Cite
Citations (15)
This work studies limited memory preconditioners for linear symmetric positive definite systems of equations. Connections are established between a partial Cholesky factorization from the literature and a variant of Quasi-Newton type preconditioners. Then, a strategy for enhancing the Quasi-Newton preconditioner via available information is proposed. Numerical experiments show the behaviour of the resulting preconditioner.
Minimum degree algorithm
Quasi-Newton method
Cite
Citations (2)
Dixon's factorization method
Minimum degree algorithm
Matrix (chemical analysis)
Cite
Citations (12)
Sparse approximate inverse(SAI)preconditioner based on a revised Cholesky factorization is presented in this paper.The traditional Cholesky factorization is firstly revised to cope with the matrix arising from electric field integral equations,which is a complex symmetric matrix,then this revised Cholesky factorization is applied to construct SAI preconditioner for the multilevel fast multipole algorithm(MLFMA).Numerical experiments show that SAI preconditioner constructed by the revised Cholesky factorization performs more efficiently than the previous SAI constructed from QR factorization.
Minimum degree algorithm
Matrix (chemical analysis)
Cite
Citations (0)
Cite
Citations (7)
Abstract Consider the solution of large sparse symmetric positive definite linear systems using the preconditioned conjugate gradient method. On sequential architectures, incomplete Cholesky factorizations provide effective preconditioning for systems from a variety of application domains, some of which may have widely differing preconditioning requirements. However, incomplete factorization based preconditioners are not considered suitable for multiprocessors. This is primarily because the triangular solution step required to apply the preconditioner (at each iteration) does not scale well due to the large latency of inter‐processor communication. We propose a new approach to overcome this performance bottleneck by coupling incomplete factorization with a selective inversion scheme to replace triangular solutions by scalable matrix–vector multiplications. We discuss our algorithm, analyze its communication latency for model sparse linear systems, and provide empirical results on its performance and scalability. Copyright © 2003 John Wiley & Sons, Ltd.
Minimum degree algorithm
Solver
Cite
Citations (16)
This study aims to improve the computation of the search direction in the primal-dual Interior Point Method through preconditioned iterative methods. It is about a hybrid approach that combines the Controlled Cholesky Factorization preconditioner and the Splitting preconditioner. This approach has shown good results, however, in these preconditioners there are factors that reduce their efficiency, such as faults on the diagonal when performing the Cholesky factorization, as well as a demand for excessive memory, among others. Thus, some modifications are proposed in these preconditioners, as well as a new phase change, in order toimprove the performance of the hybrid preconditioner. In the Controlled Cholesky Factorization, the parameters that control the filling and the correction of the faults which occur on the diagonal are modified. It considers the relationship between the components from Controlled Cholesky Factorization obtained before and after the fault on the diagonal. In the Splitting preconditioner, in turn, a sparse base is constructed through an appropriate ordering of the columns from constrained matrix optimization problem. In addition, a theoretical result is presented, which shows that, with the proposed ordering, the condition number of the preconditioned Normal Equation matrix with the Splitting preconditioner is uniformly limited by an amount that depends only on the original data of the problem and not on the iteration of the Interior Point Method. Numerical experiments with large scale problems, corroborate the robustness and computational efficiency from this approach.
Minimum degree algorithm
Condition number
Matrix (chemical analysis)
Interior point method
Robustness
Cite
Citations (1)
We present a new method for constructing incomplete Cholesky factorization preconditioners for use in solving large sparse symmetric positive-definite linear systems. This method uses max-plus algebra to predict the positions of the largest entries in the Cholesky factor and then uses these positions as the sparsity pattern for the preconditioner. Our method builds on the max-plus incomplete LU factorization preconditioner recently proposed in [J. Hook and F. Tisseur, SIAM J. Matrix Anal. Appl., 38 (2017), pp. 1160--1189] but is applied to symmetric positive-definite matrices, which comprise an important special case for the method and its application. An attractive feature of our approach is that the sparsity pattern of each column of the preconditioner can be computed in parallel. Numerical comparisons are made with other incomplete Cholesky factorization preconditioners using problems from a range of practical applications. We demonstrate that the new preconditioner can outperform traditional level-based preconditioners and offer a parallel alternative to a serial limited-memory--based approach.
Minimum degree algorithm
Matrix (chemical analysis)
Cite
Citations (4)