# 1 Introduction     continued...

A great many algorithms are available for all these problems. The choice of algorithm depends on three things:

• The structure of A has a large influence on the algorithm. For example, solving Ax=b using Gaussian elimination takes flops (floating point operations) if A is a dense matrix. If A is symmetric and positive definite, we can use the Cholesky algorithm which costs half as much: flops. If A is triangular (i.e. either zero above the diagonal or zero below the diagonal), then we can solve Ax=b in only flops by simple substitution, which is much faster. Recognizing triangularity is easy, but other structures are more subtle. For example, if A arises from solving certain elliptic partial differential equations (like Poisson's equation), then Ax=b can actually be solved in flops using multigrid, which is essentially as little work as possible.
• The desired accuracy limits which algorithms are suitable. For example, if one needs to solve Ax=b to 16 decimals of accuracy (more on what this means below), one might use a careful and expensive implementation of Gaussian elimination, but if one only needs 3 decimal digits, a few iterations of a much cheaper iterative method like conjugate gradients might suffice.
• The computer system on which one wants to solve the problem influences the algorithm choice greatly, and is the main topic of this chapter. Differences in the computer architecture, available programming languages, and compiler quality can make large differences in the way one implements a given algorithm; we saw this in Table 1 above, and will see it later as well. The computer system can influence algorithm performance so much that one would choose very different algorithms on different machines. New parallel architectures have also lead to the invention of new and interesting parallel algorithms.