CS 680/780: Numerical Computing Foundations Fall 2005
Johnstone Course outline

Professor	Dr. John K. Johnstone, CH125
Time	MWF 10:10am-11, 134 Education Building
TA	Ying Sun (suny@cis.uab.edu)
Office Hours	Johnstone: M-F 12-1 (CH125); Sun: TTh6-8pm (CH153)
Prerequisites	Graduate standing, including knowledge of linear algebra, C, and UNIX.
Textbook	Gene Golub and Charles Van Loan (1996)
	Matrix Computations (3rd edition). Johns Hopkins University Press.
Website	www.cis.uab.edu/cs680 or www.cis.uab.edu/cs780
Equipment	CH135 or workstations in your lab (for PhD students).
	Get a department computer account if you don't already have one
	(go to www.cis.uab.edu/it/accountApplication.php)

Additional References

• A linear algebra textbook. E.g., Serge Lang (1971), Linear Algebra. Addison Wesley.
• Books and papers referenced in Golub and van Loan.
• Steven Chapra and Raymond Canale (2006), Numerical Methods for Engineers (Fifth Edition), McGraw Hill.
• Jonathan Shewchuk, An Introduction to the Conjugate Gradient without the Agonizing Pain. CMU Tech Report, 1994.
• LAPACK and CLAPACK documentation (www.netlib.org/lapack, www.netlib.org/clapack)

Grading

 		 Homework 		 15% (25% for 680)


Project (780 only)		 25% 

		 Midterms (September 23 and October 28, in class) 		 30% (40% for 680)

		 Final   (Wednesday, December 14, 8am-10:30) 		 30% (35% for 680) 

There will also be differences between the 680 and 780 exams (e.g., an extra question for 780 or an alternative question), and between homeworks (e.g., number of homeworks).

Homework is due in class, at the beginning of class. Late penalty is 10% per day; however, note that the homework must be handed in before a homework solution is handed back, which will be done within a week. Late homework should be handed in to the department office (Campbell 115), with a secretary's signature acknowledging time and date of receipt. Homeworks will be marked by the TA. I will mark all exams. Last day to withdraw with 'W': December 5, 2005.

Course Description

This is predominantly a course about matrix computation, emphasizing efficiency and robustness. The major topics are the solution of linear systems and spectral analysis (computation of eigenvectors and eigenvalues). Other topics include efficient algorithms for matrix multiplication, singular value decomposition, least squares, and nonlinear systems. A selection of applications of these methods will also be explored, such as curve fitting and principal component analysis.

Topics

• Matrix multiplication and matrix analysis (Chapters 1-2)
• Linear systems (Chapters 3, 4, 10)
• Nonlinear systems (course notes)
• Least squares (Chapter 5)
• Spectral analysis (Chapters 7 and 8)
• Case studies (supplementary material)
• LAPACK software

Applications

A unique aspect of this course is its coverage of applications, which formally and informally motivate the numerical techniques developed in the course. Examples of applications include:

• subdivision curves and surfaces (motivating matrix multiplication and spectral analysis);
• principal component analysis (motivating spectral analysis);
• curve fitting (solution of special linear systems);
• radiosity (solution of linear systems)

These and other applications can be further explored in the projects.

Curriculum

• Introduction
  • Matrix multiplication (GvL 1, Sections 1-3, skim 4)
  • Matrix analysis (Linear algebra textbook; GvL 2, Sections 1-2; 3.1-3.2 (skim 3.3); 4.1-4.4 (skim rest of 4); 5.1-5.3 and 5.5; 7.2-7.3)
• Solution of linear systems
  • General linear systems (GvL 3, Sections 1.1-1.5 and 1.8; 2.1-2.8, 2.10 and 2.12; all of Section 4 except 4.5-4.6)
  • Special linear systems (skim Section 1, all odd sections of Section 2 in detail)
• Solution of nonlinear equations I (course notes)
  • Root finding of univariate functions
• Optimization (course notes and Chapra/Canale, Chapters 13-14)
• Solution of linear systems (continued)
  • Sparse linear systems (Shewchuk; GvL 10, preamble to Section 1, Section 2 except 2.5, skim 3.1-3.2)
• Least squares
  • Triangulation (GvL 5, Sections 1 except 1.7 and 1.12-1.13; Section 2.1, skim 2.3, 2.4, 2.6 and 2.10)
  • Least squares (GvL 5, Section 3 except 3.5-3.7)
• Spectral analysis
  • Definitions (GvL 7, Section 1.1; GvL 8, Section 1.1)
  • Tridiagonalization and QR iteration (GvL 8, preamble to Section 2, 3.1, 3.3, 3.4)
  • Jacobi methods (GvL 8, Section 4 except 4.8)
  • Applications (Stollnitz; SIGGRAPH proceedings; lecture notes)
  • Singular value decomposition (GvL 8, Section 6.2 and 6.3)
• Solution of nonlinear systems II (course notes)
  • symbolic solutions, counting roots, resultants

Honour code

All of the following are strictly forbidden:

• Any form of cooperation on exams, whether take-home or in-class.
• Any form of cooperation on homework or projects, other than preliminary oral discussion at a high level (that is, definition of the problem). Homework is to be solved and written up alone and independently.
• Any coercion of other students to help on homework, exams, or projects (even if help is not forthcoming).

All references and/or websites used must be included in a bibliography. Care must be taken not to plagiarize.

Violations of any part of this honour code will result in a 0 on that exam/assignment/project, possible failure of the course, and possible forwarding of the case to the school ethics board, where a decision about expulsion from UAB is made.

Grading policy

In general, the marking scheme for this class will be as follows.

• A: 85-100
• B: 70-84
• C: 60-69
• F: below 60

These standards may be adjusted for certain exams or homeworks, but any adjustment will be announced in class.

Attendance policy

You are expected to attend every class. If you must miss a class because of illness or other unavoidable reason, you are responsible for getting the notes and any assignments from a fellow student. Large gaps in attendance are not acceptable (e.g., if you must work during class hours, please drop the course).

Makeup policy

Midterm exams can be made up if missed due to illness, upon receipt of a doctor's note. The final exam cannot be made up. The final exam cannot be offered to students early (e.g., for Christmas travel).