# Stone's method

(Difference between revisions)
 Revision as of 06:16, 27 September 2005 (view source)Zxaar (Talk | contribs)← Older edit Latest revision as of 09:42, 12 May 2007 (view source)Jola (Talk | contribs) m (7 intermediate revisions not shown) Line 1: Line 1: - == Basic Concept == + == Introduction == 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'''. 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. + 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== ==Algorithm== - :    '''A'''x = b
+ :    For the linear system '''A'''x = b
:    calculate Incomplete '''LU''' factorization of matrix '''A'''
:    calculate Incomplete '''LU''' factorization of matrix '''A'''
::    '''A'''x = ('''M'''-'''N''')x = ('''LU'''-'''N''')x = b
::    '''A'''x = ('''M'''-'''N''')x = ('''LU'''-'''N''')x = b
Line 22: Line 22: :    end while :    end while + == References == + + *{{reference-paper|author=Acosta, J.M.|year=2001|title=Numerical Algorithms for Three Dimensional Computational Fluid Dynamic Problems|rest=PhD Thesis, Polytechnic University of Catalunia}} + *{{reference-book|author=Ferziger, J.H. and Peric, M.|year=2001|title=Computational Methods for Fluid Dynamics|rest=ISBN 3540420746, 3rd Rev. Ed., Springer-Verlag, Berlin.}} + *{{reference-paper|author=Stone, H. L.|year=1968|title=Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations|rest=SIAM Journal of Numerical Analysis, 1968, vol. 5, pp. 530–538}} + + == External link == + *[http://en.wikipedia.org/wiki/Stone_method Wikipedia article on Stone method] ---- ---- + Return to [[Numerical methods | Numerical Methods]]

## Introduction

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)||2 $\ge \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

• Acosta, J.M. (2001), "Numerical Algorithms for Three Dimensional Computational Fluid Dynamic Problems", PhD Thesis, Polytechnic University of Catalunia.
• Ferziger, J.H. and Peric, M. (2001), Computational Methods for Fluid Dynamics, ISBN 3540420746, 3rd Rev. Ed., Springer-Verlag, Berlin..
• Stone, H. L. (1968), "Iterative Solution of Implicit Approximations of Multidimensional Partial Differential Equations", SIAM Journal of Numerical Analysis, 1968, vol. 5, pp. 530–538.