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.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

O(dlog?N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling

In the present paper, we discuss the novel concept of super-compressed tensor-structured data formats in high-dimensional applications. We describe the multifolding or quantics-based tensor approximation method of O(dlog N)-complexity (logarithmic scaling in the volume size), applied to the discrete functions over the product index set {1,…,N}^⊗d , or briefly N-d tensors of size N ^d , and to the respective discretized differential-integral operators in ℝ ^d . As the basic approximation result, we prove that a complex exponential sampled on an equispaced grid has quantics rank 1. Moreover, a Chebyshev polynomial, sampled over a Chebyshev Gauss–Lobatto grid, has separation rank 2 in the quantics tensor format, while for the polynomial of degree m over a Chebyshev grid the respective quantics rank is at most 2m+1. For N-d tensors generated by certain analytic functions, we give a constructive proof of the O(dlog Nlog ε ⁻¹)-complexity bound for their approximation by low-rank 2-(dlog N) quantics tensors up to the accuracy ε>0. In the case ε=O(N ^−α ), α>0, our approach leads to the quantics tensor numerical method in dimension d, with the nearly optimal asymptotic complexity O(d/αlog ² ε ⁻¹). From numerical examples presented here, we observe that the quantics tensor method has proved its value in application to various function related tensors/matrices arising in computational quantum chemistry and in the traditional finite element method/boundary element method (FEM/BEM). The tool apparently works.     

Asymptotic behavior of eigenvalues and eigenfunctions of the Fourier problem in a thick multilevel junction

A spectral boundary-value problem is considered in a plane thick two-level junction Ω_ε formed as the union of a domain Ω₀ and a large number 2N of thin rods with thickness of order ε = O(N ⁻¹). The thin rods are split into two levels depending on their length. In addition, the thin rods from the indicated levels are ε-periodically alternating. The Fourier conditions are given on the lateral boundaries of the thin rods. The asymptotic behavior of the eigenvalues and eigenfunctions is investigated as ε → 0, i.e., when the number of thin rods infinitely increases and their thickness approaches zero. The Hausdorff convergence of the spectrum is proved as ε → 0, the leading terms of asymptotics are constructed, and the corresponding asymptotic estimates are justified for the eigenvalues and eigenfunctions. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 195–216, February, 2006.     

Asymptotic Analysis of an Optimal Control Problem Involving a Thick Two-Level Junction with Alternate Type of Controls

We study the asymptotic behavior (as ε→0) of an optimal control problem in a plane thick two-level junction, which is the union of some domain and a large number 2N of thin rods with variable thickness of order e = O(N^-1).\varepsilon =\mathcal{O}(N^{-1}). The thin rods are divided into two levels depending on the geometrical characteristics and on the controls given on their bases. In addition, the thin rods from each level are ε-periodically alternated and the inhomogeneous perturbed Fourier boundary conditions are given on the lateral sides of the rods. Using the direct method of the calculus of variations and the Buttazzo-Dal Maso abstract scheme for variational convergence of constrained minimization problems, the asymptotic analysis of this problem for different kinds of controls is made as ε→0.     

Kinetic Spanners in ℝ<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a new (1+ε)-spanner for sets of n points in ℝ ^d . Our spanner has size O(n/ε ^d−1) and maximum degree O(log  ^d n). The main advantage of our spanner is that it can be maintained efficiently as the points move: Assuming that the trajectories of the points can be described by bounded-degree polynomials, the number of topological changes to the spanner is O(n ²/ε ^d−1), and using a supporting data structure of size O(nlog  ^d n), we can handle events in time O(log  ^d+1 n). Moreover, the spanner can be updated in time O(log n) if the flight plan of a point changes. This is the first kinetic spanner for points in ℝ ^d whose performance does not depend on the spread of the point set.     

Homogenization of eigenvalue problems in perforated domains

In this paper, we treat some eigenvalue problems in periodically perforated domains and study the asymptotic behaviour of the eigenvalues and the eigenvectors when the number of holes in the domain increases to infinity Using the method of asymptotic expansion, we give explicit formula for the homogenized coefficients and expansion for eigenvalues and eigenvectors. If we denote by ε the size of each hole in the domain, then we obtain the following aysmptotic expansion for the eigenvalues: Dirichlet: λ_ε = ε⁻² λ + λ₀ +O (ε), Stekloff: λ_ε = ελ₁ +O (ε²), Neumann: λ_ε = λ₀ + ελ₁ +O (ε²). Using the method of energy, we prove a theorem of convergence in each case considered here. We briefly study correctors in the case of Neumann eigenvalue problem.     

Semidiscrete and asymptotic approximations for the nonstationary radiative–conductive heat transfer problem in a periodic system of grey heat shields

We consider semidiscrete and asymptotic approximations to a solution to the nonstationary nonlinear initial-boundary-value problem governing the radiative–conductive heat transfer in a periodic system consisting of n grey parallel plate heat shields of width ε = 1/n, separated by vacuum interlayers. We study properties of special semidiscrete and homogenized problems whose solutions approximate the solution to the problem under consideration. We establish the unique solvability of the problem and deduce a priori estimates for the solutions. We obtain error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε) for semidiscrete approximations and error estimates of order O( ?{e} ) O\left( {\sqrt {\varepsilon } } \right) and O(ε ^3/4) for asymptotic approximations. Bibliography: 9 titles.     

Complex ordering and stochastic oscillations in a class of reaction-diffusion systems with small diffusion

Summary We consider four models of partial differential equations obtained by applying a generalization of the method of normal forms to two-component reaction-diffusion systems with small diffusionu _t=εDu _xx+(A+εA ₁)u+F(u),u ∈ ℝ². These equations (quasinormal forms) describe the behaviour of solutions of the original equation forε → 0. One of the quasinormal forms is the well-known complex Ginzburg-Landau equation. The properties of attractors of the other three equations are considered. Two of these equations have an interesting feature that may be called asensitivity to small parameters: they contain a new parameterϑ(ε)=−(aε ^−1/2 mod 1) that influences the behaviour of solutions, but changes infinitely many times whenε → 0. This does not create problems in numerical analysis of quasinormal forms, but makes numerical study of the original problem involvingε almost impossible.     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.     

The number of elliptic curves over ℚ with conductorNwith conductorN

We prove that the number of elliptic curves E/ℚ with conductorN isO(N ^1/2+ε). More generally, we prove that the number of elliptic curves E/ℚ with good reduction outsideS isO(M ^1/2+ε), whereM is the product of the primes inS. Assuming various standard conjectures, we show that this bound can be improved toO(M ^c/loglogM ). Research partially supported by NSF DMS-9424642.     

Construction of Solutions and L^1-error Estimates of Viscous Methods for Scalar Conservation Laws with Boundary

This paper is concerned with an initial boundary value problem for strictly convex conservation laws whose weak entropy solution is in the piecewise smooth solution class consisting of finitely many discontinuities. By the structure of the weak entropy solution of the corresponding initial value problem and the boundary entropy condition developed by Bardos-Leroux Nedelec, we give a construction method to the weak entropy solution of the initial boundary value problem. Compared with the initial value problem, the weak entropy solution of the initial boundary value problem includes the following new interaction type： an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary. According to the structure and some global estimates of the weak entropy solution, we derive the global L^1-error estimate for viscous methods to this initial boundary value problem by using the matching travelling wave solutions method. If the inviscid solution includes the interaction that an expansion wave collides with the boundary and the boundary reflects a new shock wave which is tangent to the boundary, or the inviscid solution includes some shock wave which is tangent to the boundary, then the error of the viscosity solution to the inviscid solution is bounded by O（ε^1/2） in L^1-norm; otherwise, as in the initial value problem, the L^1-error bound is O（ε｜ In ε｜）.     

A nonlinear version of Roth's theorem for sets of positive density in the real line

It is proved that given ε>0, there is δ(ε)>0 such that ifS is a measurable set of [0,N], |S|>εN, then there is a triplex, x+h, x+h ² inS withh satisfyingh>δ(ε)N ^1/2. The argument is related to [B] and uses the behavior of certain non-linear convolution-type operators. The method can be adapted in a variety of situations. For instance, it can be used to prove the analogue of the previous statement with the square replaced by another power,h ³,h ⁴ etc.     

Cutting hyperplane arrangements

We consider a collectionH ofn hyperplanes in E ^d (where the dimensiond is fixed). An ε-cutting forH is a collection of (possibly unbounded)d-dimensional simplices with disjoint interors, which cover all E ^d and such that the interior of any simplex is intersected by at mostεn hyperplanes ofH. We give a deterministic algorithm for finding a (1/r)-cutting withO(r ^d ) simplices (which is asymptotically optimal). Forr≤n ^1−σ, where δ>0 is arbitrary but fixed, the running time of this algorithm isO(n(logn) ^O(1) r ^d−1). In the plane we achieve a time boundO(nr) forr≤n ^1−δ, which is optimal if we also want to compute the collection of lines intersecting each simplex of the cutting. This improves a result of Agarwal, and gives a conceptually simpler algorithm. For ann point setX⊆E ^d and a parameterr, we can deterministically compute a (1/r)-net of sizeO(rlogr) for the range space (X, {X ϒ R; R is a simplex}), In timeO(n(logn) ^O(1) r ^d−1 +r ^O(1)). The size of the (1/r)-net matches the best known existence result. By a simple transformation, this allows us to find ε-nets for other range spaces usually encountered in computational geometry. These results have numerous applications for derandomizing algorithms in computational geometry without affecting their running time significantly. A preliminary version of this paper appeared inProceedings of the Sixth ACM Symposium on Computational Geometry, Berkeley, 1990, pp. 1–9. Work on this paper was supported by DIMACS Center.     

The limit of the Boussinesq system of Rayleigh-Bénard convection as the Prandtl number approaches infinity

In this paper, the initial layer problem and infinite Prandtl number limit of Rayleigh-Bénard convection is studied by the asymptotic expansion methods of singular perturbation theory and the classical energy methods. For ill-prepared initial data, an exact approximating solution with expansions up to any order are given and the convergence rates O(ɛ ^m+1/2) and the optimal convergence rates O(ɛ ^m+1) are obtained respectively. This improves the result of J.G. SHI.     

A result on Waring–Goldbach problem for cubes

In this paper, we prove that, with at most O(N ^5/6+ε ) exceptions, all positive integers n ⩽ N can be written as sums of a cube and four cubes of primes.     

Rank-two update algorithms for the minimum volume enclosing ellipsoid problem

We consider the problem of computing a (1+ε)-approximation to the minimum volume enclosing ellipsoid (MVEE) of a given set of m points in R ⁿ . Based on the idea of sequential minimal optimization (SMO) method, we develop a rank-two update algorithm. This algorithm computes an approximate solution to the dual optimization formulation of the MVEE problem, which updates only two weights of the dual variable at each iteration. We establish that this algorithm computes a (1+ε)-approximation to MVEE in O(mn ³/ε) operations and returns a core set of size O(n ²/ε) for ε∈(0,1). In addition, we give an extension of this rank-two update algorithm. Computational experiments show the proposed algorithms are very efficient for solving large-scale problem with a high accuracy.     

Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem

The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝ ^d , incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radius r(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ ⁴/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(n ^Δ+1 dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space. An extended abstract appeared in ACM–SIAM Symposium on Discrete Algorithms, 2006. Work was done when J. Gao was with Center for the Mathematics of Information, California Institute of Technology. Work was done when M. Langberg was a postdoctoral scholar at the California Institute of Technology. Research supported in part by NSF grant CCF-0346991. Research of L.J. Schulman supported in part by an NSF ITR and the Okawa Foundation.     

The Exceptional Set in Hua＇s Theorem for Three Squares of Primes

It is proved that with at most O(N^11/12 c) exceptions, all positive integers n ≤ N satisfying some necessary congruence conditions are the sum of three squares of primes. This improves substantially the previous results in this direction.     

Asymptotic analysis of a parabolic semilinear problem with nonlinear boundary multiphase interactions in a perforated domain

We consider a parabolic semilinear problem with rapidly oscillating coefficients in a domain Ω_ε that is ε-periodically perforated by small holes of size O\mathcal {O}(ε). The holes are divided into two ε-periodical sets depending on the boundary interaction at their surfaces, and two different nonlinear Robin boundary conditions σ_ε(u _ε) + εκ _m (u _ε) = εg ^(m) _ε, m = 1, 2, are imposed on the boundaries of holes. We study the asymptotics as ε → 0 and establish a convergence theorem without using extension operators. An asymptotic approximation of the solution and the corresponding error estimate are also obtained. Bibliography: 60 titles. Illustrations: 1 figure.