Search

In this paper, we develop a numerical scheme for the space-time fractional parabolic equation, i.e. an equation involving a fractional time derivative and a fractional spatial operator. Both the initial value problem and the non-homogeneous forcing problem (with zero initial data) are considered. The solution operator E⁢(t){E(t)}for the initial value problem can be written as a Dunford–Taylor integral involving the Mittag-Leffler function eα,1{e_{\alpha,1}}and the resolvent of the underlying (non-fractional) spatial operator over an appropriate integration path in the complex plane. Here α denotes the order of the fractional time derivative. The solution for the non-homogeneous problem can be written as a convolution involving an operator W⁢(t){W(t)}and the forcing function F⁢(t){F(t)}. We develop and analyze semi-discrete methods based on finite element approximation to the underlying (non-fractional) spatial operator in terms of analogous Dunford–Taylor integrals applied to the discrete operator. The space error is of optimal order up to a logarithm of 1h{\frac{1}{h}}. The fully discrete method for the initial value problem is developed from the semi-discrete approximation by applying a sinc quadrature technique to approximate the Dunford–Taylor integral of the discrete operator and is free of any time stepping. The sinc quadrature of step size kinvolves k-2{k^{-2}}nodes and results in an additional O⁢(exp⁡(-ck)){O(\exp(-\frac{c}{k}))}error. To approximate the convolution appearing in the semi-discrete approximation to the non-homogeneous problem, we apply a pseudo-midpoint quadrature. This involves the average of Wh⁢(s){W_{h}(s)}, (the semi-discrete approximation to W⁢(s){W(s)}) over the quadrature interval. This average can also be written as a Dunford–Taylor integral. We first analyze the error between this quadrature and the semi-discrete approximation. To develop a fully discrete method, we then introduce sinc quadrature approximations to the Dunford–Taylor integrals for computing the averages. We show that for a refined grid in time with a mesh of O⁢(𝒩⁢log⁡(𝒩)){O({\mathcal{N}}\log({\mathcal{N}}))}intervals, the error between the semi-discrete and fully discrete approximation is O⁢(𝒩-2+log⁡(𝒩)⁢exp⁡(-ck)){O({\mathcal{N}}^{-2}+\log({\mathcal{N}})\exp(-\frac{c}{k}))}. We also report the results of numerical experiments that are in agreement with the theoretical error estimates.

In this paper, we describe an approximation technique for div-curl systems based in $(L^2(\Omega)^3)$ where $\Omega$ is a domain in $\mathbb{R}^3$. We formulate this problem as a general variational problem with different test and trial spaces. The analysis requires the verification of an appropriate inf-sup condition. This results in a very weak formulation where the solution space is $(L^2(\Omega))^3$ and the data reside in various negative norm spaces. Subsequently, we consider finite element approximations based on this weak formulation. The main approach of this paper involves the development of ``stable pairs" of discrete test and trial spaces. With this approach, we enlarge the test space so that the discrete inf-sup condition holds and we use a negative-norm least-squares formulation to reduce to a uniquely solvable linear system. This leads to optimal order estimates for problems with minimal regularity which is important since it is possible to construct magnetostatic field problems whose solutions have low Sobolev regularity (e.g., $(H^s(\Omega))^3$ with $0< s< 1/2$). The resulting algebraic equations are symmetric, positive definite and well conditioned. A second approach using a smaller test space which adds terms to the form for stabilization will also be mentioned. Some numerical results are also presented.

Time harmonic Maxwell equations in lossless media lead to a second order differential equation for the electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec spaces can be employed to get approximate solutions numerically. The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically, two overlapping Schwarz methods will be shown to yield uniform preconditioners.

We prove the stability in $H^1(\Omega)$ of the $L^2$ projection onto a family of finite element spaces of conforming piecewise linear functions satisfying certain local mesh conditions. We give explicit formulae to check these conditions for a given finite element mesh in any number of spatial dimensions. In particular, stability of the $L^2$ projection in $H^1(\Omega)$ holds for locally quasiuniform geometrically refined meshes as long as the volume of neighboring elements does not change too drastically.

AbstractThe problem of approximating the band structure of electromagnetic Bloch modes in a three-dimensional periodic medium is studied. We analyze a mixed finite element approximation technique based on a variation of Nedelec edge elements. The usual conditions for convergence of the static problem are first verified. Subsequently, convergence of approximate eigenvalues to those of the continuous system is proved.

A method for computing band structures for three-dimensional photonic crystals is described. The method combines a mixed finite element discretization on a uniform grid with a fast Fourier transform preconditioner and a preconditioned subspace iteration algorithm. Numerical examples illustrating the behavior of the method are presented.

In this paper we construct and analyze new non-overlapping domain decomposition preconditioners for the solution of second-order elliptic and parabolic boundary value problems. The preconditioners are developed using uniform preconditioners on the subdomains instead of exact solves. They exhibit the same asymptotic condition number growth as the corresponding preconditioners with exact subdomain solves and are much more efficient computationally. Moreover, this asymptotic condition number growth is bounded independently of jumps in the operator coefficients across subdomain boundaries. We also show that our preconditioners fit into the additive Schwarz framework with appropriately chosen subspace decompositions. Condition numbers associated with the new algorithms are computed numerically in several cases and compared with those of the corresponding algorithms in which exact subdomain solves are used.

Spectral and pseudo spectral methods for advection equations are investigated. A basic framework is given which allows the application of techniques used in finite element analysis to spectral methods with trigonometric polynomials. Error estimates for semidiscrete spectral and pseudo spectral as well as fully discrete explicit pseudo spectral methods are given. The approximation schemes are shown to converge with infinite order.

In this paper, new convergence estimates are proved for both symmetric and nonsymmetric multigrid algorithms applied to symmetric positive definite problems. Our theory relates the convergence of multigrid algorithms to a "regularity and approximation" parameter $ \alpha \in (0,1]$m. We show that for the symmetric and nonsymmetric $ \mathcal{V}$m at a rate which deteriorates no worse than $ 1 - c{j^{ - (1 - \alpha )/\alpha }}$j is the number of grid levels. We then define a generalized $ \mathcal{V}$ with rates that are independent of the mesh size. The theory is presented in an abstract setting which can be applied to finite element multigrid and finite difference multigrid methods.

This paper provides a preconditioned iterative technique for the solution of saddle point problems. These problems typically arise in the numerical approximation of partial differential equations by Lagrange multiplier techniques and/or mixed methods. The saddle point problem is reformulated as a symmetric positive definite system, which is then solved by conjugate gradient iteration. Applications to the equations of elasticity and Stokes are discussed and the results of numerical experiments are given.

Backward difference methods for the discretization of parabolic boundary value problems are considered in this paper. In particular, we analyze the case when the backward difference equations are only solved 'approximately' by a preconditioned iteration. We provide an analysis which shows that these methods remain stable and accurate if a suitable number of iterations (often independent of the spatial discretization and time step size) are used. Results are provided for the smooth as well as non-smooth initial data cases. Finally, the results of numerical experiments illustrating the algorithms' performance on model problems are given.

Multigrid algorithms are developed to solve the discrete systems approximating the solutions of operator equations involving pseudodifferential operators of order minus one. Classical multigrid theory deals with the case of differential operators of positive order. The pseudodifferential operator gives rise to a coercive form on $ {H^{ - 1/2}}(\Omega )$ as a base inner product for the multigrid development. We show that the resulting rate of iterative convergence can, at worst, depend linearly on the number of levels in these novel multigrid algorithms. In addition, it is shown that the convergence rate is independent of the number of levels (and unknowns) in the case of a pseudodifferential operator defined by a single-layer potential. Finally, the results of numerical experiments illustrating the theory are presented.

The purpose of this paper is twofold. The first is to describe some simple and robust iterative schemes for nonsymmetric and indefinite elliptic boundary value problems. The schemes are based in the Sobolev space and require minimal hypotheses. The second is to develop algorithms utilizing a coarse-grid approximation. This leads to iteration matrices whose eigenvalues lie in the right half of the complex plane. In fact, for symmetric indefinite problems, the iteration is reduced to a well-conditioned symmetric positive definite system which can be solved by conjugate gradient iteration. Applications of the general theory as well as numerical examples are given.

The purpose of this paper is to provide new estimates for certain multilevel algorithms. In particular, we are concerned with the simple additive multilevel algorithm discussed recently together with J. Xu and the standard V-cycle algorithm with one smoothing step per grid. We shall prove that these algorithms have a uniform reduction per iteration independent of the mesh sizes and number of levels, even on nonconvex domains which do not provide full elliptic regularity. For example, the theory applies to the standard multigrid V-cycle on the L-shaped domain, or a domain with a crack, and yields a uniform convergence rate. We also prove uniform convergence rates for the multigrid V-cycle for problems with nonuniformly refined meshes. Finally, we give a new multigrid approach for problems on domains with curved boundaries and prove a uniform rate of convergence for the corresponding multigrid V-cycle algorithms.

We analyze the spectrum of a certain singular integral operator on the space $ {({L^2}(\Omega ))^3}$ is contained in three dimensional Euclidean space and has a Lipschitz continuous boundary. This operator arises in the integral formulation of the magnetostatic field problem. We decompose into invariant subspaces: in one where the operator is the zero map; in one, the identity map; and in one where the operator is positive definite and bounded. These results give rise to the formulation of new efficient numerical techniques for approximating nonlinear magnetostatic field problems [5], [6], [12].

A new method for approximating magnetostatic field problems is given in this paper. The new method approximates the scalar potential for the magnetic intensity and is based on a volume integral formulation. The derivation of the new computational method uses the spectral properties of the relevant integral operator. The corresponding algorithm is similar to that obtained from coupled differential and boundary integral approaches. Convergence and stability theorems are proven. Finally, convergence results in actual computations are compared with results for the usual volume integral method used in GFUN3D.

In this paper, we provide techniques for the development and analysis of parallel multilevel preconditioners for the discrete systems which arise in numerical approximation of symmetric elliptic boundary value problems. These preconditioners are defined as a sum of independent operators on a sequence of nested subspaces of the full approximation space. On a parallel computer, the evaluation of these operators and hence of the preconditioner on a given function can be computed concurrently. We shall study this new technique for developing preconditioners first in an abstract setting, next by considering applications to second-order elliptic problems, and finally by providing numerically computed condition numbers for the resulting preconditioned systems. The abstract theory gives estimates on the condition number in terms of three assumptions. These assumptions can be verified for quasi-uniform as well as refined meshes in any number of dimensions. Numerical results for the condition number of the preconditioned systems are provided for the new algorithms and compared with other well-known multilevel approaches.

We provide a theory for the analysis of multigrid algorithms for symmetric positive definite problems with nonnested spaces and noninherited quadratic forms. By this we mean that the form on the coarser grids need not be related to that on the finest, i.e., we do not stay within the standard variational setting. In this more general setting, we give new estimates corresponding to the $ \mathcal{V}$ $ \mathcal{W}$ $ \mathcal{V}$ We apply this theory to various numerical approximations of second-order elliptic boundary value problems. In our first example, we consider certain finite difference multigrid algorithms. In the second example, we consider a finite element multigrid algorithm with nested spaces, which however uses a prolongation operator that does not coincide with the natural subspace imbedding. The third example gives a multigrid algorithm derived from a loosely coupled sequence of approximation grids. Such a loosely coupled grid structure results from the most natural standard finite element application on a domain with curved boundary. The fourth example develops and analyzes a multigrid algorithm for a mixed finite element method using the so-called Raviart-Thomas elements.

In this paper, we consider iterative methods for the solution of symmetric positive definite problems on a space which are defined in terms of products of operators defined with respect to a number of subspaces. The simplest algorithm of this sort has an error-reducing operator which is the product of orthogonal projections onto the complement of the subspaces. New norm-reduction estimates for these iterative techniques will be presented in an abstract setting. Applications are given for overlapping Schwarz algorithms with many subregions for finite element approximation of second-order elliptic problems.

A new technique for proving rate of convergence estimates of multigrid algorithms for symmetric positive definite problems will be given in this paper. The standard multigrid theory requires a "regularity and approximation" assumption. In contrast, the new theory requires only an easily verified approximation assumption. This leads to convergence results for multigrid refinement applications, problems with irregular coefficients, and problems whose coefficients have large jumps. In addition, the new theory shows why it suffices to smooth only in the regions where new nodes are being added in multigrid refinement applications.

The purpose of this paper is to provide a general technique for defining and analyzing smoothing operators for use in multigrid algorithms. The smoothing operators considered are based on subspace decomposition and include point, line, and block versions of Jacobi and Gauss-Seidel iteration as well as generalizations. We shall show that these smoothers will be effective in multigrid algorithms provided that the subspace decomposition satisfies two simple conditions. In many applications, these conditions are trivial to verify.

In earlier parts of this series of papers, we constructed preconditioners for the discrete systems of equations arising from the numerical approximation of elliptic boundary value problems. The resulting algorithms are well suited for implementation on computers with parallel architecture. In this paper, we will develop a technique which utilizes these earlier methods to derive even more efficient preconditioners. The iterative algorithms using these new preconditioners converge to the solution of the discrete equations with a rate that is independent of the number of unknowns. These preconditioners involve an incomplete Chebyshev iteration for boundary interface conditions which results in a negligible increase in the amount of computational work. Theoretical estimates and the results of numerical experiments are given which demonstrate the effectiveness of the methods.

We prove some new estimates for the convergence of multigrid algorithms applied to nonsymmetric and indefinite elliptic boundary value problems. We provide results for the so-called 'symmetric' multigrid schemes. We show that for the variable $ \mathcal{V}$ $ \mathcal{W}$ $ \mathcal{V}$ -cycle may occur even in the case of full elliptic regularity. Finally, the results of numerical experiments are given which illustrate the convergence behavior suggested by the theory.

We consider the problem of solving the algebraic system of equations which result from the discretization of elliptic boundary value problems defined on three-dimensional Euclidean space. We develop preconditioners for such systems based on substructuring (also known as domain decomposition). The resulting algorithms are well suited to emerging parallel computing architectures. We describe two techniques for developing these preconditioners. A theory for the analysis of the condition number for the resulting preconditioned system is given and the results of supporting numerical experiments are presented.