Developments and trends in the parallel solution of linear systems

In this review paper, we consider some important developments and trends in algorithm design for the solution of linear systems concentrating on aspects that involve the exploitation of parallelism. We briefly discuss the solution of dense linear systems, before studying the solution of sparse equations by direct and iterative methods. We consider preconditioning techniques for iterative solvers and discuss some of the present research issues in this field.     

Sparse iterative algorithm software for large-scale MIMD machines: An initial discussion and implementation

The parallelization of sophisticated applications has dramatically increased in recent years. As machine capabilities rise, greater emphasis on modeling complex phenomena can be expected. Many of these applications require the solution of large sparse matrix equations which approximate systems of partial differential equations (PDEs). Therefore we consider parallel iterative solvers for large sparse non-symmetric systems and issues related to parallel sparse matrix software. We describe a collection of parallel iterative solvers which use a distributed sparse matrix format that facilitates the interface between specific applications and a variety of Krylov subspace techniques and multigrid methods. These methods have been used to solve a number of linear and non-linear PDE problems on a 1024-processor NCUBE 2 hypercube. Over 1 Gflop sustained computation rates are achieved with many of these solvers, demonstrating that high performance can be attained even when using sparse matrix data structures.     

线性系统求解中迭代算法的GPU加速方法

在求解线性系统时,迭代法是一种基本的方法,特别是在系数矩阵为大规模稀疏矩阵的情况下,高效地使用迭代法求解变得十分重要。本文通过分析迭代法的一般特点,提出了使用具有强大计算能力和存储带宽的GPU加速迭代法的一般方法。利用这些方法,在两种主流GPU平台上实现了一个经典的迭代法PQMRCGSTAB,并且针对不同的GPU平台特点提出了具体的优化方法。与AMD Opteron 2.4GHz 4核处理器相比,双精度版本的PQMRCGSTAB算法经NVIDIA Tesla S1070加速后性能提高31倍,经AMD Radeon HD 4870 X2加速后性能提高9倍。     

GMRES implementations and residual smoothing techniques for solving ill-posed linear systems

There are verities of useful Krylov subspace methods to solve nonsymmetric linear system of equations. GMRES is one of the best Krylov solvers with several different variants to solve large sparse linear systems. Any GMRES implementation has some advantages. As the solution of ill-posed problems are important. In this paper, some GMRES variants are discussed and applied to solve these kinds of problems. Residual smoothing techniques are efficient ways to accelerate the convergence speed of some iterative methods like CG variants. At the end of this paper, some residual smoothing techniques are applied for different GMRES methods to test the influence of these techniques on GMRES implementations.     

Distributed generic approximate sparse inverses

The need for accuracy in the solution of linear systems derived from the discretization of partial differential equations leads to large sparse linear systems. The solution of sparse linear systems requires efficient scalable methods. Iterative solvers require efficient parallel preconditioning methods to solve effectively sparse linear systems. Herewith, a new parallel algorithm for the generic approximate sparse inverse matrix method for distributed memory systems is proposed. The computation of the distributed generic approximate sparse inverse matrix is based on a column-wise approach, which allows the separation to independent problems that can be handled in parallel without synchronization points or intermediate communications. This is achieved by reforming the generic approximate sparse inverse matrix algorithm and its process of computation with a new partial solution method for the computation of the nonzero elements of each column dictated by the approximate inverse sparsity pattern. Moreover, an algorithmic scheme is proposed for the efficient distribution of data amongst the available workstations, along with a load balancing scheme for problems with large standard deviation in the number of nonzero elements per column. Numerical results are presented for the proposed schemes for various model problems.     

Updating preconditioner for iterative method in time domain simulation of power systems

The numerical solution of the differential-algebraic equations(DAEs) involved in time domain simulation(TDS) of power systems requires the solution of a sequence of large scale and sparse linear systems.The use of iterative methods such as the Krylov subspace method is imperative for the solution of these large and sparse linear systems.The motivation of the present work is to develop a new algorithm to efficiently precondition the whole sequence of linear systems involved in TDS.As an improvement of dishon...     

A numerical investigation on the interplay amongst geometry, meshes, and linear algebra in the finite element solution of elliptic PDEs

In this paper, we study the effect of the choice of mesh quality metric, preconditioner, and sparse linear solver on the numerical solution of elliptic partial differential equations (PDEs). We smooth meshes on several geometric domains using various quality metrics and solve the associated elliptic PDEs using the finite element method. The resulting linear systems are solved using various combinations of preconditioners and sparse linear solvers. We use the inverse mean ratio and radius ratio metrics in addition to conditioning-based scale-invariant and interpolation-based size-and-shape metrics. We employ the Jacobi, SSOR, incomplete LU, and algebraic multigrid preconditioners and the conjugate gradient, minimum residual, generalized minimum residual, and bi-conjugate gradient stabilized solvers. We focus on determining the most efficient quality metric, preconditioner, and linear solver combination for the numerical solution of various elliptic PDEs with isotropic coefficients. We also investigate the effect of vertex perturbation and the effect of increasing the problem size on the number of iterations required to converge and on the solver time. In this paper, we consider Poisson’s equation, general second-order elliptic PDEs, and linear elasticity problems.     

Computing subdominant unstable modes of turbulent plasma with a parallel Jacobi–Davidson eigensolver

In the numerical solution of large‐scale eigenvalue problems, Davidson‐type methods are an increasingly popular alternative to Krylov eigensolvers. The main motivation is to avoid the expensive factorizations that are often needed by Krylov solvers when the problem is generalized or interior eigenvalues are desired. In Davidson‐type methods, the factorization is replaced by iterative linear solvers that can be accelerated by a smart preconditioner. Jacobi–Davidson is one of the most effective variants. However, parallel implementations of this method are not widely available, particularly for non‐symmetric problems. We present a parallel implementation that has been included in SLEPc, the Scalable Library for Eigenvalue Problem Computations, and test it in the context of a highly scalable plasma turbulence simulation code. We analyze its parallel efficiency and compare it with a Krylov–Schur eigensolver. Copyright © 2011 John Wiley & Sons, Ltd.     

Solvers for the verified solution of parametric linear systems

We present a newly developed version of our solvers for the verified solution of dense parametric linear systems, i.e. linear systems whose system matrix and right-hand side depend affine-linearly on parameters that vary inside prescribed intervals. The solvers use our C++ class library for reliable computing, C-XSC. The C-XSC library provides many features, especially easy to handle data types for dense and sparse matrices and vectors and the ability to compute dot products and dot product expressions in arbitrary precision. The new solvers can use either sparse or dense matrices as the coefficient matrices for the parameters. The use of sparse coefficient matrices can result in huge improvements in both performance and memory consumption. BLAS and LAPACK routines are used where applicable, and OpenMP is used for the parallelization on multi-core and multi-processor systems. The solvers also provide the ability to compute not only an outer but also a componentwise inner enclosure of the solution set of the system and to choose between two versions of the algorithm, one being very fast and one giving sharp results and extending the range of solvable systems. We give some examples for parametric linear systems (also from real world examples such as worst-case tolerance analysis of linear electric circuits), give performance measurements of our solvers and also demonstrate that they scale very well when using multiple cores or processors.     

Numerical simulation of three-dimensional thermal convection on the array processor DAP 510

In this paper we deal with the numerical simulation of time dependent three-dimensional thermal convection on the array processor DAP 510. Applying finite differences in combination with a pressure correction method to the underlying non-linear system of partial differential equations, we reduce the numerical solution of the problem to the solution of a sequence of sparse linear systems. Using polynomial preconditioned conjugate gradient methods for the solution of these systems results in a highly parallel algorithm for the simulation of the considered flows on the DAP 510. Using this parallel algorithm, data can be mapped in different ways onto the processor array. Depending on the number of grid points, several methods are shown. Numerical experiments illustrate the capabilities of the proposed algorithm.     

A Matrix-free Two-grid Preconditioner for Solving Boundary Integral Equations in Electromagnetism

In this paper, we describe a matrix-free iterative algorithm based on the GMRES method for solving electromagnetic scattering problems expressed in an integral formulation. Integral methods are an interesting alternative to differential equation solvers for this problem class since they do not require absorbing boundary conditions and they mesh only the surface of the radiating object giving rise to dense and smaller linear systems of equations. However, in realistic applications the discretized systems can be very large and for some integral formulations, like the popular Electric Field Integral Equation, they become ill-conditioned when the frequency increases. This means that iterative Krylov solvers have to be combined with fast methods for the matrix-vector products and robust preconditioning to be affordable in terms of CPU time. In this work we describe a matrix-free two-grid preconditioner for the GMRES solver combined with the Fast Multipole Method. The preconditioner is an algebraic two-grid cycle built on top of a sparse approximate inverse that is used as smoother, while the grid transfer operators are defined using spectral information of the preconditioned matrix. Experiments on a set of linear systems arising from real radar cross section calculation in industry illustrate the potential of the proposed approach for solving large-scale problems in electromagnetism.     

Accelerating iterative linear solvers using multiple graphical processing units

In this paper, we develop, study and implement iterative linear solvers and preconditioners using multiple graphical processing units (GPUs). Techniques for accelerating sparse matrix–vector (SpMV) multiplication, linear solvers and preconditioners are presented. Four Krylov subspace solvers, a Neumann polynomial preconditioner and a domain decomposition preconditioner are implemented. Our numerical tests with NVIDIA C2050 GPUs show that the SpMV kernel can be sped over 40 times faster using four GPUs. Our linear solvers and preconditioners have similar speedup.     

Application of single-level,pointwise algebraic,and smoothed aggregation multigrid methods to direct numerical simulations of incompressible turbulent flows

Single- and multi-level iterative methods for sparse linear systems are applied to unsteady flow simulations via implementation into a direct numerical simulation solver for incompressible turbulent flows on unstructured meshes. The performance of these solution methods, implemented in the well-established SAMG and ML packages, are quantified in terms of computational speed and memory consumption, with a direct sparse LU solver (SuperLU) used as a reference. The classical test case of unsteady flow over a circular cylinder at low Reynolds numbers is considered, employing a series of increasingly fine anisotropic meshes. As expected, the memory consumption increases dramatically with the considered problem size for the direct solver. Surprisingly, however, the computation times remain reasonable. The speed and memory usage of pointwise algebraic and smoothed aggregation multigrid solvers are found to exhibit near-linear scaling. As an alternative to multi-level solvers, a single-level ILUT-preconditioned GMRES solver with low drop tolerance is also considered. This solver is found to perform sufficiently well only on small meshes. Even then, it is outperformed by pointwise algebraic multigrid on all counts. Finally, the effectiveness of pointwise algebraic multigrid is illustrated by considering a large three-dimensional direct numerical simulation case using a novel parallelization approach on a large distributed memory computing cluster.     

Numerical solution of KKT systems in PDE-constrained optimization problems via the affine scaling trust-region approach†

A recently proposed trust-region approach for bound-constrained nonlinear equations is applied to the Karush-Kuhn-Tucker (KKT) system arising from the discretization of a class of partial differential equation (PDE)-constrained optimization problems. Two different implementations are developed that take into account the large dimension and the special structure of the problems. The linear algebra phase is analysed considering the possibility of solving the arising linear systems by either direct methods or short-recurrence iterative linear solvers. Viability of the approach is proved through several numerical experiments on large KKT systems arising from the discretization of control problems.     

Generalized extended to the limit sparse factorization techniques for solving unsymmetric finite element systems

Generalized extended to the limit sparse factorization procedures in algorithmic form are derived yielding direct and iterative methods for the solution of unsymmetric finite element or finite difference systems of irregular structure. The proposed approximate factorization procedures are chosen as the basis to yield systems on which Chebyshev methods are implicitly applied. Application of the methods on a two dimensional linear boundary-value problem is discussed and numerical results are given.     

On sparse lu factorization procedures for the solution of parabolic differential equations in three space dimensions

The numerical solution of partial differential equations in 3 dimensions by finite difference methods leads to the problem of solving large order sparse structured linear systems.

In this paper, a factorization procedure in algorithmic form is derived yielding direct and iterative methods of solution of some interesting boundary value problems in physics and engineering.     

The use of the generalized extended to the limit sparse factorization techniques for the solution of non-linear elliptic and parabolic difference equations

Generalized Extended to the Limit LU sparse factorization procedures for the solution of large sparse unsymmetric linear systems of irregular and unsymmetric structure are presented. Composite “inner-outer” iterative schemes incorporating these procedures are introduced for solving non-linear elliptic and parabolic difference equations. Applications of the methods on non-linear boundary-value problems are discussed and numerical results are given.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Direct Solvers for the Biharmonic Eigenvalue Problems Using Legendre Polynomials

We propose an efficient algorithm based on the Legendre–Galerkin approximations for the direct solution of the biharmonic eigenvalue problems with the boundary conditions of the clamped plate, the simply supported plate and the Cahn–Hilliard type. The key point to the efficiency of our algorithm is to construct appropriate basis functions which satisfying the corresponding boundary condition automatically and leading to linear systems with sparse matrices for the discrete variational formulations. In addition, the error estimate was driven by the minimax principle. Finally, the numerical results demonstrate the accuracy and the efficiency of this method.