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

Complexity and tractability of the heat equation

Arthur G. Werschulz

Published Jan 1, 2006• 1 citation
Publisher

Abstract

In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the heat equation ut = ∆u − qu in Id × (0,T), where I is the unit inter- val and T is a maximum time value. This problem is to be solved subject to homogeneous Dirichlet boundary conditions, along with the initial conditions u(·,0) = f over Id. The solution u depends linearly on f, but nonlinearly on q. Here, both f and q are d-variate functions from a reproducing kernel Hilbert space with finite-order weights of order ω. This means that, although d can be arbitrary large, f and q can be decomposed as sums of functions of at most ω variables, with ω independent of d. In this paper, we apply our previous general results to the heat equation. We study both the absolute and normalized error criteria. For either error criterion, we show that the problem is . That is, the number of evaluations of f and q needed to obtain an ε-approximation is polynomial in ε and d, with the degree of the polynomial depending linearly on ω. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in ε, independently of d. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in d and the integral of the univariate kernel is positive, then the heat equation is strongly tractable

DOI
10.7916/d8nk3nwf

Related papers

Tractability of multivariate approximation over a weighted unanchored Sobolev space: Smoothness sometimes hurts

Arthur G. Werschulz, Henryk Woźniakowski

We study d-variate approximation for a weighted unanchored Sobolev space having smoothness m ≥ 1. Folk wisdom would lead us to believe that this problem should become easier as its smoothness increases. This is true if we are only concerned with asymptotic analysis: the nth minimal error is of order n^-(m-δ) for any δ > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? We prove that no matter how the weights are chosen, the waiting period is at least m^d, even if the error demand ε is arbitrarily close to 1. Hence, for m ≥ 2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So, we will be unable to vanquish the curse of dimensionality unless m = 1 , i.e., unless the smoothness is minimal. We then show that our problem can be tractable if m = 1. That is, we can find an ε-approximation using polynomially-many (in d and ε^-1) information operations, even if only function values are permitted. When m = 1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε^-1) information operations, independent of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.

•Jan 1, 2008•1 citation

Tractability of Approximation for Weighted Korobov Spaces on Classical and Quantum Computers

Erich Novak, Ian H. Sloan, H. Woźniakowski

The paper studies quantum complexity, tractability, and strong tractability for high dimensional multivariate approximation. We study a space of functions important in many applications. A function space is weighted if certain variables are more important than others; the weights show the relative importance of the variables. In an unweighted space all variables are equally important and multivariate approximation is intractable. We want to study when the complexity of multivariate approximation is independent of the number of variables and depends polynomially on 1/E. The main conclusions are: Multivariate approximation on a quantum computer can be solved roughly (1/E)^(1+r) times faster than on a classical computer using randomization. Here, r is a positive parameter that depends on the weights and may be large. This means that the speed-up of quantum over classical computers may be much larger than quadratic. Multivariate approximation on a quantum computer is exponentially faster than on a classical computer with a worst case assurance even if the sum of weights is infinite but a certain power of them is finite. We have designed a quantum algorithm with error at most E that uses about d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and logarithmic dependence on 1/E. Therefore, for some applications the number of qubits is quite modest.

arXiv:quant-ph/0206023•Jun 4, 2002•0 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•56 citations

Tractability of multivariate analytic problems

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which $s$-variate problems can be approximated to within $\varepsilon$ by using, say, polynomially many in $s$ and $\varepsilon^{-1}$ function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with $\varepsilon^{-1}$ replaced by $1+\log \varepsilon^{-1}$. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of $s$ and $1+\log \varepsilon^{-1}$. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.

arXiv:1407.1615•De Gruyter eBooks•Jul 25, 2014•25 citations

Quasi-Monte Carlo tractability of integration problem in function spaces defined over products of balls

Jie Zhang, Yongping Liu

Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.

International Journal of Wavelets Multiresolution and Information Processing•May 12, 2019•3 citations

A note about EC-$(s,t)$-weak tractability of multivariate approximation with analytic Korobov kernels

Heping Wang

This note is devoted to discussing multivariate approximation of continuous functions on $[0,1]^d$ with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-$(s, t)$-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for $0<\min(s,t)<1$ and $\max(s,t)\le 1$ in the worst case setting and for $s,t>0$ in the average case setting.

arXiv:1808.01470•Aug 4, 2018•0 citations
In a previous paper, we developed a general framework for establishing tractability and strong tractability for quasilinear multivariate problems in the worst case setting. One important example of such a problem is the solution of the heat equation ut = ∆u − qu in Id × (0,T), where I is the unit inter- val and T is a maximum time value. This problem is to be solved subject to homogeneous Dirichlet boundary conditions, along with the initial conditions u(·,0) = f over Id. The solution u depends linearly on f, but nonlinearly on q. Here, both f and q are d-variate functions from a reproducing kernel Hilbert space with finite-order weights of order ω. This means that, although d can be arbitrary large, f and q can be decomposed as sums of functions of at most ω variables, with ω independent of d. In this paper, we apply our previous general results to the heat equation. We study both the absolute and normalized error criteria. For either error criterion, we show that the problem is . That is, the number of evaluations of f and q needed to obtain an ε-approximation is polynomial in ε and d, with the degree of the polynomial depending linearly on ω. In addition, we want to know when the problem is strongly tractable, meaning that the dependence is polynomial only in ε, independently of d. We show that if the sum of the weights defining the weighted reproducing kernel Hilbert space is uniformly bounded in d and the integral of the univariate kernel is positive, then the heat equation is strongly tractable
We study d-variate approximation for a weighted unanchored Sobolev space having smoothness m ≥ 1. Folk wisdom would lead us to believe that this problem should become easier as its smoothness increases. This is true if we are only concerned with asymptotic analysis: the nth minimal error is of order n^-(m-δ) for any δ > 0. However, it is unclear how long we need to wait before this asymptotic behavior kicks in. How does this waiting period depend on d and m? We prove that no matter how the weights are chosen, the waiting period is at least m^d, even if the error demand ε is arbitrarily close to 1. Hence, for m ≥ 2, this waiting period is exponential in d, so that the problem suffers from the curse of dimensionality and is intractable. In other words, the fact that the asymptotic behavior improves with m is irrelevant when d is large. So, we will be unable to vanquish the curse of dimensionality unless m = 1 , i.e., unless the smoothness is minimal. We then show that our problem can be tractable if m = 1. That is, we can find an ε-approximation using polynomially-many (in d and ε^-1) information operations, even if only function values are permitted. When m = 1, it is even possible for the problem to be strongly tractable, i.e., we can find an ε-approximation using polynomially-many (in ε^-1) information operations, independent of d. These positive results hold when the weights of the Sobolev space decay sufficiently quickly or are bounded finite-order weights, i.e., the d-variate functions we wish to approximate can be decomposed as sums of functions depending on at most ω variables, where ω is independent of d.
The paper studies quantum complexity, tractability, and strong tractability for high dimensional multivariate approximation. We study a space of functions important in many applications. A function space is weighted if certain variables are more important than others; the weights show the relative importance of the variables. In an unweighted space all variables are equally important and multivariate approximation is intractable. We want to study when the complexity of multivariate approximation is independent of the number of variables and depends polynomially on 1/E. The main conclusions are: Multivariate approximation on a quantum computer can be solved roughly (1/E)^(1+r) times faster than on a classical computer using randomization. Here, r is a positive parameter that depends on the weights and may be large. This means that the speed-up of quantum over classical computers may be much larger than quadratic. Multivariate approximation on a quantum computer is exponentially faster than on a classical computer with a worst case assurance even if the sum of weights is infinite but a certain power of them is finite. We have designed a quantum algorithm with error at most E that uses about d+log(1/E) qubits. Hence, we have only linear dependence on the dimension d and logarithmic dependence on 1/E. Therefore, for some applications the number of qubits is quite modest.
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 })
In the theory of tractability of multivariate problems one usually studies problems with finite smoothness. Then we want to know which sss-variate problems can be approximated to within ε\varepsilonε by using, say, polynomially many in sss and ε−1\varepsilon^{-1}ε−1 function values or arbitrary linear functionals. There is a recent stream of work for multivariate analytic problems for which we want to answer the usual tractability questions with ε−1\varepsilon^{-1}ε−1 replaced by 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. In this vein of research, multivariate integration and approximation have been studied over Korobov spaces with exponentially fast decaying Fourier coefficients. This is work of J. Dick, G. Larcher, and the authors. There is a natural need to analyze more general analytic problems defined over more general spaces and obtain tractability results in terms of sss and 1+log⁡ε−11+\log \varepsilon^{-1}1+logε−1. The goal of this paper is to survey the existing results, present some new results, and propose further questions for the study of tractability of multivariate analytic questions.
Recently, quasi-Monte Carlo (QMC) rules for multivariate integration in some weighted Sobolev spaces of functions defined over unit cubes [Formula: see text], products of [Formula: see text] copies of the simplex [Formula: see text] and products of [Formula: see text] copies of the unit sphere [Formula: see text] have been well-studied in the literature. In this paper, we consider QMC tractability of integrals of functions defined over product of [Formula: see text] copies of the ball [Formula: see text]. The space is a tensor product of [Formula: see text] reproducing kernel Hilbert spaces defined by positive and uniformly bounded weights [Formula: see text] for [Formula: see text]. We obtain matching necessary and sufficient conditions in terms of this weights for various notions of QMC tractability, including strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniformly weak tractability and [Formula: see text]-weak tractability.
A note about EC-(s,t)(s,t)(s,t)-weak tractability of multivariate approximation with analytic Korobov kernels
This note is devoted to discussing multivariate approximation of continuous functions on [0,1]d[0,1]^d[0,1]d with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-(s,t)(s, t)(s,t)-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for 0<min⁡(s,t)<10<\min(s,t)<10<min(s,t)<1 and max⁡(s,t)≤1\max(s,t)\le 1max(s,t)≤1 in the worst case setting and for s,t>0s,t>0s,t>0 in the average case setting.