Explicit Cost Bounds of Algorithms for Multivariate Tensor Product Problems

We study multivariate tenser product problems in the worst case and average case settings. They are defined on functions of d variables. For arbitrary d, we provide explicit upper bounds on the costs of algorithms which compute an ϵ-approximation to the solution. The cost bounds are of the form (c(d) + 2)β₁(β₂ + β₃(ln 1/ϵ)/(d − 1))^{β₄(d − 1)}(1/ϵ)^β₅. Here c(d) is the cost of one function evaluation (or one linear functional evaluation), and β_i′s do not depend on d; they are determined by the properties of the problem for d = 1. For certain tensor product problems, these cost bounds do not exceed c(d)Kϵ^−p for some numbers K and p, both independent of d. However, the exponents p which we obtain are too large. We apply these general estimates to certain integration and approximation problems in the worst and average case settings. We also obtain an upper bound, which is independent of d, for the number, n(ϵ, d), of points for which discrepancy (with unequal weights) is at most ϵ, n(ϵ, d) ≤ 7.26ϵ^−2.454, ∀d, ϵ ≤ 1.     

Differential forms in Carnot groups: a Γ-convergence approach

Carnot groups (connected simply connected nilpotent stratified Lie groups) can be endowed with a complex (E ₀ ^* , d _c ) of “intrinsic” differential forms. In this paper we prove that, in a free Carnot group of step κ, intrinsic 1-forms as well as their intrinsic differentials d _c appear naturally as limits of usual “Riemannian” differentials d _ε , ε >?0. More precisely, we show that L ²-energies associated with ε ^?κ d _ε on 1 forms Γ-converge, as ε → 0, to the energy associated with d _c .     

How to minimize the cost of iterative methods in the presence of perturbations

We consider iterative methods for approximating solutions of nonlinear equations, where the iteration cannot be computed exactly, but is corrupted by additive perturbations. The cost of computing each iteration depends on the size of the perturbation. For a class of cost functions, we show that the total cost of producing an ε-approximation can be made proportional to the cost c(ε) of one single iterative step performed with the accuracy proportional to ε. We also demonstrate that for some cost functions the total cost is proportional to c(ε)². In both cases matching lower bounds are shown. The results find natural application to establishing the complexity of nonlinear boundary-value problems, where they yield an improvement over the known upper bounds, and remove the existing gap between the upper and lower bounds.     

The Exponent of Discrepancy Is at Least 1.0669

LetP⊂[0, 1]^dbe ann-point set and letw: P→[0, ∞) be a weight function withw(P)=∑_z∈P w(z)=1. TheL₂-discrepancy of the weighted set (P, w) is defined as theL₂-average ofD(x)=vol(B_x)−w(P∩B_x) overx∈[0, 1]^d, where vol(B_x) is the volume of thed-dimensional intervalB_x=∏^d_k=1 [0, x_k). The exponent of discrepancyp* is defined as the infimum of numberspsuch that for all dimensionsd⩾1 and allε>0 there exists a weighted set of at mostKε^−ppoints in [0, 1]^dwithL₂-discrepancy at mostε, whereK=K(p) is a suitable number independent ofεandd. Wasilkowski and Woźniakowski proved thatp*⩽1.4779, by combining known bounds for the error of numerical integration and using their relation toL₂-discrepancy. In this note we observe that a careful treatment of a classical lower- bound proof of Roth yieldsp*⩾1.04882, and by a slight modification of the proof we getp*⩾1.0669. Determiningp* exactly seems to be quite a difficult problem.     

A Note on the Complexity of Solving Poisson's Equation for Spaces of Bounded Mixed Derivatives

We study the complexity of solving the d-dimensional Poisson equation on ]0, 1[^d. We restrict ourselves to cases where the solution u lies in some space of functions of bounded mixed derivatives (with respect to the L_∞- or the L₂-norm) up to ∂^2d/∏^d_j=1 ∂x²_j. An upper bound for the complexity of computing a solution of some prescribed accuracy ε with respect to the energy norm is given, which is proportional to ε⁻¹. We show this result in a constructive manner by proposing a finite element method in a special sparse grid space, which is obtained by an a priori grid optimization process based on the energy norm. Thus, the result of this paper is twofold: First, from a theoretical point of view concerning the complexity of solving elliptic PDEs, a strong tractability result of the order O(ε⁻¹) is given, and, second, we provide a practically usable hierarchical basis finite element method of this complexity O(ε⁻¹), i.e., without logarithmic terms growing exponentially in d, at least for our sparse grid setting with its underlying smoothness requirements.     

Maximal periods of (Ehrhart) quasi-polynomials

A quasi-polynomial is a function defined of the form q(k)=cd(k)kd+cd−1(k)kd−1+?+c₀(k), where c₀,c₁,…,cd are periodic functions in k∈Z. Prominent examples of quasi-polynomials appear in Ehrhart's theory as integer-point counting functions for rational polytopes, and McMullen gives upper bounds for the periods of the cj(k) for Ehrhart quasi-polynomials. For generic polytopes, McMullen's bounds seem to be sharp, but sometimes smaller periods exist. We prove that the second leading coefficient of an Ehrhart quasi-polynomial always has maximal expected period and present a general theorem that yields maximal periods for the coefficients of certain quasi-polynomials. We present a construction for (Ehrhart) quasi-polynomials that exhibit maximal period behavior and use it to answer a question of Zaslavsky on convolutions of quasi-polynomials.     

Bounds of the hyper-chaotic Lorenz–Stenflo system

To estimate the ultimate bound and positively invariant set for a dynamical system is an important but quite challenging task in general. This paper attempts to investigate the ultimate bounds and positively invariant sets of the hyper-chaotic Lorenz–Stenflo (L–S) system, which is based on the optimization method and the comparison principle. A family of ellipsoidal bounds for all the positive parameters values a, b, c, dand a cylindrical bound for a > 0, b > 1, c > 0, d > 0 are derived. Numerical results show the effectiveness and advantage of our methods.     

Quantum Complexity of Integration

It is known that quantum computers yield a speed-up for certain discrete problems. Here we want to know whether quantum computers are useful for continuous problems. We study the computation of the integral of functions from the classical Hölder classes F^k, α_d on [0, 1]^d and define γ by γ=(k+α)/d. The known optimal orders for the complexity of deterministic and (general) randomized methods are comp(F^k, α_d, ε)≍ε^−1/γ and comp^random(F^k, α_d, ε)≍ε^−2/(1+2γ). For a quantum computer we prove comp^quant_query(F^k, α_d, ε)≍ε^−1/(1+γ) and comp^quant(F^k, α_d, ε)⩽Cε^−1/(1+γ)(log ε⁻¹)^1/(1+γ). For restricted Monte Carlo (only coin tossing instead of general random numbers) we prove comp^coin(F^k, α_d, ε)⩽Cε^−2/(1+2γ)(log ε⁻¹)^1/(1+2γ). To summarize the results one can say that   • there is an exponential speed-up of quantum algorithms over deterministic (classical) algorithms, if γ is small;   • there is a (roughly) quadratic speed-up of quantum algorithms over randomized classical methods, if γ is small.     

A Probabilistic Analysis of Linear Operator Testing

We test for β-conformance of an implementation linear operator A to a specification linear operator S where the operator domain and range are separable Hilbert spaces and the domain space F is equipped with a Gaussian measure μ. Given an error bound ε>0 and a tolerance parameter β∈(0, 1), we want to determine either that there is an element f in a ball B_q of radius q in domain F such that 6Sf−Af6>ε or that Aβ-conforms to S on a set of measure at least 1−β in the ball B_q; i.e., μ_q(f: 6Sf−Af6⩽ε)⩾1−β where μ_q is the truncated Gaussian measure to B_q. We present a deterministic algorithm that solves this problem and uses almost a minimal number of tests where each test is an evaluation of operators S and A at an element of F. We prove that optimal tests are conducted on the eigenvectors of the covariance operator of μ. They are universal; they are independent of the operators under consideration and other problem parameters. We show that finite testing is conclusive in this probabilistic setting. In contrast, finite testing is inconclusive in the worst and average case settings; see [5, 7]. We discuss the upper and lower bounds on the minimal number of tests. For q=∞ we derive the exact bounds on the minimal number of tests, which depend on β very weakly. On the other hand, for a finite q, the bounds on the minimal number of tests depend on β more significantly. We explain our approach by an example with the Wiener measure.     

Tractability of Multivariate Integration for Periodic Functions

We study multivariate integration in the worst case setting for weighted Korobov spaces of smooth periodic functions of d variables. We wish to reduce the initial error by a factor ε for functions from the unit ball of the weighted Korobov space. Tractability means that the minimal number of function samples needed to solve the problem is polynomial in ε⁻¹ and d. Strong tractability means that we have only a polynomial dependence in ε⁻¹. This problem has been recently studied for quasi-Monte Carlo quadrature rules and for quadrature rules with non-negative coefficients. In this paper we study arbitrary quadrature rules. We show that tractability and strong tractability in the worst case setting hold under the same assumptions on the weights of the Korobov space as for the restricted classes of quadrature rules. More precisely, let γ_j moderate the behavior of functions with respect to the jth variable in the weighted Korobov space. Then strong tractability holds iff ∑^∞_j=1 γ_j<∞, whereas tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/ln d<∞. We obtain necessary conditions on tractability and strong tractability by showing that multivariate integration for the weighted Korobov space is no easier than multivariate integration for the corresponding weighted Sobolev space of smooth functions with boundary conditions. For the weighted Sobolev space we apply general results from E. Novak and H. Woźniakowski (J. Complexity17 (2001), 388–441) concerning decomposable kernels.     

Analytic regularity for a singularly perturbed system of reaction-diffusion equations with multiple scales

We consider a coupled system of two singularly perturbed reaction-diffusion equations, with two small parameters 0?<?ε?≤?μ?≤?1, each multiplying the highest derivative in the equations. The presence of these parameters causes the solution(s) to have boundary layers which overlap and interact, based on the relative size of ε and μ. We show how one can construct full asymptotic expansions together with error bounds that cover the complete range 0?<?ε?≤?μ?≤?1. For the present case of analytic input data, we present derivative growth estimates for the terms of the asymptotic expansion that are explicit in the perturbation parameters and the expansion order.     

Core instances for testing: A case study

Data generation for computational testing of optimization algorithms is a key topic in experimental algorithmics. Recently, concern has arisen that many published computational experiments are inadequate with respect to the way test instances are generated. In this paper we suggest a new research direction that might be useful to cope with the possible limitations of data generation. The basic idea is to select a finite set of instances which ‘represent’ the whole set of instances. We propose a measure of the representativeness of an instance, which we call ε-representativeness: for a minimization problem, an instance x_ε is ε-representative of another instance x if a (1 + ε)-approximate solution to x can be obtained by solving x_ε. Focusing on a strongly NP-hard single machine scheduling problem, we show how to map the infinite set of all instances into a finite set of ε-representative core instances. We propose to use this finite set of ε-representative core instances to test heuristics.     

N-Widths and ε-Dimensions for High-Dimensional Approximations

In this paper, we study linear trigonometric hyperbolic cross approximations, Kolmogorov n-widths d _n (W,H ^γ ), and ε-dimensions n _ε (W,H ^γ ) of periodic d-variate function classes W with anisotropic smoothness, where d may be large. We are interested in finding the accurate dependence of d _n (W,H ^γ ) and n _ε (W,H ^γ ) as a function of two variables n, d and ε, d, respectively. Recall that n, the dimension of the approximating subspace, is the main parameter in the study of convergence rates with respect to n going to infinity. However, the parameter d may seriously affect this rate when d is large. We construct linear approximations of functions from W by trigonometric polynomials with frequencies from hyperbolic crosses and prove upper bounds for the error measured in isotropic Sobolev spaces H ^γ . Furthermore, in order to show the optimality of the proposed approximation, we prove upper and lower bounds of the corresponding n-widths d _n (W,H ^γ ) and ε-dimensions n _ε (W,H ^γ ). Some of the received results imply that the curse of dimensionality can be broken in some relevant situations.     

A Two-Dimensional Bisection Envelope Algorithm for Fixed Points

In this paper we present a new algorithm for the two-dimensional fixed point problem f(x)=x on the domain [0, 1]×[0, 1], where f is a Lipschitz continuous function with respect to the infinity norm, with constant 1. The computed approximation x satisfies 6f(x)−x6_∞⩽ε for a specified tolerance ε<0.5. The upper bound on the number of required function evaluations is given by 2⌈log₂(1/ε)⌉+1. Similar bounds were derived for the case of the 2-norm by Z. Huang et al. (1999, J. Complexity15, 200–213), our bound is the first for the infinity norm case.     

The motion of a particle on a light viscoelastic bar: asymptotic analysis of its quasilinear parabolic–hyperbolic equation

We study the large longitudinal motion of a nonlinearly viscoelastic bar with one end fixed and the other end attached to a heavy particle. This problem is a precise continuum-mechanical analog of the basic discrete mechanical problem of the motion of a particle on a (massless) spring. This motion is governed by an initial-boundary-value problem for a class of third-order quasilinear parabolic–hyperbolic partial differential equations subject to a nonstandard boundary condition, which is the equation of motion of the particle. The ratio of the mass of the bar to that of the tip mass is taken to be a small parameter ε. We prove that this problem has a unique globally defined solution that admits a valid asymptotic expansion, including an initial-layer expansion, in powers of ε for ε near 0. The validity of the expansion gives a precise meaning to the solution of the reduced problem, obtained by setting ε=0, which curiously is seldom governed by the expected ordinary differential equation. The fundamental constitutive hypothesis that the tension be a uniformly monotone function of the strain rate plays a critical role in a delicate proof that each term of the initial-layer expansion decays exponentially in time. These results depend on new decay estimates for the solution of quasilinear parabolic equations.     

Convergence of a family of solutions to a Fujita-type equation in domains with cavities

The Dirichlet problem for a Fujita-type equation, i.e., a second-order quasilinear uniformly elliptic equation is considered in domains Ω_ε with spherical or cylindrical cavities of characteristic size ε. The form of the function in the condition on the cavities’ boundaries depends on ε. For ε tending to zero and the number of cavities increasing simultaneously, sufficient conditions are established for the convergence of the family of solutions {u _ε(x)} of this problem to the solution u(х) of a similar problem in the domain Ω with no cavities with the same boundary conditions imposed on the common part of the boundaries ?Ω and ?Ω_ε. Convergence rate estimates are given.     

A regularization for discontinuous differential equations with application to state-dependent delay differential equations of neutral type

We consider a regularization for a class of discontinuous differential equations arising in the study of neutral delay differential equations with state dependent delays. For such equations the possible discontinuity in the derivative of the solution at the initial point may propagate along the integration interval giving rise to so-called “breaking points”, where the solution derivative is again discontinuous. Consequently, the problem of continuing the solution in a right neighborhood of a breaking point is equivalent to a Cauchy problem for an ode with a discontinuous right-hand side (see e.g. Bellen et al., 2009 [4]). Therefore a classical solution may cease to exist.The regularization is based on the replacement of the vector-field with its time average over an interval of length ε>0. The regularized solution converges as ε→⁰⁺ to the classical Filippov solution (Filippov, 1964, 1988 [13] and [14]). Several properties of the solutions corresponding to small ε>0 are presented.     

Maximum size of a planar graph with given degree and even diameter

We offer the exact solution of the degree-diameter problem for planar graphs in the case of even diameter 2d and large degree Δ≥6(12d+1). New graph examples are constructed improving the lower bounds for Δ≥5.