Solution of Large Sparse Equations [C]:  2008-2009

Overview

Iain Duff and Jennifer Scott (both from RAL) give a course in Weeks 1-6 of Hilary Term 2009 on "Solution of large sparse equations". These are two of the world's leading experts on large sparse systems, and in particular on sparse direct methods (and various direct/iterative hybrids).

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 methods for solving such systems with a strong emphasis on direct methods.� 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.
• A brief review of methods for solving sparse equations including iterative methods, preconditioning, and hybrid methods.
• 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; out-of-core techniques.
• 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

1. Direct Methods for Sparse Linear Systems.� T.A. Davis.� SIAM (2006).
2. Direct Methods for Sparse Matrices. I.S. Duff, A.M. Erisman and J.K. Reid. OUP (1986).
3. Computer Solution of Large Sparse Positive-Definite Systems. A. George and J.W.H. Liu. Prentice-Hall (1980).
4. Matrix Computations, third edition. G.H. Golub and C.F. Van Loan. The John Hopkins University Press Ltd (1996). (for background information only)
5. More advanced material can be obtained from reports on our Web site.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.