Search

Abstract: Building upon a recent existence result of Kuo and Sloan, this paper presents a component-by-component algorithm for constructing the m points of a quasi-Monte Carlo (QMC) rule for numerical integration over the d-fold product of unit spheres . Our construction is as follows: starting with a well-chosen generating point set of m points on , the algorithm chooses a permutation of this generating point set for each sphere, one sphere at a time, so that the projection of the m QMC points onto each sphere is the same, and is just the generating point set but with the points occurring in a different order. Understandably, the quality of our QMC rule depends on the quality of both the generating point set and the successive permutations. This paper contains two key results. Firstly, assuming that the worst-case error for the generating point set in a certain Sobolev space satisfies a certain estimate, we prove inductively that the resulting QMC rule satisfies the existence result for the worst-case error bound in a d-dimensional weighted Sobolev space established non-constructively by Kuo and Sloan: specifically, the worst-case error of our QMC rule is bounded from above by , where is independent of m and d, provided that the sum of the weights is bounded independently of d. Secondly, we show that the desired estimate for the generating point set on is automatically satisfied for m sufficiently large by a spherical n-design with points (if such spherical designs exist) and by a spherical n-design with points if slightly stronger assumptions are made on the smoothness of the weighted function space. The latter task involves techniques developed by Hesse and Sloan for numerical integration in Sobolev spaces on . The construction cost for the component-by-component algorithm grows only linearly with d. However, a complete search over all permutations at each step of the construction is infeasible, thus a randomized version of the algorithm is recommended in practice. [Copyright &y& Elsevier]

We study numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions. [ABSTRACT FROM AUTHOR]

Abstract: Many methods to compute the winding number of plane curves have been proposed, often with the aim of counting the number of roots of polynomials (or, more generally, zeros of analytic functions) inside some region by using the principle of argument. In this paper we propose another method, which are not based on numerical integration, but on discrete geometry. We give conditions that ensure its correct behavior, and a complexity bound based on the distance of the curve to singular cases. Besides, we provide a modification of the algorithm that detects the proximity to a singular case of the curve. If this proximity is such that the number of operations required grows over certain threshold, set by the user, the modified algorithm returns without winding number computation, but with information about the distance to singular case. When the method is applied to polynomials, this information refers to the localization of the roots placed near the curve. [Copyright &y& Elsevier]

Abstract: Pricing a path-dependent financial derivative, such as an Asian option, requires the computation of , the expectation of a payoff function , that depends on a Brownian motion . Employing a standard series expansion of the latter problem is equivalent to the computation of the expectation of a function of the corresponding i.i.d. sequence of random coefficients. This motivates the construction and the analysis of algorithms for numerical integration with respect to a product probability measure on the sequence space . The class of integrands studied in this paper is the unit ball in a reproducing kernel Hilbert space obtained by superposition of weighted tensor product spaces of functions of finitely many variables. Combining tractability results for high-dimensional integration with the multi-level technique we obtain new algorithms for infinite-dimensional integration. These deterministic multi-level algorithms use variable subspace sampling and they are superior to any deterministic algorithm based on fixed subspace sampling with respect to the respective worst case error. [Copyright &y& Elsevier]

Abstract: The component-by-component construction algorithm constructs the generating vector for a rank-1 lattice one component at a time by minimizing the worst-case error in each step. This algorithm can be formulated elegantly as a repeated matrix-vector product, where the matrix-vector product expresses the calculation of the worst-case error in that step. As was shown in an earlier paper, this matrix-vector product can be done in time and with memory when the number of points n is prime. Here we extend this result to general n to obtain a total construction cost of and memory of for a rank-1 lattice in s dimensions with n points. We thus obtain the same big-Oh result as for n prime. As was the case for n prime, the main calculation cost is significantly reduced by using fast Fourier transforms in the matrix-vector calculation. The number of fast Fourier transforms is dependent on the number of divisors of n and the number of prime factors of n. It is believed that the intrinsic structure present in rank-1 lattices and exploited by this fast construction method will deliver new insights in the applicability of these lattices. [Copyright &y& Elsevier]

We study the multivariate Feynman–Kac path integration problem. This problem was studied in Plaskota et al. (J. Comp. Phys. 164 (2000) 335) for the univariate case. We describe an algorithm based on uniform approximation, instead of the L2-approximation used in Plaskota et al. (2000). Similarly to Plaskota et al. (2000), our algorithm requires extensive precomputing. We also present bounds on the complexity of our problem. The lower bound is provided by the complexity of a certain integration problem, and the upper bound by the complexity of the uniform approximation problem. The algorithm presented in this paper is almost optimal for the classes of functions for which uniform approximation and integration have roughly the same complexities. [Copyright &y& Elsevier]