Synopsis

The solution of large-scale sparse linear systems lies at the heart of many computations in science, engineering, industry, and finance. The aim of this course is to provide an introduction to direct methods for solving such systems. It is presumed that participants will have some familiarity with linear algebra although a brief resume of essential background on dense Gaussian elimination will be included.

The course will cover the following topics:

Fundamentals: introduction to sparse matrices; sparse matrix storage schemes; basic manipulation of sparse matrices; complexity of sparse elimination; graph theory for sparse matrices; BLAS; features of sparse direct software.

Gaussian elimination: review of GE for dense matrices; scaling; local pivot strategies for sparse GE (symmetric and unsymmetric matrices); nested dissection orderings and hybrid schemes; level set methods for ordering and partitioning; ordering to special forms including variable band form and block triangular form.

Frontal solvers: element and non-element problems; symmetric and unsymmetric matrices; ordering schemes.

Multifrontal methods: elimination and assembly trees; symmetric positive definite and indefinite matrices; unsymmetric matrices.

Parallel direct methods: partitioning schemes; different levels of parallelism; multifrontal methods.

Reading List

• I.S. Duff, A.M. Erisman and J.K. Reid, Direct Methods for Sparse Matrices, OUP,1986

• A. George and J.W.H. Liu, Computer Solution of Large Sparse Positive-Definite Systems, Prentice-Hall,(1980).

• Matrix Computations, third edition. G.H. Golub and C.F. Van Loan. The John Hopkins University Press Ltd (1996). (For background information only).

• More advanced material can be obtained from reports on our Web site http://www.numerical.rl.ac.uk/reports/reports.html