Variable-step multilevel preconditioning methods,I: Self-adjoint and positive definite elliptic problems

When solving large size systems of equations by preconditioned iterative solution methods, one normally uses a fixed preconditioner which may be defined by some eigenvalue information, such as in a Chebyshev iteration method. In many problems, however, it may be more effective to use variable preconditioners, in particular when the eigenvalue information is not available. In the present paper, a recursive way of constructing variable-step of, in general, nonlinear multilevel preconditioners for selfadjoint and coercive second-order elliptic problems, discretized by the finite element method is proposed. The preconditioner is constructed recursively from the coarsest to finer and finer levels. Each preconditioning step requires only block-diagonal solvers at all levels except at every k₀, k₀ ≥ 1 level where we perform a sufficient number ν, ν ≥ 1 of GCG-type variable-step iterations that involve the use again of a variable-step preconditioning for that level. It turns out that for any sufficiently large value of k₀ and, asymptotically, for ν sufficiently large, but not too large, the method has both an optimal rate of convergence and an optimal order of computational complexity, both for two and three space dimensional problem domains. The method requires no parameter estimates and the convergence results do not depend on the regularity of the elliptic problem.     

Trace Formulas for Some Singular Differential Operators and Applications

We characterize the convergence of the series ∑ λ^–1_n, where λⁿ are the non‐zero eigenvalues of some boundary value problems for degenerate second order ordinary differential operators and we prove a formula for the above sum when the coefficient of the zero‐order term vanishes. We study these operators both in weighted Hilbert spaces and in spaces of continuous functions. After investigating the boundary behaviour of the eigenfunctions, we give applications to the regularity of the generated semigroups.     

Exponential attractor for a planar shear‐thinning flow

We study the dynamics of an incompressible, homogeneous fluid of a power‐law type, with the stress tensor T = ν(1 + µ|Dv|)^p?2Dv, where Dv is a symmetric velocity gradient. We consider the two‐dimensional problem with periodic boundary conditions and p ∈ (1, 2). Under these assumptions, we estimate the fractal dimension of the exponential attractor, using the so‐called method of ??‐trajectories. Copyright © 2007 John Wiley & Sons, Ltd.     

Solutions of symmetry‐constrained least‐squares problems

In this paper, two new matrix‐form iterative methods are presented to solve the least‐squares problem: and matrix nearness problem: where matrices and are given; ??₁ and ??₂ are the set of constraint matrices, such as symmetric, skew symmetric, bisymmetric and centrosymmetric matrices sets and S_XY is the solution pair set of the minimum residual problem. These new matrix‐form iterative methods have also faster convergence rate and higher accuracy than the matrix‐form iterative methods proposed by Peng and Peng (Numer. Linear Algebra Appl. 2006; 13 : 473–485) for solving the linear matrix equation AXB+CYD=E. Paige's algorithms, which are based on the bidiagonalization procedure of Golub and Kahan, are used as the framework for deriving these new matrix‐form iterative methods. Some numerical examples illustrate the efficiency of the new matrix‐form iterative methods. Copyright © 2008 John Wiley & Sons, Ltd.     

On probabilistic elimination of generalized quantifiers

Let ?? be a collection of generalized quantifiers. We give a convenient characterization for the cases where the logic ??(??) has quantifier elimination for an arbitrary class of structures. The results provide a method to prove zero‐one and convergence laws for such logics with arbitrary sequences of probability measures of finite structures. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 1–36, 2001     

Symmetries that latin squares inherit from 1‐factorizations

A 1‐factorization of a graph is a decomposition of the graph into edge disjoint perfect matchings. There is a well‐known method, which we call the ??‐construction, for building a 1‐factorization of K_n,n from a 1‐factorization of K_{n + 1}. The 1‐factorization of K_n,n can be written as a latin square of order n. The ??‐construction has been used, among other things, to make perfect 1‐factorizations, subsquare‐free latin squares, and atomic latin squares. This paper studies the relationship between the factorizations involved in the ??‐construction. In particular, we show how symmetries (automorphisms) of the starting factorization are inherited as symmetries by the end product, either as automorphisms of the factorization or as autotopies of the latin square. Suppose that the ??‐construction produces a latin square L from a 1‐factorization F of K_{n + 1}. We show that the main class of L determines the isomorphism class of F, although the converse is false. We also prove a number of restrictions on the symmetries (autotopies and paratopies) which L may possess, many of which are simple consequences of the fact that L must be symmetric (in the usual matrix sense) and idempotent. In some circumstances, these restrictions are tight enough to ensure that L has trivial autotopy group. Finally, we give a cubic time algorithm for deciding whether a main class of latin squares contains any square derived from the ??‐construction. The algorithm also detects symmetric squares and totally symmetric squares (latin squares that equal their six conjugates). © 2005 Wiley Periodicals, Inc. J Combin Designs 13: 157–172, 2005.     

Positive numerical splitting method for the Hull and White 2D Black–Scholes equation

We consider the locally one‐dimensional backward Euler splitting method to solve numerically the Hull and White problem for pricing European options with stochastic volatility in the presence of a mixed derivative term. We prove the first‐order convergence of the time‐splitting. The parabolic equation degenerates on the boundary x = 0 and we apply a fitted finite volume scheme to the equation to resolve the degeneracy and derive the fully discrete problem as we also investigate the discrete maximum principle. Numerical experiments illustrate the efficiency of our difference scheme. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 31: 822–846, 2015     

On the critical exponents of random k‐SAT

There has been much recent interest in the satisfiability of random Boolean formulas. A random k‐SAT formula is the conjunction of m random clauses, each of which is the disjunction of k literals (a variable or its negation). It is known that when the number of variables n is large, there is a sharp transition from satisfiability to unsatisfiability; in the case of 2‐SAT this happens when m/n → 1, for 3‐SAT the critical ratio is thought to be m/n ≈ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called ν = ν_k (the smaller the value of ν the sharper the transition). Experiments have suggested that ν₃ = 1.5 ± 0.1. ν₄ = 1.25 ± 0.05, ν₅ = 1.1 ± 0.05, ν₆ = 1.05 ± 0.05, and heuristics have suggested that ν_k → 1 as k → ∞. We give here a simple proof that each of these exponents is at least 2 (provided the exponent is well defined). This result holds for each of the three standard ensembles of random k‐SAT formulas: m clauses selected uniformly at random without replacement, m clauses selected uniformly at random with replacement, and each clause selected with probability p independent of the other clauses. We also obtain similar results for q‐colorability and the appearance of a q‐core in a random graph. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002     

Global and Superlinear Convergence of a Restricted Class of Self-Scaling Methods with Inexact Line Searches, for Convex Functions

This paper studies the convergence properties of algorithms belonging to the class of self-scaling (SS) quasi-Newton methods for unconstrained optimization. This class depends on two parameters, say _k and _k , for which the choice _k =1 gives the Broyden family of unscaled methods, where _k =1 corresponds to the well known DFP method. We propose simple conditions on these parameters that give rise to global convergence with inexact line searches, for convex objective functions. The q-superlinear convergence is achieved if further restrictions on the scaling parameter are introduced. These convergence results are an extension of the known results for the unscaled methods. Because the scaling parameter is heavily restricted, we consider a subclass of SS methods which satisfies the required conditions. Although convergence for the unscaled methods with _k 1 is still an open question, we show that the global and superlinear convergence for SS methods is possible and present, in particular, a new SS-DFP method.     

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.     

A penalty‐FEM for navier‐stokes type variational inequality with nonlinear damping term

In this article, we consider a penalty finite element (FE) method for incompressible Navier‐Stokes type variational inequality with nonlinear damping term. First, we establish penalty variational formulation and prove the well‐posedness and convergence of this problem. Then we show the penalty FE scheme and derive some error estimates. Finally, we give some numerical results to verify the theoretical rate of convergence. © 2017 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 33: 918–940, 2017     

A note on Solodov and Tseng’s methods for maximal monotone mappings

This paper considers the problem of finding a zero of the sum of a single-valued Lipschitz continuous mapping A and a maximal monotone mapping B in a closed convex set C. We first give some projection-type methods and extend a modified projection method proposed by Solodov and Tseng for the special case of B=N_C to this problem, then we give a refinement of Tseng’s method that replaces P_C by P_Ck. Finally, convergence of these methods is established.     

Constant sign and nodal solutions for logistic-type equations with equidiffusive reaction

We consider a logistic-type equation driven by the p-Laplace differential operator with an equidiffusive reaction term. Combining variational methods based on critical point theory together with truncation techniques and Morse theory, we show that when ?? > ??₁, the problem has extremal solutions of constant sign and when ?? > ??₂ it has also a nodal (sign-changing) solution. Here ??₁?<???₂ are the first two eigenvalues of the negative Dirichlet p-Laplacian. In the semilinear case (i.e. p?=?2) we produce two nodal solutions.     

Stable signal recovery from incomplete and inaccurate measurements

Suppose we wish to recover a vector x₀ ∈ ?^?? (e.g., a digital signal or image) from incomplete and contaminated observations y = A x₀ + e; A is an ?? × ?? matrix with far fewer rows than columns (?? ? ??) and e is an error term. Is it possible to recover x₀ accurately based on the data y? To recover x₀, we consider the solution x^# to the ??₁‐regularization problem where ? is the size of the error term e. We show that if A obeys a uniform uncertainty principle (with unit‐normed columns) and if the vector x₀ is sufficiently sparse, then the solution is within the noise level As a first example, suppose that A is a Gaussian random matrix; then stable recovery occurs for almost all such A's provided that the number of nonzeros of x₀ is of about the same order as the number of observations. As a second instance, suppose one observes few Fourier samples of x₀; then stable recovery occurs for almost any set of ?? coefficients provided that the number of nonzeros is of the order of ??/(log ??)⁶. In the case where the error term vanishes, the recovery is of course exact, and this work actually provides novel insights into the exact recovery phenomenon discussed in earlier papers. The methodology also explains why one can also very nearly recover approximately sparse signals. © 2006 Wiley Periodicals, Inc.     

Multigrid methods for the symmetric interior penalty method on graded meshes

The symmetric interior penalty (SIP) method on graded meshes and its fast solution by multigrid methods are studied in this paper. We obtain quasi‐optimal error estimates in both the energy norm and the L₂ norm for the SIP method, and prove uniform convergence of the W‐cycle multigrid algorithm for the resulting discrete problem. The performance of these methods is illustrated by numerical results. Copyright © 2009 John Wiley & Sons, Ltd.     

Distributive smoothers in multigrid for problems with dominating grad–div operators

In this paper, we present efficient multigrid methods for systems of partial differential equations that are governed by a dominating grad–div operator. In particular, we show that distributive smoothing methods give multigrid convergence factors that are independent of problem parameters and of the mesh sizes in space and time. The applications range from model problems to secondary consolidation Biot's model. We focus on the smoothing issue and mainly solve academic problems on Cartesian‐staggered grids. Copyright © 2008 John Wiley & Sons, Ltd.     

Error estimates for two‐level penalty finite volume method for the stationary Navier–Stokes equations

Two‐level penalty finite volume method for the stationary Navier–Stokes equations based on the P₁ ? P₀ element is considered in this paper. The method involves solving one small penalty Navier–Stokes problem on a coarse mesh with mesh size H = ?^{1 / 4}h^{1 / 2}, a large penalty Stokes problem on a fine mesh with mesh size h, where 0 < ? < 1 is a penalty parameter. The method we study provides an approximate solution with the convergence rate of same order as the penalty finite volume solution (u_?h,p_?h), which involves solving one large penalty Navier–Stokes problem on a fine mesh with the same mesh size h. However, our method can save a large amount of computational time. Copyright © 2013 John Wiley & Sons, Ltd.     

Homogenization of the Signorini boundary‐value problem in a thick junction and boundary integral equations for the homogenized problem

We consider a mixed boundary‐value problem for the Poisson equation in a thick junction Ω_ε which is the union of a domain Ω₀ and a large number of ε—periodically situated thin cylinders. The non‐uniform Signorini conditions are given on the lateral surfaces of the cylinders. The asymptotic analysis of this problem is done as ε→0, i.e. when the number of the thin cylinders infinitely increases and their thickness tends to zero. We prove a convergence theorem and show that the non‐uniform Signorini boundary conditions are transformed in the limiting variational inequalities in the region that is filled up by the thin cylinders as ε→0. The convergence of the energy integrals is proved as well. The existence and uniqueness of the solution to this non‐standard limit problem is established. This solution can be constructed by using a penalty formulation and successive iteration. For some subclass, these problems can be reduced to an obstacle problem in Ω₀ and an appropriate postprocessing. The equations in Ω₀ finally are also treated with boundary integral equations. Copyright © 2010 John Wiley & Sons, Ltd.     

Time delay and finite differences for the non-stationary non-linear Navier–Stokes equations

In the present paper we use a time delay ? > 0 for an energy conserving approximation of the non-linear term of the non-stationary Navier–Stokes equations. We prove that the corresponding initial-value problem (N_?) in smoothly bounded domains G ? ?³ is well-posed. We study a semidiscretized difference scheme for (N_?) and prove convergence to optimal order in the Sobolev space H²(G). Passing to the limit ?→0 we show that the sequence of stabilized solutions has an accumulation point such that it solves the Navier–Stokes problem (N_o) in a weak sense (Hopf).