MIS40530 Numerical Analytics and Software

Academic Year 2016/2017

1. Models of computation. Turing machines. Problems and their instances. Decidability and complexity of discrete algorithms. Reductions. Witnesses. [Ch1]
A lab: toying with a simulator of a Turing machine.
2. Finite-precision floating-point numbers. IEEE standards. Arithmetic as implemented in modern computers. Errors and error bounds. Witnesses and lack thereof.
A lab: Introduction to Python and Numpy.
3. Models of iterative, numerical computation. Decidability and complexity over a ring. Iteration complexity. Condition numbers. Stability. Witnesses. [Ch3]
4. Systems of linear equations and condition numbers therein. Iteration complexity. Condition numbers. Stability. Witnesses. Iterative methods: Jacobi, Gauss-Seidel. Direct methods: Gaussian elimination, LU decomposition [Ch11]
A lab: implementations thereof.
5. Univariate polynomial equations. Newton’s algorithm. Iteration complexity. Witnesses. [Ch8, Ch9]
A lab: implementations thereof.
7. Systems of multi-variate polynomial equations. Newton’s algorithm. Homotopy methods. Iteration complexity. Witnesses. Applications in power systems. [Ch10]
A lab: Introduction to Matplotlib and comparison of algorithms.
8. Unconstrained Optimisation. Differentiability, convexity, and strong convexity. Gradient methods. Accelerated gradient methods. Second-order methods. Iteration complexity. Applications in machine learning.
A lab: implementations thereof.
9. Linear (and conic) programming. Cones. Duality. Farkas Lemma and Witnesses. Interior-point methods. Applications in prescriptive analytics. [Ch15]
A lab: implementations thereof.
10. Complexity of parallel and distributed computing. Communication complexity. [Ch18]
A lab: A practical demo of commercial and open-source machine learning within cloud computing.
11. Complexity of dealing with uncertainty. The lack of witness. Closed loop and the difficulty of system identification and problem formulation.
A lab: revision.

Show/hide contentOpenClose All

Curricular information is subject to change

Learning Outcomes:

On completing this course, you should be able to:
* Understand common models of computation and their relative strengths, incl. the difficulties of numerical computation on finite-precision machines
* Understand the complexity of iterative (numerical) computations and be able to contrast it with the complexity of discrete algorithms
* Understand key algorithms in solving systems of linear and non-linear equations, optimisation with linear and non-linear constraints
* Implement some algorithms in solving systems of linear and non-linear equations and optimisation with linear and non-linear constraints
* Understand some of the connections to machine learning and prescriptive analytics

Student Effort Hours: 
Student Effort Type Hours
Lectures

36
Conversation Class

12
Specified Learning Activities

40
Autonomous Student Learning

84
Total

172
 
Requirements, Exclusions and Recommendations
Learning Requirements:

Basic mathematics, the equivalent of at least 1 year of University mathematics, to include such topics as linear algebra, calculus of several variables, optimisation techniques and some numerical analysis. The MSc(BA) / MSc(QF) course Quantitative Methods covers all required topics.

You should also be reasonably competent at computer programming, being aware of the basic conditional, looping etc., constructs. You do not need to have met the principles of object oriented programming before, as they will be introduced from scratch in the first few weeks of term; however, the more experience you have of programming, the better.

Learning Recommendations:

MSc(BA) / MSc(QF) Quantitative Methods should be taken either before or concurrently with this module



 
Description % of Final Grade Timing
Examination: Final Exam

60

 2 hour End of Trimester Exam
Continuous Assessment: Programming Homework

40

 Varies over the Trimester

Compensation

This module is not passable by compensation

Resit Opportunities

End of Semester Exam

Remediation

If you fail this module you may repeat, resit or substitute where permissible

Name Role
Assoc Professor James McDermott Lecturer / Co-Lecturer
Assoc Professor Sean McGarraghy Lecturer / Co-Lecturer
Baibing Li Tutor