Previous Lecture

lect05

Next Lecture

lect05, Tue 01/21

Permutation vectors and matrices, SPD matrices, Cholesky

• Lecture Files

Reading assignment

Thursday’s lecture topics are not in the NCM book. Instead, please read two sections of the Templates book: one on the Jacobi method and one on the conjugate gradient method (CG).

If you’re interested in learning more about how CG works, there’s a great paper called An introduction to the conjugate gradient method without the agonizing pain by Jonathan Shewchuk at Berkeley. Reading it is optional for CS 111, but fun if you like the math.

References for today’s lecture

NCM Problem 2.5 (Cholesky factorization) and Section 5.5 (QR factorization), and Nick Higham’s writeup of Cholesky factorization.

Outline

• More on matrix factorizations:
  • Using LU factorization with partial pivoting to solve Ax = b
  • Permutation matrices and permutation vectors
  • SPD matrices, Cholesky factorization, and Ax = b
  • Orthogonal matrices, QR factorization, and Ax = b
• Interesting matrices:
  • Permutation matrices
  • Symmetric positive definite (SPD) matrices
  • Orthogonal matrices
• numpy/scipy routines:
  • npla.norm()
  • npla.solve()
  • spla.lu()
  • npla.cholesky()
  • npla.qr()
• Lecture codes:
  • LUfactor()
  • Lsolve()
  • Usolve()
  • LUsolve()