• Instructor: Haesun Park, CCB 256, 404.385.2170
  hpark@cc.gatech.edu
  Office Hours: Th 2:55-3:55 pm or by appointment
  

• August 31: Home Work 1 is posted. Due Sep. 14, in class. (Home Work 1)

• September 14: Home Work 2 is posted. Due Sep. 28, in class. (Home Work 2)

• September 28: Prof. Hongyuan Zha will give today's lecture.

• October 5: Home Work 3 is posted. Due Oct. 24, in class. (Home Work 3)

• October 26: Home Work 4 is posted. Due Nov. 9, in class. (Home Work 4)

• November 2: November 7 Tuesday lecture will be given by a guest speaker, Prof. Ananth Grama of Purdue University at MiRc Building room 102 A and B.

• November 13: For a new version of LAPACK 3.1 which is just released, see LAPACK Changes for the details. The software can be found at LAPACK3.1

• November 15: Nov. 16 lecture will be based on the file Some Matrix Decompositions in Dimension Reduction

• November 21: Home Work 5 is posted. Due Dec. 7, in class. (Home Work 5)

• December 7: Final Exam Reading is Revised. (Final Exam Reading)
• HW5 is due today except for Question 3.
  You may submit Question 3 by midnight of Dec. 12 by e-mail to hpark@cc.gatech.edu .
  Please make sure to put "CS8803" in the mail subject.

(all from the textbook by Golub and Van Loan, 3rd Edition)

• August 22:
1.1 Basic algorithms and notation
1.2 Exploiting structure
1.3 Block matrices and algorithms

• August 24:
2.1 Basic ideas from linear algebra
2.2 Vector norms
2.3 Matrix norms (up to 2.3.2)
2.4 Finite precision matrix computations (up to 2.4.9)
2.5 Orthogonality and the SVD (up to 2.5.2)

• August 29:
3.1 Triangular systems (up to 3.1.4)
3.2 The LU factorization (exclude 3.2.3)
3.4 Pivoting (exclude 3.4.6)

• September 6:
2.7 The sensitivity of Square Systems (exclude 2.7.1 for now but read it after the SVD is covered in the class)
Chapter 4: LAPACK Information (pp. 134-135)
4.2 Positive definite systems (up to 4.2.6)
4.3 Banded systems

• September 19:
5.1 Householder and Givens Matrices (up to 5.1.11)
5.2 The QR Factorization
5.3 The full rank LS problem (up to 5.3.5)

• October 3:
5.3.8 Normal Equations Versus QR
5.4 Other Othogonal Factorizations
5.5 The Rank Deficient LS problem

• October 23:
7.1 Properties and Decompositions
7.3 Power Iterations (up to 7.3.3)
7.4 The Hessenberg and Real Schur Forms (up to 7.4.3)
7.5 The Practical QR Algorihtm

• November 2:
8.4 Jacobi Methods (up to 8.4.4)

• November 26:
8.7 Some Generalized Eigenvalue Problems (optional)
12.3 Total Least Squares

• November 27: The reading for the rest of this semester is from
D. Luenberger, Linear and Nonlinear Programming, 2nd Ed.
Ch. 1. Introduction
Ch. 2. Basic Properties of Linear Programs
3.1 Pivots
3.2 Adjacent Extreme Points
3.3 Determining a Minimum Feasible Solution
3.4 Computational Procedure -Simplex Method
3.5 Artificial Variables

• December 7:
3.7 Matrix Form of the Simplex Method
4.1 Dual Linear Programs
4.2 Duality Theorem
4.3 Relations to the Simplex Procedure

• Evaluation:

5 Homeworks (Some programming in MATLAB, Fortran, C, or C++. You may use other programming languages with the instructors permission) 50%
Midterm Exam 1, 15\% (Sep. 26, Tuesday, in class, open books/notes)
Midterm Exam 2, 15\% (Nov. 9, Thursday, in class, open books/notes)
Final 20\% (Dec. 12, Tuesday, 11:30am -2:20pm, Cherry Emerson 322)

• Textbook:

There are two required text books:
Required textbook 1 : Matrix Computations 3/e by Golub \& Van Loan, Johns Hopkins, 1996
Required textbook 2 :
Linear and Nonlinear Programming 2/e by D. Luenberger, Springer, 2003

Supplementary (you do not need to purchase these books):
Applied Numerical Linear Algebra by J.W. Demmel, SIAM, 1997
Lloyd N. Trefethen and David Bau, Numerical Linear Algebra, SIAM, 1997
Introduction to MATLAB for Engineers and Scientists, D.M. Etter, Prentice Hall, 1996

• Topics:
• Introduction (1 week):
• Floating point arithmetic, source of errors
• Subspace, basis, orthogonality, projections, norms, condition number
• Numerical softwares, Floating point operation counts
• Systems of Linear Equations (3 weeks):
• LU factorization and Pivoting
• Perturbation analysis, Condition number
• Symmetric positive definite and banded systems
• Introduction to iterative methods for large sparse matrices
• Solving Linear Least Squares Problems (4 weeks):
• Orthogonal transformation, QR decomposition, pivoting
• Householder methods, Givens method, Gram-Schmidt methods
• Singular value decomposition
• Introduction to Eigenvalue Problems (1 week):
• Properties, Schur decomposition
• Power and inverse power methods
• Symmetric Eigenvalue Decomposition (3 weeks):
• QR algorithm
• Jacobi method
• Linear Programming (3 weeks):
• Simplex method
• Feasible solution, optimality conditions
• Iterative solution, computational procedure, LU decomposition and basis
• degeneracy
• duality, sensitivity