View source for Stone's method

{{Multiple issues|
{{primary sources|date=October 2015}}
{{no footnotes|date=September 2013}}
}}

In [[numerical analysis]], '''Stone's method''', also known as the '''strongly implicit procedure''' or '''SIP''', is an [[algorithm]] for solving a [[sparse matrix|sparse]] [[linear system of equations]]. The method uses an [[incomplete LU factorization|incomplete LU decomposition]], which approximates the exact [[LU decomposition]], to get an [[iterative method|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 [[Random access memory|memory]] and number of [[Instruction (computer science)|arithmetical operations]].

In the [[preconditioned]] [[iterative method]]s, 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]]s and was firstly used for a [[Pentadiagonal matrix|pentadiagonal]] system of equations obtained while solving an [[Elliptic operator|elliptic]] partial differential equation in a [[two-dimensional]] space by a [[finite difference]] method. The LU approximate decomposition was looked{{Clarify|reason=vague|date=March 2016}} 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 {{math|'''A'''x {{=}} b}}
     calculate incomplete {{math|'''LU'''}} factorization of matrix {{math|'''A'''}}
        {{math|'''A'''x {{=}} ('''M'''-'''N''')x {{=}} ('''LU'''-'''N''')x {{=}} b}}
        {{math|'''M'''x<sup>(k+1)</sup> {{=}} '''N'''x<sup>(k)</sup>+b , with {{!}}{{!}}'''M'''{{!}}{{!}} >> {{!}}{{!}}'''N'''{{!}}{{!}}}}
        {{math|'''M'''x<sup>(k+1)</sup> {{=}} '''LU'''x<sup>(k+1)</sup> {{=}} c<sup>(k)</sup>}}
        {{math|'''LU'''x<sup>(k)</sup> {{=}} '''L'''('''U'''x<sup>(k+1)</sup>) {{=}} '''L'''y<sup>(k)</sup> {{=}} c<sup>(k)</sup>}}
     set a guess
        {{math|k {{=}} 0, x<sup>(k)</sup>
        r<sup>(k)</sup>{{=}}b - '''A'''x<sup>(k)</sup>}}
     '''while''' ( {{math|{{!}}{{!}}r<sup>(k)</sup>{{!}}{{!}}<sub>2</sub> ≥ ε}} ) '''do'''
        evaluate new right hand side
           {{math|c<sup>(k)</sup> {{=}} '''N'''x<sup>(k)</sup> + b}}
        solve {{math|'''L'''y<sup>(k)</sup> {{=}} c<sup>(k)</sup>}} by forward substitution
           {{math|y<sup>(k)</sup> {{=}} '''L'''<sup>−1</sup>c<sup>(k)</sup>}}
        solve {{math|'''U'''x<sup>(k+1)</sup> {{=}} y<sup>(k)</sup>}} by back substitution
           {{math|x<sup>(k+1)</sup> {{=}} '''U'''<sup>−1</sup>y<sup>(k)</sup>}}
     '''end while'''

==Footnotes==
{{Reflist}}

== References ==
* {{cite journal | author= Stone, H. L. | title= Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations | journal=SIAM Journal on Numerical Analysis | year= 1968 | volume= 5| pages= 530–538 | doi= 10.1137/0705044 | issue= 3| bibcode= 1968SJNA....5..530S | hdl= 10338.dmlcz/104038 | hdl-access= free }} - '''the original article'''
* {{cite book|author=[[Joel H. Ferziger|Ferziger, J.H.]] and Peric, M.|year=2001|title=Computational Methods for Fluid Dynamics|isbn=3-540-42074-6|publisher=Springer-Verlag, Berlin}}
* {{cite book|author=Acosta, J.M.|year=2001|title=Numerical Algorithms for Three Dimensional Computational Fluid Dynamic Problems. PhD Thesis|publisher=Polytechnic University of Catalonia}}
* {{CFDWiki|name=Stone's_method}}

{{Numerical linear algebra}}

[[Category:Numerical linear algebra]]
[[Category:Articles with example pseudocode]]