Block-circulant preconditioners for systems arising from discretization of the three-dimensional convection–diffusion equation

We consider the system of equations arising from finite difference discretization of a three-dimensional convection–diffusion model problem. This system is typically nonsymmetric. The GMRES method with the Strang block-circulant preconditioner is proposed for solving this linear system. We show that our preconditioners are invertible and study the spectra of the preconditioned matrices. Numerical results are reported to illustrate the effectiveness of our methods.     

基于多层增量未知元方法的一类三维对流扩散方程的研究

对于一类一般形式的三维对流扩散方程, 运用有限差分方法, 在增量未知元方法(IU)下, 可以得到一个IU型正定但非对称的线性方程组.其系数矩阵条件数要远远优于不用IU方法的情形^[1]. 考虑到IU方法的这一优点, 作者在文中将IU方法与几种经典的迭代方法相结合, 来求解上述系统. 作者从理论上对该系统的IU型系数矩阵条件数进行了估计, 并通过数值试验验证了这几种IU型迭代方法的有效性.     

Semi-Conjugate Direction Methods for Real Positive Definite Systems

In this preliminary work, left and right conjugate direction vectors are defined for nonsymmetric, nonsingular matrices A and some properties of these vectors are studied. A left conjugate direction (LCD) method for solving nonsymmetric systems of linear equations is proposed. The method has no breakdown for real positive definite systems. The method reduces to the usual conjugate gradient method when A is symmetric positive definite. A finite termination property of the semi-conjugate direction method is shown, providing a new simple proof of the finite termination property of conjugate gradient methods. The new method is well defined for all nonsingular M-matrices. Some techniques for overcoming breakdown are suggested for general nonsymmetric A. The connection between the semi-conjugate direction method and LU decomposition is established. The semi-conjugate direction method is successfully applied to solve some sample linear systems arising from linear partial differential equations, with attractive convergence rates. Some numerical experiments show the benefits of this method in comparison to well-known methods. This revised version was published online in July 2006 with corrections to the Cover Date.     

Two-grid finite volume element methods for semilinear parabolic problems

Two-grid finite volume element methods, based on two linear conforming finite element spaces on one coarse grid and one fine grid, are presented and studied for two-dimensional semilinear parabolic problems. With the proposed techniques, solving the nonsymmetric and nonlinear system on the fine space is reduced to solving a symmetric and linear system on the fine space and solving the nonsymmetric and nonlinear system on a much smaller space. Convergence estimates are derived to justify the efficiency of the proposed two-grid algorithms. It is proved that the coarse grid can be much coarser than the fine grid. As a result, solving such a large class of semilinear parabolic problems will not be much more difficult than solving one single linearized equation. In the end a numerical example is presented to validate the usefulness and efficiency of the method.     

Uzawa type algorithms for nonsymmetric saddle point problems

In this paper, we consider iterative algorithms of Uzawa type for solving linear nonsymmetric saddle point problems. Specifically, we consider systems, written as usual in block form, where the upper left block is an invertible linear operator with positive definite symmetric part. Such saddle point problems arise, for example, in certain finite element and finite difference discretizations of Navier-Stokes equations, Oseen equations, and mixed finite element discretization of second order convection-diffusion problems. We consider two algorithms, each of which utilizes a preconditioner for the operator in the upper left block. Convergence results for the algorithms are established in appropriate norms. The convergence of one of the algorithms is shown assuming only that the preconditioner is spectrally equivalent to the inverse of the symmetric part of the operator. The other algorithm is shown to converge provided that the preconditioner is a sufficiently accurate approximation of the inverse of the upper left block. Applications to the solution of steady-state Navier-Stokes equations are discussed, and, finally, the results of numerical experiments involving the algorithms are presented.

     

Exponential Stability for Discrete Time Linear Equations Defined by Positive Operators

In this paper the problem of exponential stability of the zero state equilibrium of a discrete-time time-varying linear equation described by a sequence of linear positive operators acting on an ordered finite dimensional Hilbert space is investigated. The class of linear equations considered in this paper contains as particular cases linear equations described by Lyapunov operators or symmetric Stein operators as well as nonsymmetric Stein operators. Such equations occur in connection with the problem of mean square exponential stability for a class of difference stochastic equations affected by independent random perturbations and Markovian jumping as well us in connection with some iterative procedures which allow us to compute global solutions of discrete time generalized symmetric or nonsymmetric Riccati equations. The exponential stability is characterized in terms of the existence of some globally defined and bounded solutions of some suitable backward affine equations (inequalities) or forward affine equations (inequalities).     

A comparison of some domain decomposition and ILU preconditioned iterative methods for nonsymmetric elliptic problems

In recent years, competitive domain-decomposed preconditioned iterative techniques of Krylov-Schwarz type have been developed for nonsymmetric linear elliptic systems. Such systems arise when convection-diffusion-reaction problems from computational fluid dynamics or heat and mass transfer are linearized for iterative solution. Through domain decomposition, a large problem is divided into many smaller problems whose requirements for coordination can be controlled to allow effective solution on parallel machines. A central question is how to choose these small problems and how to arrange the order of their solution. Different specifications of decomposition and solution order lead to a plethora of algorithms possessing complementary advantages and disadvantages. In this report we compare several methods, including the additive Schwarz algorithm, the classical multiplicative Schwarz algorithm, an accelerated multiplicative Schwarz algorithm, the tile algorithm, the CGK algorithm, the CSPD algorithm, and also the popular global ILU-family of preconditioners, on some nonsymmetric or indefinite elliptic model problems discretized by finite difference methods. The preconditioned problems are solved by the unrestarted GMRES method. A version of the accelerated multiplicative Schwarz method is a consistently good performer.     

Cascadic Multigrid for Finite Volume Methods for Elliptic Problems

In this paper, some effective cascadic multigrid methods are proposed for solving the large scale symmetric or nonsymmetric algebraic systems arising from the finite volume methods for second order elliptic problems. It is shown that these algorithms are optimal in both accuracy and computational complexity. Numerical experiments are reported to support our theory.     

Convergence and quasi-optimality of adaptive nonconforming finite element methods for some nonsymmetric and indefinite problems

Recently an adaptive nonconforming finite element method (ANFEM) has been developed by Carstensen and Hoppe (in Numer Math 103:251–266, 2006). In this paper, we extend the result to some nonsymmetric and indefinite problems. The main tools in our analysis are a posteriori error estimators and a quasi-orthogonality property. In this case, we need to overcome two main difficulties: one stems from the nonconformity of the finite element space, the other is how to handle the effect of a nonsymmetric and indefinite bilinear form. An appropriate adaptive nonconforming finite element method featuring a marking strategy based on the comparison of the a posteriori error estimator and a volume term is proposed for the lowest order Crouzeix–Raviart element. It is shown that the ANFEM is a contraction for the sum of the energy error and a scaled volume term between two consecutive adaptive loops. Moreover, quasi-optimality in the sense of quasi-optimal algorithmic complexity can be shown for the ANFEM. The results of numerical experiments confirm the theoretical findings.     

Nonlinear uzawa methods for solving nonsymmetric saddle point problems

In [A new nonlinear Uzawa algorithm for generalized saddle point problems, Appl. Math. Comput., 175(2006), 1432–1454], a nonlinear Uzawa algorithm for solving symmetric saddle point problems iteratively, which was defined by two nonlinear approximate inverses, was considered. In this paper, we extend it to the nonsymmetric case. For the nonsymmetric case, its convergence result is deduced. Moreover, we compare the convergence rates of three nonlinear Uzawa methods and show that our method is more efficient than other nonlinear Uzawa methods in some cases. The results of numerical experiments are presented when we apply them to Navier-Stokes equations discretized by mixed finite elements.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

Error bounds for monotone approximation schemes for parabolic Hamilton-Jacobi-Bellman equations

We obtain nonsymmetric upper and lower bounds on the rate of convergence of general monotone approximation/numerical schemes for parabolic Hamilton-Jacobi-Bellman equations by introducing a new notion of consistency. Our results are robust and general - they improve and extend earlier results by Krylov, Barles, and Jakobsen. We apply our general results to various schemes including Crank-Nicholson type finite difference schemes, splitting methods, and the classical approximation by piecewise constant controls. In the first two cases our results are new, and in the last two cases the results are obtained by a new method which we develop here.

     

A Two-Level Method for Nonsymmetric Eigenvalue Problems

A two-level discretization method for eigenvalue problems is studied. Compared to the standard Galerkin finite element discretization technique performed on a fine grid this method discretizes the eigenvalue problem on a coarse grid and obtains an improved eigenvector (eigenvalue) approximation by solving only a linear problem on the fine grid (or two linear problems for the case of eigenvalue approximation of nonsymmetric problems). The improved solution has the asymptotic accuracy of the Galerkin discretization solution. The link between the method and the iterated Galerkin method is established. Error estimates for the general nonsymmetric case are derived.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996     

A fast approach of nonparametric elastic image registration problem

In this paper, we present a fast algorithm of the nonparametric elastic image registration using a simple implementation of the Range Restricted GMRES (RRGMRES) method. This approach differs from the others in the fact that it is specified to the tridiagonal block matrix type to resolve a nonsymmetric linear system. In what follows, we prove existence and uniqueness of minimizer of the elastic registration problem and present the corresponding discrete problem by employing a finite difference scheme. The accuracy of the proposed method is demonstrated on different image registration examples; we also show the speedup of the proposed approach by calculating the corresponding CPU time and compared it with the classical elastic registration method.     

Relaxed and stabilized incomplete factorizations for non-self-adjoint linear systems

Two classes of incomplete factorization preconditioners are considered for nonsymmetric linear systems arising from second order finite difference discretizations of non-self-adjoint elliptic partial differential equations. Analytic and experimental results show that relaxed incomplete factorization methods exhibit numerical instabilities of the type observed with other incomplete factorizations, and the effects of instability are characterized in terms of the relaxation parameter. Several stabilized incomplete factorizations are introduced that are designed to avoid numerically unstable computations. In experiments with two-dimensional problems with variable coefficients and on nonuniform meshes, the stabilized methods are shown to be much more robust than standard incomplete factorizations.The work presented in this paper was supported by the National Science Foundation under grants DMS-8607478, CCR-8818340, and ASC-8958544, and by the U.S. Army Research Office under grant DAAL-0389-K-0016.     

Symmetric Part Preconditioning of the CG Method for Stokes Type Saddle-Point Systems

A nonsymmetric formulation of saddle-point systems is considered, and symmetric part preconditioning of the CG method is applied. Linear and superlinear convergence estimates are derived for the finite element solution of the Stokes problem and of Navier's equations of elasticity. Mesh independence of the estimates is obtained from proper Hilbert space operator background.     

INTERFACE PROBLEMS FOR ELLIPTIC DIFFERENTIAL EQUATIONS

ＩＮＴＥＲＦＡＣＥＰＲＯＢＬＥＭＳＦＯＲＥＬＬＩＰＴＩＣＤＩＦＦＥＲＥＮＴＩＡＬＥＱＵＡＴＩＯＮＳＹＩＮＧＬＵＮＧＡＮＡｂｓｔｒａｃｔＡｎｅｗａｐｐｒｏａｃｈｉｓｇｉｖｅｎｔｏａｎａｌｙｓｅｔｈｅｒｅｇｕｌａｒｉｔｙｏｆｓｏｌｕｔｉｏｎｓｎｅａｒｓ...     

Numerical simulations of glacial rebound using preconditioned iterative solution methods

This paper discusses finite element discretization and preconditioning strategies for the iterative solution of nonsymmetric indefinite linear algebraic systems of equations arising in modelling of glacial rebound processes. Some numerical experiments for the purely elastic model setting are provided. Comparisons of the performance of the iterative solution method with a direct solution method are included as well.     

非匹配网格上Stokes-Darcy模型的非协调元方法及其预条件技术

本文讨论了非匹配网格上Stokes-Darcy模型的两种低阶非协调元方法,证明了离散问题的适定性并得到了最优的误差估计.对离散出来的非对称不定线性方程组,我们提出了几种有效的预条件子,证明了预条件子的最优性.最后,数值试验验证了我们的理论结果.