Stone's method

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 approximate LU decomposition to get an iterative solution of the problem. The method is named after H. L. Stone who proposed it in 1968.

The LU decomposition is an excellent general purpose linear equation solver. The biggest disadvantage is that it fail to take advantage of coefficient matrix to be a sparce matrix. The LU decomposition of a sparce matrix is usually not sparse, thus, for large system of equations, LU decomposition may require a prohibitive amount of memory and 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 us 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 H. L. 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 equation obtained while solving an Elliptic Partial differential equation in a two dimensional space by a finite difference method. The LU approximate decomposition was looked in the same pentadiagonal form as the original matrix (three diagonal for L and three diagonals for U) as the best match of the seven possible equations for the five unknowns for the each row of the matrix.

Algorithm

For the linear system Ax = b

calculate Incomplete LU factorization of matrix A

Ax = (M-N)x = (LU-N)x = b

Mx^(k+1) = Nx^(k)+b , with ||M|| >> ||N||

Mx^(k+1) = LUx^(k+1) = c^(k)

LUx^(k) = L(Ux^(k+1)) = Ly^(k) = c^(k)

set a guess

k = 0, x^(k)

r^(k)=b - Ax^(k)

while ( ||r^(k)||₂ $\geq \varepsilon$) do

evaluate new right hand side

c^(k) = Nx^(k) + b

solve Ly^(k) = c^(k) by forward substitution

y^(k) = L^-1c^(k)

solve Ux^(k+1) = y^(k) by back substitution

x^(k+1) = U^-1y^(k)

end while

---

References

• Template:Journal reference - the original article
• . ISBN 3540420746. {{cite book}}: Missing or empty |title= (help); Unknown parameter |Author= ignored (|author= suggested) (help); Unknown parameter |Publisher= ignored (|publisher= suggested) (help); Unknown parameter |Title= ignored (|title= suggested) (help); Unknown parameter |Year= ignored (|year= suggested) (help)
• {{cite book}}: Empty citation (help)
• This article incorporates text from the article Stone's_method on CFD-Wiki that is under the GFDL license.