Circulant block-factorization preconditioning of anisotropic elliptic problems

The recently introduced circulant block-factorization preconditioners are studied in this paper. The general approach is first formulated for the case of block-tridiagonal sparse matrices. Then an estimate of the condition number of the preconditioned matrix for a model anisotropic Dirichlet boundary value problem is derived in the formκ<√2ε(n+1)+2, whereN=n ² is the size of the discrete problem, andε stands for the ratio of the anisotropy. Various numerical tests demonstrating the behavior of the circulant block-factorization preconditioners for anisotropic problems are presented.     

Block preconditioners with circulant blocks for general linear systems

Block preconditioner with circulant blocks (BPCB) has been used for solving linear systems with block Toeplitz structure since 1992 [R. Chan, X. Jin, A family of block preconditioners for block systems, SIAM J. Sci. Statist. Comput. (13) (1992) 1218–1235]. In this new paper, we use BPCBs to general linear systems (with no block structure usually). The BPCBs are constructed by partitioning a general matrix into a block matrix with blocks of the same size and then applying T. Chan’s optimal circulant preconditioner [T. Chan, An optimal circulant preconditioner for Toeplitz systems, SIAM J. Sci. Statist. Comput. (9) (1988) 766–771] to each block. These BPCBs can be viewed as a generalization of T. Chan’s preconditioner. It is well-known that the optimal circulant preconditioner works well for solving some structured systems such as Toeplitz systems by using the preconditioned conjugate gradient (PCG) method, but it is usually not efficient for solving general linear systems. Unlike T. Chan’s preconditioner, BPCBs used here are efficient for solving some general linear systems by the PCG method. Several basic properties of BPCBs are studied. The relations of the block partition with the cost per iteration and the convergence rate of the PCG method are discussed. Numerical tests are given to compare the cost of the PCG method with different BPCBs.     

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.     

Lanczos based preconditioner for discrete ill-posed problems

In this paper we use the Lanczos process for preconditioning discrete ill-posed problems. We show that by few steps of this process one can obtain a well qualified and efficient preconditioner. This is a general method in the sense that it is not limited only to special structured matrices and the matrix–vector multiplications can be carried out in O(n) operations. Also even in problems with structured matrices this preconditioner performs more efficiently than the circulant and Kronecker product approximate preconditioners.     

The approximate Dirichlet Domain Decomposition method. Part I: An algebraic approach

We present a new approach to the construction of Domain Decomposition (DD) preconditioners for the conjugate gradient method applied to the solution of symmetric and positive definite finite element equations. The DD technique is based on a non-overlapping decomposition of the domain Ω intop subdomains connected later with thep processors of a MIMD computer. The DD preconditioner derived contains three block matrices which must be specified for the specific problem considered. One of the matrices is used for the transformation of the nodal finite element basis into the approximate discrete harmonic basis. The other two matrices are block preconditioners for the Dirichlet problems arising on the subdomains and for a modified Schur complement defined over all nodes on the coupling boundaries between the subdomains. The relative spectral condition number is estimated. Relations to the additive Schwarz method are discussed. In the second part of this paper, we will apply the results of this paper to two-dimensional, symmetric, second-order, elliptic boundary value problems and present numerical results performed on a transputer-network.     

Block {ω}-circulant preconditioners¶for the systems of differential equations

The numerical solution of large and sparse nonsymmetric linear systems of algebraic equations is usually the most time consuming part of time-step integrators for differential equations based on implicit formulas. Preconditioned Krylov subspace methods using Strang block circulant preconditioners have been employed to solve such linear systems. However, it has been observed that these block circulant preconditioners can be very ill-conditioned or singular even when the underlying nonpreconditioned matrix is well-conditioned. In this paper we propose the more general class of the block { ω }-circulant preconditioners. For the underlying problems, ω can be chosen so that the condition number of these preconditioners is much smaller than that of the Strang block circulant preconditioner (which belongs to the same class with ω =1) and the related iterations can converge very quickly. Received: January 2002 / Accepted: December 2002 The research of the first author was supported in part by INdAM-GNCS and by a grant from the MURST project “Progetto Giovani Ricercatori anno 2000”. The research of the second author was supported in part by Hong Kong Research Grants Council Grants Nos. HKU 7130/02P and HKU 7132/00P and UK/HK Joint Research Scheme Grant No. 20009819.     

On the multi-grid method applied to difference equations

Multi-grid methods are characterized by the simultaneous use of additional auxiliary grids corresponding to coarser step widths. Contrary to usual iterative methods the speed of convergence is very fast and does not tend to one if the step size approaches zero. The computational amount of one iteration is proportional toN, the number of grid points. Thus, a solution with accuracy ? requires 0 (|log ?|N) operations. In this paper we apply a multi-grid method to Helmholtz's equation (Dirichlet boundary data) in a general region and to a differential equation with variable coefficients subject to arbitrary boundary conditions.     

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.     

h-p Spectral Element Method for Elliptic Problems on Non-smooth Domains Using Parallel Computers

We propose a new h-p spectral element method to solve elliptic boundary value problems with mixed Neumann and Dirichlet boundary conditions on non-smooth domains. The method is shown to be exponentially accurate and asymptotically faster than the standard h-p finite element method. The spectral element functions are fully non-conforming for pure Dirichlet problems and conforming only at the vertices of the elements for mixed problems, and hence, the dimension of the resulting Schur complement matrix is quite small. The method is a least-squares collocation method and the resulting normal equations are solved using preconditioned conjugate gradient method with an almost optimal preconditioner. The algorithm is suitable for a distributed memory parallel computer. The numerical results of a number of model problems are presented, which confirm the theoretical estimates.     

Variants of the deteriorated PSS preconditioner for saddle point problems

Two new preconditioners, which can be viewed as variants of the deteriorated positive definite and skew-Hermitian splitting preconditioner, are proposed for solving saddle point problems. The corresponding iteration methods are proved to be convergent unconditionally for cases with positive definite leading blocks. The choice strategies of optimal parameters for the two iteration methods are discussed based on two recent optimization results for extrapolated Cayley transform, which result in faster convergence rate and more clustered spectrum. Compared with some preconditioners of similar structures, the new preconditioners have better convergence properties and spectrum distributions. In addition, more practical preconditioning variants of the new preconditioners are considered. Numerical experiments are presented to illustrate the advantages of the new preconditioners over some similar preconditioners to accelerate GMRES.     

New block triangular preconditioner for linear systems arising from the discretized time-harmonic Maxwell equations

In this paper, based on the preconditioners presented by Rees and Greif [T. Rees, C. Greif, A preconditioner for linear systems arising from interior point optimization methods, SIAM J. Sci. Comput. 29 (2007) 1992-2007], we present a new block triangular preconditioner applied to the problem of solving linear systems arising from finite element discretization of the mixed formulation of the time-harmonic Maxwell equations (k=0) in electromagnetic problems, since linear systems arising from the corresponding equations and methods have the same matrix block structure. Similar to spectral distribution of the preconditioners presented by Rees and Greif, this paper analyzes the corresponding spectral distribution of the new preconditioners considered in this paper. From the views of theories and applications, the presented preconditioners are as efficient as the preconditioners presented by Rees and Greif to apply. Moreover, numerical experiments are also reported to illustrate the efficiency of the presented preconditioners.     

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 preconditioner for generalized saddle point matrices with highly singular(1,1) blocks

In this paper, based on the preconditioners presented by Cao [A note on spectrum analysis of augmentation block preconditioned generalized saddle point matrices, Journal of Computational and Applied Mathematics 238(15) (2013), pp. 109–115], we introduce and study a new augmentation block preconditioners for generalized saddle point matrices whose coefficient matrices have singular (1,1) blocks. Moreover, theoretical analysis gives the eigenvalue distribution, forms of the eigenvectors and its minimal polynomial. Finally, numerical examples show that the eigenvalue distribution with presented preconditioner has the same spectral clustering with preconditioners in the literature when choosing the optimal parameters and the preconditioner in this paper and in the literature improve the convergence of BICGSTAB and GMRES iteration efficiently when they are applied to the preconditioned BICGSTAB and GMRES to solve the Stokes equation and two-dimensional time-harmonic Maxwell equations by choosing different parameters.     

A general class of shift-splitting preconditioners for non-Hermitian saddle point problems with applications to time-harmonic eddy current models

Based on a general splitting of the (1,1) leading block matrix, we first construct a general class of shift-splitting (GCSS) preconditioners for non-Hermitian saddle point problems. Convergence conditions of the corresponding matrix splitting iteration methods and preconditioning properties of the GCSS preconditioned saddle point matrices are analyzed. Then the GCSS preconditioner is specifically applied to the non-Hermitian saddle point problems arising from the finite element discretizations of the hybrid formulations of the time-harmonic eddy current models. With suitable choices of the splittings, the new GCSS preconditioners are easier to implement and have faster convergence rates than the existing shift-splitting preconditioner and its modified variant. Two numerical examples are presented to verify the theoretical results and show effectiveness of the new proposed preconditioners.     

Variable Additive Preconditioning Procedures

Iterative methods with variable preconditioners of additive type are proposed. The scaling factors of each summand in the additive preconditioners are optimized within each iteration step. It is proved that the presented methods converge at least as fast as the Richardson's iterative method with the corresponding additive preconditioner with optimal scaling factors. In the presented numerical experiments the suggested methods need nearly the same number of iterations as the usual preconditioned conjugate gradient method with the corresponding additive preconditioner with numerically determined fixed optimal scaling factors. Received: June 10, 1998; revised October 16, 1998     

Multilevel Schwarz methods for elliptic partial differential equations

We investigate multilevel Schwarz domain decomposition preconditioners, to efficiently solve linear systems arising from numerical discretizations of elliptic partial differential equations by the finite element method. In our analysis we deal with unstructured mesh partitions and with subdomain boundaries resulting from using the mesh partitioner. We start from two-level preconditioners with either aggregative or interpolative coarse level components, then we focus on a strategy to increase the number of levels. For all preconditioners, we consider the additive residual update and its multiplicative variants within and between levels. Moreover, we compare the preconditioners behaviour, regarding scalability and rate of convergence. Numerical results are provided for elliptic boundary value problems, including a convection–diffusion problem when suitable stabilization becomes necessary.     

A numerical method for exact boundary controllability problems for the wave equation

The computational approximation of exact boundary controllability problems for the wave equation in two dimensions is studied. A numerical method is defined that is based on the direct solution of optimization problems that are introduced in order to determine unique solutions of the controllability problem. The uniqueness of the discrete finite-difference solutions obtained in this manner is demonstrated. The convergence properties of the method are illustrated through computational experiments. Efficient implementation strategies for the method are also discussed. It is shown that for smooth, minimum L²-norm Dirichlet controls, the method results in convergent approximations without the need to introduce regularization. Furthermore, for the generic case of nonsmooth Dirichlet controls, convergence with respect to L² norms is also numerically demonstrated. One of the strengths of the method is the flexibility it allows for treating other controls and other minimization criteria; such generalizations are discussed. In particular, the minimum H¹-norm Dirichlet controllability problem is approximated and solved, as are minimum regularized L²-norm Dirichlet controllability problems with small penalty constants. Finally, a discussion is provided about the differences between our method and existing methods; these differences may explain why our methods provide convergent approximations for problems for which existing methods produce divergent approximations unless they are regularized in some manner.     

A sixth-order extrapolation method for special nonlinear fourth-order boundary value problems

A sixth-order convergent finite difference method is developed for the numerical solution of the special nonlinear fourth-order boundary value problem y^(iv)(x) = f(x, y), a < x < b, y(a) = A₀, y″(a) = B₀, y(b) = A₁ y′(b) = B₁, the simple-simple beam problem.The method is based on a second-order convergent method which is used on three grids, sixth-order convergence being obtained by taking a linear combination of the (second-order) numerical results calculated using the three individual grids.Special formulas are proposed for application to points of the discretization adjacent to the boundaries x = a and x= b, the first two terms of the local truncation errors of these formulas being the same as those of the second-order method used at the other points of each grid.Modifications to these two formulas are obtained for problems with boundary conditions of the form y(a) = A₀, y′(a) = C₀, y(b) = A₁, y′(b) = C₁, the clamped-clamped beam problem.The general boundary value problem, for which the differential equation is y^(iv)(x) = f(x, y, y′, y″, y‴), is also considered.     

Schwarz iterations for the efficient solution of screen problems with boundary elements

This paper investigates two domain decomposition algorithms for the numerical solution of boundary integral equations of the first kind. The schemes are based on theh-type boundary element Galerkin method to which the multiplicative and the additive Schwarz methods are applied. As for twodimensional problems, the rates of convergence of both methods are shown to be independent of the number of unknowns. Numerical results for standard model problems arising from Laplaces' equation with Dirichlet or Neumann boundary conditions in both two and three dimensions are discussed. A multidomain decomposition strategy is indicated by means of a screen problem in three dimensions, so as to obtain satisfactory experimental convergence rates.     

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.