1 Introduction     continued...

Computational science problems can often be reduced to solving one or a sequence of the following standard linear algebra problems:

• Solving linear systems of equations: A x=b. Here A is a given n -by-n nonsingular real or complex matrix, b is a given column vector with n entries, and x is a column vector with n entries we wish to compute.
• Least squares problems: compute the x which minimizes where A is m-by-n, b is m-by-1 , and x is n-by-1. is called the 2-norm of the vector y. If m > n, so we have more equations than unknowns, the system is called overdetermined. In this case we cannot generally solve Ax=b exactly. If m < n, the system is called underdetermined, and we will have infinitely many solutions.
• Eigenvalue problems: Given an n-by-n matrix A, find an n-by-1 nonzero vector x and a scalar so that .

For example, linear equations often arise when solving ordinary or partial differential equations numerically; the linear system must be solved to advance the solution by a time step. Least squares problems arise in fitting curves or surfaces to experimental data. Eigenvalue problems arise when analyzing vibrations. There are also many important variations on these basic problems, but to keep this chapter to a reasonable length, we will concentrate on algorithms for solving systems of linear equations, and refer elsewhere for least squares and eigenvalue problems [3,4,5,6].

• continued...