Stone's method

Stone's method also known as the Strongly implicit procedure or SIP is an alogorithm 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.

We have seen that LU decomposition is an excellent general purpose linear equation solver. The biggest disadvantage of these type of solver is they fail to take advantage of coefficient matrix. In 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 Stone (1968). This method is also called the strongly implicit procedure or SIP. This method is designed for equation system arising from discretisation of partial differential equations. This method does not apply to generic system of equations.

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 - 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.