This thesis extends the utility of the Monte Carlo approach to PDE-based methods presented in the paper Monte Carlo Geometry Processing. In particular, we implement this method on the GPU using CUDA, and investigate more viable methods of estimating the source integral when solving Poisson’s equation with intricate source terms. This is the case for a large group of gradient-domain methods in computer graphics, where source terms are represented by discrete volumetric data on regular grids. We develop unbiased source integral estimators like image-based importance sampling (IBIS) and biased estimators like source integral caching (SIC) and evaluate these against existing GPU-accelerated finite difference solvers for gradient-domain applications. By decoupling the source integration step from the WoS-algorithm, we find that the SIC method can improve performance by several orders of magnitude, making it competitive with existing finite difference solvers in many cases. We further investigate the viability of distance fields for accelerated distance queries and find that these can provide significant performance improvements compared to BVHs without meaningfully affecting bias. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

Cette thèse porte sur le développement de méthodes de Monte-Carlo pour calculer des représentations Feynman-Kac impliquant des opérateurs sous forme divergence avec un coefficient de diffusion constant par morceaux. Les méthodes proposées sont des variantes de la marche sur les sphères à l'intérieur des zones avec un coefficient de diffusion constant et des techniques de différences finies stochastiques pour traiter les conditions aux interfaces aussi bien que les conditions aux limites de différents types. En combinant ces deux techniques, on obtient des marches aléatoires dont le score calculé le long du chemin fourni un estimateur biaisé de la solution de l'équation aux dérivées partielles considérée. On montre que le biais global de notre algorithme est en général d'ordre deux par rapport au pas de différences finies. Ces méthodes sont ensuite appliquées au problème direct lié à la tomographie par impédance électrique pour la détection de tumeurs. Une technique de réduction de variance est également proposée dans ce cadre. On traite finalement du problème inverse de la détection de tumeurs à partir de mesures de surfaces à l'aide de deux algorithmes stochastiques basés sur une représentation paramétrique de la tumeur ou des tumeurs sous forme d'une ou plusieurs sphères. De nombreux essais numériques sont proposés et montrent des résultats probants dans la localisation des tumeurs. / This thesis deals with the development of Monte-Carlo methods to compute Feynman-Kac representations involving divergence form operators with a piecewise constant diffusion coefficient. The proposed methods are variations around the walk on spheres method inside the regions with a constant diffusion coefficient and stochastic finite differences techniques to treat the interface conditions as well as the different kinds of boundary conditions. By combining these two techniques, we build random walks which score computed along the walk gives us a biased estimator of the solution of the partial differential equation we consider. We prove that the global bias is in general of order two with respect to the finite difference step. These methods are then applied for tumour detection to the forward problem in electrical impedance tomography. A variance reduction technique is also proposed in this case. Finally, we treat the inverse problem of tumours detection from surface measurements using two stochastics algorithms based on a spherical parametric representation of the tumours. Many numerical tests are proposed and show convincing results in the localization of the tumours.