Spring 2013

 

CIS 6930 - Sparse matrix algorithms


Course Objectives and Prerequisites

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 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, 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.


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.



Instructor:

Timothy A. Davis CSE E338. office phone: 352-505-1546. cell 352-359-2812

email: davis@cise.ufl.edu or DrTimothyAldenDavis@gmail.com

class web site: http://www.cise.ufl.edu/~davis/sparse13.html

Office hours: just after class, until at least 11:30am in CSE E338.  I’m also generally available at other times.  Stop by and come on in if my door is open.


Teaching Assistants:

none


Class meeting times:

MWF 9:35am to 10:25am in CSE E119.

Final exam: none.

There is no lab or discussion section.


Material and Supply Fees:

None.


Textbooks:

Direct Methods for Sparse Linear Systems, by Tim Davis.  Required.

MATLAB Primer, 8th edition, by Tim Davis (optional). The book is on reserve in the Marston Science Library.


You will require access to MATLAB.  It is available on the CISE systems, and most UF computers.  You can use MATLAB remotely from your own computer, by logging into CISE systems.  You can also purchase the Student Edition of MATLAB if you want to run MATLAB on your computer directly.  The cost is $99 (you don't need any toolboxes beyond the default ones provided).


Other Resource Links:

  1. •CSparse, version 3.1.1:  you will use this for your projects.

  2. •UFget_settings.zip : for modifying UFget when used on CISE systems.

  3. •spok.zip: for checking the validity of a MATLAB sparse matrix.

  4. •spring11.zip: Notes from Spring 2011.  I will update these as needed for Spring 2013.

  5. •Video for the SIAM 2006 lecture on sparse direct methods, and slides


Course outline:

Chapter 1: Introduction

Chapter 2: Basic algorithms

Chapter 3: Solving triangular systems

Chapter 4: Cholesky factorization

Chapter 5: Orthogonal methods

Chapter 6: LU factorization

Chapter 7: Fill-reducing orderings

Chapter 8: Solving sparse linear systems

Chapter 9: CSparse

Chapter 10: Sparse matrices in MATLAB


Attendance and expectations:

I expect you to attend class, but I don’t take attendance.  You may not use laptops in class without explicit permission.  They are a distraction.


Grading:

No exams.  All grading is based on the projects.


Collaboration:  None.

All projects are to be done by yourself.


Turning in homework:
Homework will be turned in on the UF e-Learning site at https://lss.at.ufl.edu/.  You will not be submitting paper copies. 


Grading scale:

A: 90, B: 80, C: 70, etc. I will curve as needed. I also give plus and minus grades (87 is an A-, 84 a B+, 77 a B-, etc).


Class pictures:

I will take pictures of each student in the class so that I can get to know you. Only I will have access to the photos.


Other standard policy:

Honesty Policy: All students admitted to the University of Florida have signed a statement of academic honesty committing themselves to be honest in all academic work and understanding that failure to comply with this commitment will result in disciplinary action.  This statement is a reminder to uphold your obligation as a UF student and to be honest in all work submitted and exams taken in this course and all others.


Accommodation for Students with Disabilities: Students Requesting classroom accommodation must first register with the Dean of Students Office.  That office will provide the student with documentation that he/she must provide to the course instructor when requesting accommodation.


UF Counseling Services: Resources are available on-campus for students having personal problems or lacking clear career and academic goals.  The resources include the UF Counseling and Wellness Center, 3190 Radio Rd, 392-1575, for psychological and psychiatric services; and the Career Resource Center, Reitz Union, 392-1601, career and job search services.


Software Use:  All faculty, staff and student of the University are required and expected to obey the laws and legal agreements governing software use.  Failure to do so can lead to monetary damages and/or criminal penalties for the individual violator.  Because such violations are also against University policies and rules, disciplinary action will be taken as appropriate.  We, the members of the University of Florida community, pledge to uphold ourselves and our peers to the highest standards of honesty and integrity.