速度追踪问题中鞍点系统的新分裂迭代

 有限元离散一类速度追踪问题后得到具有鞍点结构的线性系统,针对该鞍点系统,本文提出了一种新的分裂迭代技术.证明了新的分裂迭代方法的无条件收敛性,详细分析了新的分裂预条件子对应的预处理矩阵的谱性质.数值结果验证了对于大范围的网格参数和正则参数,新的分裂预条件子在求解有限元离散速度追踪问题得到的鞍点系统时的可行性和有效性.     

A Dirichlet-Neumann Algorithm for Mortar Saddle Point Problems

A discretization of second order elliptic problems by the finite element method on nonmatching triangulation is discussed. The discrete problem is described as a saddle point problem obtained by a mortar technique. A Dirichlet-Neumann preconditioner is designed and analyzed for the discrete problem. It allows the use of an iterative preconditioner cg method with almost optimal rate of convergence.     

A new relaxed HSS preconditioner for saddle point problems

We present a preconditioner for saddle point problems. The proposed preconditioner is extracted from a stationary iterative method which is convergent under a mild condition. Some properties of the preconditioner as well as the eigenvalues distribution of the preconditioned matrix are presented. The preconditioned system is solved by a Krylov subspace method like restarted GMRES. Finally, some numerical experiments on test problems arisen from finite element discretization of the Stokes problem are given to show the effectiveness of the preconditioner.     

A robust optimal preconditioner for the mixed finite element discretization of elliptic optimal control problems

In this paper, we consider the efficient solving of the resulting algebraic system for elliptic optimal control problems with mixed finite element discretization. We propose a block‐diagonal preconditioner for the symmetric and indefinite algebraic system solved with minimum residual method, which is proved to be robust and optimal with respect to both the mesh size and the regularization parameter. The block‐diagonal preconditioner is constructed based on an isomorphism between appropriately chosen solution space and its dual for a general control problem with both state and gradient state observations in the objective functional. Numerical experiments confirm the efficiency of our proposed preconditioner.     

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.     

A multilevel discontinuous Galerkin method

A variable V-cycle preconditioner for an interior penalty finite element discretization for elliptic problems is presented. An analysis under a mild regularity assumption shows that the preconditioner is uniform. The interior penalty method is then combined with a discontinuous Galerkin scheme to arrive at a discretization scheme for an advection-diffusion problem, for which an error estimate is proved. A multigrid algorithm for this method is presented, and numerical experiments indicating its robustness with respect to diffusion coefficient are reported.Received: 5 June 2001, Revised: 12 December 2001, Published online: 4 April 2003Mathematics Subject Classification (1991): 65F10, 65N55, 65N30This research was supported in part by Institute for Mathematics and its Applications, Supercomputing Institute of University of Minnesota, and Deutsche Forschungsgemeinschaft.     

Robust multigrid preconditioners for the high‐contrast biharmonic plate equation

We study the high‐contrast biharmonic plate equation with Hsieh–Clough–Tocher discretization. We construct a preconditioner that is robust with respect to contrast size and mesh size simultaneously based on the preconditioner proposed by Aksoylu et al. (Comput. Vis. Sci. 2008; 11 :319–331). By extending the devised singular perturbation analysis from linear finite element discretization to the above discretization, we prove and numerically demonstrate the robustness of the preconditioner. Therefore, we accomplish a desirable preconditioning design goal by using the same family of preconditioners to solve the elliptic family of PDEs with varying discretizations. We also present a strategy on how to generalize the proposed preconditioner to cover high‐contrast elliptic PDEs of order 2k, k>2. Moreover, we prove a fundamental qualitative property of the solution to the high‐contrast biharmonic plate equation. Namely, the solution over the highly bending island becomes a linear polynomial asymptotically. The effectiveness of our preconditioner is largely due to the integration of this qualitative understanding of the underlying PDE into its construction. Copyright © 2010 John Wiley & Sons, Ltd.     

A prewavelet-based algorithm for the solution of second-order elliptic differential equations with variable coefficients on sparse grids

We present a Ritz-Galerkin discretization on sparse grids using prewavelets, which allows us to solve elliptic differential equations with variable coefficients for dimensions d ≥ 2. The method applies multilinear finite elements. We introduce an efficient algorithm for matrix vector multiplication using a Ritz-Galerkin discretization and semi-orthogonality. This algorithm is based on standard 1-dimensional restrictions and prolongations, a simple prewavelet stencil, and the classical operator-dependent stencil for multilinear finite elements. Numerical simulation results are presented for a three-dimensional problem on a curvilinear bounded domain and for a six-dimensional problem with variable coefficients. Simulation results show a convergence of the discretization according to the approximation properties of the finite element space. The condition number of the stiffness matrix can be bounded below 10 using a standard diagonal preconditioner.     

Analysis of a Stokes interface problem

We consider a stationary Stokes problem with a piecewise constant viscosity coefficient. For the variational formulation of this problem we prove a well-posedness result in which the constants are uniform with respect to the jump in the viscosity coefficient. We apply a standard discretization with a pair of LBB stable finite element spaces. The main result of the paper is an infsup result for the discrete problem that is uniform with respect to the jump in the viscosity coefficient. From this we derive a robust estimate for the discretization error. We prove that the mass matrix with respect to some suitable scalar product yields a robust preconditioner for the Schur complement. Results of numerical experiments are presented that illustrate this robustness property. This author was supported by the German Research Foundation through the guest program of SFB 540     

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.     

Fast preconditioned iterative methods for finite volume discretization of steady-state space-fractional diffusion equations

We consider the preconditioned Krylov subspace method for linear systems arising from the finite volume discretization method of steady-state variable-coefficient conservative space-fractional diffusion equations. We propose to use a scaled-circulant preconditioner to deal with such Toeplitz-like discretization matrices. We show that the difference between the scaled-circulant preconditioner and the coefficient matrix is equal to the sum of a small-norm matrix and a low-rank matrix. Numerical tests are conducted to show the effectiveness of the proposed method for one- and two-dimensional steady-state space-fractional diffusion equations and demonstrate that the preconditioned Krylov subspace method converges very quickly.     

AMLI preconditioner for the p‐version of the FEM

From the literature it is known that the conjugate gradient method with domain decomposition preconditioners is one of the most efficient methods for solving systems of linear algebraic equations resulting from p‐version finite element discretizations of elliptic boundary value problems. One ingredient of such a preconditioner is a preconditioner related to the Dirichlet problems. In the case of Poisson's equation, we present a preconditioner for the Dirichlet problems which can be interpreted as the stiffness matrix K_h,k resulting from the h‐version finite element discretization of a special degenerated problem. We construct an AMLI preconditioner C_h,k for the matrix K_h,k and show that the condition number of C K_h,k is independent of the discretization parameter. This proof is based on the strengthened Cauchy inequality. The theoretical result is confirmed by numerical examples. Copyright © 2003 John Wiley & Sons, Ltd.     

A preconditioned GMRES for complex dense linear systems from electromagnetic wave scattering problems

We consider the numerical solution of linear systems arising from the discretization of the electric field integral equation (EFIE). For some geometries the associated matrix can be poorly conditioned making the use of a preconditioner mandatory to obtain convergence. The electromagnetic scattering problem is here solved by means of a preconditioned GMRES in the context of the multilevel fast multipole method (MLFMM). The novelty of this work is the construction of an approximate hierarchically semiseparable (HSS) representation of the near-field matrix, the part of the matrix capturing interactions among nearby groups in the MLFMM, as preconditioner for the GMRES iterations. As experience shows, the efficiency of an ILU preconditioning for such systems essentially depends on a sufficient fill-in, which apparently sacrifices the sparsity of the near-field matrix. In the light of this experience we propose a multilevel near-field matrix and its corresponding HSS representation as a hierarchical preconditioner in order to substantially reduce the number of iterations in the solution of the resulting system of equations.     

Block triangular preconditioners for nonsymmetric saddle point problems: field-of-values analysis

A preconditioned minimal residual method for nonsymmetric saddle point problems is analyzed. The proposed preconditioner is of block triangular form. The aim of this article is to show that a rigorous convergence analysis can be performed by using the field of values of the preconditioned linear system. As an example, a saddle point problem obtained from a mixed finite element discretization of the Oseen equations is considered. The convergence estimates obtained by using a field–of–values analysis are independent of the discretization parameter h. Several computational experiments supplement the theoretical results and illustrate the performance of the method. Received March 20, 1997 / Revised version received January 14, 1998     

Numerical solution of the elastic body-plate problem by nonoverlapping domain decomposition type techniques

The purpose of this paper is to provide two numerical methods for solving the elastic body-plate problem by nonoverlapping domain decomposition type techniques, based on the discretization method by Wang. The first one is similar to an older method, but here the corresponding Schur complement matrix is preconditioned by a specific preconditioner associated with the plate problem. The second one is a ``displacement-force' type Schwarz alternating method. At each iteration step of the two methods, either a pure body or a pure plate problem needs to be solved. It is shown that both methods have a convergence rate independent of the size of the finite element mesh.

     

On the singular Neumann problem in linear elasticity

The Neumann problem of linear elasticity is singular with a kernel formed by the rigid motions of the body. There are several tricks that are commonly used to obtain a nonsingular linear system. However, they often cause reduced accuracy or lead to poor convergence of the iterative solvers. In this paper, different well‐posed formulations of the problem are studied through discretization by the finite element method, and preconditioning strategies based on operator preconditioning are discussed. For each formulation, we derive preconditioners that are independent of the discretization parameter. Preconditioners that are robust with respect to the first Lamé constant are constructed for the pure displacement formulations, whereas a preconditioner that is robust in both Lamé constants is constructed for the mixed formulation. It is shown that, for convergence in the first Sobolev norm, it is crucial to respect the orthogonality constraint derived from the continuous problem. On the basis of this observation, a modification to the conjugate gradient method is proposed, which achieves optimal error convergence of the computed solution.     

Hierarchical Schur complement preconditioner for the stochastic Galerkin finite element methods

Use of the stochastic Galerkin finite element methods leads to large systems of linear equations obtained by the discretization of tensor product solution spaces along their spatial and stochastic dimensions. These systems are typically solved iteratively by a Krylov subspace method. We propose a preconditioner, which takes an advantage of the recursive hierarchy in the structure of the global matrices. In particular, the matrices posses a recursive hierarchical two‐by‐two structure, with one of the submatrices block diagonal. Each of the diagonal blocks in this submatrix is closely related to the deterministic mean‐value problem, and the action of its inverse is in the implementation approximated by inner loops of Krylov iterations. Thus, our hierarchical Schur complement preconditioner combines, on each level in the approximation of the hierarchical structure of the global matrix, the idea of Schur complement with loops for a number of mutually independent inner Krylov iterations, and several matrix–vector multiplications for the off‐diagonal blocks. Neither the global matrix nor the matrix of the preconditioner need to be formed explicitly. The ingredients include only the number of stiffness matrices from the truncated Karhunen–Loève expansion and a good preconditioned for the mean‐value deterministic problem. We provide a condition number bound for a model elliptic problem, and the performance of the method is illustrated by numerical experiments. Copyright © 2013 John Wiley & Sons, Ltd.     

Modified tangential frequency filtering decomposition and its fourier analysis

In this paper, a modified tangential frequency filtering decomposition (MTFFD) preconditioner is proposed. The optimal order of the modification and the optimal relaxation parameter is determined by Fourier analysis. With the choice of optimal order of modification, the Fourier results show that the condition number of the preconditioned matrix is O(h^-\frac23){{\mathcal O}(h^{-\frac{2}{3}})}, and the spectrum distribution of the preconditioned matrix can be predicted by the Fourier results. The performance of MTFFD preconditioner is compared with tangential frequency filtering (TFFD) preconditioner on a variety of large sparse matrices arising from the discretization of PDEs with discontinuous coefficients. The numerical results show that the MTFFD preconditioner is much more efficient than the TFFD preconditioner.     

Low frequency tangential filtering decomposition

For block‐tridiagonal systems of linear equations arising from the discretization of partial differential equations, a composite preconditioner is proposed and tested. It combines a classical ILU0 factorization for high frequencies with a tangential filtering preconditioner. The choice of the filtering vector is important: the test‐vector is the Ritz eigenvector corresponding to the approximate lowest eigenvalue, obtained after a limited number of iterations of a ILU0 preconditioned Krylov method. Numerical tests are carried out for this method. Copyright © 2006 John Wiley & Sons, Ltd.     

Additive Schwarz Method for Mortar Discretization of Elliptic Problems with <Emphasis Type="Italic">P</Emphasis><Subscript>1</Subscript> Nonconforming Finite Elements

An additive Schwarz preconditioner for nonconforming mortar finite element discretization of a second order elliptic problem in two dimensions with arbitrary large jumps of the discontinuous coefficients in subdomains is described. An almost optimal estimate of the condition number of the preconditioned problem is proved. The number of preconditioned conjugate gradient iterations is independent of jumps of the coefficients and is proportional to (1+log(H/h)), where H,h are mesh sizes. AMS subject classification (2000) 65N55, 65N30, 65N22