|
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 |
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.
Direct Methods for Sparse Linear Systems, T. Davis, SIAM, 2006.
MATLAB Primer, T. Davis and K. Sigmon, CRC Press, 2004. This book is optional.
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