Laplacian Occasion

Inspiration

It turns out you can solve Laplace's equation and other partial differential equations by sampling random walks!

Physicists use finite difference methods or finite element methods to solve many PDEs they encounter computationally. However, there are some problems that arise with these methods. First of all, they both require construcing grids. This has some down-sides

Working with meshes is hard. Meshes in the wild can come with a host of problems (singularities, self-intersecting faces, and all sorts of horible stuff)
The FEM/FDM solution does not always converge as fast as we would like it to. I.e. very fine meshes are required to obtain decent results.
Constructing meshes is computationally expensive and can take hours.

Enter Monte Carlo methods. (Monte Carlo is just a fancy name for statistical sampling. For instance, the way to measure the area of a circle with monte carlo is to drop many many tiny pins onto a square of known dimensions bounding the circle, and then count the ratio of pins that fall inside the circle vs the ones that fall in the square but outside the circle.)

The solver we are interested in is called the Walk-On-Spheres algorithm. It's a Monte Carlo algorithm that uses random walks and exploits the mean value property of the Laplace equation. It's been known about for some time, but recently researchers have been trying to generalise it to other problems.

Another type of solver inspired by ray-tracing algorithms, from the graphics industry, may be able to help scientists solve PDEs more efficiently. These are Monte Carlo methods.

What it does

Solves and beautifully display's Laplace's equation for a Dirichelet BVP computation using the mesh-free random walk-on spheres algorithm.

How we built it

You draw a line on a canvas, which drops some pixels on the screens. We simplify this curve and turn it into a spline with fewer points. This reduces the computation of the min distances from points in the domain to the boundary.

We used three.js to render it in real-time.

Challenges we ran into

User interface. Getting the 3d thing to render.

Optimizing the algorithm so that it would run fast enough to render in real-time. Even though this is an educational project, we still had to make optimizations.