106 Rows is a Big Matrix

• Normal matrix operations are O(n3)

  • Can’t use Gaussian elimination, Jacobi, QR, …

• Almost everybody uses iterative solvers

  • Based on a fast “guess-and-check” method
  • Each iteration consists of a matrix-vector product
  • Typically converges in 10 to 100 iterations

• Popular iterative solvers:

  • Conjugate gradient (CG)
  • Bidirectional Conjugate Gradient (BiCG)
  • Generalized modified residual (GMRES)