Additive polynomial preconditioners for parallel computers

We present a polynomial preconditioner that can be used with the conjugate gradient method to solve symmetric and positive definite systems of linear equations. Each step of the preconditioning is achieved by simultaneously taking an iteration of the SOR method and an iteration of the reverse SOR method (equations taken in reverse order) and averaging the results. This yields a symmetric preconditioner that can be implemented on parallel computers by performing the forward and reverse SOR iterations simultaneously. We give necessary and sufficient conditions for additive preconditioners to be positive definite.

We find an optimal parameter, ω, for the SOR-Additive linear stationary iterative method applied to 2-cyclic matrices. We show this method is asymptotically twice as fast as SSOR when the optimal ω is used.

We compare our preconditioner to the SSOR polynomial preconditioner for a model problem. With the optimal ω, our preconditioner was found to be as effective as the SSOR polynomial preconditioner in reducing the number of conjugate gradient iterations. Parallel implementations of both methods are discussed for vector and multiple processors. Results show that if the same number of processors are used for both preconditioners, the SSOR preconditioner is more effective. If twice as many processors are used for the SOR-Additive preconditioner, it becomes more efficient than the SSOR preconditioner when the number of equations assigned to a processor is small. These results are confirmed by the Blue Chip emulator at the University of Washington.     

On relaxed nested factorization and combination preconditioning

The efficient solution of block tridiagonal linear systems arising from the discretization of convection–diffusion problem is considered in this paper. Starting with the classical nested factorization, we propose a relaxed nested factorization preconditioner. Then, several combination preconditioners are developed based on relaxed nested factorization and a tangential filtering preconditioner. Influence of the relaxation parameter is numerically studied, the results indicate that the optimal relaxation parameter should be close to but less than 1. The number of iteration counts exhibit an extremely sensitive behaviour. This phenomena resembles the behaviour of relaxed ILU preconditioner. For symmetric positive-definite coefficient matrix, we also show that the proposed combination preconditioner is convergent. Finally, numerous test cases are carried out with both additive and multiplicative combinations to verify the robustness of the proposed preconditioners.     

A new matrix splitting preconditioner for generalized saddle point problems

For generalized saddle point problems, we establish a new matrix splitting preconditioner and give the implementing process in detail. The new preconditioner is much easier to be implemented than the modified dimensional split (MDS) preconditioner. The convergence properties of the new splitting iteration method are analyzed. The eigenvalue distribution of the new preconditioned matrix is discussed and an upper bound for the degree of its minimal polynomial is derived. Finally, some numerical examples are carried out to verify the effectiveness and robustness of our preconditioner on generalized saddle point problems discretizing the incompressible Navier–Stokes equations.     

Approximate polynomial preconditionings applied to biharmonic equations

Applying a finite difference approximation to a biharmonic equation results in a very ill conditioned system of equations. This paper examines the conjugate gradient method used with polynomial preconditioning techniques for solving such linear systems. A new approach using an approximate polynomial preconditioner is described. The preconditioner is constructed from a series approximation based on the Laplacian finite difference matrix. A particularly attractive feature of this approach is that the Laplacian matrix consists of far fewer non-zero entries than the biharmonic finite difference matrix. Moreover, analytical estimates and computational results show that this preconditioner is more effective (in terms of the rate of convergence and the computational work required per iteration) than the polynomial preconditioner based on the original biharmonic matrix operator. The conjugate gradient algorithm and the preconditioning step can be efficiently implemented on a vector super-computer such as the CDC CYBER 205.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada Grant U0375; and in part by NASA (funded under the Space Act Agreement C99066G) while the author was visiting ICOMP, NASA Lewis Research Center.The work of this author was supported by an Izaak Walton Killam Memorial Scholarship.     

Physically based adaptive preconditioning for early vision

Several problems in early vision have been formulated in the past in a regularization framework. These problems, when discretized, lead to large sparse linear systems. In this paper, we present a novel physically based adaptive preconditioning technique which can be used in conjunction with a conjugate gradient algorithm to dramatically improve the speed of convergence for solving the aforementioned linear systems. A preconditioner, based on the membrane spline, or the thin plate spline, or a convex combination of the two, is termed a physically based preconditioner for obvious reasons. The adaptation of the preconditioner to an early vision problem is achieved via the explicit use of the spectral characteristics of the regularization filter in conjunction with the data. This spectral function is used to modulate the frequency characteristics of a chosen wavelet basis, and these modulated values are then used in the construction of our preconditioner. We present the preconditioner construction for three different early vision problems namely, the surface reconstruction, the shape from shading, and the optical flow computation problems. Performance of the preconditioning scheme is demonstrated via experiments on synthetic and real data sets     

A Uniform Additive Schwarz Preconditioner for High-Order Discontinuous Galerkin Approximations of Elliptic Problems

In this paper we design and analyze a uniform preconditioner for a class of high-order Discontinuous Galerkin schemes. The preconditioner is based on a space splitting involving the high-order conforming subspace and results from the interpretation of the problem as a nearly-singular problem. We show that the proposed preconditioner exhibits spectral bounds that are uniform with respect to the discretization parameters, i.e., the mesh size, the polynomial degree and the penalization coefficient. The theoretical estimates obtained are supported by numerical tests.     

Improving the preconditioning of linear systems from interior point methods

This paper deals with preconditioners for solving linear systems arising from interior point methods, using iterative methods. The main focus is the development of a set of results that allows a more efficient computation of the splitting preconditioner. During the interior point methods iterations, the linear system matrix becomes ill conditioned, leading to numerical difficulties to find a solution, even with iterative methods. Therefore, the choice of an effective preconditioner is essential for the success of the approach. The paper proposes a new ordering for a splitting preconditioner, taking advantage of the sparse structure of the original matrix. A formal demonstration shows that performing this new ordering the preconditioned matrix condition number is limited; numerical experiments reinforce the theoretical results. Case studies show that the proposed idea has better sparsity features than the original version of the splitting preconditioner and that it is competitive regarding the computational time.     

An efficient method for constructing an ILU preconditioner for solving large sparse nonsymmetric linear systems by the GMRES method

The main idea of this paper is in determination of the pattern of nonzero elements of the LU factors of a given matrix A. The idea is based on taking the powers of the Boolean matrix derived from A. This powers of a Boolean matrix strategy (PBS) is an efficient, effective, and inexpensive approach. Construction of an ILU preconditioner using PBS is described and used in solving large nonsymmetric sparse linear systems. Effectiveness of the proposed ILU preconditioner in solving large nonsymmetric sparse linear systems by the GMRES method is also shown. Numerical experiments are performed which show that it is possible to considerably reduce the number of GMRES iterations when the ILU preconditioner constructed here is used. In numerical examples, the influence of k, the dimension of the Krylov subspace, on the performance of the GMRES method using an ILU preconditioner is tested. For all the tests carried out, the best value for k is found to be 10.     

SOLVING SPARSE LEAST SQUARES PROBLEMS WITH PRECONDITIONED CGLS METHOD ON PARALLEL DISTRIBUTED MEMORY COMPUTERS

Abstract

In this paper we study the parallel aspects of PCGLS, a basic iterative method based on the conjugate gradient method with preconditioner applied to normal equations and Incomplete Modified Gram-Schmidt (IMGS) preconditioner, for solving sparse least squares problems on massively parallel distributed memory computers. The performance of these methods on this kind of architecture is usually limited because of the global communication required for the inner products. We will describe the parallelization of PCGLS and IMGS preconditioner by two ways of improvement. One is to accumulate the results of a number of inner products collectively and the other is to create situations where communication can be overlapped with computation. A theoretical model of computation and communication phases is presented which allows us to determine the optimal number of processors that minimizes the runtime. Several numerical experiments on the Parsytec GC/PowerPlus are presented.     

An approach for structural static reanalysis with unchanged number of degrees of freedom

This paper presents an approach for structural static reanalysis with unchanged number of degrees of freedom. Preconditioned conjugate gradient method is employed, and a new preconditioner is constructed by updating the Cholesky factorization of the initial stiffness matrix with little cost. The proposed method preserves the ease of implementation and significantly improves the quality of the results. In particular, the accuracy of the approximate solutions can adaptively be monitored. Numerical examples show that the condition number of preconditioned system using the new preconditioner is much smaller than that using the initial stiffness matrix as the preconditioner. Therefore, the fast convergence and accurate results can be obtained by the proposed approach.     

A variant of the HSS preconditioner for complex symmetric indefinite linear systems

Using the equivalent block two-by-two real linear systems, we establish a new variant of the Hermitian and skew-Hermitian splitting (HSS) preconditioner for a class of complex symmetric indefinite linear systems. The new preconditioner is not only a better approximation to the block two-by-two real coefficient matrix than the well-known HSS preconditioner, but also resulting in an unconditional convergent fixed-point iteration. The quasi-optimal parameter, which minimizes an upper bound of the spectral radius of the iteration matrix, is analyzed. Eigen-properties and an upper bound of the degree of the minimal polynomial of the preconditioned matrix are discussed. Finally, two numerical examples are provided to show the efficiency of the new preconditioner.     

Fully iterative ILU preconditioning of the unsteady Navier–Stokes equations for GPGPU

In this work we investigate the numerical difficulties that arise in optimizing the efficiency of Newtonian fluids simulations on a massively parallel computing hardware like a GPU. In particular, we will concentrate on the resulting algebraic problem. We will present an approximate, fully-iterative, ILU preconditioner and we will show that this solution is very efficient on a GPU if compared with an intrinsic massively parallel preconditioner like the diagonal preconditioner, which indeed goes faster than more robust techniques, like ILU, despite their strong decrease in the number of iterations. We refer to GMRES as the iterative scheme used to solve the linear system. In particular, we will deal with the solution of incompressible flows with variable density and we will investigate the interplay between Reynolds and Atwood numbers. We will show that the numerical simulation at medium–high Reynolds numbers produces linear systems whose matrices can be reasonably preconditioned with the diagonal preconditioner, while at low Reynolds numbers the higher viscosity of the fluid makes the diagonal preconditioner ineffective in the solution time requested from GMRES and, decreasing the Reynolds number, unable to let GMRES converge at all. In this situation, we will show how an adequate iterative approach to the parallel solution of the triangular systems that result from the ILU preconditioning, turns out to be robust and efficient. We will show numerical results for variable-density fluids, discretized with the scheme described in Calgaro et al. (2008), in classical benchmarks and, in particular, in the well-known Rayleigh–Taylor instability.     

Robust multigrid preconditioners for cell-centered finite volume discretization of the high-contrast diffusion equation

We study a conservative 5-point cell-centered finite volume discretization of the high-contrast diffusion equation. We aim to construct preconditioners that are robust with respect to the magnitude of the coefficient contrast and the mesh size simultaneously. For that, we prove and numerically demonstrate the robustness of the preconditioner proposed by Aksoylu et al. (Comput Vis Sci 11:319–331, 2008) by extending the devised singular perturbation analysis from linear finite element discretization to the above discretization. The singular perturbation analysis is more involved than that of finite element case because all the subblocks in the discretization matrix depend on the diffusion coefficient. However, as the diffusion coefficient approaches infinity, that dependence is eliminated. This allows the same preconditioner to be utilized due to similar limiting behaviours of the submatrices; leading to a narrowing family of preconditioners that can be used for different discretizations. Therefore, we have accomplished a desirable preconditioner design goal. We compare our numerical results to standard cell-centered multigrid implementations and observe that performance of our preconditioner is independent of the utilized smoothers and prolongation operators. As a side result, we also prove a fundamental qualitative property of solution of the high-contrast diffusion equation. Namely, the solution over the highly-diffusive island becomes constant asymptotically. Integration of this qualitative understanding of the underlying PDE to our preconditioner is the main reason behind its superior performance. Diagonal scaling is probably the most basic preconditioner for high-contrast coefficients. Extending the matrix entry based spectral analysis introduced by Graham and Hagger, we rigorously show that the number of small eigenvalues of the diagonally scaled matrix depends on the number of isolated islands comprising the highly-diffusive region. This indicates that diagonal scaling creates a significant clustering of the spectrum, a favorable property for faster convergence of Krylov subspace solvers.     

Structure Preserving Preconditioners for Image Deblurring

Regularizing preconditioners for accelerating the convergence of iterative regularization methods without spoiling the quality of the approximated solution have been extensively investigated in the last twenty years. Several strategies have been proposed for defining proper preconditioners. Usually, in methods for image restoration, the structure of the preconditioner is chosen Block Circulant with Circulant Blocks (BCCB) because it can be efficiently exploited by Fast Fourier Transform (FFT). Nevertheless, for ill-conditioned problems, it is well-known that BCCB preconditioners cannot provide a strong clustering of the eigenvalues. Moreover, in order to get an effective preconditioner, it is crucial to preserve the structure of the coefficient matrix. The structure of such a matrix, in case of image deblurring problem, depends on the boundary conditions imposed on the imaging model. Therefore, we propose a technique to construct a preconditioner which has the same structure of the blurring matrix related to the restoration problem at hand. The construction of our preconditioner requires two FFTs like the BCCB preconditioner. The presented preconditioning strategy represents a generalization and an improvement with respect to both circulant and structured preconditioning available in the literature. The technique is further extended to provide a non-stationary preconditioning in the same spirit of a recent proposal for BCCB matrices. Some numerical results show the importance of preserving the matrix structure from the point of view of both restoration quality and robustness of the regularization parameter.     

A fast preconditioner for the incompressible Navier Stokes Equations

The pressure matrix method is a well known scheme for the solution of the incompressible Navier–Stokes equations by splitting the computation of the velocity and the pressure fields (see, e.g., [17]). However, the set-up of effective preconditioners for the pressure matrix is mandatory in order to have an acceptable computational cost. Different strategies can be pursued (see, e.g., [6, 22 , 4, 7, 9]). Inexact block LU factorizations of the matrix obtained after the discretization and linearization of the problem, originally proposed as fractional step solvers, provide also a strategy for building effective preconditioners of the pressure matrix (see [23]). In this paper, we present numerical results about a new preconditioner, based on an inexact factorization. The new preconditioner applies to the case of the generalized Stokes problem and to the Navier–Stokes one, as well. In the former case, it improves the performances of the well known Cahouet–Chabard preconditioner (see [2]). In the latter one, numerical results presented here show an almost optimal behavior (with respect to the space discretization) and suggest that the new preconditioner is well suited also for flexible or inexact strategies, in which the systems for the preconditioner are solved inaccurately.     

Efficient solution for Galerkin-based polynomial chaos expansion systems

Iterative solvers and preconditioners are widely used for handling the linear system of equations arising from stochastic finite element method (SFEM) formulations, e.g. galerkin-based polynomial chaos (G-P-C) Expansion method. Especially, Preconditioned Conjugate Gradient (PCG) solver and the Incomplete Cholesky (IC) preconditioner are shown to be adequate choices within this context. In this study, approaches for the automated adjustment of the input parameters for these tools are to be introduced. The proposed algorithms aim to enable the use of the PCG solver and IC preconditioner in a black-box fashion. As a result, the requirement of the expertise for using these tools is removed to a certain extend. Furthermore, these algorithms can be used also for the implementation purposes of SFEM’s within general purpose software by increasing the ease of the use of these tools and hence leading to an improved user-comfort.     

On the use of inexact subdomain solvers for BDDC algorithms

The standard BDDC (balancing domain decomposition by constraints) preconditioner is shown to be equivalent to a preconditioner built from a partially subassembled finite element model. This results in a system of linear algebraic equations which is much easier to solve in parallel than the fully assembled model; the cost is then often dominated by that of the problems on the subdomains. An important role is also played, both in theory and practice, by an averaging operator and in addition exact Dirichlet solvers are used on the subdomains in order to eliminate the residual in the interior of the subdomains. The use of inexact solvers for these problems and even the replacement of the Dirichlet solvers by a trivial extension are considered. It is established that one of the resulting algorithms has the same eigenvalues as the standard BDDC algorithm, and the connection of another with the FETI-DP algorithm with a lumped preconditioner is also considered. Multigrid methods are used in the experimental work and under certain assumptions, it is established that the iteration count essentially remains the same as when exact solvers are used, while considerable gains in the speed of the algorithm can be realized since the cost of the exact solvers grows superlinearly with the size of the subdomain problems while the multigrid methods are linear.     

块三对角矩阵的并行局部块分解预条件

该文首先分析了并行局部块分解预条件的特征分布,分析表明其与串行局部块分解预条件的特征分布基本相当,从而从理论上保证了利用该预条件进行并行计算时的高效性．其次分析了利用该预条件进行并行计算时影响加速比的因素,由此说明了当问题规模不大而处理机台数增加时,计算效率必然逐渐下降的原因．最后在由6台微机连成的机群系统上将该预条件与利用多分裂技术构造的多种预条件进行了比较,实验结果说明该预条件效率高于其它预条件方法．同时在某巨型机上进行的实验表明对处理机台数比较多时,该预条件也仍然很有效．     

On parameterized matrix splitting preconditioner for the saddle point problems

In this paper, we present a parameterized matrix splitting (PMS) preconditioner for the large sparse saddle point problems. The preconditioner is based on a parameterized splitting of the saddle point matrix, resulting in a fixed-point iteration. The convergence theorem of the new iteration method for solving large sparse saddle point problems is proposed by giving the restrictions imposed on the parameter. Based on the idea of the parameterized splitting, we further propose a modified PMS preconditioner. Some useful properties of the preconditioned matrix are established. Numerical implementations show that the resulting preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as generalized minimal residual method.     

Towards a rigorously justified algebraic preconditioner for high-contrast diffusion problems

In this paper we present a new preconditioner suitable for solving linear systems arising from finite element approximations of elliptic PDEs with high-contrast coefficients. The construction of the preconditioner consists of two phases. The first phase is an algebraic one which partitions the degrees of freedom into “high” and “low” permeability regions which may be of arbitrary geometry. This partition yields a corresponding blocking of the stiffness matrix and hence a formula for the action of its inverse involving the inverses of both the high permeability block and its Schur complement in the original matrix. The structure of the required sub-block inverses in the high contrast case is revealed by a singular perturbation analysis (with the contrast playing the role of a large parameter). This shows that for high enough contrast each of the sub-block inverses can be approximated well by solving only systems with constant coefficients. The second phase of the algorithm involves the approximation of these constant coefficient systems using multigrid methods. The result is a general method of algebraic character which (under suitable hypotheses) can be proved to be robust with respect to both the contrast and the mesh size. While a similar performance is also achieved in practice by algebraic multigrid (AMG) methods, this performance is still without theoretical justification. Since the first phase of our method is comparable to the process of identifying weak and strong connections in conventional AMG algorithms, our theory provides to some extent a theoretical justification for these successful algebraic procedures. We demonstrate the advantageous properties of our preconditioner using experiments on model problems. Our numerical experiments show that for sufficiently high contrast the performance of our new preconditioner is almost identical to that of the Ruge and Stüben AMG preconditioner, both in terms of iteration count and CPU-time.