TABLE OF CONTENTS These methods are used both to solve Ax = b and to find eigenvalues of A. They assume that A is accessible only via a "black-box" subroutine that returns y = Az given any z (and perhaps y = A Tz if A is nonsymmetric). In other words, no direct access or manipulation of matrix entries is used. This is a reasonable assumption for several reasons. First, the cheapest nontrivial operation that one can perform on a (sparse) matrix is to multiply it by a vector; if A has m nonzero entries, matrix-vector multiplication costs m multiplications and (at most) m additions. Second, A may not be represented explicitly as a matrix but may be available only as a subroutine for computing Ax.
Suppose that we have a physical device whose behavior is modeled by a program that takes a vector x of input parameters and produces a vector y of output parameters describing the device's behavior. The output y may be an arbitrarily complicated function y = f( x), perhaps requiring the solution of nonlinear differential equations. For example, x could be parameters describing the shape of a wing and f( x) could be the drag on the wing, computed by solving the Navier-Stokes equations for the airflow over the wing. A common engineering design problem is...
