Justus Sagemüller: Representing Continuous Functions with Lazy Infinite Data Structures – Dos and Don'ts

Abstract.

Continuous functions are ubiquitous in applications of computational mathematics.
Yet the continuity is most commonly not explicitly exploited in the implementations, though that would have potential for both convergence guarantees and more efficient discretization.
Simplistic ε-δ approaches to this (and more broadly, interval arithmetic techniques) are useful for analysing the robustness of existing algorithms. They have however only limited / highly inefficient capability of guiding discretization, because any change in requested result-precision would require a complete recomputation.

In this talk I examine use of lazy evaluation to, instead of recomputing new finite discretizations, retain a single infinite tree data structure that represents conceptually exact discretization of a function between compact spaces.
The aim is being able to add, compose etc. those representations, ideally forming a cartesian monoidal category of them.
I discuss challenges with doing this in a relatively straightforward way inspired by adaptive-resolution numerical schemes.
As a solution, I propose nested preimages of recursively split parts of the codomain, implemented as a combination of primitive diffeomorphic deformations and tree splitting.
Various choices of primitives are compared in a prototype implementation for the 1D and 2D cases.