Bounded-Independence Derandomization of Geometric Partitioning with Applications to Parallel Fixed-Dimensional Linear Programming

We give fast and efficient methods for constructing ε-nets and ε-approximations for range spaces with bounded VC-exponent. These combinatorial structures have wide applicability to geometric partitioning problems, which are often used in divide-and-conquer constructions in computational geometry algorithms. In addition, we introduce a new deterministic set approximation for range spaces with bounded VC-exponent, which we call the δ-relative ε-approximation, and we show how such approximations can be efficiently constructed in parallel. To demonstrate the utility of these constructions we show how they can be used to solve the linear programming problem in deterministically in time using linear work in the PRAM model of computation, for any fixed constant d. Our method is developed for the CRCW variant of the PRAM parallel computation model, and can be easily implemented to run in time using linear work on an EREW PRAM. Received August 7, 1995, and in revised form November 11, 1996.     

Efficient Algorithms for Approximating Polygonal Chains

We consider the problem of approximating a polygonal chain C by another polygonal chain C' whose vertices are constrained to be a subset of the set of vertices of C . The goal is to minimize the number of vertices needed in the approximation C' . Based on a framework introduced by Imai and Iri [25], we define an error criterion for measuring the quality of an approximation. We consider two problems. (1) Given a polygonal chain C and a parameter ɛ \geq 0 , compute an approximation of C , among all approximations whose error is at most ɛ , that has the smallest number of vertices. We present an O(n ^{4/3 + δ} ) -time algorithm to solve this problem, for any δ > 0; the constant of proportionality in the running time depends on δ . (2) Given a polygonal chain C and an integer k , compute an approximation of C with at most k vertices whose error is the smallest among all approximations with at most k vertices. We present a simple randomized algorithm, with expected running time O(n ^{4/3 + δ} ) , to solve this problem. Received September 17, 1998, and in revised form July 8, 1999.     

Scaling Methods and Approximative Equations for Homogeneous Reaction—Diffusion Systems and Applications to Epidemics

Summary. We consider a reaction-diffusion equation that is homogeneous of degree one. This homogeneity is a symmetry. The dynamics is factorized into trivial evolution due to symmetry and nontrivial behavior by a projection to an appropriate hypermanifold. The resulting evolution equations are rather complex. We examine the bifurcation behavior of a stationary point of the projected system. For these purposes we develop techniques for dimension reduction similar to the Ginzburg-Landau (GL) approximation, the modulation equations. Since we are not in the classical GL situation, the remaining approximative equations have a quadratic nonlinearity and the amplitude does not scale with ε but with ε ² where ε ² denotes the bifurcation parameter. Moreover, the symmetry requires that not only one but two equations are necessary to describe the behavior of the system. We investigate traveling fronts for the modulation equations. This result is used to analyze an epidemic model. Received April 9, 1996; second revision received January 3, 1997; final revision received October 7, 1997; accepted January 19, 1998     

Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

Let Ω be a set of pairwise-disjoint polyhedral obstacles in R ³ with a total of n vertices, and let B be a ball in R ³. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n ^2+ε ), for any ε >0; the constant of proportionality depends on ε. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F . The special case in which Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n ^2+ε ). Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.     

An analytic center quadratic cut method for the convex quadratic feasibility problem

 We consider a quadratic cut method based on analytic centers for two cases of convex quadratic feasibility problems. In the first case, the convex set is defined by a finite yet large number, N, of convex quadratic inequalities. We extend quadratic cut algorithm of Luo and Sun [3] for solving such problems by placing or translating the quadratic cuts directly through the current approximate center. We show that, in terms of total number of addition and translation of cuts, our algorithm has the same polynomial worst case complexity as theirs [3]. However, the total number of steps, where steps consist of (damped) Newton steps, function evaluations and arithmetic operations, required to update from one approximate center to another is , where ε is the radius of the largest ball contained in the feasible set. In the second case, the convex set is defined by an infinite number of certain strongly convex quadratic inequalities. We adapt the same quadratic cut method for the first case to the second one. We show that in this case the quadratic cut algorithm is a fully polynomial approximation scheme. Furthermore, we show that, at each iteration, k, the total number steps (as described above) required to update from one approximate center to another is at most , with ε as defined above. Received: April 2000 / Accepted: June 2002 Published online: September 5, 2002 Key words. convex quadratic feasibility problem – interior-point methods – analytic center – quadratic cuts – potential function     

Artinian property of constants of algebraicq-skew derivations

Let δ denote aq-skew σ-derivation of an algebraR andR ^(δ)={r εR│δ(r)=0} stand for the subalgebra of invariants. We prove thatR ^(δ) is left artinian iffR is left artinian providedR is semiprime and the action of δ onR is algebraic. This research was supported by the grant 190/R97/R98 in the frame of French-Polish joint projects and by Polish KBN grant no. 2 PO3A 039 14. We would like to thank all three universities for their hospitality.     

Efficient piecewise-linear function approximation using the uniform metric

We given anO(n logn)-time method for finding a bestk-link piecewise-linear function approximating ann-point planar point set using the well-known uniform metric to measure the error, ε≥0, of the approximation. Our methods is based upon new characterizations of such functions, which we exploit to design an efficient algorithm using a plane sweep in “ε space” followed by several applications of the parametric-searching technique. The previous best running time for this problems wasO(n ²). This research was announced in preliminary form at the 10th ACM Symposium on Computational Geometry. The author was partially supported by the NSF and DARPA under Grant CCR-8908092, and by the NSF under Grants IRI-9116843 and CCR-9300079.     

Convergence Properties of a Self-adaptive Levenberg-Marquardt Algorithm Under Local Error Bound Condition

We propose a new self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear equations F(x) = 0. The Levenberg-Marquardt parameter is chosen as the product of ‖F_k‖^δ with δ being a positive constant, and some function of the ratio between the actual reduction and predicted reduction of the merit function. Under the local error bound condition which is weaker than the nonsingularity, we show that the Levenberg-Marquardt method converges superlinearly to the solution for δ∈ (0, 1), while quadratically for δ∈ [1, 2]. Numerical results show that the new algorithm performs very well for the nonlinear equations with high rank deficiency. This work is supported by Chinese NSFC grants 10401023 and 10501013, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Shanghai Municipal Education Commission, N. E03004.     

Helly-Type Theorems for Approximate Covering

Let ℱ∪{U} be a collection of convex sets in ℝ ^d such that ℱ covers U. We prove that if the elements of ℱ and U have comparable size, then a small subset of ℱ suffices to cover most of the volume of U; we analyze how small this subset can be depending on the geometry of the elements of ℱ and show that smooth convex sets and axis parallel squares behave differently. We obtain similar results for surface-to-surface visibility amongst balls in three dimensions for a notion of volume related to form factor. For each of these situations, we give an algorithm that takes ℱ and U as input and computes in time O(|ℱ|*|ℋ _ε |) either a point in U not covered by ℱ or a subset ℋ _ε covering U up to a measure ε, with |ℋ _ε | meeting our combinatorial bounds. The authors acknowledge support from the French–Korean Science and Technology amicable relationship program (STAR) 11844QJ.     

s-Representations for involutions¶on affine Kac–Moody algebras are polar

Let denote the eigenspace decomposition of a twisted affine Kac–Moody algebra with respect to an involution , where is a twisted loop algebra, is the center and d is the scaling element of . We endow with the standard bilinear symmetrical form.Then with and carries a Lorentzian signature. Let denote the group that corresponds to , then the adjoint representation of on can be restricted to and this submanifold is isometrical to the Hilbert space E _ε, where is the decomposition of the twisted loop algebra with respect to the induced involutionρ₀.We thus obtain an affine representation on E _ε and we show that this representation is polar, i. e., there exists a submanifold that intersects all orbits, and intersects them orthogonally. Received: 16 February 2000 RID=" ID="Supported by a DFG grant.     

On the Best Constant in the Error Bound for theH0-Projection into Piecewise Polynomial Spaces

Explicita priorierror bounds for the approximation by theH¹₀-projection into piecewise polynomial spaces are given. In particular, for the quadratic approximation, the optimal constant is derived, and a nearly optimal value for the cubic is obtained. These constants play an important role in the numerical verification method of finite element solutions for nonlinear elliptic equations.     

Representing a Functional Curve by Curves with Fewer Peaks

In this paper, we study the problems of (approximately) representing a functional curve in 2-D by a set of curves with fewer peaks. Representing a function (or its curve) by certain classes of structurally simpler functions (or their curves) is a basic mathematical problem. Problems of this kind also find applications in applied areas such as intensity-modulated radiation therapy (IMRT). Let f\bf f be an input piecewise linear functional curve of size n. We consider several variations of the problems. (1) Uphill–downhill pair representation (UDPR): Find two nonnegative piecewise linear curves, one nondecreasing (uphill) and one nonincreasing (downhill), such that their sum exactly or approximately represents f\bf f. (2) Unimodal representation (UR): Find a set of unimodal (single-peak) curves such that their sum exactly or approximately represents f\bf f. (3) Fewer-peak representation (FPR): Find a piecewise linear curve with at most k peaks that exactly or approximately represents f\bf f. Furthermore, for each problem, we consider two versions. For the UDPR problem, we study its feasibility version: Given ε>0, determine whether there is a feasible UDPR solution for f\bf f with an approximation error ε; its min-ε version: Compute the minimum approximation error ε ^∗ such that there is a feasible UDPR solution for f\bf f with error ε ^∗. For the UR problem, we study its min-k version: Given ε>0, find a feasible solution with the minimum number k ^∗ of unimodal curves for f\bf f with an error ε; its min-ε version: given k>0, compute the minimum error ε ^∗ such that there is a feasible solution with at most k unimodal curves for f\bf f with error ε ^∗. For the FPR problem, we study its min-k version: Given ε>0, find one feasible curve with the minimum number k ^∗ of peaks for f\bf f with an error ε; its min-ε version: given k≥0, compute the minimum error ε ^∗ such that there is a feasible curve with at most k peaks for f\bf f with error ε ^∗. Little work has been done previously on solving these functional curve representation problems. We solve all the problems (except the UR min-ε version) in optimal O(n) time, and the UR min-ε version in O(n+mlog m) time, where m<n is the number of peaks of f\bf f. Our algorithms are based on new geometric observations and interesting techniques.     

Asymptotic analysis of a boundary-value problem with nonlinear multiphase boundary interactions in a perforated domain

We consider a boundary-value problem for the second-order elliptic differential operator with rapidly oscillating coefficients in a domain Ω _ε that is ε-periodically perforated by small holes. The holes are split into two ε-periodic sets depending on the boundary interaction via their boundary surfaces. Therefore, two different nonlinear boundary conditions σ _ε (u _ε ) + εκ _m (u _ε ) = εg _ε ^(m) , m = 1, 2, are given on the corresponding boundaries of the small holes. The asymptotic analysis of this problem is performed as ε → 0, namely, the convergence theorem for both the solution and the energy integral is proved without using an extension operator, asymptotic approximations for the solution and the energy integral are constructed, and the corresponding approximation error estimates are obtained.     

Guaranteed velocity error control for the pseudostress approximation of the Stokes equations

The pseudostress approximation of the Stokes equations rewrites the stationary Stokes equations with pure (but possibly inhomogeneous) Dirichlet boundary conditions as another (equivalent) mixed scheme based on a stress in H(div) and the velocity in L². Any standard mixed finite element function space can be utilized for this mixed formulation, e.g., the Raviart‐Thomas discretization which is related to the Crouzeix‐Raviart nonconforming finite element scheme in the lowest‐order case. The effective and guaranteed a posteriori error control for this nonconforming velocity‐oriented discretization can be generalized to the error control of some piecewise quadratic velocity approximation that is related to the discrete pseudostress. The analysis allows for local inf‐sup constants which can be chosen in a global partition to improve the estimation. Numerical examples provide strong evidence for an effective and guaranteed error control with very small overestimation factors even for domains with large anisotropy.© 2016 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 32: 1411–1432, 2016     

A second order nonconforming rectangular finite element method for approximating Maxwell’s equations

The main objective of this paper is to present a new rectangular nonconforming finite element scheme with the second order convergence behavior for approximation of Maxwell’s equations.Then the corresponding optimal error estimates are derived.The difficulty in construction of this finite element scheme is how to choose a compatible pair of degrees of freedom and shape function space so as to make the consistency error due to the nonconformity of the element being of order O(h 3 ) ,properly one order higher than that of its interpolation error O(h 2 ) in the broken energy norm,where h is the subdivision parameter tending to zero.     

Convergence analysis of a projection semi-implicit coupling scheme for fluid–structure interaction problems

In this paper, we provide a convergence analysis of a projection semi-implicit scheme for the simulation of fluid–structure systems involving an incompressible viscous fluid. The error analysis is performed on a fully discretized linear coupled problem: a finite element approximation and a semi-implicit time-stepping strategy are respectively used for space and time discretization. The fluid is described by the Stokes equations, the structure by the classical linear elastodynamics equations (linearized elasticity, plate or shell models) and all changes of geometry are neglected. We derive an error estimate in finite time and we prove that the time discretization error for the coupling scheme is at least ${\sqrt{\delta t}}In this paper, we provide a convergence analysis of a projection semi-implicit scheme for the simulation of fluid–structure systems involving an incompressible viscous fluid. The error analysis is performed on a fully discretized linear coupled problem: a finite element approximation and a semi-implicit time-stepping strategy are respectively used for space and time discretization. The fluid is described by the Stokes equations, the structure by the classical linear elastodynamics equations (linearized elasticity, plate or shell models) and all changes of geometry are neglected. We derive an error estimate in finite time and we prove that the time discretization error for the coupling scheme is at least ?{dt}{\sqrt{\delta t}}. Finally, some numerical experiments that confirm the theoretical analysis are presented.     

Coefficient Quantization in Banach Spaces

Let (e _i ) be a dictionary for a separable infinite-dimensional Banach space X. We consider the problem of approximation by linear combinations of dictionary elements with quantized coefficients drawn usually from a ‘finite alphabet’. We investigate several approximation properties of this type and connect them to the Banach space geometry of X. The existence of a total minimal system with one of these properties, namely the coefficient quantization property, is shown to be equivalent to X containing c ₀. We also show that, for every ε>0, the unit ball of every separable infinite-dimensional Banach space X contains a dictionary (x _i ) such that the additive group generated by (x _i ) is (3+ε)⁻¹-separated and 1/3-dense in X.      

Almost Given Length Cycles in Digraphs

A digraph is called k-cyclic if it cannot be made acyclic by removing less than k arcs. It is proved that for every ε > 0 there are constants K and δ so that for every d ∈ (0, δn), every ε n²-cyclic digraph with n vertices contains a directed cycle whose length is between d and d + K. A more general result of the same form is obtained for blow-ups of directed cycles.     

High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rⁿ. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax [9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly projected cross polytopes in the proportional-dimensional case where d ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rⁿ. We derive ρ_N(δ) > 0 with the property that, for any ρ < ρ_N(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 ≤ k ≤ ρd. This implies that P is centrally ⌊ ρ d ⌋-neighborly, and its skeleton Skel_{⌊ ρ d ⌋}(P) is combinatorially equivalent to Skel_{⌊ ρ d⌋}(C). We display graphs of ρ_N. Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness [9]; we study both. Weak (k,ε)-neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces f_k(P) ≥ f_k(C)(1 – ε). We characterize and compute the critical proportion ρ_W(δ) > 0 such that weak (k,ε) neighborliness holds at k significantly smaller than ρ_W · d and fails for k significantly larger than ρ_W · d. Sectional (k,ε)-neighborliness asks whether all, except for a small fraction ε, of the k-dimensional intrinsic sections of P are k-dimensional cross polytopes. (Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion ρ_S(δ) > 0 guaranteeing this property for k/d ∼ ρ < ρ_S(δ). We display graphs of ρ_S and ρ_W.     

Dynamics of neighborhoods of points under a continuous mapping of an interval

Let {I, f, Z ⁺} be a dynamical system induced by a continuous mapping f of a closed bounded interval I into itself. To describe the dynamics of neighborhoods of points unstable under the mapping f, we propose the concept of the εω-set ω ^{f, ε}(x) of a point x as the ω-limit set of the ε-neighborhood of the point x. We investigate the relationship between the εω-set and the domain of influence of a point. It is also shown that the domain of influence of an unstable point is always a cycle of intervals. The results obtained can be directly used in the theory of difference equations with continuous time and similar equations. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 57, No. 11, pp. 1534–1547, November, 2005.