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

- The
**structure of**has a large influence on the algorithm. For example, solving**A****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.