Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

PAMM

Strong tractability of multivariate integration of arbitrary order

Josef Dick, Friedrich Pillichshammer

Published Dec 1, 2007• 0 citations
Publisher

Abstract

Abstract We show the existence of digitally‐shifted polynomial lattice rules which achieve strong tractability results for Sobolev spaces of arbitrary high smoothness. The convergence rate is shown to be best possible up to a given degree of smoothness of the integrand. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)
DOI
10.1002/pamm.200700276

Related papers

Richardson Extrapolation of Polynomial Lattice Rules

Josef Dick, Takashi Goda, Takehito Yoshiki

We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness $\alpha\geq 2$ defined over the $s$-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over $\Bbb{F}_b$ with $\alpha$ consecutive sizes of nodes, $b^{m-\alpha+1},\ldots,b^{m}$, and (ii) recursive application of Richardson extrapolation to a chain of $\alpha$ approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order $(s+\alpha)N\log N$, which improves the currently known result for the interlaced polynomial lattice rule, which is of order $s\alpha N\log N$. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.

arXiv:1707.03989•SIAM Journal on Numerical Analysis•Jan 1, 2019•10 citations

Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules

Josef Dick, Friedrich Pillichshammer

Journal of Complexity•Feb 23, 2007•35 citations

Strong tractability of multivariate integration using quasi–Monte Carlo algorithms

Xiaoqun Wang

We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })

Mathematics of Computation•Jun 25, 2002•58 citations

Scaled lattice rules for integration on ℝ^{𝕕} achieving higher-order convergence with error analysis in terms of orthogonal projections onto periodic spaces

Dirk Nuyens, Yuya Suzuki

We introduce a new method to approximate integrals ∫ R d f ( x ) d x \int _{\mathbb {R}^d} f(\boldsymbol {x}) \,\mathrm {d}\boldsymbol {x} which simply scales lattice rules from the unit cube [ 0 , 1 ] d [0,1]^d to properly sized boxes on R d \mathbb {R}^d , hereby achieving higher-order convergence that matches the smoothness of the integrand function f f in a certain Sobolev space of dominating mixed smoothness. Our method only assumes that we can evaluate the integrand function f f and does not assume a particular density nor the ability to sample from it. In particular, for the theoretical analysis we show a new result that the method of adding Bernoulli polynomials to a function to make it “periodic” on a box without changing its integral value over the box is equivalent to an orthogonal projection from a well chosen Sobolev space of dominating mixed smoothness to an associated periodic Sobolev space of the same dominating mixed smoothness, which we call a Korobov space. We note that the Bernoulli polynomial method is often not used because of its excessive computational complexity and also here we only make use of it in our theoretical analysis. We show that our new method of applying scaled lattice rules to increasing boxes can be interpreted as orthogonal projections with decreasing projection error. Such a method would not work on the unit cube since then the committed error caused by non-periodicity of the integrand would be constant, but for integration on the Euclidean space we can use the certain decay towards zero when the boxes grow. Hence we can bound the truncation error as well as the projection error and show higher-order convergence in applying scaled lattice rules for integration on Euclidean space. We illustrate our theoretical analysis by numerical experiments which confirm our findings.

arXiv:2108.12639•Mathematics of Computation•May 11, 2022•14 citations

Accelerating convergence and tractability of multivariate integration for infinitely differentiable functions

Kosuke Suzuki

We investigate multivariate integration for a space of infinitely differentiable functions $ \mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1$ such that $e(n,s) \in O(q^{(\log{n})^{p}})$ holds as $n$ goes to infinity, where $e(n,s)$ may depend on $s$ in an arbitrary way. We prove that accelerating convergence holds for $p=2$ for any $\boldsymbol{u}$ and $s$ considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants $C>0$, $0 1$ independent of $s$ such that $e(n,s) \leq C q^{(\log{n})^{p}}$ holds for all $s$ and $n$. We prove that AC-ST holds if the weights $\boldsymbol{u}$ decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which $\mathcal{F}_{s, \boldsymbol{u}}$ is embedded.

•May 8, 2015•2 citations

Conjugate gradient algorithms for best rank‐1 approximation of tensors

O. Curtef, Gunther Dirr, Uwe Helmke

Abstract Motivated by considerations of pure state entanglement in quantum information, we consider the problem of finding the best rank‐1 approximation to an arbitrary r ‐th order tensor. Reformulating the problem as an optimization problem on the Lie group SU (n1) ⊗ … ⊗ SU (nr) of so‐called local unitary transformations and exploiting its intrinsic geometry yields a new approach, which finally leads to Riemannian variant of the conjugate gradient algorithm. Numerical simulations support that our method offers an alternative to the higher‐order power method for computing the best rank‐1 approximation to a tensor. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

PAMM•Dec 1, 2007•5 citations
We study multivariate numerical integration of smooth functions in weighted Sobolev spaces with dominating mixed smoothness α≥2\alpha\geq 2α≥2 defined over the sss-dimensional unit cube. We propose a new quasi-Monte Carlo (QMC)-based quadrature rule, named the extrapolated polynomial lattice rule, which achieves the almost optimal rate of convergence. Extrapolated polynomial lattice rules are constructed in two steps: (i) construction of classical polynomial lattice rules over Fb\Bbb{F}_bFb​ with α\alphaα consecutive sizes of nodes, bm−α+1,…,bmb^{m-\alpha+1},\ldots,b^{m}bm−α+1,…,bm, and (ii) recursive application of Richardson extrapolation to a chain of α\alphaα approximate values of the integral obtained by consecutive polynomial lattice rules. We prove the existence of good extrapolated polynomial lattice rules achieving the almost optimal order of convergence of the worst-case error in Sobolev spaces with general weights. Then, by restricting to product weights, we show that such good extrapolated polynomial lattice rules can be constructed by the fast component-by-component algorithm under a computable quality criterion. The required total construction cost is of order (s+α)Nlog⁡N(s+\alpha)N\log N(s+α)NlogN, which improves the currently known result for the interlaced polynomial lattice rule, which is of order sαNlog⁡Ns\alpha N\log NsαNlogN. We also study the dependence of the worst-case error bound on the dimension. A big advantage of our method compared to interlaced polynomial lattice rules is that the fast QMC matrix vector method can be used in this setting, while still achieving the same rate of convergence. Such a method was previously not known. Numerical experiments for test integrands support our theoretical result.
We study quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })
We introduce a new method to approximate integrals ∫ R d f ( x ) d x \int _{\mathbb {R}^d} f(\boldsymbol {x}) \,\mathrm {d}\boldsymbol {x} which simply scales lattice rules from the unit cube [ 0 , 1 ] d [0,1]^d to properly sized boxes on R d \mathbb {R}^d , hereby achieving higher-order convergence that matches the smoothness of the integrand function f f in a certain Sobolev space of dominating mixed smoothness. Our method only assumes that we can evaluate the integrand function f f and does not assume a particular density nor the ability to sample from it. In particular, for the theoretical analysis we show a new result that the method of adding Bernoulli polynomials to a function to make it “periodic” on a box without changing its integral value over the box is equivalent to an orthogonal projection from a well chosen Sobolev space of dominating mixed smoothness to an associated periodic Sobolev space of the same dominating mixed smoothness, which we call a Korobov space. We note that the Bernoulli polynomial method is often not used because of its excessive computational complexity and also here we only make use of it in our theoretical analysis. We show that our new method of applying scaled lattice rules to increasing boxes can be interpreted as orthogonal projections with decreasing projection error. Such a method would not work on the unit cube since then the committed error caused by non-periodicity of the integrand would be constant, but for integration on the Euclidean space we can use the certain decay towards zero when the boxes grow. Hence we can bound the truncation error as well as the projection error and show higher-order convergence in applying scaled lattice rules for integration on Euclidean space. We illustrate our theoretical analysis by numerical experiments which confirm our findings.
We investigate multivariate integration for a space of infinitely differentiable functions $ \mathcal{F}_{s, \boldsymbol{u}} := \{f \in C^\infty [0,1]^s \mid \| f \|_{\mathcal{F}_{s, \boldsymbol{u}} } := \sup_{(\alpha_1, \dots, \alpha_s) \in \mathbb{N}_0^s} \|f^{(\alpha_1, \dots, \alpha_s)}\|_{L^1}/\prod_{j=1}^s u_j^{\alpha_j} 1$ such that e(n,s)∈O(q(log⁡n)p)e(n,s) \in O(q^{(\log{n})^{p}})e(n,s)∈O(q(logn)p) holds as nnn goes to infinity, where e(n,s)e(n,s)e(n,s) may depend on sss in an arbitrary way. We prove that accelerating convergence holds for p=2p=2p=2 for any u\boldsymbol{u}u and sss considered. We also study a sufficient condition for accelerating convergence with strong tractability (AC-ST), which means that there exist constants C>0C>0C>0, 010 101 independent of sss such that e(n,s)≤Cq(log⁡n)pe(n,s) \leq C q^{(\log{n})^{p}}e(n,s)≤Cq(logn)p holds for all sss and nnn. We prove that AC-ST holds if the weights u\boldsymbol{u}u decay sufficiently fast. These results come from the convergence and tractability results for the Walsh space into which Fs,u\mathcal{F}_{s, \boldsymbol{u}}Fs,u​ is embedded.
Abstract Motivated by considerations of pure state entanglement in quantum information, we consider the problem of finding the best rank‐1 approximation to an arbitrary r ‐th order tensor. Reformulating the problem as an optimization problem on the Lie group SU (n1) ⊗ … ⊗ SU (nr) of so‐called local unitary transformations and exploiting its intrinsic geometry yields a new approach, which finally leads to Riemannian variant of the conjugate gradient algorithm. Numerical simulations support that our method offers an alternative to the higher‐order power method for computing the best rank‐1 approximation to a tensor. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)