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
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three equations in ...
. 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
Harold Stuart Stone (born August 10, 1938 in St. Louis, Missouri) is an American computer scientist specializing in parallel computer architecture. He is an IEEE Fellow, and a Fellow of the Association for Computing Machinery (1993).
Education an ...
, 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 equation
In mathematics, a partial differential equation (PDE) is an equation which imposes relations between the various partial derivatives of a Multivariable calculus, multivariable function.
The function is often thought of as an "unknown" to be sol ...
s 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 looked 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
calculate incomplete factorization of matrix
set a guess
while ( ) do
evaluate new right hand side
solve by forward substitution
solve by back substitution
end while
Footnotes
References
* - the original article
*
*
*
{{Numerical linear algebra
Numerical linear algebra
Articles with example pseudocode