Domain Theory, Computational Geometry and Differential Calculus (A short course)
by
Abbas Edalat
Department of Computing, Imperial College London

Domain theory is a mathematical theory of computation, which was originally developed in the late 1960's to model the semantics of programming languages, but later found applications in mainstream mathematical computation. A domain is a structure for modeling a computational process or a data type with incompletely specified elements. It is a partially ordered set, where every directed subset has a supremum and it is equipped with the notions of finitary approximation (or way-below relation) and a basis. Every element of the domain can be expressed as the supremum of basis elements way-below it; these basis elements are considered as approximations to the element. The set of all non-empty compact subsets of the real line ordered by reverse inclusion is a simple example of a domain and it gives a data-type for real numbers: every real number can be obtained as the supremum of an increasing sequence of compact intervals with rational endpoints.

We present a domain-theoretic synthesis of two major paradigms of modern science and technology: Differential Calculus and Computer Science. Initially we treat functions of a real variable. We extend the notions of the indefinite integral and the derivative to interval-valued functions of a real variable and obtain a domain-theoretic generalization of the Fundamental Theorem of Calculus. The domain-theoretic derivative (for locally Lipschitz functions) coincides with Clarke's gradient. Then a domain for continuously differentiable functions is constructed as a subset of the product of two copies of the function space of the real line with the interval domain. It is composed of consistent pairs of functions, each pair providing a function approximation and a derivative approximation for a classical continuously differentiable function. Consistency is shown to be decidable, with a linear time algorithm, on the pairs of basis elements of the function space. The set of continuously differentiable functions with their sup norm is embedded into the set of maximal elements of this domain.

A similar domain can be constructed for Cⁿ functions for n > 1. Currently there is an exponential algorithm to check consistency for the C² domain, but decidability of consistency for n > 2 is an open question.

Having considered functions of a single real variable, we embark on extending all our results to multivariable calculus. We obtain a Fundamental Theorem of Calculus for functions of several variables, where in the simplest model the domain-theoretic derivative gives the smallest hyper-rectangle containing Clarke's gradient. The main result here is to show, in two stages, that consistency is decidable on basis elements. First, a domain-theoretic notion of line integral is used to extend Green's theorem to interval-valued vector fields and show that integrability of the derivative information is decidable. Then, we use techniques from the theory of minimal surfaces to construct the least and the greatest piecewise linear functions that can be obtained from a tuple of n+1 rational step functions, assuming the integrability of the n-tuple of the derivative part. This provides an algorithm to check consistency on the rational basis elements of the domain, giving an effective framework for multi-variable differential calculus. The question of decidability of consistency for domains for multivariable Cⁿ functions (n > 1) is open.

We then present a domain-theoretic framework for solving differential equations. Given a continuous vector field, uniformly Lipschitz in the space component, and an initial value, a domain-theoretic generalization of the classical Picard operator is defined on the function space of the interval domain. This operator successively updates the function approximation and the derivative approximation to produce better and better refined approximations to the solution of the differential equations, enabling us to compute the solution up to any given precision, a distinguishing feature that is unique to the domain-theoretic technique. An alternative method provides a domain-theoretic generalization of the Euler method for solving initial value problems. A more refined framework, using the domain for differentiable functions, also allows us to tackle differential equations when the vector field and/or the initial value are uncertain or imprecise. The extension of the domain-theoretic method to solve boundary value problems and partial differential equations remain highly challenging open questions.

We also present a domain-theoretic synthesis of Computational Geometry and Computer Science. We introduce a domain for geometric objects in the n-dimensional Euclidean space, which consists of pairs of disjoint open subsets representing the interior and exterior of subsets. For the first time, it enables us to define data-types for geometric computation and develop the notions of a computable geometric object and operation. In classical geometry and point-set topology, the membership predicate and other predicates such as subset inclusion are not continuous, and neither is the intersection operator with respect to, say, the Hausdorff metric. This lack of continuity means that in the classical model these predicates and operations are not computable. In contrast to the classical model, all basic predicates and operations such as membership and Boolean operations are continuous and computable in the domain-theoretic model. Furthermore, the model gives rise to data-types for geometry where the input, such as points, are only imprecisely given, and supports the design of robust geometric algorithms. We illustrate this with domain-theoretic robust algorithms for the Convex Hull, Voronoi Diagram and Delaunay triangulation in 2D, which have the same complexity as the classical algorithms. The question of complexity of such algorithms in the degenerate Delaunay triangulation and in 3D is open.

Finally, we combine the two frameworks by developing domain-theoretic versions of the inverse and implicit function theorems, which allow us to construct C¹ approximations to curves and surfaces within a robust framework. These results are intended to provide the basis of kernel for a robust CAD system.

With contributions from Andre Lieutier, (Dassault Systemes, Aix-en-Province) Dirk Pattinson, Ali Khanban and Marko Krznaric (Imperial College London).

Papers on this subject can be obtained from http://www.doc.ic.ac.uk/ ae/papers.html/

Date received: November 11, 2004