Uzawa methods for a class of block three‐by‐three saddle‐point problems

In this work, we consider numerical methods for solving a class of block three‐by‐three saddle‐point problems, which arise from finite element methods for solving time‐dependent Maxwell equations and some other applications. The direct extension of the Uzawa method for solving this block three‐by‐three saddle‐point problem requires the exact solution of a symmetric indefinite system of linear equations at each step. To avoid heavy computations at each step, we propose an inexact Uzawa method, which solves the symmetric indefinite linear system in some inexact way. Under suitable assumptions, we show that the inexact Uzawa method converges to the unique solution of the saddle‐point problem within the approximation level. Two special algorithms are customized for the inexact Uzawa method combining the splitting iteration method and a preconditioning technique, respectively. Numerical experiments are presented, which demonstrated the usefulness of the inexact Uzawa method and the two customized algorithms.     

Optimal parameters in the HSS‐like methods for saddle‐point problems

For the Hermitian and skew‐Hermitian splitting iteration method and its accelerated variant for solving the large sparse saddle‐point problems, we compute their quasi‐optimal iteration parameters and the corresponding quasi‐optimal convergence factors for the more practical but more difficult case that the (1, 1)‐block of the saddle‐point matrix is not algebraically equivalent to the identity matrix. In addition, the algebraic behaviors and the clustering properties of the eigenvalues of the preconditioned matrices with respect to these two iterations are investigated in detail, and the formulas for computing good iteration parameters are given under certain principle for optimizing the distribution of the eigenvalues. Copyright © 2008 John Wiley & Sons, Ltd.     

Analysis of iterative methods for saddle point problems: a unified approach

In this paper two classes of iterative methods for saddle point problems are considered: inexact Uzawa algorithms and a class of methods with symmetric preconditioners. In both cases the iteration matrix can be transformed to a symmetric matrix by block diagonal matrices, a simple but essential observation which allows one to estimate the convergence rate of both classes by studying associated eigenvalue problems. The obtained estimates apply for a wider range of situations and are partially sharper than the known estimates in literature. A few numerical tests are given which confirm the sharpness of the estimates.

     

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.     

Interior‐point methods and preconditioning for PDE‐constrained optimization problems involving sparsity terms

Partial differential equation (PDE)–constrained optimization problems with control or state constraints are challenging from an analytical and numerical perspective. The combination of these constraints with a sparsity‐promoting L¹ term within the objective function requires sophisticated optimization methods. We propose the use of an interior‐point scheme applied to a smoothed reformulation of the discretized problem and illustrate that such a scheme exhibits robust performance with respect to parameter changes. To increase the potency of this method, we introduce fast and efficient preconditioners that enable us to solve problems from a number of PDE applications in low iteration numbers and CPU times, even when the parameters involved are altered dramatically.     

求解分布控制问题的预处理最小残量方法(英文)

通过分析Bai(Bai Z Z.Block preconditioners for elliptic PDE-constrained optimization problems.Computing,2011,91:379-395)给出的离散分布控制问题的块反对角预处理线性系统,提出了该问题的一个等价线性系统,并且运用带有预处理子的最小残量方法对该系统进行求解.理论分析和数值实验结果表明,所提出的预处理最小残量方法对于求解该类椭圆型偏微分方程约束最优分布控制问题非常有效,尤其当正则参数适当小的时候.     

A high‐order compact ADI method for solving three‐dimensional unsteady convection‐diffusion problems

We derive a high‐order compact alternating direction implicit (ADI) method for solving three‐dimentional unsteady convection‐diffusion problems. The method is fourth‐order in space and second‐order in time. It permits multiple uses of the one‐dimensional tridiagonal algorithm with a considerable saving in computing time and results in a very efficient solver. It is shown through a discrete Fourier analysis that the method is unconditionally stable in the diffusion case. Numerical experiments are conducted to test its high order and to compare it with the standard second‐order Douglas‐Gunn ADI method and the spatial fourth‐order compact scheme by Karaa. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

Preconditioned iterative methods for fractional diffusion models in finance

Most recent qualitative models for financial assets assume that the dynamics of underlying equity prices follows a jump or Lévy process. It has been evident that some most intricate characteristics of such dynamics can be captured by CGMY and KoBoL procedures. The prices of financial derivatives with such models satisfy fractional partial differential equations or partial integro‐differential equations. This study focuses at aforementioned fractional equations and discretizes them via a monotone Crank–Nicolson procedure. A spatial extrapolation strategy is introduced to ensure an overall second‐order accuracy in approximations. Preconditioned conjugate gradient normal residual methods are incorporated for solving resulted linear systems. Numerical examples are given to illustrate the accuracy and efficiency of the novel computational approaches implemented. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 1382–1395, 2015     

Fast iterative solver for convection‐diffusion systems with spectral elements

We introduce a solver and preconditioning technique based on Domain Decomposition and the Fast Diagonalization Method that can be applied to tensor product based discretizations of the steady convection–diffusion equation. The method is based on a Robin–Robin interface preconditioner coupled to a fast diagonalization solver which is used to efficiently eliminate the interior degrees of freedom and perform subsidiary subdomain solves. Using a spectral element discretization, we first apply our technique to constant wind problems, and then propose a means for applying the technique as a preconditioner for variable wind problems. We demonstrate that iteration counts are mildly dependent on changes in mesh size and convection strength. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Duality scheme for solving the semicoercive signorini problem with friction

The iterative Uzawa method with a modified Lagrangian functional is used to numerically solve the semicoercive Signorini problem with friction (quasi-variational inequality).     

The corrected Uzawa method for solving saddle point problems

In this paper, we consider the solution of linear systems of saddle point type by correcting the Uzawa algorithm, which has been proposed in [K. Arrow, L. Hurwicz, H. Uzawa, Studies in nonlinear programming, Stanford University Press, Stanford, CA, 1958]. We call this method as corrected Uzawa (CU) method. The convergence of the CU method is analyzed for solving nonsingular saddle point problem as well as the semi‐convergence for the singular case. First, the corrected model for the Uzawa algorithm is established, and the CU algorithm is presented. Then we study the geometric meaning of the CU model. Moreover, we introduce the overall reduction coefficient α to measure the effect of the CU process. It is shown that the CU method converges faster than the Uzawa method and several other methods if the overall reduction coefficient α satisfies certain conditions. Numerical experiments are presented to illustrate the theoretical results and examine the numerical effectiveness of the CU method. Copyright © 2015 John Wiley & Sons, Ltd.     

Preconditioners for state‐constrained optimal control problems with Moreau–Yosida penalty function

Optimal control problems with partial differential equations as constraints play an important role in many applications. The inclusion of bound constraints for the state variable poses a significant challenge for optimization methods. Our focus here is on the incorporation of the constraints via the Moreau–Yosida regularization technique. This method has been studied recently and has proven to be advantageous compared with other approaches. In this paper, we develop robust preconditioners for the efficient solution of the Newton steps associated with the fast solution of the Moreau–Yosida regularized problem. Numerical results illustrate the efficiency of our approach. Copyright © 2012 John Wiley & Sons, Ltd.     

Projected Schur complement method for solving non‐symmetric systems arising from a smooth fictitious domain approach

This paper deals with a fast method for solving large‐scale algebraic saddle‐point systems arising from fictitious domain formulations of elliptic boundary value problems. A new variant of the fictitious domain approach is analyzed. Boundary conditions are enforced by control variables introduced on an auxiliary boundary located outside the original domain. This approach has a significantly higher convergence rate; however, the algebraic systems resulting from finite element discretizations are typically non‐symmetric. The presented method is based on the Schur complement reduction. If the stiffness matrix is singular, the reduced system can be formulated again as another saddle‐point problem. Its modification by orthogonal projectors leads to an equation that can be efficiently solved using a projected Krylov subspace method for non‐symmetric operators. For this purpose, the projected variant of the BiCGSTAB algorithm is derived from the non‐projected one. The behavior of the method is illustrated by examples, in which the BiCGSTAB iterations are accelerated by a multigrid strategy. Copyright © 2007 John Wiley & Sons, Ltd.     

Preconditioning trace coupled 3d‐1d systems using fractional Laplacian

Multiscale or multiphysics problems often involve coupling of partial differential equations posed on domains of different dimensionality. In this work, we consider a simplified model problem of a 3d‐1d coupling and the main objective is to construct algorithms that may utilize standard multilevel algorithms for the 3d domain, which has the dominating computational complexity. Preconditioning for a system of two elliptic problems posed, respectively, in a three‐dimensional domain and an embedded one dimensional curve and coupled by the trace constraint is discussed. Investigating numerically the properties of the well‐defined discrete trace operator, it is found that negative fractional Sobolev norms are suitable preconditioners for the Schur complement of the system. The norms are employed to construct a robust block diagonal preconditioner for the coupled problem.     

An iterative method based on a modified Lagrangian functional for finding a saddle point in the semicoercive Signorini problem

The iterative Uzawa method with a modified Lagrangian functional is examined in the framework of the Signorini problem.     

A parameterized extended shift-splitting preconditioner for nonsymmetric saddle point problems

In this article, a parameterized extended shift-splitting (PESS) method and its induced preconditioner are given for solving nonsingular and nonsymmetric saddle point problems with nonsymmetric positive definite (1,1) part. The convergence analysis of the $PESS$ iteration method is discussed. The distribution of eigenvalues of the preconditioned matrix is provided. A number of experiments are given to verify the efficiency of the $PESS$ method for solving nonsymmetric saddle-point problems.     

Graded Galerkin methods for the high‐order convection‐diffusion problem

We develop a Galerkin method using the Hermite spline on an admissible graded mesh for solving the high‐order singular perturbation problem of the convection‐diffusion type. We identify a special function class to which the solution of the convection‐diffusion problem belongs and characterize the approximation order of the Hermite spline for such a function class. The approximation order is then used to establish the optimal order of uniform convergence for the Galerkin method. Numerical results are presented to confirm the theoretical estimate.© 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Robust multilevel methods for quadratic finite element anisotropic elliptic problems

This paper discusses a class of multilevel preconditioners based on approximate block factorization for conforming finite element methods employing quadratic trial and test functions. The main focus is on diffusion problems governed by a scalar elliptic partial differential equation with a strongly anisotropic coefficient tensor. The proposed method provides a high robustness with respect to non‐grid‐aligned anisotropy, which is achieved by the interaction of the following components: (i) an additive Schur complement approximation to construct the coarse‐grid operator; (ii) a global block (Jacobi or Gauss–Seidel) smoother complementing the coarse‐grid correction based on (i); and (iii) utilization of an augmented coarse grid, which enhances the efficiency of the interplay between (i) and (ii). The performed analysis indicates the high robustness of the resulting two‐level method. Moreover, numerical tests with a nonlinear algebraic multilevel iteration method demonstrate that the presented two‐level method can be applied successfully in the recursive construction of uniform multilevel preconditioners of optimal or nearly optimal order of computational complexity. Copyright © 2013 John Wiley & Sons, Ltd.     

Iterative proximal regularization of the modified Lagrangian functional for solving the quasi-variational Signorini inequality

The iterative Uzawa method with a modified Lagrangian functional is used to numerically solve the semicoercive Signorini problem with friction (quasi-variational inequality).