Residual reduction algorithms for nonsymmetric saddle point problems

In this paper, we introduce and analyze Uzawa algorithms for non-symmetric saddle point systems. Convergence for the algorithms is established based on new spectral results about Schur complements. A new Uzawa type algorithm with optimal relaxation parameters at each new iteration is introduced and analyzed in a general framework. Numerical results supporting the efficiency of the algorithms are presented for finite element discretization of steady state Navier-Stokes equations.     

Perturbation analysis of generalized saddle point systems

We discuss the perturbation analysis of generalized saddle point systems in this paper. We give the nonlinear perturbation bounds, then derive the condition numbers, and analyze the sensitivity of the computed solutions.     

A dual-parametric finite element method for cavitation in nonlinear elasticity

A dual-parametric finite element method is introduced in this paper for the computation of singular minimizers in the 2D cavitation problem in nonlinear elasticity. The method overcomes the difficulties, such as the mesh entanglement and material interpenetration, generally encountered in the finite element approximation of problems with extremely large expansionary deformation. Numerical experiments show that the method is highly efficient in the computation of cavitation problems. Numerical experiments are also conducted on discrete problems without the radial symmetry to show the validity of the method to more general settings and the potential of its application to the study of mechanism of cavity nucleation in nonlinear elastic materials.     

Robust smoothers for high-order discontinuous Galerkin discretizations of advection–diffusion problems

The multigrid method for discontinuous Galerkin (DG) discretizations of advection–diffusion problems is presented. It is based on a block Gauss–Seidel smoother with downwind ordering honoring the advection operator. The cell matrices of the DG scheme are inverted in this smoother in order to obtain robustness for higher order elements. Employing a set of experiments, we show that this technique actually yields an efficient preconditioner and that both ingredients, downwind ordering and blocking of cell matrices are crucial for robustness.     

Linear and bilinear immersed finite elements for planar elasticity interface problems

This article is to discuss the linear (which was proposed in  and ) and bilinear immersed finite element (IFE) methods for solving planar elasticity interface problems with structured Cartesian meshes. Basic features of linear and bilinear IFE functions, including the unisolvent property, will be discussed. While both methods have comparable accuracy, the bilinear IFE method requires less time for assembling its algebraic system. Our analysis further indicates that the bilinear IFE functions are guaranteed to be applicable to a larger class of elasticity interface problems than linear IFE functions. Numerical examples are provided to demonstrate that both linear and bilinear IFE spaces have the optimal approximation capability, and that numerical solutions produced by a Galerkin method with these IFE functions for elasticity interface problem also converge optimally in both L²$L^2$ and semi-H¹$H^1$ norms.     

On nonsymmetric saddle point matrices that allow conjugate gradient iterations

Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix ${{\mathcal A}}Linear systems in saddle point form are usually highly indefinite,which often slows down iterative solvers such as Krylov subspace methods. It has been noted by several authors that negating the second block row of a symmetric indefinite saddle point matrix leads to a nonsymmetric matrix whose spectrum is entirely contained in the right half plane. In this paper we study conditions so that is diagonalizable with a real and positive spectrum. These conditions are based on necessary and sufficient conditions for positive definiteness of a certain bilinear form,with respect to which is symmetric. In case the latter conditions are satisfied, there exists a well defined conjugate gradient (CG) method for solving linear systems with . We give an efficient implementation of this method, discuss practical issues such as error bounds, and present numerical experiments. In memory of Gene Golub (1932–2007), our wonderful friend and colleague, who had a great interest in the conjugate gradient method and the numerical solution of saddle point problems. The work of J?rg Liesen was supported by the Emmy Noether-Program and the Heisenberg-Program of the Deutsche Forschungsgemeinschaft.     

A mixed finite element method for nonlinear elasticity: two-fold saddle point approach and a-posteriori error estimate

Summary. We extend the applicability of stable mixed finite elements for linear plane elasticity, such as PEERS, to a mixed variational formulation of hyperelasticity. The present approach is based on the introduction of the strain tensor as a further unknown, which yields a two-fold saddle point nonlinear operator equation for the corresponding weak formulation. We provide the uniqueness of solution for the continuous and discrete schemes, and derive the usual Cea estimate for the associated error. Finally, a reliable a-posteriori error estimate, based on the solution of local Dirichlet problems, and well suited for adaptive computations, is also given. Received August 5, 2000 / Published online August 17, 2001     

Static condensation,partial orthogonalization of basis functions,and ILU preconditioning in the hp-FEM

Static condensation of internal degrees of freedom, partial orthogonalization of basis functions, and ILU preconditioning are techniques used to facilitate the solution of discrete problems obtained in the hp-FEM. This paper shows that for symmetric linear (not necessarily positive-definite) problems, under mild technical assumptions, these three techniques are completely equivalent. In fact, the same matrices can be obtained by the same arithmetic operations. The study can be extended to nonsymmetric problems naturally.     

A posteriori dual-mixed adaptive finite element error control for Lamé and Stokes equations

A unified and robust mathematical model for compressible and incompressible linear elasticity can be obtained by rephrasing the Herrmann formulation within the Hellinger-Reissner principle. This quasi-optimally converging extension of PEERS (Plane Elasticity Element with Reduced Symmetry) is called Dual-Mixed Hybrid formulation (DMH). Explicit residual-based a posteriori error estimates for DMH are introduced and are mathematically shown to be locking-free, reliable, and efficient. The estimator serves as a refinement indicator in an adaptive algorithm for effective automatic mesh generation. Numerical evidence supports that the adaptive scheme leads to optimal convergence for Lamé and Stokes benchmark problems with singularities.     

Limiting accuracy of segregated solution methods for nonsymmetric saddle point problems

Nonsymmetric saddle point problems arise in a wide variety of applications in computational science and engineering. The aim of this paper is to discuss the numerical behavior of several nonsymmetric iterative methods applied for solving the saddle point systems via the Schur complement reduction or the null-space projection approach. Krylov subspace methods often produce the iterates which fluctuate rather strongly. Here we address the question whether large intermediate approximate solutions reduce the final accuracy of these two-level (inner–outer) iteration algorithms. We extend our previous analysis obtained for symmetric saddle point problems and distinguish between three mathematically equivalent back-substitution schemes which lead to a different numerical behavior when applied in finite precision arithmetic. Theoretical results are then illustrated on a simple model example.     

On the eigenvalues of a class of saddle point matrices

We study spectral properties of a class of block 2 × 2 matrices that arise in the solution of saddle point problems. These matrices are obtained by a sign change in the second block equation of the symmetric saddle point linear system. We give conditions for having a (positive) real spectrum and for ensuring diagonalizability of the matrix. In particular, we show that these properties hold for the discrete Stokes operator, and we discuss the implications of our characterization for augmented Lagrangian formulations, for Krylov subspace solvers and for certain types of preconditioners. The work of this author was supported in part by the National Science Foundation grant DMS-0207599 Revision dated 5 December 2005.     

Numerical solution of the two-dimensional Poincaré equation

This paper deals with numerical approximation of the two-dimensional Poincaré equation that arises as a model for internal wave motion in enclosed containers. Inspired by the hyperbolicity of the equation we propose a discretisation particularly suited for this problem, which results in matrices whose size varies linearly with the number of grid points along the coordinate axes. Exact solutions are obtained, defined on a perturbed boundary. Furthermore, the problem is seen to be ill-posed and there is need for a regularisation scheme, which we base on a minimal-energy approach.     

A saddle point variational formulation for projection–regularized parameter identification

Summary. This paper is concerned with the ill-posed problem of identifying a parameter in an elliptic equation and its solution applying regularization by projection. As the theory has shown, the ansatz functions for the parameter have to be sufficiently smooth. In this paper we show that these – for a practical implementation unrealistic – smoothness assumptions can be circumvented by reformulating the problem under consideration as a mixed variational equation. We prove convergence as the discretization gets finer in the noise free case and convergence as the data noise level goes to zero in the case of noisy data, as well as convergence rates under additional smoothness conditions. Received August 4, 2000 / Revised version received March 21, 2001 / Published online October 17, 2001     

On Schwarz-type smoothers for saddle point problems with applications to PDE-constrained optimization problems

In this paper we consider a (one-shot) multigrid strategy for solving the discretized optimality system (KKT system) of a PDE-constrained optimization problem. In particular, we discuss the construction of an additive Schwarz-type smoother for a certain class of optimal control problems. A rigorous multigrid convergence analysis is presented. Numerical experiments are shown which confirm the theoretical results. The work was supported by the Austrian Science Fund (FWF) under grant SFB 013/F1309.     

Performance and analysis of saddle point preconditioners for the discrete steady-state Navier-Stokes equations

Summary. We examine the convergence characteristics of iterative methods based on a new preconditioning operator for solving the linear systems arising from discretization and linearization of the steady-state Navier-Stokes equations. With a combination of analytic and empirical results, we study the effects of fundamental parameters on convergence. We demonstrate that the preconditioned problem has an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. The structure of these distributions is independent of the discretization mesh size, but the cardinality of the set of outliers increases slowly as the viscosity becomes smaller. These characteristics are directly correlated with the convergence properties of iterative solvers. Received August 5, 2000 / Published online June 20, 2001     

An augmented mixed finite element method for 3D linear elasticity problems

In this paper we introduce and analyze a new augmented mixed finite element method for linear elasticity problems in 3D. Our approach is an extension of a technique developed recently for plane elasticity, which is based on the introduction of consistent terms of Galerkin least-squares type. We consider non-homogeneous and homogeneous Dirichlet boundary conditions and prove that the resulting augmented variational formulations lead to strongly coercive bilinear forms. In this way, the associated Galerkin schemes become well posed for arbitrary choices of the corresponding finite element subspaces. In particular, Raviart-Thomas spaces of order 0 for the stress tensor, continuous piecewise linear elements for the displacement, and piecewise constants for the rotation can be utilized. Moreover, we show that in this case the number of unknowns behaves approximately as 9.5 times the number of elements (tetrahedrons) of the triangulation, which is cheaper, by a factor of 3, than the classical PEERS in 3D. Several numerical results illustrating the good performance of the augmented schemes are provided.     

Iterative solution of a singular convection-diffusion perturbation problem

An iterative domain decomposition method is developed to solve a singular perturbation problem. The problem consists of a convection-diffusion equation with a discontinuous (piecewise-constant) diffusion coefficient, and the problem domain is decomposed into two subdomains, on each of which the coefficient is constant. After showing that the boundary value problem is well posed, we indicate a specific numerical implementation of the iterative technique that combines the finite element method on one subdomain with the method of matched asymptotic expansions on the other subdomain. This procedure extends work by Carlenzoli and Quarteroni, which was originally intended for a boundary layer problem with an outer region and an inner region. Our extension carries over to a problem where the domain consists of the outer and inner boundary layer regions plus a region in which the diffusion coefficient is constant and significant in magnitude. An unexpected benefit of our new implementation is its efficiency, which is due to the fact that at each iteration the problem needs to be solved explicitly only on one subdomain. It is only when the final approximation on the entire domain is desired that the matched asymptotic expansions approximation need be computed on the second subdomain. Two-dimensional convergence results and numerical results illustrating the method for a two-dimensional test problem are given.Received: February 12, 2004     

An iterative algorithm for a quasivariational inequality system related to HJB equation

This paper presents a new iterative algorithm for a quasivariational inequality system related to HJB equation. A domain decomposition method based on this algorithm is proposed. The convergence theorems have been established.     

Boundary value problems in spaces of distributions on smooth and polygonal domains

We study boundary value problems of the form -Δu=f$-\mathrm{\Delta }u=f$ on Ω$\Omega$ and Bu=g$\mathit{Bu}=g$ on the boundary ∂Ω$\mathrm{\partial }\Omega$, with either Dirichlet or Neumann boundary conditions, where Ω$\Omega$ is a smooth bounded domain in Rⁿ${\mathbb{R}}^n$ and the data f,g$f,g$ are distributions  . This problem has to be first properly reformulated and, for practical applications, it is of crucial importance to obtain the continuity of the solution u$u$ in terms of f and g  . For f=0$f=0$, taking advantage of the fact that u$u$ is harmonic on Ω$\Omega$, we provide four formulations of this boundary value problem (one using nontangential limits of harmonic functions, one using Green functions, one using the Dirichlet-to-Neumann map, and a variational one); we show that these four formulations are equivalent. We provide a similar analysis for f≠0$f\ne 0$ and discuss the roles of f and g, which turn to be somewhat interchangeable in the low regularity case. The weak formulation is more convenient for numerical approximation, whereas the nontangential limits definition is closer to the intuition and easier to check in concrete situations. We extend the weak formulation to polygonal domains using weighted Sobolev spaces. We also point out some new phenomena for the “concentrated loads” at the vertices in the polygonal case.     

Characterizing Hilbert cube manifolds by their homological structure

A hierarchy of disjoint ?ech carriers properties is introduced; and each is shown to be characteristic of ANR's whose products with 2-cells are Hilbert cube manifolds.