CS3414 Afterclass Notes --- 18 June, 2002

1. Introduction

   • The problem Ax=b: find x, given A and b.

   • Context
     • This is a very important problem, arising in many scientific computing applications.
     • Typical computational science codes need to solve very large instances of this problem, and often many different instances of this problem.
     • An important theme in algorithms for Ax=b is exploiting structure, e.g., sparsity, symmetry, bandedness.
     • Another important theme is algorithms that are resource-aware, e.g., algorithms that use the memory hierarchy efficiently.

   • Some facts from linear algebra.
     We looked at several equivalent properties that imply that there is a unique solution. Most important for our purposes is the idea that A is nonsingular (invertible) and that Gaussian Elimination works (with the huge assumption of infinite precision).