Interior Hölder and gradient estimates for the homogenization of the linear elliptic equations

Hölder and gradient estimates for the correctors in the homogenization are presented based on the translation invariance and Li-Vogelius’s gradient estimate. If the coefficients are piecewise smooth and the homogenized solution is smooth enough, the interior error of the first-order expansion is O(?) in the Hölder norm; it is O(?) in W ^1,∞ based on the Avellaneda-Lin’s gradient estimate when the coefficients are Lipschitz continuous. These estimates can be partly extended to the nonlinear parabolic equations.     

A model of fracture for elliptic problems with flux and solution jumps

A new model of fracture for elliptic problems combining flux and solution jumps as immersed boundary conditions is proposed and proved to be well-posed. An application of this model to the flow in fractured porous media is also proposed including the cases of “impermeable fracture” and “fully permeable fracture” satisfying the so-called “cubic law”, as well as intermediate cases. A finite volume scheme on general polygonal meshes is built to solve such problems. Since no unknown is required at the fracture interface, the scheme is as cheap as standard schemes for the same problems without fault. The convergence of the scheme can be proved to the weak solution of the problem. With weak regularity assumptions, we also establish for the discrete H¹₀ and L² norms some error estimates in $\text{O}\text{(h)}$, where h is the maximum diameter of the control volumes of the mesh. To cite this article: Ph. Angot, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Rectilinear line segment intersection,layered segment trees,and dynamization

The aim of the present paper is to provide an efficient solution to the following problem: “Given a family of n rectilinear line segments in two-space report all intersections in the family with a query consisting of an arbitrary rectilinear line segment.” We provide an algorithm which takes O(nlog₂n) preprocessing time, o(nlog₂n) space and O(log₂n + k) query time, where k is the number of reported intersections. This solution serves to introduce a powerful new data structure, the layered segment tree, which is of independent interest. Second it yields, by way of recent dynamization techniques, a solution to the on-line version of the above problem, that is the operations INSERT and DELETE and QUERY with a line segment are allowed. Third it also yields a new nonscanning solution to the batched version of the above problem. Finally we apply these techniques to the problem obtained by replacing “line segment” by “rectangle” in the above problem, giving an efficient solution in this case also.     

Large transitive models in local ZFC

This paper is a sequel to Tzouvaras (Arch Math Log 49(5):571–601, 2010), where a local version of ZFC, LZFC, was introduced and examined and transitive models of ZFC with properties that resemble large cardinal properties, namely Mahlo and ${\Pi_1^1}$ -indescribable models, were considered. By analogy we refer to such models as “large models”, and the properties in question as “large model properties”. Continuing here in the same spirit we consider further large model properties, that resemble stronger large cardinals, namely, “elementarily embeddable”, “extendible” and “strongly extendible”, “critical” and “strongly critical”, “self-critical” and “strongly self-critical”, the definitions of which involve elementary embeddings. Each large model property ? gives rise to a localization axiom Loc ^? (ZFC) saying that every set belongs to a transitive model of ZFC satisfying ?. The theories LZFC ^?  = LZFC + Loc ^? (ZFC) are local analogues of the theories ZFC+“there is a proper class of large cardinals ψ”, where ψ is a large cardinal property. If sext(x) is the property of strong extendibility, it is shown that LZFC ^sext proves Powerset and Σ₁-Collection. In order to refute V = L over LZFC, we combine the existence of strongly critical models with an axiom of different flavor, the Tall Model Axiom (TMA). V = L can also be refuted by TMA plus the axiom GC saying that “there is a greatest cardinal”, although it is not known if TMA + GC is consistent over LZFC. Finally Vopěnka’s Principle (V P) and its impact on LZFC are examined. It is shown that LZFC ^sext  + V P proves Powerset and Replacement, i.e., ZFC is fully recovered. The same is true for some weaker variants of LZFC ^sext . Moreover the theories LZFC ^sext +V P and ZFC+V P are shown to be identical.     

Théorèmes d'existence pour un modèle membranaire « proprement invariantde plaque non linéairement élastique

We establish the “local” existence of an injective solution to the nonlinear, “properly invariant”, membrane plate model, stated in [1] and [2], successively for the clamped plate submitted to forces parallel to its plane and for the plate submitted to a boundary condition of place of “extended” state.     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

Quasi-GCD computations

For univariate polynomials with real or complex coefficients and a given error bound ? > 0, h is called a quasi-gcd of f and g, if h is an ?-approximate divisor of f and of g and if any (exact) common divisor of f, g is an approximate divisor of h. Extended quasi-gcd computation means to find such h and additional cofactors u, ν such that | uf + νg ? h | < ? | h | holds. Suitable “pivoting” leads to a numerically stable version of Euclid's algorithm for solving this task. Further refinements by a divide-and-conquer technique and by means of fast algorithms for polynomial arithmetic then yield the worst case upper bound O(n² lg n(lg(1/?) + n lg n)) of “pointer time” for nth-degree polynomials. In the particular case of integer polynomials, however, an immediate reduction to fast integer gcd computation is recommended, instead.     

Stability of periodic travelling wave solutions with large spatial periods in reaction-diffusion systems

We consider a spatially homogeneous system of reaction-diffusion equation defined on the interval (?∞, ∞) of the one-dimensional spatial variable x. It is known that this equation has a one-parameter family of periodic travelling wave solutions Ψ(x + ct; c) if this equation has a spatially homogeneous periodic solution φ(t). The spatial period L(c) of the travelling wave solution satisfies $\text{L(c)}\text{c}\text{→ T}\text{if}\text{c → +∞}$, where c is the propagation speed and T is the period of φ(t). We prove that, in the case c > 0 is sufficiently large, Ψ(x + ct; c) is unstable if φ(t) is “strongly unstable” and Ψ(x + ct; c) is “marginally stable” if φ(t) is “strongly stable.” If the equation is defined on a finite interval [0, l] of the variable x with the periodic boundary conditions, we can obtain a more precise result regarding the stability of $\text{Ψ(x +}\text{c}\text{?}\text{t;}\text{c}\text{?}\text{)}$, where $\text{c}\text{?}\text{> 0}$ is a speed which satisfies $\text{l = mL(}\text{c}\text{?}\text{)}$ for some positive integer m. We prove that this solution is asymptotically stable in the sense of waveform stability if $\text{c}\text{?}\text{> 0}$ is sufficiently large and if φ(t) is “strongly stable.”     

Weighted Monte Carlo method for an approximate solution of the nonlinear coagulation equation

New weighted modifications of direct statistical simulation methods designed for the approximate solution of the nonlinear Smoluchowski equation are developed on the basis of stratification of the interaction distribution in a multiparticle system according to the index of a pair of interacting particles. The weighted algorithms are validated for a model problem with a known solution. It is shown that they effectively estimate variations in the functionals with varying parameters, in particular, with the initial number N ₀ of particles in the simulating ensemble. The computations performed for the problem with a known solution confirm the semiheuristic hypothesis that the model error is O(N ₀ ^?1 ). Estimates are derived for the derivatives of the approximate solution with respect to the coagulation coefficient.     

Asymptotic modelling of conductive thin sheets

We derive and analyse models which reduce conducting sheets of a small thickness ε in two dimensions to an interface and approximate their shielding behaviour by conditions on this interface. For this we consider a model problem with a conductivity scaled reciprocal to the thickness ε, which leads to a nontrivial limit solution for ε → 0. The functions of the expansion are defined hierarchically, i.e. order by order. Our analysis shows that for smooth sheets the models are well defined for any order and have optimal convergence meaning that the H ¹-modelling error for an expansion with N terms is bounded by O(ε ^N+1) in the exterior of the sheet and by O(ε ^N+1/2) in its interior. We explicitly specify the models of order zero, one and two. Numerical experiments for sheets with varying curvature validate the theoretical results.     

Infinite families of recursive formulas generating power moments of Kloosterman sums: O −(2n,2 r ) case

In this paper, we construct eight infinite families of binary linear codes associated with double cosets with respect to a certain maximal parabolic subgroup of the special orthogonal group SO ^?(2n, 2 ^r ). And we obtain four infinite families of recursive formulas for the power moments of Kloosterman sums and four those of 2-dimensional Kloosterman sums in terms of the frequencies of weights in the codes. This is done via Pless power moment identity and by utilizing the explicit expressions of exponential sums over those double cosets related to the evaluations of “Gauss sums” for the orthogonal groups O ^?(2n, 2 ^r ).     

Quadratic spaces over finite fields and codes

Let V be a finite-dimensional quadratic space over a finite field GF(?) of characteristic different from 2. It is shown that, even if V is singular, the geometry of V is completely determined by the number of points on the unit sphere, the “sphere of the nonsquares,” and the “0-sphere.” For ? = 3, this implies that two codes over GF(3) with the same weight enumerator are isometric.     

Conditioning of finite difference schemes for a singularly perturbed convection-diffusion parabolic equation

In the case of the boundary value problem for a singularly perturbed convection-diffusion parabolic equation, conditioning of an ε-uniformly convergent finite difference scheme on a piecewise uniform grid is examined. Conditioning of a finite difference scheme on a uniform grid is also examined provided that this scheme is convergent. For the condition number of the scheme on a piecewise uniform grid, an ε-uniform bound O(δ ₁ ^?2 lnδ ₁ ^?1 + δ ₀ ^?1 ) is obtained, where δ₁ and δ₀ are the error components due to the approximation of the derivatives with respect to x and t, respectively. Thus, this scheme is ε-uniformly well-conditioned. For the condition number of the scheme on a uniform grid, we have the estimate O(ε^?1δ ₁ ^?2 + δ ₀ ^?1 ); this scheme is not ε-uniformly well-conditioned. In the case of the difference scheme on a uniform grid, there is an additional error due to perturbations of the grid solution; this error grows unboundedly as ε → 0, which reduces the accuracy of the grid solution (the number of correct significant digits in the grid solution is reduced). The condition numbers of the matrices of the schemes under examination are the same; both have an order of O(ε^?1δ ₁ ^?2 + δ ₀ ^?1 ). Neither the matrix of the ε-uniformly convergent scheme nor the matrix of the scheme on a uniform grid is ε-uniformly well-conditioned.     

On the divergence of trigonometric Fourier series in classes <Emphasis Type="Italic">ϕ</Emphasis>(<Emphasis Type="Italic">L</Emphasis>) close to <Emphasis Type="Italic">L</Emphasis>

We show the unimprovability of a theorem on sufficient convergence conditions for the trigonometric Fourier series of a function in classes ?(L) in the case when the class ?(L) is “close” to L.     

Superconvergence analysis and extrapolation of quasi-Wilson nonconforming finite element method for nonlinear Sobolev equations

Quasi-Wilson nonconforming finite element approximation for a class of nonlinear Sobolev equa-tions is discussed on rectangular meshes. We first prove that this element has two special characters by novel approaches. One is that (▽h ( u-Ihu )1, ▽hvh) h may be estimated as order O ( h2 ) when u ∈ H3 (Ω), where Ihu denotes the bilinear interpolation of u , vh is a polynomial belongs to quasi-Wilson finite element space and ▽h denotes the piecewise defined gradient operator, h is the mesh size tending to zero. The other is that the consistency error of this element is of order O ( h2 ) /O ( h3 ) in broken H 1-norm, which is one/two order higher than its interpolation error when u ∈ H3 (Ω) /H4 (Ω). Then we derive the optimal order error estimate and su- perclose property via mean-value method and the known high accuracy result of bilinear element. Furthermore, we deduce the global superconvergence through interpolation post processing technique. At last, an extrapola- tion result of order O ( h3 ), two order higher than traditional error estimate, is obtained by constructing a new suitable extrapolation scheme.     

Long time error analysis of the fourth‐order compact finite difference methods for the nonlinear Klein–Gordon equation with weak nonlinearity

We present the fourth‐order compact finite difference (4cFD) discretizations for the long time dynamics of the nonlinear Klein–Gordon equation (NKGE), while the nonlinearity strength is characterized by ?^p with a constant p ∈ ?⁺ and a dimensionless parameter ? ∈ (0, 1] . Based on analytical results of the life‐span of the solution, rigorous error bounds of the 4cFD methods are carried out up to the time at O(?^?p) . We pay particular attention to how error bounds depend explicitly on the mesh size h and time step τ as well as the small parameter ? ∈ (0, 1] , which indicate that, in order to obtain ‘correct’ numerical solutions up to the time at O(?^?p) , the ? ‐scalability (or meshing strategy requirement) of the 4cFD methods should be taken as: h = O(?^p/4) and τ = O(?^p/2) . It has better spatial resolution capacity than the classical second order central difference methods. By a rescaling in time, it is equivalent to an oscillatory NKGE whose solution propagates waves with wavelength at O(1) in space and O(?^p) in time. It is straightforward to get the error bounds of the oscillatory NKGE in the fixed time. Finally, numerical results are provided to confirm our theoretical analysis.     

MICZ-Kepler: Dynamics on the cone over SO(n)

We show that the n-dimensional MICZ-Kepler system arises from symplectic reduction of the “Kepler problem” on the cone over the rotation group SO(n). As a corollary we derive an elementary formula for the general solution of the MICZ-Kepler problem. The heart of the computation is the observation that the additional MICZ-Kepler potential, |?|²/r ², agrees with the rotational part of the cone’s kinetic energy.     

Network delay in a model with inputs of functional elements

We consider a model of delays in networks of functional elements in an arbitrary finite complete basis B, where the delays of basis elements are arbitrary positive real numbers for each input and each input set of variables going to the remaining inputs. This model estimates the delays in a multiplexer function of nth order asymptotically as τ_B n ± O(logn), where τ_B is a constant depending only on the basis B. On the basis of these estimates and within this model, asymptotic estimates of the form τ_B n ± O(logn) are obtained for the corresponding Shannon function, i.e., for the delay of the “worst” Boolean algebra function of given n variables.     

A method of asymptotic constructions with improved accuracy for a quasilinear singularly perturbed parabolic convection-diffusion equation

The Dirichlet problem on an interval for quasilinear singularly perturbed parabolic convection-diffusion equation is considered. The higher order derivative of the equation is multiplied by a parameter ε that takes any values from the half-open interval (0, 1]. For this type of linear problems, the order of the ε-uniform convergence (with respect to x and t) for the well-known schemes is not higher than unity (in the maximum norm). For the boundary value problem under consideration, grid approximations are constructed that converge ε-uniformly at the rate of O(N ^?2ln² N + N ^?2 ₀), where N + 1 and N ₀ + 1 are the numbers of the mesh points with respect to x and t, respectively. On the x axis, piecewise uniform meshes that condense in the boundary layer are used. If the parameter value is small compared to the effective step of the spatial grid, the domain decomposition method is used, which is motivated by “asymptotic constructions.” Monotone approximations of “auxiliary” subproblems describing the main terms of the asymptotic expansion of the solution outside a neighborhood of the boundary layer neighborhood are used. In the neighborhood of the boundary layer (of the width O(ε ln N)) the first derivative with respect to x is approximated by the central difference derivative. These subproblems are successively solved in the subdomains on uniform grids. If the parameter values are not sufficiently small (compared to the effective step of the mesh with respect to x), the classical implicit difference schemes approximating the first derivative with respect to x by the central difference derivative are applied. To improve the accuracy in t, the defect correction technique is used. Notice that the calculation of the solution of the constructed difference scheme (the scheme based on the method of asymptotic constructions) can be considerably simplified for sufficiently small values of the parameter ε.     

An O(n) algorithm for discrete n-point convex approximation with applications to continuous case

Given a bounded real function ? defined on a closed bounded real interval I, the problem is to find a convex function g so as to minimize the supremum of $\text{¦f(t) ? g(t)¦}$ for all t in I, over the class of all convex functions on I. The usual approach is to consider a discrete version of the problem on a grid of (n + 1) points in I, apply a conventional linear program to obtain an optimal solution, and let the grid size go to zero. This paper presents an alternative algorithm of complexity O(n), which is based on the concept of the greatest convex minorant of a function, for computation of a special “maximal” optimal solution to the discrete problem. It establishes the rate of convergence of this optimal solution to a solution of the original problem as the grid size goes to zero. It presents an alternative efficient linear program that generates the maximal optimal solution to the discrete problem. It also gives an O(n) algorithm for the discrete n-point monotone approximation problem.