The Importance of ExploitingMathematical Structure

• How do I solve the n-by-n system Ax = b?

  • No structure:
    • 2/3 n3 using Gaussian elimination [ PRAM O(n) ]
  • Symmetric Positive Definite:
    • 1/3 n3 using Cholesky
  • Bandwidth :
    • O(n2 ) using band Cholesky
  • O(n) nonzeros, O(n) condition number:
    • O(n3/2 ) using Conjugate Gradients (CG) [ PRAM O(n1/2 log n) ]
  • 5 point Poisson equation on square:
    • O(n) using Multigrid (MG) [ PRAM O(log2 n) ]

Previous slide

Next slide

Back to first slide

View graphic version