Convergence analysis of the local defect correction method for diffusion equations

Summary. This paper is concerned with the convergence analysis of the local defect correction (LDC) method for diffusion equations. We derive a general expression for the iteration matrix of the method. We consider the model problem of Poisson's equation on the unit square and use standard five-point finite difference discretizations on uniform grids. It is shown via both an upper bound for the norm of the iteration matrix and numerical experiments, that the rate of convergence of the LDC method is proportional to H ² with H the grid size of the global coarse grid. Mathematics Subject Classification (2000):65N22, 65N50     

A two‐grid method for mixed finite‐element solution of reaction‐diffusion equations

We present a scheme for solving two‐dimensional, nonlinear reaction‐diffusion equations, using a mixed finite‐element method. To linearize the mixed‐method equations, we use a two grid scheme that relegates all the Newton‐like iterations to a grid Δ_H much coarser than the original one Δ_h, with no loss in order of accuracy so long as the mesh sizes obey . The use of a multigrid‐based solver for the indefinite linear systems that arise at each coarse‐grid iteration, as well as for the similar system that arises on the fine grid, allows for even greater efficiency. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 317–332, 1999     

A comparison of abstract versions of deflation,balancing and additive coarse grid correction preconditioners

In this paper we consider various preconditioners for the conjugate gradient (CG) method to solve large linear systems of equations with symmetric positive definite system matrix. We continue the comparison between abstract versions of the deflation, balancing and additive coarse grid correction preconditioning techniques started in (SIAM J. Numer. Anal. 2004; 42 :1631–1647; SIAM J. Sci. Comput. 2006; 27 :1742–1759). There the deflation method is compared with the abstract additive coarse grid correction preconditioner and the abstract balancing preconditioner. Here, we close the triangle between these three methods. First of all, we show that a theoretical comparison of the condition numbers of the abstract additive coarse grid correction and the condition number of the system preconditioned by the abstract balancing preconditioner is not possible. We present a counter example, for which the condition number of the abstract additive coarse grid correction preconditioned system is below the condition number of the system preconditioned with the abstract balancing preconditioner. However, if the CG method is preconditioned by the abstract balancing preconditioner and is started with a special starting vector, the asymptotic convergence behavior of the CG method can be described by the so‐called effective condition number with respect to the starting vector. We prove that this effective condition number of the system preconditioned by the abstract balancing preconditioner is less than or equal to the condition number of the system preconditioned by the abstract additive coarse grid correction method. We also provide a short proof of the relationship between the effective condition number and the convergence of CG. Moreover, we compare the A‐norm of the errors of the iterates given by the different preconditioners and establish the orthogonal invariants of all three types of preconditioners. Copyright © 2008 John Wiley & Sons, Ltd.     

Analysis of two‐grid discretization scheme for semilinear hyperbolic equations by mixed finite element methods

In this paper, the full discrete scheme of mixed finite element approximation is introduced for semilinear hyperbolic equations. To solve the nonlinear problem efficiently, two two‐grid algorithms are developed and analyzed. In this approach, the nonlinear system is solved on a coarse mesh with width H, and the linear system is solved on a fine mesh with width h≪H. Error estimates and convergence results of two‐grid method are derived in detail. It is shown that if we choose in the first algorithm and in the second algorithm, the two‐grid algorithms can achieve the same accuracy of the mixed finite element solutions. Finally, the numerical examples also show that the two‐grid method is much more efficient than solving the nonlinear mixed finite element system directly.     

Two‐grid method for two‐dimensional nonlinear Schrödinger equation by finite element method

A conservative two‐grid finite element scheme is presented for the two‐dimensional nonlinear Schrödinger equation. One Newton iteration is applied on the fine grid to linearize the fully discrete problem using the coarse‐grid solution as the initial guess. Moreover, error estimates are conducted for the two‐grid method. It is shown that the coarse space can be extremely coarse, with no loss in the order of accuracy, and still achieve the asymptotically optimal approximation as long as the mesh sizes satisfy in the two‐grid method. The numerical results show that this method is very effective.     

Comparisons between multiplicative and additive Schwarz iterations in domain decomposition methods

We consider the multiplicative and additive Schwarz methods for solving linear systems of equations and we compare their asymptotic rate of convergence. Moreover, we compare the multiplicative Schwarz method with the weighted restricted additive Schwarz method. We prove that the multiplicative Schwarz method is the fastest method among these three. Our comparisons can be done in the case of exact and inexact subspaces solves. In addition, we analyse two ways of adding a coarse grid correction – multiplicatively or additively. Mathematics Subject Classification (1991):65F10, 65F35, 65M55     

Treewidth of Cartesian Products of Highly Connected Graphs

The following theorem is proved: for all k‐connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well‐known result about the treewidth of planar grid graphs.     

When does the top homology of a random simplicial complex vanish?

Several years ago Linial and Meshulam (Combinatorica 26 (2006) 457–487) introduced a model called of random n‐vertex d‐dimensional simplicial complexes. The following question suggests itself very naturally: What is the threshold probability at which the d‐dimensional homology of such a random d‐complex is, almost surely, nonzero? Here we derive an upper bound on this threshold. Computer experiments that we have conducted suggest that this bound may coincide with the actual threshold, but this remains an open question. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 26–35, 2015     

A new level‐dependent coarse grid correction scheme for indefinite Helmholtz problems

In this paper, we construct and analyze a level‐dependent coarse grid correction scheme for indefinite Helmholtz problems. This adapted multigrid (MG) method is capable of solving the Helmholtz equation on the finest grid using a series of MG cycles with a grid‐dependent complex shift, leading to a stable correction scheme on all levels. It is rigorously shown that the adaptation of the complex shift throughout the MG cycle maintains the functionality of the two‐grid correction scheme, as no smooth modes are amplified in or added to the error. In addition, a sufficiently smoothing relaxation scheme should be applied to ensure damping of the oscillatory error components. Numerical experiments on various benchmark problems show the method to be competitive with or even outperform the current state‐of‐the‐art MG‐preconditioned Krylov methods, for example, complex shifted Laplacian preconditioned flexible GMRES. Copyright © 2013 John Wiley & Sons, Ltd.     

Existence of magic 3‐dimensional rectangles

Since the complete solution for the existence of magic 2‐dimensional rectangles in 1881, much attention has been paid on the existence of magic l‐dimensional rectangles for . The existence problem for magic l‐dimensional rectangles with even sizes has been solved completely for all integers . However, very little is known for the existence of magic l‐dimensional rectangles () with odd sizes except for some families and a few sporadic examples. In this paper, we focus our attention on the existence of magic 3‐dimensional rectangles and prove that the necessary conditions for the existence of magic 3‐dimensional rectangles are also sufficient. Our construction method is mainly based on a new concept, symmetric zero‐sum subset partition, which plays a crucial role in the recursive constructions of magic 3‐rectangles similar to that of PBD in the PBD‐closure construction in combinatorial design theory.     

A two‐grid stabilized mixed finite element method for Darcy‐Forchheimer model

A two‐grid stabilized mixed finite element method based on pressure projection stabilization is proposed for the two‐dimensional Darcy‐Forchheimer model. We use the derivative of a smooth function, , to approximate the derivative of in constructing the two‐grid algorithm. The two‐grid method consists of solving a small nonlinear system on the coarse mesh and then solving a linear system on the fine mesh. There are a substantial reduction in computational cost. We prove the existence and uniqueness of solution of the discrete schemes on the coarse grid and the fine grid and obtain error estimates for the two‐grid algorithm. Finally, some numerical experiments are carried out to verify the accuracy and efficiency of the method.     

Volume estimates for sections of certain convex bodies

This paper deals with volume estimates for hyperplane sections of the simplex and for m‐codimensional sections of powers of m‐dimensional Euclidean balls. In the first part we consider sections through the centroid of the n‐dimensional regular simplex. We state a volume formula and give a lower bound for the volume of sections through the centroid. In the second part we study the extremal volumes of m‐codimensional sections “perpendicular” to of unit balls in the space for all . We give volume formulas and use them to show that the normal vector (1, 0, …, 0) yields the minimal volume. Furthermore we give an upper bound for the ‐dimensional volumes for natural numbers . This bound is asymptotically attained for the normal vector as .     

Splitting methods for tensor equations

The Jacobi, Gauss‐Seidel and successive over‐relaxation methods are well‐known basic iterative methods for solving system of linear equations. In this paper, we extend those basic methods to solve the tensor equation , where is an m th‐order n ?dimensional symmetric tensor and b is an n ‐dimensional vector. Under appropriate conditions, we show that the proposed methods are globally convergent and locally r‐linearly convergent. Taking into account the special structure of the Newton method for the problem, we propose a Newton‐Gauss‐Seidel method, which is expected to converge faster than the above methods. The proposed methods can be extended to solve a general symmetric tensor equations. Our preliminary numerical results show the effectiveness of the proposed methods.     

The upper and lower quantization coefficient for Markov‐type measures

We study the asymptotic quantization error for Markov‐type measures μ on a class of ratio‐specified graph directed fractals E . Assuming a separation condition for E , we show that the quantization dimension for μ of order r exists and determine its exact value in terms of spectral radius of a related matrix. We prove that the ‐dimensional lower quantization coefficient for μ is always positive. Moreover, we establish a necessary and sufficient condition for the ‐dimensional upper quantization coefficient for μ to be finite.     

Two‐level Fourier analysis of multigrid for higher‐order finite‐element discretizations of the Laplacian

In this paper, we employ local Fourier analysis (LFA) to analyze the convergence properties of multigrid methods for higher‐order finite‐element approximations to the Laplacian problem. We find that the classical LFA smoothing factor, where the coarse‐grid correction is assumed to be an ideal operator that annihilates the low‐frequency error components and leaves the high‐frequency components unchanged, fails to accurately predict the observed multigrid performance and, consequently, cannot be a reliable analysis tool to give good performance estimates of the two‐grid convergence factor. While two‐grid LFA still offers a reliable prediction, it leads to more complex symbols that are cumbersome to use to optimize parameters of the relaxation scheme, as is often needed for complex problems. For the purposes of this analytical optimization as well as to have simple predictive analysis, we propose a modification that is “between” two‐grid LFA and smoothing analysis, which yields reasonable predictions to help choose correct damping parameters for relaxation. This exploration may help us better understand multigrid performance for higher‐order finite element discretizations, including for Q₂‐Q₁ (Taylor‐Hood) elements for the Stokes equations. Finally, we present two‐grid and multigrid experiments, where the corrected parameter choice is shown to yield significant improvements in the resulting two‐grid and multigrid convergence factors.     

Convergence analysis for second‐order accurate schemes for the periodic nonlocal Allen‐Cahn and Cahn‐Hilliard equations

In this paper, we provide a detailed convergence analysis for fully discrete second‐order (in both time and space) numerical schemes for nonlocal Allen‐Cahn and nonlocal Cahn‐Hilliard equations. The unconditional unique solvability and energy stability ensures ? ⁴ stability. The convergence analysis for the nonlocal Allen‐Cahn equation follows the standard procedure of consistency and stability estimate for the numerical error function. For the nonlocal Cahn‐Hilliard equation, because of the complicated form of the nonlinear term, a careful expansion of its discrete gradient is undertaken, and an H ^?1 inner‐product estimate of this nonlinear numerical error is derived to establish convergence. In addition, an a priori bound of the numerical solution at the discrete level is needed in the error estimate. Such a bound can be obtained by performing a higher order consistency analysis by using asymptotic expansions for the numerical solution. Following the technique originally proposed by Strang (eg, 1964), instead of the standard comparison between the exact and numerical solutions, an error estimate between the numerical solution and the constructed approximate solution yields an O (s ³+h ⁴) convergence in norm, in which s and h denote the time step and spatial mesh sizes, respectively. This in turn leads to the necessary bound under a standard constraint s ≤C h . Here, we also prove convergence of the scheme in the maximum norm under the same constraint.     

Sharp bounds for the first eigenvalue and the torsional rigidity related to some anisotropic operators

In this paper we prove a sharp upper bound for the first Dirichlet eigenvalue of a class of nonlinear elliptic operators which includes the operator , that is the p‐Laplacian, and , namely the pseudo‐p‐Laplacian. Moreover we prove a stability result by means of a suitable isoperimetric deficit. Finally, we give a sharp lower bound for the anisotropic p‐torsional rigidity.     

Monotone numerical schemes for a Dirichlet problem for elliptic operators in divergence form

We consider a second‐order differential operator A( x )=?∑?_ia_ij( x )?_j+ ∑?_j(b_j( x )·)+c( x ) on ?^d, on a bounded domain D with Dirichlet boundary conditions on ?D, under mild assumptions on the coefficients of the diffusion tensor a_ij. The object is to construct monotone numerical schemes to approximate the solution of the problem A( x )u( x )=µ( x ), x ∈D, where µ is a positive Radon measure. We start by briefly mentioning questions of existence and uniqueness introducing function spaces needed to prove convergence results. Then, we define non‐standard stencils on grid‐knots that lead to extended discretization schemes by matrices possessing compartmental structure. We proceed to discretization of elliptic operators, starting with constant diffusion tensor and ending with operators in divergence form. Finally, we discuss W‐convergence in detail, and mention convergence in C and L₁ spaces. We conclude by a numerical example illustrating the schemes and convergence results. Copyright © 2008 John Wiley & Sons, Ltd.     

Global existence and asymptotic behavior of classical solutions for a 3D two‐species chemotaxis‐Stokes system with competitive kinetics

This paper considers the 2‐species chemotaxis‐Stokes system with competitive kinetics under homogeneous Neumann boundary conditions in a 3‐dimensional bounded domain with smooth boundary. Both chemotaxis‐fluid systems and 2‐species chemotaxis systems with competitive terms were studied by many mathematicians. However, there have not been rich results on coupled 2‐species–fluid systems. Recently, global existence and asymptotic stability in the above problem with (u·∇)u in the fluid equation were established in the 2‐dimensional case. The purpose of this paper is to give results for global existence, boundedness, and stabilization of solutions to the above system in the 3‐dimensional case when is sufficiently small.     

Involutions in split semi‐quaternions

A map is an involution (resp, anti‐involution) if it is a self‐inverse homomorphism (resp, antihomomorphism) of a field algebra. The main purpose of this paper is to show how split semi‐quaternions can be used to express half‐turn planar rotations in 3‐dimensional Euclidean space and how they can be used to express hyperbolic‐isoclinic rotations in 4‐dimensional semi‐Euclidean space . We present an involution and an anti‐involution map using split semi‐quaternions and give their geometric interpretations as half‐turn planar rotations in . Also, we give the geometric interpretation of nonpure unit split semi‐quaternions, which are in the form p = coshθ + sinhθ i + 0 j + 0 k = coshθ + sinhθ i , as hyperbolic‐isoclinic rotations in .