Dr. Annie Cuyt and Dr. Brigitte Verdonk
Department of Mathematics and Computer Science
University of Antwerp
Universiteitsplein 1
B2610 Antwerp - Wilrijk
BELGIUM
Annie.Cuyt@uia.ua.ac.be
Brigitte.Verdonk@uia.ua.ac.be
Computer Arithmetic and Numerical Techniques
The course "Computer Arithmetic and Numerical Techniques" aims to introduce CS-students to scientific computing. When the idea to set up a special course for computer science students was first launched in 1993, many colleagues world-wide reacted very enthusiastically. The course is special in the sense that it emphasizes the differences between a mathematical algorithm on paper and its implementation on a machine using finite precision arithmetic.
COMPUTER ARITHMETIC
The essence of this part of the course is to discuss how the number sets Z, Q and R can be represented on a computer and to show how computing with the computer representation of these numbers instead of with the numbers themselves influences the computations. Throughout this part of the course, the level of complexity evolves in two directions. On one hand, the complexity changes as we go from Z (integer arithmetic) to Q (exact rational arithmetic) to R (exactly rounded arithmetic). On the other hand, the complexity increases as we allow more complex operations on each of these number sets.
The course material is essentially simple and clear-cut. Yet students have difficulties grasping all the intricacies of the material. To this end, we have finalized in the last year a full-fledged didactical software environment, which visualizes all the intricacies of computer arithmetic described in the course. How is this achieved? In this environment it is possible to specify and simulate that computations are performed, not in the hardware IEEE singles or doubles, but in a user-defined set of floating-point numbers. By choosing a small precision t and a limited exponent range, students can then much more easily follow the computations at the bit-level. Moreover, in a low-precision floating-point set, one can zoom in on the unmistakable effects of finite precision arithmetic.
In addition to using the environment for simple expressions, the students can also run their own downloaded code from within the didactical software tool, with a user-specified precision and exponent range, rather than with the IEEE single or double hardware floats.
NUMERICAL TECHNIQUES
Starting from small-scale real-life problems, different numerical techniques are introduced, discussed, implemented and compared. The emphasis is on actual problem-solving. This part of the course is consists of four modules and includes small individual projects which are afterwards discussed in class.
Linear Algebra:
This subject is of uttermost importance because so many real-life problems involve the solution of a system of linear equations. Hence the real-life problems that we discuss come from quite different areas such as computer graphics, where one needs to find the intersection of planes and lines, and robotics, where the movements of a robot can be expressed by matrix-vector operations.
Root-finding:
Motivating examples for this subject are the implementation on a chip of a routine to compute the square root and the difficult problem of exact and approximate polynomial root solving.
Approximation Theory:
Of all the modules, this is the most comprehensive one since it covers several mathematical techniques, including interpolation, Chebyshev approximation, splines, least squares and rational approximation. For all except the last of these techniques, polynomials are used as approximating functions. We emphasize how the nature of the problem influences the choice of the approximation technique. A particular computational problem has been discussed in more detail above.
Random Number Generators:
Simulation techniques are essential in many of today's complex problems such as traffic engineering and the computation of irregular tank volumes.