Dynamic Programming in Futhark

My note Dynamic Programming in Futhark explains how to use the dpsolve library to solve numerical fixed-point problems and compute solutions to many problem instances in parallel on GPUs.

The solver starts with successive approximations, then switches to Newton’s method to converge more quickly. Through examples in one and several dimensions, the note shows how to set up these calculations in Futhark. Automatic differentiation can supply the Jacobian matrices needed by Newton’s method, saving the programmer from deriving and implementing those derivatives by hand.

The result is a practical introduction to combining numerical methods, automatic differentiation, and data-parallel execution. The examples begin with finding the intersection of a circle and a quadratic curve, making the solver’s behaviour easy to explore before moving to larger problems.

Read the note (PDF, September 27, 2025). An earlier version (PDF) is also available.