The choice between different methods very much depends on which of these operations one has available at a reasonable cost. We list the major ones in decreasing order of power:
e.g. as a part of an FEM (finite element method) package, but any other implementation may also be used, such as those based on multigrid or more specialized methods. It is also possible to use an iterative solver which only uses multiplication by (or and ) internally, but this may not be superior to other methods discussed below.
If, in a special purpose method, it is possible to multiply a vector by in addition to , or possibly or , depending on the situation, then a broader, more powerful class of algorithms are available.
Sometimes it is significantly cheaper to apply the operator to a set of vectors rather than just 1 vector at a time. This can happen because of memory hierarchy effects. There are algorithms to exploit this behavior.
The worst case is when the only operation we can perform is multiplication of a vector by (and possibly ). But algorithms are available in this case too.
Not only the matrix-vector operations but also the vector algebra needs special consideration. In all the algorithms that we will consider, only two different vector operations have to be applied to vectors of length , dot products and the addition of a multiple of one vector to another, axpy to use terminology from the BLAS. These operations may be implemented on distributed processors in a way that is appropriate for the application or the computer at hand. In some cases a vector is not even represented as an array of numbers, but stands for a function represented in e.g. a finite element or wavelet basis. Then user-supplied routines for dot products and axpy will replace the basic vector operations in our templates.