Tim Davis: Sparse matrix algorithms, CIS 4930/6930

Prof. Tim Davis,
P.O. Box 116120
University of Florida
Gainesville, FL 32611-6120
phone (352) 392-1481, fax (352) 392-1220
email: my last name AT cise.ufl.edu

CIS 4930/6930: Sparse matrix algorithms, Fall 2007

Course Overview

Taking effective advantage of the structure of a sparse matrix requires a combination of numerical and combinatorial methods (graph algorithms and related data structures). For example, finding the best ordering to factorize a matrix is an NP-complete graph problem. Topics focus on direct methods, but with some application to iterative methods: sparse matrix-vector multiply, matrix-matrix multiply and transpose, forward/backsolve, LU and Cholesky factorization, singular value decomposition, reordering methods (including the use of graph partitioning methods), and updating/downdating a sparse Cholesky factorization. Projects in the course include programming assignments in C and MATLAB.

Prerequisites: numerical linear algebra, graph theory, data structures and algorithms, C, and MATLAB. This background can be obtained in COT 4501 Numerical Analysis, COT 3100 Discrete Mathematics, and COP 3530 Data Structures and Algorithms, or related courses. Contact the instructor if you have any questions about the prerequisites, or about the course in general.

Syllabus

Class photos

About the instructor:

Tim Davis

http://www.cise.ufl.edu/research/sparse

Class time: MWF 4th period (10:40am to 11:30am) in CSE E220.

Office hours: to be determined.

Books:

Direct Methods for Sparse Linear Systems

MATLAB Primer, T. Davis and K. Sigmon, CRC Press, 2004. This book is optional.

Software:

CSparse:

UFget_defaults.m

UFget

Grading: The grading will be purely project based. There are no exams or quizzes.

Projects

Project 1, due Friday, Sept 7. See also the test script hw1.m. Note that I forgot to subtract one from Ai and Aj. You can do that in the revised hw1.m script, or inside your mexFunction. Either way is fine; just include your test script (hw1.m with the decrement, or without) in your submission.
Project 2, due Monday, Sept 17.
HW 3, due Friday, Sept 21. Problem 2.12 in the book.
HW 4, due Friday, Sept 28. Problems 3.1, 3.2, and 3.8 in the book.
HW 5, due Monday, Oct 8. Problem 3.3.
HW 6, due Friday, Oct 19. Problems 4.1 and 4.3.
HW 7, due Friday, Nov 5. Problems 6.1, 6.8, and 6.15.
HW 8, due Wed, Nov 14. Problem 6.13. Do both the drop tolerance and the pattern-of-A methods. Use the syntax cs_ilu (A,tol) where if tol is greater than zero it's a drop tolerance. If tol is zero, use the pattern of A method. I will post a method to test your code shortly. See also luinc (and ilu on MATLAB 7.5).
HW 9, due Thurs, Dec. 13. Problem 7.4. Only do the square non-singular case (the fine decomposition, not the course one). Write as a C mexFunction. Test with HB/west* and Sandia/* matrices (except the huge ones).

Click here for solutions (password required).