Analysis of FETI methods for multiscale PDEs

In this paper, we study a variant of the finite element tearing and interconnecting (FETI) method which is suitable for elliptic PDEs with highly heterogeneous (multiscale) coefficients α(x); in particular, coefficients with strong variation within subdomains and/or jumps that are not aligned with the subdomain interfaces. Using energy minimisation and cut-off arguments we can show rigorously that for an arbitrary (positive) coefficient function the condition number of the preconditioned FETI system can be bounded by C(α) (1 + log(H/h))² where H is the subdomain diameter and h is the mesh size, and where the function C(α) depends only on the coefficient variation in the vicinity of subdomain interfaces. In particular, if varies only mildly in a layer Ω _i,η of width η near the boundary of each of the subdomains Ω _i , then , independent of the variation of α in the remainder Ω _i \Ω _i,η of each subdomain and independent of any jumps of α across subdomain interfaces. The quadratic dependence of C(α) on H/η can be relaxed to a linear dependence under stronger assumptions on the behaviour of α in the interior of the subdomains. Our theoretical findings are confirmed in numerical tests. C. Pechstein was supported by the Austrian Science Funds (FWF) under grant F1306.     

Domain decomposition based $${\mathcal H}$$ -LU preconditioning

Hierarchical matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an -matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In this paper, we develop a new approach to construct the necessary partition based on domain decomposition. Compared to standard geometric bisection based -matrices, this new approach yields -LU factorizations of finite element stiffness matrices with significantly improved storage and computational complexity requirements. These rigorously proven and numerically verified improvements result from an -matrix block structure which is naturally suited for parallelization and in which large subblocks of the stiffness matrix remain zero in an LU factorization. We provide numerical results in which a domain decomposition based -LU factorization is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation. This work was supported in part by the US Department of Energy under Grant No. DE-FG02-04ER25649 and by the National Science Foundation under grant No. DMS-0408950.     

A new iterative method for discrete HJB equations

A successive relaxation iterative algorithm for discrete HJB equations is proposed. Monotone convergence has been proved for the algorithm. This work was supported by NNSF of China (no. 10571046).     

A dual iterative substructuring method with a penalty term

An iterative substructuring method with Lagrange multipliers is considered for second order elliptic problems, which is a variant of the FETI-DP method. The standard FETI-DP formulation is associated with the saddle-point problem which is induced from the minimization problem with a constraint for imposing the continuity across the interface. Starting from the slightly changed saddle-point problem by addition of a penalty term with a positive penalization parameter η, we propose a dual substructuring method which is implemented iteratively by the conjugate gradient method. In spite of the absence of any preconditioners, it is shown that the proposed method is numerically scalable in the sense that for a large value of η, the condition number of the resultant dual problem is bounded by a constant independent of both the subdomain size H and the mesh size h. Computational issues and numerical results are presented. This work was partially supported by the SRC/ERC program of MOST/KOSEF(R11-2002-103).     

The rate of convergence of GMRES on a tridiagonal Toeplitz linear system

The Generalized Minimal Residual method (GMRES) is often used to solve a nonsymmetric linear system Ax = b. But its convergence analysis is a rather difficult task in general. A commonly used approach is to diagonalize A = XΛ X ⁻¹ and then separate the study of GMRES convergence behavior into optimizing the condition number of X and a polynomial minimization problem over A’s spectrum. This artificial separation could greatly overestimate GMRES residuals and likely yields error bounds that are too far from the actual ones. On the other hand, considering the effects of both A’s spectrum and the conditioning of X at the same time poses a difficult challenge, perhaps impossible to deal with in general but only possible for certain particular linear systems. This paper will do so for a (nonsymmetric) tridiagonal Toeplitz system. Sharp error bounds on and sometimes exact expressions for residuals are obtained. These expressions and/or bounds are in terms of the three parameters that define A and Chebyshev polynomials of the first kind.     

Robust multigrid method for the planar linear elasticity problems

We consider the solution of the system of equations that arise from the higher order conforming finite element (Scott–Vogelius element) discretizations of the boundary value problems associated with the differential operator −ρ ² Δ − κ ²∇div, where ρ and κ are nonzero parameters. Robust multigrid method is constructed, i.e., the convergence rate of multigrid method is optimal with respect to the mesh size, the number of levels, and weights on the two terms in the aforementioned differential operator.

---

     

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.     

Crouzeix–Raviart boundary elements

This paper establishes a foundation of non-conforming boundary elements. We present a discrete weak formulation of hypersingular integral operator equations that uses Crouzeix–Raviart elements for the approximation. The cases of closed and open polyhedral surfaces are dealt with. We prove that, for shape regular elements, this non-conforming boundary element method converges and that the usual convergence rates of conforming elements are achieved. Key ingredient of the analysis is a discrete Poincaré–Friedrichs inequality in fractional order Sobolev spaces. A numerical experiment confirms the predicted convergence of Crouzeix–Raviart boundary elements. Norbert Heuer is supported by Fondecyt-Chile under grant no. 1080044. F.-J. Sayas is partially supported by MEC-FEDER Project MTM2007-63204 and Gobierno de Aragón (Grupo Consolidado PDIE).     

Convergence of LR algorithm for a one-point spectrum tridiagonal matrix

We prove convergence for the basic LR algorithm on a real unreduced tridiagonal matrix with a one-point spectrum—the Jordan form is one big Jordan block. First we develop properties of eigenvector matrices. We also show how to deal with the singular case.     

Adaptive eigenvalue computation: complexity estimates

This paper is concerned with the design and analysis of a fully adaptive eigenvalue solver for linear symmetric operators. After transforming the original problem into an equivalent one formulated on ℓ ₂, the space of square summable sequences, the problem becomes sufficiently well conditioned so that a gradient type iteration can be shown to reduce the error by some fixed factor per step. It then remains to realize these (ideal) iterations within suitable dynamically updated error tolerances. It is shown under which circumstances the adaptive scheme exhibits in some sense asymptotically optimal complexity. This research was supported in part by the Leibniz Programme of the DFG, by the SFB 401 funded by DFG, the DFG Priority Program SPP1145 and by the EU NEST project BigDFT.     

Hamiltonian systems of PDEs with selfdual boundary conditions

Selfdual variational calculus is developed further and used to address questions of existence of local and global solutions for various parabolic semi-linear equations, and Hamiltonian systems of PDEs. This allows for the resolution of such equations under general time boundary conditions which include the more traditional ones such as initial value problems, periodic and anti-periodic orbits, but also yield new ones such as “periodic orbits up to an isometry” for evolution equations that may not have periodic solutions. In the process, we introduce a method for perturbing selfdual functionals in order to induce coercivity and compactness, without destroying the selfdual character of the system. N. Ghoussoub was partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. A. Moameni’s research was supported by a postdoctoral fellowship at the University of British Columbia.     

Convergence analysis of the high-order mimetic finite difference method

We prove second-order convergence of the conservative variable and its flux in the high-order MFD method. The convergence results are proved for unstructured polyhedral meshes and full tensor diffusion coefficients. For the case of non-constant coefficients, we also develop a new family of high-order MFD methods. Theoretical result are confirmed through numerical experiments.     

Theoretical aspects of the application of convolution quadrature to scattering of acoustic waves

In this paper we address several theoretical questions related to the numerical approximation of the scattering of acoustic waves in two or three dimensions by penetrable non-homogeneous obstacles using convolution quadrature (CQ) techniques for the time variable and coupled boundary element method/finite element method for the space variable. The applicability of CQ to waves requires polynomial type bounds for operators related to the operator Δ − s ² in the right half complex plane. We propose a new systematic way of dealing with this problem, both at the continuous and semidiscrete-in-space cases. We apply the technique to three different situations: scattering by a group of sound-soft and -hard obstacles, by homogeneous and non-homogeneous obstacles.     

Discontinuous Galerkin least-squares finite element methods for singularly perturbed reaction-diffusion problems with discontinuous coefficients and boundary singularities

In this paper, a discontinuous Galerkin least-squares finite element method is developed for singularly perturbed reaction-diffusion problems with discontinuous coefficients and boundary singularities by recasting the second-order elliptic equations as a system of first-order equations. In a companion paper (Lin in SIAM J Numer Anal 47:89–108, 2008) a similar method has been developed for problems with continuous data and shown to be well-posed, uniformly convergent, and optimal in convergence rate. In this paper the method is modified to take care of conditions that arise at interfaces and boundary singularities. Coercivity and uniform error estimates for the finite element approximation are established in an appropriately scaled norm. Numerical examples confirm the theoretical results.     

A boundary element method for the Dirichlet eigenvalue problem of the Laplace operator

The solution of eigenvalue problems for partial differential operators by using boundary integral equation methods usually involves some Newton potentials which may be resolved by using a multiple reciprocity approach. Here we propose an alternative approach which is in some sense equivalent to the above. Instead of a linear eigenvalue problem for the partial differential operator we consider a nonlinear eigenvalue problem for an associated boundary integral operator. This nonlinear eigenvalue problem can be solved by using some appropriate iterative scheme, here we will consider a Newton scheme. We will discuss the convergence and the boundary element discretization of this algorithm, and give some numerical results.     

Domain decomposition iterative procedures for solving scalar waves in the frequency domain

The propagation of dispersive waves can be modeled relevantly in the frequency domain. A wave problem in the frequency domain is difficult to solve numerically. In addition to having a complex–valued solution, the problem is neither Hermitian symmetric nor coercive in a wide range of applications in Geophysics or Quantum–Mechanics. In this paper, we consider a parallel domain decomposition iterative procedure for solving the problem by finite differences or conforming finite element methods. The analysis includes the decomposition of the domain into either the individual elements or larger subdomains ( of finite elements). To accelerate the speed of convergence, we introduce relaxation parameters on the subdomain interfaces and an artificial damping iteration. The convergence rate of the resulting algorithm turns out to be independent on the mesh size and the wave number. Numerical results carried out on an nCUBE2 parallel computer are presented to show the effectiveness of the method. Received October 30, 1995 / Revised version received January 10, 1997     

Mathematical and numerical study of a corrosion model

In this paper, we consider a PDE system arising in corrosion modelling. This system consists in two convection-diffusion equations on the densities of charge carriers and a Poisson equation on the electric potential. Boundary conditions are Robin boundary conditions. We discretize each equation by a finite volume scheme and we prove the convergence of the scheme towards a weak solution to the initial system. Finally, we provide numerical results describing the behaviour of the solutions with respect to an applied voltage.     

Function classes for double exponential integration formulas

The double exponential (DE) formulas for numerical integration are known to be highly efficient, more efficient than the single exponential (SE) formulas in many cases. Function classes suited to the SE formulas have already been investigated in the literature through rigorous mathematical analysis, whereas this is not the case with the DE formulas. This paper identifies function classes suited to the DE formulas in a way compatible with the existing theoretical results for the SE formulas. The DE formulas are good for more restricted classes of functions, but more efficient for such functions. Two concrete examples demonstrate the subtlety in the behavior of the DE formulas that is revealed by our theoretical analysis.     

A new a posteriori error estimate for the Morley element

In this paper, we present a posteriori error analysis for the nonconforming Morley element of the fourth order elliptic equation. We propose a new residual-based a posteriori error estimator and prove its reliability and efficiency. These results refine those of Beirao da Veiga et al. (Numer Math 106:165–179, 2007) by dropping two edge jump terms in both the energy norm of the error and the estimator, and those of Wang and Zhang (Local a priori and a posteriori error estimates of finite elements for biharmonic equation, Research Report, 13, 2006) by showing the efficiency in the sense of Verfürth (A review of a posteriori error estimation and adaptive mesh-refinement techniques, Wiley-Teubner, New York, 1996). Moreover, the normal component in the estimators of Beirao da Veiga et al. (Numer Math 106:165–179, 2007) and Wang and Zhang (Local a priori and a posteriori error estimates of finite elements for biharmonic equation, Research Report, 13, 2006) is dropped, and therefore only the tangential component of the stress on each edge comes into the estimator. In addition, we generalize these results to three dimensional case.     

High accuracy analysis of two nonconforming plate elements

We prove the superconvergence of Morley element and the incomplete biquadratic nonconforming element for the plate bending problem. Under uniform rectangular meshes, we obtain a superconvergence property at the symmetric points of the elements and a global superconvergent result by a proper postprocessing method. The research is supported by the Special Funds For Major State Basic Research Project (No. 2005CB321701).