Course pages 2013–14

# Numerical Methods

**Principal lecturer:** Dr David Greaves**Taken by:** Part IA CST, Part IA NST, Part I PBS**Past exam questions****Information for supervisors** (contact lecturer for access permission)

No. of lectures: 11

Suggested hours of supervisions: 4

This course is useful for the Part II courses Advanced Graphics and Digital Signal Processing.

## Aims

This course provides:

- an introduction to (IEEE) floating-point data representation and arithmetic;
- illustrations of how naïve implementations of obvious mathematics can go badly wrong;
- a study of several standard numerical algorithms.

An overall implicit aim is to encourage caution when using any floating-point value produced by a computer program.

## Lectures

**Integer and floating-point representation and arithmetic.**Signed and unsigned integers and fixed-point; arithmetic, saturating arithmetic. IEEE 754/854 floating point (32 and 64 bit); zeros, infinities, NaN. What numbers are exactly representable in bases 2 and 10. Accuracy in terms of significant figures. Floating-point arithmetic is non-associative, and mathematical equivalences fail. Nonsensical results, e.g.`sin(1e40)`.**IEEE floating-point arithmetic.**Floating-point arithmetic, and the IEEE requirements. Why the IEEE standard has endured. Overflow, underflow, progressive loss of significance. Rounding modes. Difficulty in obtaining IEEE-quality in libraries. The java.lang.Math trigonometric library promises.**How floating-point computations diverge from real-number calculations.**Absolute Error, Relative Error, Machine epsilon, Unit in Last Place (ulp). Finite computation: solving a quadratic. Summing a finite series. Rounding (round-off) and truncation (discretisation) error. Numerical differentiation; determining a good step size.**Iteration and when to stop.**Unbounded computation may produce unbounded errors. Solving equations by iteration and comparison to terminate it. Newton’s method. Order of convergence. Why summing a Taylor series is problematic.**Custom Encodings**Arbitrary precision floating point, adaptive floating point, interval arithmetic. Logarithmic and other non-linear representations. Their use in a-posteriori decision algorithms. Eg for rapid multiplication in Viterbi/Bayes and specialist ALUs (e.g. for low-density parity).**Matrix Methods**Gaussian Elimination. L/U and Cholesky decompositions. Doolittle, Crout methods. Their stability and usefulness.**Efficient Implementation**Chebychev orthogonal basis (for power series economisation) Practical implementation of scientific (trig/log) functions. Comparison of Taylor, Chebychev and Cordic.**Ill Conditioning and Chaotic Simulations.**Role of partial derivatives and backwards stability. Condition number when amenable to mathematical analysis; Monte-Carlo exploration when not. Finite-difference simulation and chaos in weather forecasting and Mandelbrot.**Adaptive methods**Linear approximations. Wave propagation simulation. Non-linear spatial quantisation. Dynamic temporal quantisation and its use in SPICE.**Miscellaneous Topics**Discussion on the problems of exact real arithmetic. Remark on the x86 implementations of IEEE arithmetic, interaction of coding style and compiler “optimisations”. Final Remarks.

## Objectives

At the end of the course students should

- be able to convert simple decimal numbers to and from IEEE floating-point format, and to perform IEEE arithmetic on them;
- be able to identify problems with floating-point implementations of simple mathematical problems and know when incorrect solution is likely;
- be familiar with several key algorithms from the history of numerical analysis;
- decide how and when computation energy should be traded for accuracy;
- know to use a professionally-written package whenever possible (and still to treat claims of accuracy with suspicion).

## Recommended reading

Overton, M.L. (2001). *Numerical computing with IEEE floating point arithmetic*. SIAM.

Further reading - goes far beyond the course

Goldberg, D. (1991). *What every computer scientist should know about floating-point arithmetic*. ACM Computing Surveys, vol. 23, pp. 5-48.