CLASSIFICATION: Numerical Processing
SH: Y - UF
CM: Y - F
BM: N -
Project: 001 Supervisor: TLF
The conventional algorithm for forming the product of two n*n matrices requires O(n^3) flops (floating point operations). There also exist alternative (faster) algorithms; for example, Winograd suggested an algorithm that replaced some of the multiplications by additions (and this was significant for the machines of the time), Strassen suggested a recursive algorithm that requires O(n^(2.807)) flops to form a matrix product, and Winograd, again, suggested a slightly more efficient implementation of Strassen's algorithm. More recently, Pan, and Coppersmith and Winograd, have suggested recursive algorithms that have reduced the complexity to O(n^(2.376)). However, the accuracy properties of these recursive algorithms are often different from those of the standard algorithm. In this project we will investigate both the execution time and accuracy performances of a number of these matrix multiplication algorithms.
REFERENCES: N J Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 1996.
CLASSIFICATION: Numerical Processing
SH: Y - F
CM: Y - LF
BM: N -
Project: 002 Supervisor: TLF
The classical, recursive, algorithm for calculating the determinant of an n*n matrix A is known to have very poor time complexity properties. An alternative approach is first to form the triangular factors of A and then calculate the determinant from the diagonal elements of the factors. In this project we will implement these two algorithms and investigate their performances on test problems of various sizes. If time permits we will investigate alternative ways to calculate the determinant of a matrix.
REFERENCES: N J Higham, Accuracy and Stability of Numerical Algorithms, SIAM, 1996.
CLASSIFICATION: Numerical Processing
SH: Y - C
CM: Y - UF
BM: N -
Project: 003 Supervisor: TLF
The Symmetric QR Algorithm is one of the most widely-used algorithms for the calculation of the eigenvalues of a symmetric n*n matrix. It is based on forming the QR factorisation of a sequence of matrices that are orthogonally similar to (and thus have the same eigenvalues as) A. The convergence of the QR algorithm is frequently accelerated by the incorporation of (explicit or implicit) shifts at each stage of the iteration process. In this project we will implement the QR algorithm with shifts for a real symmetric matrix and evaluate its performance.
REFERENCE:
G Golub and C Van Loan, Matrix Computations, The Johns Hopkins University
Press, 1996.
SH: Y - C
CM: Y - C
BM: N -
Project: 004 Supervisor: TLF
Quasi-Newton Algorithms, and in particular algorithms from the Broyden family, are the most widely-used algorithms for the unconstrained minimisation of a nonlinear function. In idealised circumstances, it has been proved that these algorithms have some remarkable and unexpected properties - for example, for a nonlinear function and an exact line search, it can be shown that the progress of the algorithm is independent of the parameter that defines the updating formula (Dixon's theorem). This remarkable result was first postulated using a set of carefully defined numerical tests, before the result was formally established. The objective of this project is to study, understand and implement the Broyden family of quasi-Newton algorithms and to recreate the numerical evidence that motivated Dixon's theorem.
REFERENCES:
R Fletcher, Practical Methods of Optimization, John Wiley & Sons, 1987.