The Price of Pessimism for Multidimensional Quadrature

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.     

Tractability of Multivariate Integration for Weighted Korobov Classes

We study the worst-case error of multivariate integration in weighted Korobov classes of periodic functions of d coordinates. This class is defined in terms of weights γ_j which moderate the behavior of functions with respect to successive coordinates. We study two classes of quadrature rules. They are quasi-Monte Carlo rules which use n function values and in which all quadrature weights are 1/n and rules for which all quadrature weights are non-negative. Tractability for these two classes of quadrature rules means that the minimal number of function values needed to guarantee error in the worst-case setting is bounded by a polynomial in d and ⁻¹. Strong tractability means that the bound does not depend on d and depends polynomially on ⁻¹. We prove that strong tractability holds iff ∑^∞_j=1 γ_j<∞, and tractability holds iff lim sup_d→∞ ∑^d_j=1 γ_j/log d<∞. Furthermore, strong tractability or tractability results are achieved by the relatively small class of lattice rules. We also prove that if ∑^∞_j=1 γ^1/α_j<∞, where α measures the decay of Fourier coefficients in the weighted Korobov class, then for d1, n prime and δ>0 there exist lattice rules that satisfy an error bound independent of d and of order n^−α/2+δ. This is almost the best possible result, since the order n^−α/2 cannot be improved upon even for d=1. A corresponding result is deduced for weighted non-periodic Sobolev spaces: if ∑^∞_j=1 γ^1/2_j<∞, then for d1, n prime and δ>0 there exist shifted lattice rules that satisfy an error bound independent of d and of order n^−1+δ. We also check how the randomized error of the (classical) Monte Carlo algorithm depends on d for weighted Korobov classes. It turns out that Monte Carlo is strongly tractable iff ∑^∞_j=1 log γ_j<∞ and tractable iff lim sup_d→∞ ∑^d_j=1 log γ_j/log d<∞. Hence, in particular, for γ_j=1 we have the usual Korobov space in which integration is intractable for the two classes of quadrature rules in the worst-case setting, whereas Monte Carlo is strongly tractable in the randomized setting.     

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 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.     

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.     

TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS

The authors study the tractability and strong tractability of a multivariate integration problem in the worst case setting for weighted l-periodic continuous functions spaces of d coordinates with absolutely convergent Fourier series.The authors reduce the initial error by a factor ε for functions from the unit ball of the weighted periodic contin- uous functions spaces.Tractability is the minimal number of function samples required to solve the problem in polynomial in ε~(-1)and d.and the strong tractability is the pres- ence of only a polynomial dependence in ε.This problem has been recently studied for quasi-Monte Carlo quadrature rules.quadrature rules with non-negative coefficients. and rules for which all quadrature weights are arbitrary for weighted Korobov spaces of smooth periodic functions of d variables.The authors show that the tractability and strong tractability of a multivariate integration problem in worst case setting hold for the weighted periodic continuous functions spaces with absolutely convergent Fourier series under the same assumptions as in Ref.[14]on the weights of the Korobov space for quasi-Monte Carlo rules and rules for which all quadrature weights are non-negative.The arguments are not constructive.     

Component-by-Component Construction of Good Lattice Rules with a Composite Number of Points

We develop algorithms to construct rank-1 lattice rules in weighted Korobov spaces of periodic functions and shifted rank-1 lattice rules in weighted Sobolev spaces of non-periodic functions. Analyses are given which show that the rules so constructed achieve strong QMC tractability error bounds. Unlike earlier analyses, there is no assumption that n, the number of quadrature points, be a prime number. However, we do assume that there is an upper bound on the number of distinct prime factors of n. The generating vectors and shifts characterizing the rules are constructed ‘component-by-component,’ that is, the (d+1)th components of the generating vectors and shifts are obtained using one-dimensional searches, with the previous d components kept unchanged.     

Lattice-Nyström method for Fredholm integral equations of the second kind with convolution type kernels

We consider Fredholm integral equations of the second kind of the form , where g and k are given functions from weighted Korobov spaces. These spaces are characterized by a smoothness parameter α>1 and weights γ₁≥γ₂≥. The weight γ_j moderates the behavior of the functions with respect to the jth variable. We approximate f  by the Nyström method using n rank-1 lattice points. The combination of convolution and lattice group structure means that the resulting linear system can be solved in O(nlogn) operations. We analyze the worst case error measured in sup norm for functions g in the unit ball and a class of functions k in weighted Korobov spaces. We show that the generating vector of the lattice rule can be constructed component-by-component to achieve the optimal rate of convergence O(n^-α/2+δ), δ>0, with the implied constant independent of the dimension d under an appropriate condition on the weights. This construction makes use of an error criterion similar to the worst case integration error in weighted Korobov spaces, and the computational cost is only O(nlognd) operations. We also study the notion of QMC-Nyström tractability: tractability means that the smallest n needed to reduce the worst case error (or normalized error) to is bounded polynomially in ^-1 and d; strong tractability means that the bound is independent of d. We prove that strong QMC-Nyström tractability in the absolute sense holds iff , and QMC-Nyström tractability holds in the absolute sense iff .     

Matrix characterization of linear codes with arbitrary Hamming weight hierarchy

The support of an [n, k] linear code C over a finite field F_q is the set of all coordinate positions such that at least one codeword has a nonzero entry in each of these coordinate position. The rth generalized Hamming weight d_r(C), 1 ⩽ r ⩽ k, of C is defined as the minimum of the cardinalities of the supports of all [n, r] subcodes of C. The sequence (d₁(C), d₂(C), … , d_k(C)) is called the Hamming weight hierarchy (HWH) of C. The HWH, d_r(C) = n − k + r;  r = 1, 2 , …, k, characterizes maximum distance separable (MDS) codes. Therefore the matrix characterization of MDS codes is also the characterization of codes with the HWH d_r(C) = n − k + r; r = 1, 2, … , k. A linear code C with systematic check matrix [I∣P], where I is the (n − k) × (n − k) identity matrix and P is a (n − k) × k matrix, is MDS iff every square submatrix of P is nonsingular. In this paper we extend this characterization to linear codes with arbitrary HWH. Using this result, we characterize Near-MDS codes, Near-Near-MDS (N²-MDS) codes and A^μ-MDS codes. The MDS-rank of C is the smallest integer η such that d_η+1 = n − k + η + 1 and the defect vector of C with MDS-rank η is defined as the ordered set {μ₁(C), μ₂(C), μ₃(C), … , μ_η(C), μ_η+1(C)}, where μ_i(C) = n − k + i − d_i(C). We call C a dually defective code if the defect vector of the code and its dual are the same. We also discuss matrix characterization of dually defective codes. Further, the codes meeting the generalized Greismer bound are characterized in terms of their generator matrix. The HWH of dually defective codes meeting the generalized Greismer bound are also reported.     

Lattice Algorithms for Multivariate L ∞ Approximation in the Worst-Case Setting

We approximate d-variate functions from weighted Korobov spaces with the error of approximation defined in the L _∞ sense. We study lattice algorithms and consider the worst-case setting in which the error is defined by its worst-case behavior over the unit ball of the space of functions. A lattice algorithm is specified by a generating (integer) vector. We propose three choices of such vectors, each corresponding to a different search criterion in the component-by-component construction. We present worst-case error bounds that go to zero polynomially with n ^?1, where n is the number of function values used by the lattice algorithm. Under some assumptions on the weights of the function space, the worst-case error bounds are also polynomial in d, in which case we have (polynomial) tractability, or even independent of d, in which case we have strong (polynomial) tractability. We discuss the exponents of n ^?1 and stress that we do not know if these exponents can be improved.     

Electrostatics in fractal geometry: Fractional calculus approach

An electric field in a composite dielectric with a fractal charge distribution is obtained in the spherical symmetry case. The method is based on the splitting of a composite volume into a fractal volume V_d ～ r^d with the fractal dimension d and a complementary host volume V_h = V₃ ? V_d. Integrations over these fractal volumes correspond to the convolution integrals that eventually lead to the employment of the fractional integro-differentiation.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

Multivariate approximation in the worst case setting over reproducing kernel Hilbert spaces

We study the worst case setting for approximation of d variate functions from a general reproducing kernel Hilbert space with the error measured in the L_∞ norm. We mainly consider algorithms that use n arbitrary continuous linear functionals. We look for algorithms with the minimal worst case errors and for their rates of convergence as n goes to infinity. Algorithms using n function values will be analyzed in a forthcoming paper.We show that the L_∞ approximation problem in the worst case setting is related to the weighted L₂ approximation problem in the average case setting with respect to a zero-mean Gaussian stochastic process whose covariance function is the same as the reproducing kernel of the Hilbert space. This relation enables us to find optimal algorithms and their rates of convergence for the weighted Korobov space with an arbitrary smoothness parameter α>1, and for the weighted Sobolev space whose reproducing kernel corresponds to the Wiener sheet measure. The optimal convergence rates are n^-(α-1)/2 and n^-1/2, respectively.We also study tractability of L_∞ approximation for the absolute and normalized error criteria, i.e., how the minimal worst case errors depend on the number of variables, d, especially when d is arbitrarily large. We provide necessary and sufficient conditions on tractability of L_∞ approximation in terms of tractability conditions of the weighted L₂ approximation in the average case setting. In particular, tractability holds in weighted Korobov and Sobolev spaces only for weights tending sufficiently fast to zero and does not hold for the classical unweighted spaces.     

A semi-Markov process with an inverse Gaussian distribution as sojourn time

Let X_n denote the state of a device after n repairs. We assume that the time between two repairs is the time τ taken by a Wiener process {W(t), t ? 0}, starting from w₀ and with drift μ < 0, to reach c ∈ [0, w₀). After the nth repair, the process takes on either the value X_n?1 + 1 or X_n?1 + 2. The probability that X_n = X_n?1 + j, for j = 1, 2, depends on whether τ ? t₀ (a fixed constant) or τ > t₀. The device is considered to be worn out when X_n ? k, where k ∈ {1, 2, …}. This model is based on the ones proposed by Rishel (1991) [1] and Tseng and Peng (2007) [2]. We obtain an explicit expression for the mean lifetime of the device. Numerical methods are used to illustrate the analytical findings.     

On generalized Jordan 1-derivation in rings

Let n ⩾ 1 be a fixed integer and let R be an (n + 1)!-torsion free 1-ring with identity element e. If F, d:R → R are two additive mappings satisfying F(xⁿ⁺¹) = F(x)(x¹)ⁿ + xd(x)(x¹)ⁿ⁻¹ + x²d(x)(x¹)ⁿ⁻²+ ⋯ +xⁿd(x) for all x ∈ R, then d is a Jordan 1-derivation and F is a generalized Jordan 1-derivation on R.     

Space–time symmetry violation,configuration mixing model and E-infinity theory

We have studied the time reversal symmetry violation on the bases of the configuration mixing model and E-infinity theory. With the use of the Cabibbo angle approximation, we have presented the transformation matrix in terms of the golden ratio (?), and shown that the time reversal symmetry violation is described by the configuration mixing of the unstable and stable manifolds (W^u, W^s). The magnitude of the mixing for the weak interaction field is given by the expression sin² θ_T(theor) ≈ sin⁴ θ_C(theor) ≈ (?)¹² = 3.105 × 10^?3, which is compared to the Kaon decay experiment ～2.3 × 10^?3. We have also discussed the space–time symmetry violation by using the CPT theorem.     

Where Does Smoothness Count the Most for Two-Point Boundary-Value Problems?

We study the complexity of scalar 2mth order elliptic two-point boundary-value problems Lu=f, error being measured in the energy norm. Previous work on the complexity of these problems has generally assumed that we had partial information about the right-hand side f and complete information about the coefficients of L. In this paper, we study the complexity of such problems when, in addition to partial information about f, we have only partial information about the coefficients of L. More precisely, we suppose that f has r derivatives in the L_p-sense, with r⩾−m and p∈[2, ∞], and that L has the usual divergence form Lv=∑_{0⩽i, j⩽m} (−1)ⁱ Dⁱ(a_i, j D^jv), with a_i, j being r_i, j-times continuously differentiable, where r_i, j⩾0. We first suppose that continuous linear information is available. Let r=min{r, min_{0⩽i, j⩽m} {r_i, j−i}}. If r=−m, the problem is unsolvable; for r>−m, we find that the ε-complexity is proportional to (1/ε)^1/(r+m), and we show that a finite element method (FEM) is optimal. We next suppose that only standard information (consisting of function and/or derivative evaluations) is available. Let r_min=min{r, min_{0⩽i, j⩽m} {r_i, j}}. If r_min=0, the problem is unsolvable; for r_min>0, we find that the ε-complexity is proportional to (1/ε)^1/r_min, and we show that a modified FEM (which uses only function evaluations, and not derivatives) is optimal.