Source author record

Dirk Nuyens

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA Numerical Analysis q-fin.CP q-fin.TR

Catalog footprint

Research overview

18works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < α\le 1/2$

In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of $O(n^{-α-1/2+ε})$ , $ε> 0$ , for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness $α> 1/2$ . Compared to the optimal deterministic rate of $O(n^{-α+ε})$ , $ε> 0$ , such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of $0 < α\le 1/2$ . Also here we obtain the near optimal convergence of $O(n^{-α-1/2+ε})$ , $ε> 0$ ; or in more detail, we obtain $O(\sqrt{r} \, n^{-α-1/2+1/(2r)+ε'})$ which holds for any choices of $ε' > 0$ and $r \in \mathbb{N}$ with $r > 1/(2α)$ .

preprint2022arXiv

Constructing Embedded Lattice-based Algorithms for Multivariate Function Approximation with a Composite Number of Points

We approximate $d$ -variate periodic functions in weighted Korobov spaces with general weight parameters using $n$ function values at lattice points. We do not limit $n$ to be a prime number, as in currently available literature, but allow any number of points, including powers of $2$ , thus providing the fundamental theory for construction of embedded lattice sequences. Our results are constructive in that we provide a component-by-component algorithm which constructs a suitable generating vector for a given number of points or even a range of numbers of points. It does so without needing to construct the index set on which the functions will be represented. The resulting generating vector can then be used to approximate functions in the underlying weighted Korobov space. We analyse the approximation error in the worst-case setting under both the $L_2$ and $L_{\infty}$ norms. Our component-by-component construction under the $L_2$ norm achieves the best possible rate of convergence for lattice-based algorithms, and the theory can be applied to lattice-based kernel methods and splines. Depending on the value of the smoothness parameter $α$ , we propose two variants of the search criterion in the construction under the $L_{\infty}$ norm, extending previous results which hold only for product-type weight parameters and prime $n$ . We also provide a theoretical upper bound showing that embedded lattice sequences are essentially as good as lattice rules with a fixed value of $n$ . Under some standard assumptions on the weight parameters, the worst-case error bound is independent of $d$ .

preprint2020arXiv

Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

Lattice rules are among the most prominently studied quasi-Monte Carlo methods to approximate multivariate integrals. A rank-1 lattice rule to approximate an $s$ -dimensional integral is fully specified by its generating vector $\mathbf{z} \in \mathbb{Z}^s$ and its number of points $N$ . While there are many results on the existence of "good" rank-1 lattice rules, there are no explicit constructions for good generating vectors for dimensions $s \ge 3$ . This is why one usually resorts to computer search algorithms. Motivated by earlier work of Korobov from 1963 and 1982, we present two variants of search algorithms for good lattice rules and show that the resulting rules exhibit a convergence rate in weighted function spaces that can be arbitrarily close to the optimal rate. Moreover, contrary to most other algorithms, we do not need to know the smoothness of our integrands in advance, the generating vector will still recover the convergence rate associated with the smoothness of the particular integrand, and, under appropriate conditions on the weights, the error bounds can be stated without dependence on $s$ . The search algorithms presented in this paper are two variants of the well-known component-by-component (CBC) construction, one of which is combined with a digit-by-digit (DBD) construction. We present numerical results for both algorithms using fast construction algorithms in the case of product weights. They confirm our theoretical findings.

preprint2020arXiv

Function integration, reconstruction and approximation using rank-1 lattices

We consider rank-1 lattices for integration and reconstruction of functions with series expansion supported on a finite index set. We explore the connection between the periodic Fourier space and the non-periodic cosine space and Chebyshev space, via tent transform and then cosine transform, to transfer known results from the periodic setting into new insights for the non-periodic settings. Fast discrete cosine transform can be applied for the reconstruction phase. To reduce the size of the auxiliary index set in the associated component-by-component (CBC) construction for the lattice generating vectors, we work with a bi-orthonormal set of basis functions, leading to three methods for function reconstruction in the non-periodic settings. We provide new theory and efficient algorithmic strategies for the CBC construction. We also interpret our results in the context of general function approximation and discrete least-squares approximation.

preprint2020arXiv

Strang splitting in combination with rank- $1$ and rank- $r$ lattices for the time-dependent Schrödinger equation

We approximate the solution for the time dependent Schrödinger equation (TDSE) in two steps. We first use a pseudo-spectral collocation method that uses samples of functions on rank-1 or rank-r lattice points with unitary Fourier transforms. We then get a system of ordinary differential equations in time, which we solve approximately by stepping in time using the Strang splitting method. We prove that the numerical scheme proposed converges quadratically with respect to the time step size, given that the potential is in a Korobov space with the smoothness parameter greater than $9/2$ . Particularly, we prove that the required degree of smoothness is independent of the dimension of the problem. We demonstrate our new method by comparing with results using sparse grids from [12], with several numerical examples showing large advantage for our new method and pushing the examples to higher dimensionality. The proposed method has two distinctive features from a numerical perspective: (i) numerical results show the error convergence of time discretization is consistent even for higher-dimensional problems; (ii) by using the rank- $1$ lattice points, the solution can be efficiently computed (and further time stepped) using only $1$ -dimensional Fast Fourier Transforms.

preprint2017arXiv

The analysis of vertex modified lattice rules in a non-periodic Sobolev space

In a series of papers, in 1993, 1994 & 1996, Sloan & Niederreiter introduced a modification of lattice rules for non-periodic functions, called "vertex modified lattice rules"', and a particular breed called "optimal vertex modified lattice rules". In the 1994 paper, Niederreiter & Sloan concentrate explicitly on Fibonacci lattice rules, which are a particular good choice of 2-dimensional lattice rules. Error bounds in this series of papers were given related to the star discrepancy. In this paper we pose the problem in terms of the so-called unanchored Sobolev space, which is a reproducing kernel Hilbert space often studied nowadays in which functions have $L_2$ -integrable mixed first derivatives. It is known constructively that randomly shifted lattice rules, as well as deterministic tent-transformed lattice rules and deterministic fully symmetrized lattice rules can achieve close to $O(N^{-1})$ convergence in this space, see Sloan, Kuo & Joe (2002) and Dick, Nuyens & Pillichshammer (2014) respectively. We derive a break down of the worst-case error of vertex modified lattice rules in the unanchored Sobolev space in terms of the worst-case error in a Korobov space, a multilinear space and some additional "mixture term". For the 1-dimensional case this worst-case error is obvious and gives an explicit expression for the trapezoidal rule. In the 2-dimensional case this mixture term also takes on an explicit form for which we derive upper and lower bounds. For this case we prove that there exist lattice rules with a nice worst-case error bound with the additional mixture term of the form $N^{-1} \log^2(N)$ .

preprint2016arXiv

Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients - a survey of analysis and implementation

This article provides a survey of recent research efforts on the application of quasi-Monte Carlo (QMC) methods to elliptic partial differential equations (PDEs) with random diffusion coefficients. It considers, and contrasts, the uniform case versus the lognormal case, single-level algorithms versus multi-level algorithms, first order QMC rules versus higher order QMC rules, and deterministic QMC methods versus randomized QMC methods. It gives a summary of the error analysis and proof techniques in a unified view, and provides a practical guide to the software for constructing and generating QMC points tailored to the PDE problems. The analysis for the uniform case can be generalized to cover a range of affine parametric operator equations.

preprint2016arXiv

Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions

We study multivariate integration of functions that are invariant under the permutation (of a subset) of their arguments. Recently, in Nuyens, Suryanarayana, and Weimar (Adv. Comput. Math. (2016), 42(1):55--84), the authors derived an upper estimate for the $n$ th minimal worst case error for such problems, and showed that under certain conditions this upper bound only weakly depends on the dimension. We extend these results by proposing two (semi-) explicit construction schemes. We develop a component-by-component algorithm to find the generating vector for a shifted rank- $1$ lattice rule that obtains a rate of convergence arbitrarily close to $\mathcal{O}(n^{-α})$ , where $α>1/2$ denotes the smoothness of our function space and $n$ is the number of cubature nodes. Further, we develop a semi-constructive algorithm that builds on point sets which can be used to approximate the integrands of interest with a small error; the cubature error is then bounded by the error of approximation. Here the same rate of convergence is achieved while the dependence of the error bounds on the dimension $d$ is significantly improved.

preprint2016arXiv

Infinite-dimensional integration and the multivariate decomposition method

We further develop the \emph{Multivariate Decomposition Method} (MDM) for the Lebesgue integration of functions of infinitely many variables $x_1,x_2,x_3,\ldots$ with respect to a corresponding product of a one dimensional probability measure. Although a number of concepts of infinite-dimensional integrals have been used in the literature, questions of uniqueness and compatibility have mostly not been studied. We show that, under appropriate convergence conditions, the Lebesgue integral equals the `anchored' integral, independently of the anchor. The MDM assumes that point values of $f_{\mathfrak{u}}$ are available for important subsets ${\mathfrak{u}}$ , at some known cost. In this paper we introduce a new setting, in which it is assumed that each $f_{\mathfrak{u}}$ belongs to a normed space $F_{\mathfrak{u}}$ , and that bounds $B_{\mathfrak{u}}$ on $\|f_{\mathfrak{u}}\|_{F_{\mathfrak{u}}}$ are known. This contrasts with the assumption in many papers that weights $γ_{\mathfrak{u}}$ , appearing in the norm of the infinite-dimensional function space, are somehow known. Often such weights $γ_{\mathfrak{u}}$ were determined by minimizing an error bound depending on the $B_{\mathfrak{u}}$ , the $γ_{\mathfrak{u}}$ \emph{and} the chosen algorithm, resulting in weights that depend on the algorithm. In contrast, in this paper only the bounds $B_{\mathfrak{u}}$ are assumed known. We give two examples in which we specialize the MDM: in the first case $F_{\mathfrak{u}}$ is the $|{\mathfrak{u}}|$ -fold tensor product of an anchored reproducing kernel Hilbert space, and in the second case it is a particular non-Hilbert space for integration over an unbounded domain.

preprint2016arXiv

Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions

We develop algorithms for multivariate integration and approximation in the weighted half-period cosine space of smooth non-periodic functions. We use specially constructed tent-transformed rank-1 lattice points as cubature nodes for integration and as sampling points for approximation. For both integration and approximation, we study the connection between the worst-case errors of our algorithms in the cosine space and the worst-case errors of some related algorithms in the well-known weighted Korobov space of smooth periodic functions. By exploiting this connection, we are able to obtain constructive worst-case error bounds with good convergence rates for the cosine space.

preprint2015arXiv

Higher order QMC Galerkin discretization for parametric operator equations

We construct quasi-Monte Carlo methods to approximate the expected values of linear functionals of Galerkin discretizations of parametric operator equations which depend on a possibly infinite sequence of parameters. Such problems arise in the numerical solution of differential and integral equations with random field inputs. We analyze the regularity of the solutions with respect to the parameters in terms of the rate of decay of the fluctuations of the input field. If $p\in (0,1]$ denotes the "summability exponent" corresponding to the fluctuations in affine-parametric families of operators, then we prove that deterministic "interlaced polynomial lattice rules" of order $α= \lfloor 1/p \rfloor+1$ in $s$ dimensions with $N$ points can be constructed using a fast component-by-component algorithm, in $\mathcal{O}(α\,s\, N\log N + α^2\,s^2 N)$ operations, to achieve a convergence rate of $\mathcal{O}(N^{-1/p})$ , with the implied constant independent of $s$ . This dimension-independent convergence rate is superior to the rate $\mathcal{O}(N^{-1/p+1/2})$ , for $2/3\leq p\leq 1$ recently established for randomly shifted lattice rules under comparable assumptions. In our analysis we use a non-standard Banach space setting and introduce "smoothness-driven product and order dependent (SPOD)" weights for which we show fast CBC construction.

preprint2015arXiv

Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability

We study multivariate integration of functions that are invariant under permutations (of subsets) of their arguments. We find an upper bound for the $n$ th minimal worst case error and show that under certain conditions, it can be bounded independent of the number of dimensions. In particular, we study the application of unshifted and randomly shifted rank- $1$ lattice rules in such a problem setting. We derive conditions under which multivariate integration is polynomially or strongly polynomially tractable with the Monte Carlo rate of convergence $O(n^{-1/2})$ . Furthermore, we prove that those tractability results can be achieved with shifted lattice rules and that the shifts are indeed necessary. Finally, we show the existence of rank- $1$ lattice rules whose worst case error on the permutation- and shift-invariant spaces converge with (almost) optimal rate. That is, we derive error bounds of the form $O(n^{-λ/2})$ for all $1 \leq λ< 2 α$ , where $α$ denotes the smoothness of the spaces. Keywords: Numerical integration, Quadrature, Cubature, Quasi-Monte Carlo methods, Rank-1 lattice rules.

preprint2013arXiv

A Monte Carlo method for optimal portfolio executions

Traders are often faced with large block orders in markets with limited liquidity and varying volatility. Executing the entire order at once usually incurs a large trading cost because of this limited liquidity. In order to minimize this cost traders split up large orders over time. Varying volatility however implies that they now take on price risk, as the underlying assets' prices can move against the traders over the execution period. This execution problem therefore requires a careful balancing between trading slow to reduce liquidity cost and trading fast to reduce the volatility cost. R. Almgren solved this problem for a market with one asset and stochastic liquidity and volatility parameters, using a mean-variance framework. This leads to a nonlinear PDE that needs to be solved numerically. We propose a different approach using (quasi-)Monte Carlo which can handle any number of assets. Furthermore, our method can be run in real-time and allows the trader to change the parameters of the underlying stochastic processes on-the-fly.

preprint2013arXiv

The construction of good lattice rules and polynomial lattice rules

A comprehensive overview of lattice rules and polynomial lattice rules is given for function spaces based on $\ell_p$ semi-norms. Good lattice rules and polynomial lattice rules are defined as those obtaining worst-case errors bounded by the optimal rate of convergence for the function space. The focus is on algebraic rates of convergence $O(N^{-α+ε})$ for $α\ge 1$ and any $ε> 0$ , where $α$ is the decay of a series representation of the integrand function. The dependence of the implied constant on the dimension can be controlled by weights which determine the influence of the different dimensions. Different types of weights are discussed. The construction of good lattice rules, and polynomial lattice rules, can be done using the same method for all $1 < p \le \infty$ ; but the case $p=1$ is special from the construction point of view. For $1 < p \le \infty$ the component-by-component construction and its fast algorithm for different weighted function spaces is then discussed.

preprint2012arXiv

Conditional sampling for barrier option pricing under the Heston model

We propose a quasi-Monte Carlo algorithm for pricing knock-out and knock-in barrier options under the Heston (1993) stochastic volatility model. This is done by modifying the LT method from Imai and Tan (2006) for the Heston model such that the first uniform variable does not influence the stochastic volatility path and then conditionally modifying its marginals to fulfill the barrier condition(s). We show this method is unbiased and never does worse than the unconditional algorithm. Additionally the conditioning is combined with a root finding method to also force positive payouts. The effectiveness of this method is shown by extensive numerical results.

preprint2012arXiv

Conditional sampling for barrier option pricing under the LT method

We develop a conditional sampling scheme for pricing knock-out barrier options under the Linear Transformations (LT) algorithm from Imai and Tan (2006). We compare our new method to an existing conditional Monte Carlo scheme from Glasserman and Staum (2001), and show that a substantial variance reduction is achieved. We extend the method to allow pricing knock-in barrier options and introduce a root-finding method to obtain a further variance reduction. The effectiveness of the new method is supported by numerical results.

preprint2012arXiv

Lattice rules for nonperiodic smooth integrands

The aim of this paper is to show that one can achieve convergence rates of $N^{-α+ δ}$ for $α> 1/2$ (and for $δ> 0$ arbitrarily small) for nonperiodic $α$ -smooth cosine series using lattice rules without random shifting. The smoothness of the functions can be measured by the decay rate of the cosine coefficients. For a specific choice of the parameters the cosine series space coincides with the unanchored Sobolev space of smoothness 1. We study the embeddings of various reproducing kernel Hilbert spaces and numerical integration in the cosine series function space and show that by applying the so-called tent transformation to a lattice rule one can achieve the (almost) optimal rate of convergence of the integration error. The same holds true for symmetrized lattice rules for the tensor product of the direct sum of the Korobov space and cosine series space, but with a stronger dependence on the dimension in this case.

preprint2011arXiv

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

We show how to obtain a fast component-by-component construction algorithm for higher order polynomial lattice rules. Such rules are useful for multivariate quadrature of high-dimensional smooth functions over the unit cube as they achieve the near optimal order of convergence. The main problem addressed in this paper is to find an efficient way of computing the worst-case error. A general algorithm is presented and explicit expressions for base~2 are given. To obtain an efficient component-by-component construction algorithm we exploit the structure of the underlying cyclic group. We compare our new higher order multivariate quadrature rules to existing quadrature rules based on higher order digital nets by computing their worst-case error. These numerical results show that the higher order polynomial lattice rules improve upon the known constructions of quasi-Monte Carlo rules based on higher order digital nets.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Dirk Nuyens

Research overview

Is this your work?

18 publications

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < α\le 1/2$

Constructing Embedded Lattice-based Algorithms for Multivariate Function Approximation with a Composite Number of Points

Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

Function integration, reconstruction and approximation using rank-1 lattices

Strang splitting in combination with rank- $1$ and rank- $r$ lattices for the time-dependent Schrödinger equation

The analysis of vertex modified lattice rules in a non-periodic Sobolev space

Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients - a survey of analysis and implementation

Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions

Infinite-dimensional integration and the multivariate decomposition method

Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions

Higher order QMC Galerkin discretization for parametric operator equations

Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability

A Monte Carlo method for optimal portfolio executions

The construction of good lattice rules and polynomial lattice rules

Conditional sampling for barrier option pricing under the Heston model

Conditional sampling for barrier option pricing under the LT method

Lattice rules for nonperiodic smooth integrands

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

See the researcher in context

Building this map preview

Dirk Nuyens

Research overview

Is this your work?

18 publications

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/20 < α\le 1/20<α≤1/2

Constructing Embedded Lattice-based Algorithms for Multivariate Function Approximation with a Composite Number of Points

Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness

Function integration, reconstruction and approximation using rank-1 lattices

Strang splitting in combination with rank-111 and rank-rrr lattices for the time-dependent Schrödinger equation

The analysis of vertex modified lattice rules in a non-periodic Sobolev space

Application of quasi-Monte Carlo methods to elliptic PDEs with random diffusion coefficients - a survey of analysis and implementation

Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions

Infinite-dimensional integration and the multivariate decomposition method

Tent-transformed lattice rules for integration and approximation of multivariate non-periodic functions

Higher order QMC Galerkin discretization for parametric operator equations

Rank-1 lattice rules for multivariate integration in spaces of permutation-invariant functions: Error bounds and tractability

A Monte Carlo method for optimal portfolio executions

The construction of good lattice rules and polynomial lattice rules

Conditional sampling for barrier option pricing under the Heston model

Conditional sampling for barrier option pricing under the LT method

Lattice rules for nonperiodic smooth integrands

Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules

See the researcher in context

Building this map preview

A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with $0 < α\le 1/2$

Strang splitting in combination with rank- $1$ and rank- $r$ lattices for the time-dependent Schrödinger equation