On the evaluation of general sparse hybrid linear solvers

General sparse hybrid solvers are commonly used kernels for solving wide range of scientific and engineering problems. This work addresses the current problems of efficiently solving general sparse linear equations with direct/iterative hybrid solvers on many core distributed clusters. We briefly discuss the solution stages of Maphys, HIPS, and PDSLin hybrid solvers for large sparse linear systems with their major algorithmic differences. In this category of solvers, different methods with sophisticated preconditioning algorithms are suggested to solve the trade off between memory and convergence. Such solutions require a certain hierarchical level of parallelism more suitable for modern supercomputers that allow to scale for thousand numbers of processors using Schur complement framework. We study the effect of reordering and analyze the performance, scalability as well as memory for each solve phase of PDSLin, Maphys, and HIPS hybrid solvers using large set of challenging matrices arising from different actual applications and compare the results with SuperLU_DIST direct solver. We specifically focus on the level of parallel mechanisms used by the hybrid solvers and the effect on scalability. Tuning and Analysis Utilities (TAU) is employed to assess the efficient usage of heap memory profile and measuring communication volume. The tests are run on high performance large memory clusters using up to 512 processors.     

Fast inexact subspace iteration for generalized eigenvalue problems with spectral transformation

We study inexact subspace iteration for solving generalized non-Hermitian eigenvalue problems with spectral transformation, with focus on a few strategies that help accelerate preconditioned iterative solution of the linear systems of equations arising in this context. We provide new insights into a special type of preconditioner with “tuning” that has been studied for this algorithm applied to standard eigenvalue problems. Specifically, we propose an alternative way to use the tuned preconditioner to achieve similar performance for generalized problems, and we show that these performance improvements can also be obtained by solving an inexpensive least squares problem. In addition, we show that the cost of iterative solution of the linear systems can be further reduced by using deflation of converged Schur vectors, special starting vectors constructed from previously solved linear systems, and iterative linear solvers with subspace recycling. The effectiveness of these techniques is demonstrated by numerical experiments.     

A preconditioning technique for Schur complement systems arising in stochastic optimization

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time.     

On the use of dense matrix techniques within sparse simplex

In this paper we discuss some instances where dense matrix techniques can be utilized within a sparse simplex linear programming solver. The main emphasis is on the use of the Schur complement matrix as a part of the basis matrix representation. This approach enables to represent the basis matrix as an easily invertible sparse matrix and one or more dense Schur complement matrices. We describe our variant of this method which uses updating of the QR factorization of the Schur complement matrix. We also discuss some implementation issues of the LP software package which is based on this approach.     

An inexact interior point method for L 1-regularized sparse covariance selection

Sparse covariance selection problems can be formulated as log-determinant (log-det) semidefinite programming (SDP) problems with large numbers of linear constraints. Standard primal–dual interior-point methods that are based on solving the Schur complement equation would encounter severe computational bottlenecks if they are applied to solve these SDPs. In this paper, we consider a customized inexact primal–dual path-following interior-point algorithm for solving large scale log-det SDP problems arising from sparse covariance selection problems. Our inexact algorithm solves the large and ill-conditioned linear system of equations in each iteration by a preconditioned iterative solver. By exploiting the structures in sparse covariance selection problems, we are able to design highly effective preconditioners to efficiently solve the large and ill-conditioned linear systems. Numerical experiments on both synthetic and real covariance selection problems show that our algorithm is highly efficient and outperforms other existing algorithms.     

A domain-decomposing parallel sparse linear system solver

The solution of large sparse linear systems is often the most time-consuming part of many science and engineering applications. Computational fluid dynamics, circuit simulation, power network analysis, and material science are just a few examples of the application areas in which large sparse linear systems need to be solved effectively. In this paper, we introduce a new parallel hybrid sparse linear system solver for distributed memory architectures that contains both direct and iterative components. We show that by using our solver one can alleviate the drawbacks of direct and iterative solvers, achieving better scalability than with direct solvers and more robustness than with classical preconditioned iterative solvers. Comparisons to well-known direct and iterative solvers on a parallel architecture are provided.     

A domain-decomposing parallel sparse linear system solver

The solution of large sparse linear systems is often the most time-consuming part of many science and engineering applications. Computational fluid dynamics, circuit simulation, power network analysis, and material science are just a few examples of the application areas in which large sparse linear systems need to be solved effectively. In this paper, we introduce a new parallel hybrid sparse linear system solver for distributed memory architectures that contains both direct and iterative components. We show that by using our solver one can alleviate the drawbacks of direct and iterative solvers, achieving better scalability than with direct solvers and more robustness than with classical preconditioned iterative solvers. Comparisons to well-known direct and iterative solvers on a parallel architecture are provided.     

Sparse Approximations of the Schur Complement for Parallel Algebraic Hybrid Solvers in 3D

<正>In this paper we study the computational performance of variants of an algebraic additive Schwarz preconditioner for the Schur complement for the solution of large sparse linear systems.In earlier works,the local Schur complements were computed exactly using a sparse direct solver.The robustness of the preconditioner comes at the price of this memory and time intensive computation that is the main bottleneck of the approach for tackling huge problems.In this work we investigate the use of sparse approximation of the dense local Schur complements.These approximations are computed using a partial incomplete LU factorization.Such a numerical calculation is the core of the multi-level incomplete factorization such as the one implemented in pARMS. The numerical and computing performance of the new numerical scheme is illustrated on a set of large 3D convection-diffusion problems;preliminary experiments on linear systems arising from structural mechanics are also reported.     

Block and joint ℋ︁-matrix preconditioners for the Oseen equations

For saddle point problems in fluid dynamics, many preconditioners in the literature exploit the block structure of the problem to construct block diagonal or block triangular preconditioners. The performance of such preconditioners depends on whether fast, approximate solvers for the linear systems on the block diagonal as well as for the Schur complement are available. We will construct these efficient preconditioners using hierarchical matrix techniques in which fully populated matrices are approximated by blockwise low rank approximations. We will compare such block preconditioners with those obtained through a completely different approach where the given block structure is not used but a domain-decomposition based ℋ︁-LU factorization is constructed for the complete system matrix. Preconditioners resulting from these two approaches will be discussed and compared through numerical results. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Designing Optimal Algorithms for Solving Banded Triangular Systems on Rings

Parallel complexity results for designing banded triangular solvers are provided. In particular, several lower bounds based on data layout and communication along a ring are derived based on solving such systems using substitution. Lastly, a near-optimal solver for a ring is discussed and provided.     

A real-valued block conjugate gradient type method for solving complex symmetric linear systems with multiple right-hand sides

We consider solving complex symmetric linear systems with multiple right-hand sides. We assume that the coefficient matrix has indefinite real part and positive definite imaginary part. We propose a new block conjugate gradient type method based on the Schur complement of a certain 2-by-2 real block form. The algorithm of the proposed method consists of building blocks that involve only real arithmetic with real symmetric matrices of the original size. We also present the convergence property of the proposed method and an efficient algorithmic implementation. In numerical experiments, we compare our method to a complex-valued direct solver, and a preconditioned and nonpreconditioned block Krylov method that uses complex arithmetic.     

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.     

Parallel Schur complement method for large-scale systems on distributed memory computers

The Schur complement method, also known as substructuring technique, was widely used in structural mechanics to solve large-scale systems with limited memory computers for more than three decades [J.S. Przemieniecki, AIAA J. 1 (1963) 138]. Currently, due to developments in computer technology, the available on-board memory has increased considerably. Despite the existence of these high-memory systems, the Schur complement method still finds its applications in structural mechanics through parallel computing. When developing a computer program, the Schur method has a significant book-keeping load in comparison to other parallel algorithms used, e.g., Schwarz alternating domain decomposition method [H.A. Schwarz, Gesammelte Mathematiche Abhandlungen, vol. 2, Springer, Berlin, 1890, p. 133]. This results in memory usage. Although parallel systems are used, global coefficient matrices require a large amount of memory. Therefore, significant memory is reserved for the solution of large-scale systems. In this paper, we present an efficient algorithm for the assemblage and solution of interface equations which facilitates the solution of large-scale systems via the Schur complement method on multiple instruction multiple data (MIMD) distributed memory architectures. In this method, we assemble the subdomain and interface coefficient matrices in such a manner that the memory requirements decrease significantly, resulting in the solution of large-scale systems with reasonable memory usage. The computer program is tested on distributed memory architectures with UNIX, WINDOWS NT, and LINUX operating systems.     

Algebraic multilevel preconditioning of finite element matrices using local Schur complements

We consider an algebraic multilevel preconditioning technique for SPD matrices arising from finite element discretization of elliptic PDEs. In particular, we address the case of non‐M matrices. The method is based on element agglomeration and assumes access to the individual element matrices. The left upper block of the considered multiplicative two‐level preconditioner is approximated using incomplete factorization techniques. The coarse‐grid element matrices are simply Schur complements computed from local neighbourhood matrices, i.e. small collections of element matrices. Assembling these local Schur complements results in a global Schur complement approximation that can be analysed by regarding (local) macro elements. These components, when combined in the framework of an algebraic multilevel iteration, yield a robust and efficient linear solver. The presented numerical experiments include also the Lamé differential equation for the displacements in the two‐dimensional plane‐stress elasticity problem. Copyright © 2005 John Wiley & Sons, Ltd.     

A class of multilevel recursive incomplete LU preconditioning techniques

We introduce a class of multilevel recursive incomplete LU preconditioning techniques (RILUM) for solving general sparse matrices. This technique is based on a recursive two by two block incomplete LU factorization on the coefficient matrix. The coarse level system is constructed as an (approximate) Schur complement. A dynamic preconditioner is obtained by solving the Schur complement matrix approximately. The novelty of the proposed techniques is to solve the Schur complement matrix by a preconditioned Krylov subspace method. Such a reduction process is repeated to yield a multilevel recursive preconditioner.     

A fast solver for linear systems with displacement structure

We describe a fast solver for linear systems with reconstructible Cauchy-like structure, which requires O(rn ²) floating point operations and O(rn) memory locations, where n is the size of the matrix and r its displacement rank. The solver is based on the application of the generalized Schur algorithm to a suitable augmented matrix, under some assumptions on the knots of the Cauchy-like matrix. It includes various pivoting strategies, already discussed in the literature, and a new algorithm, which only requires reconstructibility. We have developed a software package, written in Matlab and C-MEX, which provides a robust implementation of the above method. Our package also includes solvers for Toeplitz(+Hankel)-like and Vandermonde-like linear systems, as these structures can be reduced to Cauchy-like by fast and stable transforms. Numerical experiments demonstrate the effectiveness of the software.     

Correlative Sparsity in Primal-Dual Interior-Point Methods for LP,SDP, and SOCP

Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in. S. Kim’s research was supported by Kosef R01-2005-000-10271-0 and KRF-2006-312-C00062.     

Solution of linear systems from an optimal control problem arising in wind simulation

Several solution strategies for a class of large, sparse linear systems with a block 2 × 2 structure arising from the finite element discretization of an optimal control problem in wind simulation are introduced and analyzed. Block preconditioners and a sparse direct solver on the original coupled system are compared with a preconditioned GMRES iteration applied to a reduced system (Schur complement). Theoretical and experimental results demonstrate the effectiveness of the reduced system approach. Copyright © 2009 John Wiley & Sons, Ltd.     

A block preconditioning technique for the streamfunction‐vorticity formulation of the Navier‐Stokes equations

Iterative methods of Krylov‐subspace type can be very effective solvers for matrix systems resulting from partial differential equations if appropriate preconditioning is employed. We describe and test block preconditioners based on a Schur complement approximation which uses a multigrid method for finite element approximations of the linearized incompressible Navier‐Stokes equations in streamfunction and vorticity formulation. By using a Picard iteration, we use this technology to solve fully nonlinear Navier‐Stokes problems. The solvers which result scale very well with problem parameters. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011