Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods

We devise a hybrid approach for solving linear systems arising from interior point methods applied to linear programming problems. These systems are solved by preconditioned conjugate gradient method that works in two phases. During phase I it uses a kind of incomplete Cholesky preconditioner such that fill-in can be controlled in terms of available memory. As the optimal solution of the problem is approached, the linear systems becomes highly ill-conditioned and the method changes to phase II. In this phase a preconditioner based on the LU factorization is found to work better near a solution of the LP problem. The numerical experiments reveal that the iterative hybrid approach works better than Cholesky factorization on some classes of large-scale problems.     

Alternating oblique projections for coupled linear systems

In this work we propose the use of alternating oblique projections (AOP) for the solution of the saddle points systems resulting from the discretization of domain decomposition problems. These systems are called coupled linear systems. The AOP method is a descent method in which the descent direction is defined by using alternating oblique projections onto the search subspaces. We prove that this method is a preconditioned simple gradient (Uzawa) method with a particular preconditioner. Finally, a preconditioned conjugate gradient based version of AOP is proposed. AMS subject classification 65F10, 65N22, 65Y05     

Suitable iterative methods for solving the linear system arising in the three fields domain decomposition method

There are two approaches for applying substructuring preconditioner for the linear system corresponding to the discrete Steklov–Poincaré operator arising in the three fields domain decomposition method for elliptic problems. One of them is to apply the preconditioner in a common way, i.e. using an iterative method such as preconditioned conjugate gradient method [S. Bertoluzza, Substructuring preconditioners for the three fields domain decomposition method, I.A.N.-C.N.R, 2000] and the other one is to apply iterative methods like for instance bi-conjugate gradient method, conjugate gradient square and etc. which are efficient for nonsymmetric systems (the preconditioned system will be nonsymmetric). In this paper, second approach will be followed and extensive numerical tests will be presented which imply that the considered iterative methods are efficient.     

A new approach for finding a basis for the splitting preconditioner for linear systems from interior point methods

The class of splitting preconditioners for the iterative solution of linear systems arising from Mehrotra’s predictor-corrector method for large scale linear programming problems needs to find a basis through a sophisticated process based on the application of a rectangular LU factorization. This class of splitting preconditioners works better near a solution of the linear programming problem when the matrices are highly ill-conditioned. In this study, we develop and implement a new approach to find a basis for the splitting preconditioner, based on standard rectangular LU factorization with partial permutation of the scaled transpose linear programming constraint matrix. In most cases, this basis is better conditioned than the existing one. In addition, we include a penalty parameter in Mehrotra’s predictor-corrector method in order to reduce ill-conditioning of the normal equations matrix. Computational experiments show a reduction in the average number of iterations of the preconditioned conjugate gradient method. Also, the increased efficiency and robustness of the new approach become evident by the performance profile.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

Parallel algorithms for solving linear systems with block-tridiagonal matrices on multi-core CPU with GPU

For solving systems of linear algebraic equations with block-tridiagonal matrices arising in geoelectrics problems, the parallel matrix sweep algorithm, conjugate gradient method with preconditioner, and square root method are proposed and implemented numerically on multi-core CPU Intel with graphics processors NVIDIA. Investigation of efficiency and optimization of parallel algorithms for solving the problem with quasi-model data are performed.     

Updating preconditioners for permuted non-symmetric linear systems

We consider the solution of a sequence of nonsymmetric linear systems arising from a supersonic model problem by exploiting triangular preconditioner updates. In addition, we demonstrate how the power of the updates can be enhanced by permuting the entire sequence beforehand with a physically motivated reordering of unknowns. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

Preconditioned tensor format conjugate gradient squared and biconjugate gradient stabilized methods for solving stein tensor equations

This article is concerned with solving the high order Stein tensor equation arising in control theory. The conjugate gradient squared (CGS) method and the biconjugate gradient stabilized (BiCGSTAB) method are attractive methods for solving linear systems. Compared with the large-scale matrix equation, the equivalent tensor equation needs less storage space and computational costs. Therefore, we present the tensor formats of CGS and BiCGSTAB methods for solving high order Stein tensor equations. Moreover, a nearest Kronecker product preconditioner is given and the preconditioned tensor format methods are studied. Finally, the feasibility and effectiveness of the new methods are verified by some numerical examples.     

A High-Quality Preconditioning Technique for Multi-Length-Scale Symmetric Positive Definite Linear Systems

We study preconditioning techniques used in conjunction with the conjugate gradient method for solving multi-length-scale symmetric positive definite linear systems originating from the quantum Monte Carlo simulation of electron interaction of correlated materials. Existing preconditioning techniques are not designed to be adaptive to varying numerical properties of the multi-length-scale systems. In this paper, we propose a hybrid incomplete Cholesky (HIC) preconditioner and demonstrate its adaptivity to the multi-length-scale systems. In addition, we propose an extension of the compressed sparse column with row access (CSCR) sparse matrix storage format to efficiently accommodate the data access pattern to compute the HIC preconditioner. We show that for moderately correlated materials, the HIC preconditioner achieves the optimal linear scaling of the simulation. The development of a linear-scaling preconditioner for strongly correlated materials remains an open topic.     

Fast computation of two-level circulant preconditioners

In this paper we present an algorithm for the construction of the superoptimal circulant preconditioner for a two-level Toeplitz linear system. The algorithm is fast, in the sense that it operates in FFT time. Numerical results are given to assess its performance when applied to the solution of two-level Toeplitz systems by the conjugate gradient method, compared with the Strang and optimal circulant preconditioners.     

Using an iterative linear solver in an interior-point method for generating support vector machines

This paper concerns the generation of support vector machine classifiers for solving the pattern recognition problem in machine learning. A method is proposed based on interior-point methods for convex quadratic programming. This interior-point method uses a linear preconditioned conjugate gradient method with a novel preconditioner to compute each iteration from the previous. An implementation is developed by adapting the object-oriented package OOQP to the problem structure. Numerical results are provided, and computational experience is discussed.     

Adaptive linear combination of heuristic orderings in constructing examination timetables

In this paper, we investigate adaptive linear combinations of graph coloring heuristics with a heuristic modifier to address the examination timetabling problem. We invoke a normalisation strategy for each parameter in order to generalise the specific problem data. Two graph coloring heuristics were used in this study (largest degree and saturation degree). A score for the difficulty of assigning each examination was obtained from an adaptive linear combination of these two heuristics and examinations in the list were ordered based on this value. The examinations with the score value representing the higher difficulty were chosen for scheduling based on two strategies. We tested for single and multiple heuristics with and without a heuristic modifier with different combinations of weight values for each parameter on the Toronto and ITC2007 benchmark data sets. We observed that the combination of multiple heuristics with a heuristic modifier offers an effective way to obtain good solution quality. Experimental results demonstrate that our approach delivers promising results. We conclude that this adaptive linear combination of heuristics is a highly effective method and simple to implement.     

Conjugate gradient method for dual-dual mixed formulations

We deal with the iterative solution of linear systems arising from so-called dual-dual mixed finite element formulations. The linear systems are of a two-fold saddle point structure; they are indefinite and ill-conditioned. We define a special inner product that makes matrices of the two-fold saddle point structure, after a specific transformation, symmetric and positive definite. Therefore, the conjugate gradient method with this special inner product can be used as iterative solver. For a model problem, we propose a preconditioner which leads to a bounded number of CG-iterations. Numerical experiments for our model problem confirming the theoretical results are also reported.

     

Improving an interior-point approach for large block-angular problems by hybrid preconditioners

The computational time required by interior-point methods is often dominated by the solution of linear systems of equations. An efficient specialized interior-point algorithm for primal block-angular problems has been used to solve these systems by combining Cholesky factorizations for the block constraints and a conjugate gradient based on a power series preconditioner for the linking constraints. In some problems this power series preconditioner resulted to be inefficient on the last interior-point iterations, when the systems became ill-conditioned. In this work this approach is combined with a splitting preconditioner based on LU factorization, which works well for the last interior-point iterations. Computational results are provided for three classes of problems: multicommodity flows (oriented and nonoriented), minimum-distance controlled tabular adjustment for statistical data protection, and the minimum congestion problem. The results show that, in most cases, the hybrid preconditioner improves the performance and robustness of the interior-point solver. In particular, for some block-angular problems the solution time is reduced by a factor of 10.     

Conjugate residual methods for almost symmetric linear systems

This paper concerns the use of conjugate residual methods for the solution of nonsymmetric linear systems arising in applications to differential equations. We focus on an application derived from a seismic inverse problem. The linear system is a small perturbation to a symmetric positive-definite system, the nonsymmetries arising from discretization errors in the solution of certain boundary-value problems. We state and prove a new error bound for a class of generalized conjugate residual methods; we show that, in some cases, the perturbed symmetric problem can be solved with an error bound similar to the one for the conjugate residual method applied to the symmetric problem. We also discuss several applications for special distributions of eigenvalues.This work was supported in part by the National Science Foundation, Grants DMS-84-03148 and DCR-81-16779, and by the Office of Naval Research, Contract N00014-85-K-0725.     

A preconditioned domain decomposition algorithm for the solution of the elliptic Neumann problem

A new preconditioned conjugate gradient (PCG)-based domain decomposition method is given for the solution of linear equations arising in the finite element method applied to the elliptic Neumann problem. The novelty of the proposed method is in the recommended preconditioner which is constructed by using cyclic matrix. The resulting preconditioned algorithms are well suited to parallel computation.     

On parallel solution of linear elasticity problems: Part I: theory

The discretized linear elasticity problem is solved by the preconditioned conjugate gradient (pcg) method. Mainly we consider the linear isotropic case but we also comment on the more general linear orthotropic problem. The preconditioner is based on the separate displacement component (sdc) part of the equations of elasticity. The preconditioning system consists of two or three subsystems (in two or three dimensions) also called inner systems, each of which is solved by the incomplete factorization pcg-method, i.e., we perform inner iterations. A finite element discretization and node numbering giving a high degree of partial parallelism with equal processor load for the solution of these systems by the MIC(0) pcg method is presented. In general, the incomplete factorization requires an M-matrix. This property is studied for the elasticity problem. The rate of convergence of the pcg-method is analysed for different preconditionings based on the sdc-part of the elasticity equations. In the following two parts of this trilogy we will focus more on parallelism and implementation aspects. © 1998 John Wiley & Sons, Ltd.