A monotone finite element scheme for convection-diffusion equations

A simple technique is given in this paper for the construction and analysis of a class of finite element discretizations for convection-diffusion problems in any spatial dimension by properly averaging the PDE coefficients on element edges. The resulting finite element stiffness matrix is an -matrix under some mild assumption for the underlying (generally unstructured) finite element grids. As a consequence the proposed edge-averaged finite element scheme is particularly interesting for the discretization of convection dominated problems. This scheme admits a simple variational formulation, it is easy to analyze, and it is also suitable for problems with a relatively smooth flux variable. Some simple numerical examples are given to demonstrate its effectiveness for convection dominated problems.

     

First-order system least squares and the energetic variational approach for two-phase flow

This paper develops a first-order system least-squares (FOSLS) formulation for equations of two-phase flow. The main goal is to show that this discretization, along with numerical techniques such as nested iteration, algebraic multigrid, and adaptive local refinement, can be used to solve these types of complex fluid flow problems. In addition, from an energetic variational approach, it can be shown that an important quantity to preserve in a given simulation is the energy law. We discuss the energy law and inherent structure for two-phase flow using the Allen–Cahn interface model and indicate how it is related to other complex fluid models, such as magnetohydrodynamics. Finally, we show that, using the FOSLS framework, one can still satisfy the appropriate energy law globally while using well-known numerical techniques.     

Commuting projections on graphs

Motivated by the increasing importance of large‐scale networks typically modeled by graphs, this paper is concerned with the development of mathematical tools for solving problems associated with the popular graph Laplacian. We exploit its mixed formulation based on its natural factorization as product of two operators. The goal is to construct a coarse version of the mixed graph Laplacian operator with the purpose to construct two‐level, and by recursion, a multilevel hierarchy of graphs and associated operators. In many situations in practice, having a coarse (i.e., reduced dimension) model that maintains some inherent features of the original large‐scale graph and respective graph Laplacian offers potential to develop efficient algorithms to analyze the underlined network modeled by this large‐scale graph. One possible application of such a hierarchy is to develop multilevel methods that have the potential to be of optimal complexity. In this paper, we consider general (connected) graphs and function spaces defined on its edges and its vertices. These two spaces are related by a discrete gradient operator, ‘Grad’ and its adjoint, ‘ ? Div’, referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then, a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ?₂‐projection Q_H onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π_H from the original edge‐space onto a properly constructed coarse edge‐space associated with the edges of the coarse graph. The projections π_H and Q_H commute with the discrete divergence operator, that is, we have Div π_H = Q_H div. The respective pair of coarse edge‐space and coarse vertex‐space offer the potential to construct two‐level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian, which utilizes the discrete divergence operator. The performance of one two‐level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples. Copyright © 2013 John Wiley & Sons, Ltd.     

On the approximation of Laplacian eigenvalues in graph disaggregation

Graph disaggregation is a technique used to address the high cost of computation for power law graphs on parallel processors. The few high-degree vertices are broken into multiple small-degree vertices, in order to allow for more efficient computation in parallel. In particular, we consider computations involving the graph Laplacian, which has significant applications, including diffusion mapping and graph partitioning, among others. We prove results regarding the spectral approximation of the Laplacian of the original graph by the Laplacian of the disaggregated graph. In addition, we construct an alternate disaggregation operator whose eigenvalues interlace those of the original Laplacian. Using this alternate operator, we construct a uniform preconditioner for the original graph Laplacian.     

A sharp convergence estimate for the method of subspace corrections for singular systems of equations

This paper is devoted to the convergence rate estimate for the method of successive subspace corrections applied to symmetric and positive semidefinite (singular) problems. In a general Hilbert space setting, a convergence rate identity is obtained for the method of subspace corrections in terms of the subspace solvers. As an illustration, the new abstract theory is used to show uniform convergence of a multigrid method applied to the solution of the Laplace equation with pure Neumann boundary conditions.

     

Analysis of a two‐level method for anisotropic diffusion equations on aligned and nonaligned grids

This paper is on the convergence analysis for two‐grid and multigrid methods for linear systems arising from conforming linear finite element discretization of the second‐order elliptic equations with anisotropic diffusion. The multigrid algorithm with a line smoother is known to behave well when the discretization grid is aligned with the anisotropic direction; however, this is not the case with a nonaligned grid. The analysis in this paper is mainly focused on two‐level algorithms. For aligned grids, a lower bound is given for a pointwise smoother, and this bound shows a deterioration in the convergence rate, whereas for ‘maximally’ nonaligned grids (with no edges in the triangulation parallel to the direction of the anisotropy), the pointwise smoother results in a robust convergence. With a specially designed block smoother, we show that, for both aligned and nonaligned grids, the convergence is uniform with respect to the anisotropy ratio and the mesh size in the energy norm. The analysis is complemented by numerical experiments that confirm the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.     

Uniformly Convergent Multigrid Methods for Convection–Diffusion Problems without Any Constraint on Coarse Grids

We construct a class of multigrid methods for convection–diffusion problems. The proposed algorithms use first order stable monotone schemes to precondition the second order standard Galerkin finite element discretization. To speed up the solution process of the lower order schemes, cross-wind-block reordering of the unknowns is applied. A V-cycle iteration, based on these algorithms, is then used as a preconditioner in GMRES. The numerical examples show that this method is convergent without imposing any constraint on the coarsest grid and the convergence of the preconditioned method is uniform.     

CONVERGENCE ANALYSIS ON ITERATIVE METHODS FOR SEMIDEFINITE SYSTEMS

The convergence analysis on the general iterative methods for the symmetric and positive semidefinite problems is presented in this paper. First, formulated are refined necessary and sumcient conditions for the energy norm convergence for iterative methods. Some illustrative examples for the conditions are also provided. The sharp convergence rate identity for the Gauss-Seidel method for the semidefinite system is obtained relying only on the pure matrix manipulations which guides us to obtain the convergence rate identity for the general successive subspace correction methods. The convergence rate identity for the successive subspace correction methods is obtained under the new conditions that the local correction schemes possess the local energy norm convergence. A convergence rate estimate is then derived in terms of the exact subspace solvers and the parameters that appear in the conditions. The uniform convergence of multigrid method for a model problem is proved by the convergence rate identity. The work can be regradled as unified and simplified analysis on the convergence of iteration methods for semidefinite problems [8, 9].     

Improving the rate of convergence of ‘high order finite elements’ on polygons and domains with cusps

Summary. Let u and u_V V be the solution and, respectively, the discrete solution of the non-homogeneous Dirichlet problem u=f on , u|=0. For any m and any bounded polygonal domain , we provide a construction of a new sequence of finite dimensional subspaces V_n such that where f H^m–1() is arbitrary and C is a constant that depends only on and not on n (we do not assume u H^m+1()). The existence of such a sequence of subspaces was first proved in a ground–breaking paper by Babuka [8]. Our method is different; it is based on the homogeneity properties of Sobolev spaces with weights and the well–posedness of non-homogeneous Dirichlet problem in suitable Sobolev spaces with weights, for which we provide a new proof, and which is a substitute of the usual shift theorems for boundary value problems in domains with smooth boundary. Our results extended right away to domains whose boundaries have conical points. We also indicate some of the changes necessary to deal with domains with cusps. Our numerical computation are in agreement with our theoretical results.The authors were supported in part by the NSF grant DMS 02-09497. Victor Nistor was also partially supported by NSF grant DMS 02-00808.     

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.