Direct solution methods transform matrix A into a product of several other operators so that each of the resulting operators is easy to invert for a given right-hand side b. For example, the LU factorization of A generates lower and upper triangular matrices, L and U, respectively, such that .

To find , compute followed by , both of which are straightforward computations. Direct methods are usually popular because they are considered to be very reliable. This is true if the problem dimension and the condition number of A are not too large. See Matrix Computations , by Golub and Van Loan for details about error bounds.

Direct methods for dense, tridiagonal, and banded matrices are quite straightforward to implement and use the three basic steps of LU factorization as mentioned previously; they may also solve for a given right-hand side without factorization. However, for general sparse matrices, the situation is considerably more complicated; in particular, the factors L and U can become extremely dense. If pivoting is required, implementing sparse factorization can use a lot of time searching lists of numbers and creating a great deal of computational overhead.

Efficient implementations can be developed, especially for SPD and symmetric pattern, positive definite matrices. See Computer Solution of Large Sparse Positive Definite Systems, by George and Liu, for details.

The following algorithm shows the basic steps of the sparse Cholesky solver:

Structural preprocessing phase:

In this case, A is SPD, and L and D can be found such that , where L is a lower triangle with unit diagonal, and D is diagonal.

Steps 1 through 3 require only the nonzero structure of A. Therefore, if two matrices and have the same structure, these steps can be skipped for . Furthermore, if the same matrix A is used for more than one right-hand side b, step 5 can be repeated (or if all right-hand sides are available at once, they can be solved for simultaneously).

Iterative solution methods comprise a wide variety of techniques. The solvers presented in this subsection are all in the general class of preconditioned conjugate gradient (CG) methods. These methods attempt to solve by solving an equivalent system , where M is some approximation to A which is inexpensive to construct and can be easily used to compute z such that .

This is left preconditioning. It is also possible to apply the preconditioner on the right side of A or on both sides. After the preconditioner is constructed and an initial approximation, to x is given, the iterative method generates a sequence of vectors such that converges to x. Each is chosen to satisfy some orthogonality or minimization condition, or both.

Unlike direct methods, iterative methods are more special-purpose. No general, effective iterative algorithms exist for an arbitrary sparse linear system. However, for certain classes of problems, an appropriate iterative method can be used to yield an approximate solution significantly faster than direct methods. Also, iterative methods usually require less memory than direct methods, thus making them the only feasible approach for large problems. See Matrix Computations, by Golub and Van Loan, for an introduction to these methods.

The standard preconditioned CG method, shown in the following algorithm, illustrates the basic phases common to all CG type methods used in the solvers:

Preprocessing phase:

Iterative methods are very flexible. Like direct solvers, if two matrices A₁ and A₂ have the same structure, the structural preprocessing needs to be done only once. If there are multiple right-hand sides, Steps 1 through 3 can be skipped after the first right-hand side.