MSc Projects

Back to Abbas Edalat's Home Page


Exact Computation: A New Paradigm

Various areas of computaton, such as computer arithmetic, numerical anaylsis, computational geometry, solid modelling and solution fo differential equations, which need to deal with and handle real numbers, greatly suffer from lack of a proper data-type. In computer arithmetic, for example, the accumulating effect of round-off errors can produce a grossly wrong end result as is very well-known. Another crucial example is in computational geometry where correctness of algorithms is usually proved using the Real RAM machine model of computation in which real numbers are treated as floating point numbers. Since this model in unrealistic, correct algorithms, when implemented, turn into unreliable programs which can result in logical inconsistency in the most basic algorithms in this area, such as in obtaining the intersection of two lines or determining the convex hull of a finite number of points in the plane.
In recent years, we have developed a proper data-type for real number computation in the above disciplines, which have resulted in efficient and sound algorithms in these area. We now have a C library for exact computation of all elementary functions developed at Imperial College. We have furthermore developed data-types for computational geometry, solid modelling and differential equations.
The aim of this Independent Study Option will be to give a detailed account of these data-types and show how they can be used to develop a framework for Exact Real number Computation, Computable Solid Modelling, Computational Geometry and Differential Equations. The subject is inter-disciplinary and brings in ideas from varius areas of computer science and mathematics together.
  The following MSc projects are available in this area:
Exact Coordinate Geometry
An Exact Numerical Calculator with Java Interface
Exact real arithmetic based on the interval [-1,1]
Boolean and isometric operations on rational polyhedra
Basic robust algorithms for computational geometry
A data-type for solving differential equations