Catalog description:  Many applications in computational science rely on algorithms for large-scale sparse matrices (circuit simulation, finite-element methods, 'big data', Google StreetView, etc).  Course equips students to understand and design methods that exploit sparsity in matrix computations.  Focus is direct methods, which rely on combinatorics, graph theory and algorithms, and numerical methods. Prerequisites: undergraduate-level numerical linear algebra and data structures/algorithms.

Course overview:  Students in any discipline that uses scientific computing methods will benefit from this course. A wide range of problems in science and engineering require fundamental matrix computations for their solution, and these matrices are often mostly zero. The objective of this course is to equip the student with the background necessary to understand and design algorithms for solving sparse matrix problems.  The world's largest sparse matrix arises in Google's web page ranking problem. About once a month, Google finds an eigenvector of sparse matrix that represents the connectivity of the web (of size billions-by-billions). Other sparse matrix problems arise in circuit and device simulation, finite element methods, linear programming and other optimization problems, acoustics, electromagnetics, computational fluid dynamics, 'big data', financial portfolio optimization, structural analysis, and quantum mechanics, to name a few.

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.

Meets from 1:50pm to 2:40pm, MWF, in 126 HRBB.

Links and other resources:

1. •Syllabus:  csce689_Spring2015_syllabus_Davis.pdf (PDF).
   

2. •about the instructor:
   

3. •College of Engineering faculty web page
   

4. •Computer Science and Engineering faculty web page 
   

5. •Parasol lab web page 
   

6. •research
   

7. •background and contact info
   

8. •All lectures are available to the right (top).  See also the SIAM Plenary talk (2006) and a talk given at Stanford (2013) for an overview of the topic.
   

9. •CSparse.zip: version 3.1.4.  Use this version as the starting point for all class projects.
   

10. •Piazza: for class discussions, announcements, and posting of resources.