Exact Computation

Reports
Papers
Implementations

Reports

Final report: Domain-theoretic Solution of Differential Equations [report.pdf].
Final report: Exact Real Arithmetic Using Linear Fractional Transformations [report.ps.gz].

Return to top

Papers

Domain-theoretic Solution of Differential Equations


	Domain-theoretic Solution of Differential Equations (Scalar Fields) (A. Edalat and M. Krznaric and A. Lieutier) Electronic Notes in Theoretical Computer Science volume 83, 2003.
	A domain theoretic account of Picard's theorem (A. Edalat and D. Pattinson) In Proceedings of ICALP 2004. Full paper to appear in the London Mathematical Society Journal of Computation and Mathematics.
	A domain theoretic account of Euler's method for Solving Initial Value Problems (A. Edalat and D. Pattinson) In Proceedings of PARA 2004
	Domain Theoretic Solutions of Initial Value Problems for Unbounded Vector Fields (A. Edalat and D. Pattinson) In Proceedings of MFPS XXI, ENTCS volume 155, 2005.
	A Computational Model for Multi-Variable Differential Calculus (A. Edalat and A. Lieutier and D. Pattinson) In Proceedings of FOSSACS 2005.
	Denotational Semantics of Hybrid Automata (A. Edalat with D. Pattinson) Proceedings of Foundations of Software Science and Computation Structures: 9th International Conference, FOSSACS 2006 Lecture Notes in Computer Science Volume 3921 pp.231-245 March, 2006
	Inverse and Implicit Functions in Domain Theory (A. Edalat and D. Pattinson) In Proceedings of LICS 2005.
	A continuous derivative for real-valued functions (A. Edalat) Invited paper for New Computational Paradigms
	Domain Theory and Differential Calculus (Functions of one variable) (A. Edalat and A.Lieutier). Mathematical Structures in Computer Science, Volume 14, Issue 06, Dec 2004, pp 771-802. (Extended abstract in Proceedings of IEEE Symposium on Logic in Computer Science (LICS) 2002.)

Exact Real Arithmetic, Computational Geometry and Solid Modelling

A. Edalat and R. Heckmann.
Computing with real numbers: (i) LFT approach to real computation, (ii) Domain-theoretic model of computational geometry.
In Gilles Barthe, Peter Dybjer, Luis Pinto, and Joao Saraiva, editors, LNCS, Springer, 2002.
[paper.ps.gz]
P. He and A. Edalat.
Visual Hull from Imprecise Polyhedral Scene
[paper.pdf] [supporting-information-paper.pdf]
A. Edalat and M. Krznaric.
Numerical integration with Exact Arithmetic.
Proceedings of ICALP'99.
[paper.ps.Z].
A. Edalat and A. Lieutier.
Foundation of a Computable Solid Modelling.
To appear in Theoretical Computer Science. Extended abstract in Proceedings of ACM's Symposium on Solid Modeling'99, ACM, 1999.
[paper.ps.gz].
A. Edalat and A. Lieutier.
Domain Theory and Differential calculus.
Proceedings of LICS'02, 2002.
[paper.ps.gz].
A. Edalat, A. Lieutier, and E. Kashefi.
Convex Hull in a New Model of Computation.
Proceedings of the 13th Canadian Conference on Computational Geometry University of Waterloo, August 13-15, 2001.
[paper.pdf].
A. Edalat and P. Sünderhauf.
A Domain-theoretic Approach to Real Number Computation.
Theoretical Computer Science, 210, (1998), 73-98.
[paper.ps.Z].
A. Edalat and P. J. Potts.
A New representation for Exact real Numbers.
Electronic Notes in Theoretical Computer Science 6, (1997).
[paper.ps.Z].
A. Edalat, P. J. Potts, and P. Sünderhauf.
Lazy computation with exact real numbers.
Proceedings of the Third ACM SIGPLAN International Confrence on Functional Programming, 185-194, (1998), ACM.
[paper.ps.Z].
A. Edalat and F. Rico.
Two Algorithms for Root Finding in Exact real Arithmetic.
Third Real Numbers and Computers Conference, 27-44, (1998).
[paper.ps.Z].
R. Heckmann.
The Appearance of Big Integers in Exact Real Arithmetic based on Linear Fractional Transformations.
Foundations of Software Science and Computation Structures, Springer LNCS 1378, 172-188 (1998)
[abstract] [paper.ps.gz (17p, 60k)].
R. Heckmann.
Big Integers and Complexity Issues in Exact Real Arithmetic.
Third Comprox workshop, Birmingham (Sept. 1997).
Electronic Notes in Theoretical Computer Science, Vol. 13 (1998)
URL: http://www.elsevier.nl/locate/entcs/volume13.html
[abstract] [paper.ps.gz (20p, 82k)].
R. Heckmann.
Contractivity of Linear Fractional Transformations.
Third Real Numbers and Computers Conference (RNC3), 45-59 (1998).
An updated version will appear in TCS.
[abstract] [paper.ps.gz (15p, 60k)].
R. Heckmann.
How Many Argument Digits are Needed to Produce n Result Digits?
RealComp '98 Real Number Computation, Indianapolis (June 1998).
Electronic Notes in Theoretical Computer Science, Vol. 24 (2000)
URL: http://www.elsevier.nl/locate/entcs/volume24.html
[abstract] [paper.ps.gz (21p, 84k)].
A. A. Khanban, A. Edalat, and A. Lieutier.
Computability of Delaunay Triangulation and Voronoi Diagram .
Proceedings of the 5th CCA Workshop, July 2002.
[paper.ps.gz].
M. Krznaric.
Computing a required absolute precision from a stream of linear fractional transformations. Proceedings of 4th CCA Workshop 2000, vol. 2064, pages 248-258.

Return to top

Implementations

IC-ODE-solvers: C library for Solving Initial value Problems. [complete package in tar.gz format]
IC-ODE-solvers is a C package, which solves initial value problems, using interval arithmetic and rational arithmetic packages. The package contains programs based on domian-theoretic versions of Picard's and Euler's methods to solve initial value problems.
The installation method and a few examples are provided in this package in order to help the user. All feedbacks and comments should be sent to the email provided in the package.

IC-Reals: C library for Exact Real Computation. [complete package in tar.gz format] [manual in ps.gz format] [manual in pdf format][copy right]
The Imperial College Exact Real Arithmetic Library is a collection of C types and functions which implement exact real arithmetic. The functions allow one to construct objects representing real numbers and then to demand information, for example some number of decimal digits, from those objects. The user need not specify a precision in advance. All the digits retrieved are correct and further digits can be demanded.
The library includes arithmetic operations as well as a suite of analytic functions on reals. In addition to a real type, the library also includes a lazy boolean type and a collection of predicates on reals, boolean operations and a conditional construct.

IC-Reals-Haskell: Haskell implementation of IC-Reals for Exact Real Computation. [complete package] [copy right]

iRRAM with Continued Fractions: C++ library for Exact Real Computation. [complete package in tar.gz format]
This C++ package combines Norbert Muller's approach to real computation, iRRAM, with the Continued Fraction algorithms for elementary functions developed at IC.

Return to top

Ali Khanban

Last modified: Tuesday, 15 January 2002.