Department of Computer Science and Technology

Course pages 2018–19

Numerical Analysis

Principal lecturer: Dr Bogdan Roman
Taken by: Part IA CST 50%, Part IA CST 75%, Part IA NST

No. of lectures: 12
Suggested hours of supervisions: 4

Aims

This course will introduce (IEEE) floating point representation and arithmetic, and core topics in the field of Numerical Analysis. Examples of their application in practice will be presented along with code snippets.

Lectures

The website will announce the list of examinable topics by the last lecture.

  • Fundamentals. Floating-point (IEEE) data representation, arithmetic and associated issues (underflow, overflow, errors, loss of significance, etc.)

  • Root-finding and stopping criteria. Iteration, bisection and secant, Newton’s and gradient methods, order of convergence, condition number, partial derivatives, backwards stability and chaos.

  • Linear Systems. Gaussian elimination and pivoting, factorization techniques, linear least squares, eigenvalues and eigenvectors.

  • Implementations. Taylor, Chebychev, splines, implementation of scientific functions, Cordic.

  • Finite-Differences, Monte Carlo, Fluid Flow. Numerical simulation of SHM, charge/discharge, waves and other examples, steady state by linear flow circuit analysis.

  • Adaptive Methods and Custom Encodings. Arbitrary precision and adaptive floating point, non-linear representations and quantisation, interval arithmetic, simulated annealing.

Objectives

The course should enable students to

  • convert decimal numbers to/from IEEE floating-point format, understand the properties of floating-point arithmetic and identify implementations issues;

  • understand and use some core concepts and algorithms in Numerical Analysis;

  • decide computation energy/accuracy tradeoffs, and to be familiar with a range of examples of Numerical Analysis in Computer Science

Recommended reading

Faul, A.C. (2016). A concise introduction to Numerical Analysis. CRC Press.
Overton, M.L. (2001). Numerical computing with IEEE floating point arithmetic. SIAM.

Further reading (goes beyond the course):

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