Tim Davis: Sparse matrix algorithms, CIS 4930/6930

Prof. Tim Davis,
P.O. Box 116120
University of Florida
Gainesville, FL 32611-6120
email: my last name AT cise.ufl.edu
or Dr Timothy Alden Davis AT gmail.com

CIS 4930/6930: Sparse matrix algorithms, Spring 2010

Resources

SIAM 2006 lecture

Announcements

Project 1 is assigned, and due Friday Jan 22 (by the time class starts).
On Wednesday Jan 20, Wednesday Feb 3, and Wednesday Feb 10 we will meet in CSE E222 (not our regular classroom) for 4th and 5th periods (4:05pm to 6pm).
Office hours for Jan 15 will be from 3-4pm. Class time as usual.

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.

Class photos will appear here.

About the instructor:

Tim Davis

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

Class time: MWF 10th period (5:10pm to 6pm) in CSE E221.

Office hours: MWF 3-5pm in CSE E338.

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 Jan 22:
- hw1.pdf: the assigment.
- hw1.m: the m-file for testing problem B.
Project 2, due Monday Feb 15:
- hw2.pdf: the assigment. You will need to generate your own test code.
Project 3, due Wednesday Mar 3:
- Problem 3.3 in the textbook. You will need to generate your own test code.
Project 4, due Monday, Mar 22.
- Problems 4.10 and 4.11
Project 5, due Wed, Apr 7. As a reminder, you must do all your own work on each project. You can discuss the topic with each other, but when you do so, pretend that you are me. That is, I would help you understand the problem, and I would point out problems in your solution. But I would not write any of your code.
- Problem 6.8. Derive, and write a MATLAB prototype. Discuss.
- Problem 6.14. Be sure not to miss my discussion in class on this problem.

Project 6. due Wed Apr 21. Problem 7.4. Test with the following matrices. Of course, you can stop the test early (the test below will try some very large matrices).

index = UFget ;
f = find (index.nrows == index.ncols & ...
    index.sprank == index.nrows & ...
    index.numerical_symmetry < 1) ;
[ignore i] = sort (index.nnz(f)) ;
f = f (i) ;
for k = 1:length (f)
    id = f (k) ;
    Prob = UFget (id) ;
    A = Prob.A ;
    cs_dmspy (A) ;
end