Stone's method

In numerical analysis, Stone's method, also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations. The method uses an incomplete LU decomposition, which approximates the exact LU decomposition, to get an iterative solution of the problem. The method is named after Harold S. Stone, who proposed it in 1968.

The LU decomposition is an excellent general-purpose linear equation solver. The biggest disadvantage is that it fails to take advantage of coefficient matrix to be a sparse matrix. The LU decomposition of a sparse matrix is usually not sparse, thus, for a large system of equations, LU decomposition may require a prohibitive amount of memory and number of arithmetical operations.

In the preconditioned iterative methods, if the preconditioner matrix M is a good approximation of coefficient matrix A then the convergence is faster. This brings one to idea of using approximate factorization LU of A as the iteration matrix M.

A version of incomplete lower-upper decomposition method was proposed by Stone in 1968. This method is designed for equation system arising from discretisation of partial differential equations and was firstly used for a pentadiagonal system of equations obtained while solving an elliptic partial differential equation in a two-dimensional space by a finite difference method. The LU approximate decomposition was lookedTemplate:Clarify in the same pentadiagonal form as the original matrix (three diagonals for L and three diagonals for U) as the best match of the seven possible equations for the five unknowns for each row of the matrix.

Algorithm

method stone is
    For the linear system Template:Math
    calculate incomplete Template:Math factorization of matrix Template:Math
       Template:Math
       Template:Math
       Template:Math
       Template:Math
    set a guess
       Template:Math
    while ( Template:Math ) do
       evaluate new right hand side
          Template:Math
       solve Template:Math by forward substitution
          Template:Math
       solve Template:Math by back substitution
          Template:Math
    end while

References

• - the original article
• This article incorporates text from the article Stone's_method on CFD-Wiki that is under the GFDL license.

Template:Numerical linear algebra