Quasi-Monte Carlo Methods in Moderate Dimensions: Chebyshev Lattices, Numerical Integration and Particle Filters (Quasi-Monte Carlo technieken in matige dimensies: Chebyshev roosterregels, numerieke integratie en deeltjesfilters)
Quasi-Monte Carlo Methods in Moderate Dimensions: Chebyshev Lattices, Numerical Integration and Particle Filters
Poppe, Koen; S0107499
In the first part, we detail our attempts to improve the particle filter performance by replacing pseudo-random numbers by quasi-random point sets. It is known from quasi-Monte Carlo techniques that these point sets provide a better rate of convergence in the context of numerical integration, however, our experiments did not reveal the same superiority. We extend the Kullback-Leibler divergence to the weighted particle sets that are typically used in particle filters. This did not meet our criteria for a quality measure and so the error on the weighted average has been used. The experiments rely on the BFL library, that has been extended with an object-oriented design for quasi-random point sets in the course of this research.The second part presents the Chebyshev lattice rules as generalising framework for cubature with Chebyshev weight function and shows how most of the well known point sets in this context fit in the framework. We then developed exhaustive computer searches for good Chebyshev lattice rules. This provided evidence that the blending formulae due to Godzina are the best, i.e., require the lowest number of function evaluations needed to ensure exactness for polynomials up to a certain total degree. Based on hyperinterpolation theory, these Chebyshev lattice rules can be used to approximate multivariate functions by means of a sum of Chebyshev polynomials. For rank-1 Chebyshev lattices and Godzina's blending formulae, we developed efficient approximation algorithms that benefit from the fast Fourier transform (FFT) by reformulating the approximation as discrete cosine transforms. All this is combined into CHEBINT, an end-user-friendly MATLAB/Octave toolbox, which also provides semi-numerical manipulations of Chebyshev approximations.A third part focusses on software: after an exercise to create an error handling paradigm for Fortran 2003 that is suitable for numerical and scientific software, we detail the developments in the context of CUBPACK. This includes the translation of the original package for automatic integration to native MATLAB/Octave code, the extension of the package with quasi-Monte Carlo methods based on software written in the context of previous PhD's and the transition of certain features to Fortran 2003.