Analysis of optimal preconditioners for CutFEM

In this article, we consider a class of unfitted finite element methods for scalar elliptic problems. These so-called CutFEM methods use standard finite element spaces on a fixed unfitted triangulation combined with the Nitsche technique and a ghost penalty stabilization. As a model problem we consider the application of such a method to the Poisson interface problem. We introduce and analyze a new class of preconditioners that is based on a subspace decomposition approach. The unfitted finite element space is split into two subspaces, where one subspace is the standard finite element space associated to the background mesh and the second subspace is spanned by all cut basis functions corresponding to nodes on the cut elements. We will show that this splitting is stable, uniformly in the discretization parameter and in the location of the interface in the triangulation. Based on this we introduce an efficient preconditioner that is uniformly spectrally equivalent to the stiffness matrix. Using a similar splitting, it is shown that the same preconditioning approach can also be applied to a fictitious domain CutFEM discretization of the Poisson equation. Results of numerical experiments are included that illustrate optimality of such preconditioners for the Poisson interface problem and the Poisson fictitious domain problem.     

Remarks on Multilevel Bases for Divergence-Free Finite Elements

The connection between the multilevel factorization method recently proposed by Sarin and Sameh for solving mixed discretizations of the Stokes equation using a divergence-free finite element formulation, and hierarchical basis preconditioners for the Poisson problem is established. For the 2D triangular Taylor–Hood element, a preconditioner is proposed that could be useful in fractional step methods.     

Uniform preconditioners for a parameter dependent saddle point problem with application to generalized Stokes interface equations

We consider an abstract parameter dependent saddle-point problem and present a general framework for analyzing robust Schur complement preconditioners. The abstract analysis is applied to a generalized Stokes problem, which yields robustness of the Cahouet-Chabard preconditioner. Motivated by models for two-phase incompressible flows we consider a generalized Stokes interface problem. Application of the general theory results in a new Schur complement preconditioner for this class of problems. The robustness of this preconditioner with respect to several parameters is treated. Results of numerical experiments are given that illustrate robustness properties of the preconditioner.     

Kronecker product approximation preconditioners for convection–diffusion model problems

We consider the iterative solution of linear systems arising from four convection–diffusion model problems: scalar convection–diffusion problem, Stokes problem, Oseen problem and Navier–Stokes problem. We design preconditioners for these model problems that are based on Kronecker product approximations (KPAs). For this we first identify explicit Kronecker product structure of the coefficient matrices, in particular for the convection term. For the latter three model cases, the coefficient matrices have a 2 × 2 block structure, where each block is a Kronecker product or a summation of several Kronecker products. We then use this structure to design a block diagonal preconditioner, a block triangular preconditioner and a constraint preconditioner. Numerical experiments show the efficiency of the three KPA preconditioners, and in particular of the constraint preconditioner that usually outperforms the other two. This can be explained by the relationship that exists between these three preconditioners: the constraint preconditioner can be regarded as a modification of the block triangular preconditioner, which at its turn is a modification of the block diagonal preconditioner based on the cell Reynolds number. Copyright © 2009 John Wiley & Sons, Ltd.     

A class of generalized shift-splitting preconditioners for nonsymmetric saddle point problems

In this paper, a class of generalized shift-splitting preconditioners with two shift parameters are implemented for nonsymmetric saddle point problems with nonsymmetric positive definite (1, 1) block. The generalized shift-splitting (GSS) preconditioner is induced by a generalized shift-splitting of the nonsymmetric saddle point matrix, resulting in an unconditional convergent fixed-point iteration. By removing the shift parameter in the (1, 1) block of the GSS preconditioner, a deteriorated shift-splitting (DSS) preconditioner is presented. Some useful properties of the DSS preconditioned saddle point matrix are studied. Finally, numerical experiments of a model Navier–Stokes problem are presented to show the effectiveness of the proposed preconditioners.     

Evaluation of ST preconditioners for saddle point problems

The general block ST decomposition of the saddle point problem is used as a preconditioner to transform the saddle point problem into an equivalent symmetric and positive definite system. Such a decomposition is called a block ST preconditioner. Two general block ST preconditioners are proposed for saddle point problems with symmetric and positive definite (1,1)-block. Some estimations of the condition number of the preconditioned system are given. The same study is done for singular (1,1)-block.     

Parallel block preconditioning based on SSOR and MILU

Two kinds of parallel preconditioners for the solution of large sparse linear systems which arise from the 2-D 5-point finite difference discretization of a convection-diffusion equation are introduced. The preconditioners are based on the SSOR or MILU preconditioners and can be implemented on parallel computers with distributed memories. One is the block preconditioner, in which the interface components of the coefficient matrix between blocks are ignored to attain parallelism in the forward-backward substitutions. The other is the modified block preconditioner, in which the block preconditioner is modified by taking the interface components into account. The effect of these preconditioners on the convergence of preconditioned iterative methods and timing results on the parallel computer (Cenju) are presented.     

Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A_n. The th column of our circulant preconditioner Sn is equal to the th column of the given matrix A_n. Thus if A_n is a square Toeplitz matrix, then Sn is just the Strang circulant preconditioner. When Sn is not Hermitian, our circulant preconditioner can be defined as . This construction is similar to the forward-backward projection method used in constructing preconditioners for tomographic inversion problems in medical imaging. We show that if the matrix A_n has decaying coefficients away from the main diagonal, then is a good preconditioner for An. Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min ∥ b - Ax∥₂. Preliminary numerical results show that our preconditioner performs quite well, in comparison to other circulant preconditioners. Promising test results are also reported for a 2-D deconvolution problem arising in ground-based atmospheric imaging.     

SINE TRANSFORM MATRIX FOR SOLVING TOEPLITZ MATRIX PROBLEMS

1. IntroductionStrang[1] first studied the use of circulallt matrices C for solving systems of linear eqllationsTi x = b witha symmetric positive definite Toeplitz matrix.Numerous authors such as T.Chan[2],R.Chan,etc.[3],[4],[5], Tyrtyshnikov[6], Huckle[7] and T.Ku and C.Kuo[8] proposed differentfamilies of circulallt / skew- circulant precondit ioners.Appling the preconditioned conjugate gradient algorithm(PCGA) to solve the systems Ti x -b, we must find a preconditioner P such that P…     

A new alternating positive semidefinite splitting preconditioner for saddle point problems from time-harmonic eddy current models

Based on the special positive semidefinite splittings of the saddle point matrix, we propose a new alternating positive semidefinite splitting (APSS) iteration method for the saddle point problem arising from the finite element discretization of the hybrid formulation of the time-harmonic eddy current problem. We prove that the new APSS iteration method is unconditionally convergent for both cases of the simple topology and the general topology. The new APSS matrix can be used as a preconditioner to accelerate the convergence rate of Krylov subspace methods. Numerical results show that the new APSS preconditioner is superior to the existing preconditioners.     

Parallel preconditioners for large scale partial difference equation systems

We propose a new preconditioner DASP (discrete approximate spectral preconditioner), based on the existing well-known preconditioners and our computational experience. Parallel preconditioning strategies for large scale partial difference equation systems arising from partial differential equations are investigated. Numerical results are given to show the efficiency and effectiveness of the new preconditioners for both model problems and real applications in petroleum reservoir simulation.     

Block ILU Preconditioners for a Nonsymmetric Block-Tridiagonal M-Matrix

We propose block ILU (incomplete LU) factorization preconditioners for a nonsymmetric block-tridiagonal M-matrix whose computation can be done in parallel based on matrix blocks. Some theoretical properties for these block ILU factorization preconditioners are studied and then we describe how to construct them effectively for a special type of matrix. We also discuss a parallelization of the preconditioner solver step used in nonstationary iterative methods with the block ILU preconditioners. Numerical results of the right preconditioned BiCGSTAB method using the block ILU preconditioners are compared with those of the right preconditioned BiCGSTAB using a standard ILU factorization preconditioner to see how effective the block ILU preconditioners are.     

A hybrid domain decomposition method based on aggregation

A new two‐level black‐box preconditioner based on the hybrid domain decomposition technique is proposed and studied. The preconditioner is a combination of an additive Schwarz preconditioner and a special smoother. The smoother removes dependence of the condition number on the number of subdomains and variations of the diffusion coefficient and leaves minor sensitivity to the problem size. The algorithm is parallel and pure algebraic which makes it a convenient framework for the construction parallel black‐box preconditioners on unstructured meshes. Copyright © 2004 John Wiley & Sons, Ltd.     

Augmented Lagrangian-based preconditioners for steady buoyancy driven flow

In this paper, we apply the augmented Lagrangian (AL) approach to steady buoyancy driven flow problems. Two AL preconditioners are developed based on the variable’s order, specifically whether the leading variable is the velocity or the temperature variable. Correspondingly, two non-augmented Lagrangian (NAL) preconditioners are also considered for comparison. An eigenvalue analysis for these two pairs of preconditioners is conducted to predict the rate of convergence for the GMRES solver. The numerical results show that the AL preconditioner pair is insensitive with respect to the mesh size, Rayleigh number, and Prandtl number in terms of GMRES iterations, resulting in a significantly more robust preconditioner pair compared to the NAL pair. Accordingly, the AL pair performs much better than the NAL pair in terms of computational time. For the AL pair, the preconditioner with velocity as the leading variable gives slightly better efficiency than the one with temperature as the leading variable.     

Parallel preconditioners and multigrid solvers for stochastic polynomial chaos discretizations of the diffusion equation at the large scale

This paper presents parallel preconditioners and multigrid solvers for solving linear systems of equations arising from stochastic polynomial chaos formulations of the diffusion equation with random coefficients. These preconditioners and solvers are extensions of the preconditioner developed in an earlier paper for strongly coupled systems of elliptic partial differential equations that are norm equivalent to systems that can be factored into an algebraic coupling component and a diagonal differential component. The first preconditioner, which is applied to the norm equivalent system, is obtained by sparsifying the inverse of the algebraic coupling component. This sparsification leads to an efficient method for solving these systems at the large scale, even for problems with large statistical variations in the random coefficients. An extension of this preconditioner leads to stand‐alone multigrid methods that can be applied directly to the actual system rather than to the norm equivalent system. These multigrid methods exploit the algebraic/differential factorization of the norm equivalent systems to produce variable‐decoupled systems on the coarse levels. Moreover, the structure of these methods allows easy software implementation through re‐use of robust high‐performance software such as the Hypre library package. Two‐grid matrix bounds will be established, and numerical results will be given. Copyright © 2015 John Wiley & Sons, Ltd.     

Preconditioners Based on Fit Techniques for the Iterative Regularization in the Image Deconvolution Problem

For large-scale image deconvolution problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n²) operations per iteration, where n² is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n² log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of O(n²) operations per iteration. A numerical experimentation shows that the fit preconditioners are competitive with the regularizing Chan preconditioner, both in the regularizing efficiency and the computational cost. AMS subject classification (2000) 65F10, 65F22.Received October 2003. Accepted December 2004. Communicated by Lars Eldén.     

An approximate BDDC preconditioner

The balancing domain decomposition by constraints (BDDC) preconditioner requires direct solutions of two linear systems for each substructure and one linear system for a global coarse problem. The computations and memory needed for these solutions can be prohibitive if any one system is too large. We investigate an approach for addressing this issue based on approximating the direct solutions using preconditioners. In order to retain the attractive numerical properties of the exact version of BDDC, some of the preconditioners must possess a property related to the substructure null spaces. We describe a simple method to equip preconditioners with this property. Numerical results demonstrate the usefulness of the approach and confirm the theory. Published in 2006 by John Wiley & Sons, Ltd.     

A New Iteration and Preconditioning Method for Elliptic PDE-Constrained Optimization Problems

Optimal control problems constrained by a partial differential equation (PDE) arise in various important applications, such as in engineering and natural sciences. Normally the problems are of very large scale, so iterative solution methods must be used. Thereby the choice of an iteration method in conjunction with an efficient preconditioner is essential. In this paper, we consider a new iteration method and a new preconditioning technique for an elliptic PDE-constrained optimal control problem with a distributed control function. Some earlier used iteration methods and preconditioners in the literature are compared, both analytically and numerically with the new iteration method and the preconditioner.     

A family of constrained pressure residual preconditioners for parallel reservoir simulations

Large‐scale reservoir simulations are extremely time‐consuming because of the solution of large‐scale linear systems arising from the Newton or Newton–Raphson iterations. The problem becomes even worse when highly heterogeneous geological models are employed. This paper introduces a family of multi‐stage preconditioners for parallel black oil simulations, which are based on the famous constrained pressure residual preconditioner. Numerical experiments demonstrate that our preconditioners are robust, efficient, and scalable. Copyright © 2015 John Wiley & Sons, Ltd.     

Effectiveness and robustness revisited for a preconditioning technique based on structured incomplete factorization

In this work, we provide new analysis for a preconditioning technique called structured incomplete factorization (SIF) for symmetric positive definite matrices. In this technique, a scaling and compression strategy is applied to construct SIF preconditioners, where off‐diagonal blocks of the original matrix are first scaled and then approximated by low‐rank forms. Some spectral behaviors after applying the preconditioner are shown. The effectiveness is confirmed with the aid of a type of two‐dimensional and three‐dimensional discretized model problems. We further show that previous studies on the robustness are too conservative. In fact, the practical multilevel version of the preconditioner has a robustness enhancement effect, and is unconditionally robust (or breakdown free) for the model problems regardless of the compression accuracy for the scaled off‐diagonal blocks. The studies give new insights into the SIF preconditioning technique and confirm that it is an effective and reliable way for designing structured preconditioners. The studies also provide useful tools for analyzing other structured preconditioners. Various spectral analysis results can be used to characterize other structured algorithms and study more general problems.