Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSuper-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
86
0
0.0
(
0
)
Authors
Kosuke Suzuki
Ask ChatGPT about the research
No Arabic abstract
We investigate multivariate integration for a space of infinitely times differentiable functions $mathcal{F}_{s, boldsymbol{u}} := {f in C^infty [0,1]^s mid | f |_{mathcal{F}_{s, boldsymbol{u}}} < infty }$, where $| f |_{mathcal{F}_{s, boldsymbol{u}}} := sup_{boldsymbol{alpha} = (alpha_1, dots, alpha_s) in mathbb{N}_0^s} |f^{(boldsymbol{alpha})}|_{L^1}/prod_{j=1}^s u_j^{alpha_j}$, $f^{(boldsymbol{alpha})} := frac{partial^{|boldsymbol{alpha}|}}{partial x_1^{alpha_1} cdots partial x_s^{alpha_s}}f$ and $boldsymbol{u} = {u_j}_{j geq 1}$ is a sequence of positive decreasing weights. Let $e(n,s)$ be the minimal worst-case error of all algorithms that use $n$ function values in the $s$-variate case. We prove that for any $boldsymbol{u}$ and $s$ considered $e(n,s) leq C(s) exp(-c(s)(log{n})^2)$ holds for all $n$, where $C(s)$ and $c(s)$ are constants which may depend on $s$. Further we show that if the weights $boldsymbol{u}$ decay sufficiently fast then there exist some $1 < p < 2$ and absolute constants $C$ and $c$ such that $e(n,s) leq C exp(-c(log{n})^p)$ holds for all $s$ and $n$. These bounds are attained by quasi-Monte Carlo integration using digital nets. These convergence and tractability results come from those for the Walsh space into which $mathcal{F}_{s, boldsymbol{u}}$ is embedded.
rate research
Read More
This article studies the problem of approximating functions belonging to a Hilbert space $H_d$ with an isotropic or anisotropic Gaussian reproducing kernel, $$ K_d(bx,bt) = expleft(-sum_{ell=1}^dgamma_ell^2(x_ell-t_ell)^2right) mbox{for all} bx,btinreals^d. $$ The isotropic case corresponds to using the same shape parameters for all coordinates, namely $gamma_ell=gamma>0$ for all $ell$, whereas the anisotropic case corresponds to varying shape parameters $gamma_ell$. We are especially interested in moderate to large $d$.
We consider approximation problems for a special space of d variate functions. We show that the problems have small number of active variables, as it has been postulated in the past using concentration of measure arguments. We also show that, depending on the norm for measuring the error, the problems are strongly polynomially or quasi-polynomially tractable even in the model of computation where functional evaluations have the cost exponential in the number of active variables.
In this paper, we study how to quickly compute the <-minimal monomial interpolating basis for a multivariate polynomial interpolation problem. We address the notion of reverse reduced basis of linearly independent polynomials and design an algorithm for it. Based on the notion, for any monomial ordering we present a new method to read off the <-minimal monomial interpolating basis from monomials appearing in the polynomials representing the interpolation conditions.
We present an optimized algorithm calculating determinant for multivariate polynomial matrix on GPU. The novel algorithm provides precise determinant for input multivariate polynomial matrix in controllable time. Our approach is based on modular methods and split into Fast Fourier Transformation, Condensation method and Chinese Remainder Theorem where each algorithm is paralleled on GPU. The experiment results show that our parallel method owns substantial speedups compared to Maple, allowing memory overhead and time expedition in steady increment. We are also able to deal with complex matrix which is over the threshold on Maple and constrained on CPU. In addition, calculation during the process could be recovered without losing accuracy at any point regardless of disruptions. Furthermore, we propose a time prediction for calculation of polynomial determinant according to some basic matrix attributes and we solve an open problem relating to harmonic elimination equations on the basis of our GPU implementation.
For $m,n in mathbb{N}$, $mgeq 1$ and a given function $f : mathbb{R}^mlongrightarrow mathbb{R}$ the polynomial interpolation problem (PIP) is to determine a emph{generic node set} $P subseteq mathbb{R}^m$ and the coefficients of the uniquely defined polynomial $Qinmathbb{R}[x_1,dots,x_m]$ in $m$ variables of degree $mathrm{deg}(Q)leq n in mathbb{N}$ that fits $f$ on $P$, i.e., $Q(p) = f(p)$, $forall, p in P$. We here show that in general, i.e., for arbitrary $m,n in mathbb{N}$, $m geq 1$, there exists an algorithm that determines $P$ and computes the $N(mbox{m,n})=#P$ coefficients of $Q$ in $mathcal{O}big(N(mbox{m,n})^2big)$ time using $mathcal{O}big(mbox{m}N(mbox{m,n})big)$ storage, without inverting the occurring Vandermonde matrix. We provide such an algorithm, termed PIP-SOLVER, based on a recursive decomposition of the problem and prove its correctness. Since the present approach solves the PIP without matrix inversion, it is computationally more efficient and numerically more robust than previous approaches. We demonstrate this in numerical experiments and compare with previous approaches based on matrix inversion and linear systems solving.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
