View source for Stencil (numerical analysis)

[[Image:Crank-Nicolson-stencil.svg|thumb|200px|right|The [[Crank–Nicolson method|Crank–Nicolson]] stencil for a 1D problem]]
In [[mathematics]], especially the areas of [[numerical analysis]] concentrating on the [[numerical partial differential equations|numerical solution of partial differential equations]], a '''stencil''' is a geometric arrangement of a nodal group that relate to the point of interest by using a numerical approximation routine. Stencils are the basis for many algorithms to numerically solve [[partial differential equation]]s (PDE). Two examples of stencils are the [[five-point stencil]] and the [[Crank–Nicolson method]] stencil.

Stencils are classified into two categories: [[Compact stencil|compact]] and [[Non-compact stencil|non-compact]], the difference being the layers from the point of interest that are also used for calculation.

In the notation used for one-dimensional stencils n-1, n, n+1 indicate the time steps where timestep n and n-1 have known solutions and time step n+1 is to be calculated. The spatial location of finite volumes used in the calculation are indicated by j-1, j and j+1.

== Etymology ==

Graphical representations of node arrangements and their coefficients arose early in the study of PDEs. Authors continue to use varying terms for these such as "relaxation patterns", "operating instructions", "lozenges", or "point patterns".<ref>{{cite journal|last1=Emmons|first1=Howard W.|title=The numerical solution of partial differential equations|journal=Quarterly of Applied Mathematics|date=1 October 1944|volume=2|issue=3|pages=173–195|doi=10.1090/qam/10680|url=http://www.ams.org/journals/qam/1944-02-03/S0033-569X-1944-10680-3/S0033-569X-1944-10680-3.pdf|accessdate=17 April 2017|doi-access=free}}</ref><ref name=Milne>{{cite book|last1=Milne|first1=William Edmund|title=Numerical solution of differential equations.|date=1953|publisher=Wiley|pages=128–131|oclc=527661 |edition=1st|url=https://www.worldcat.org/oclc/527661|accessdate=17 April 2017|language=English}}</ref> The term "stencil" was coined for such patterns to reflect the concept of laying out a [[stencil]] in the usual sense over a computational grid to reveal just the numbers needed at a particular step.<ref name=Milne/>

== Calculation of coefficients ==

The [[finite difference coefficient]]s for a given stencil are fixed by the choice of node points. The coefficients may be calculated by taking the derivative of the [[Lagrange polynomial]] interpolating between the node points,<ref name="RBF"/> by computing the [[Taylor expansion]] around each node point and solving a linear system,<ref>{{cite web|last1=Taylor|first1=Cameron|title=Finite Difference Coefficients Calculator|url=http://web.media.mit.edu/~crtaylor/calculator.html|website=web.media.mit.edu|accessdate=9 April 2017|language=en}}</ref> or by enforcing that the stencil is exact for [[monomial]]s up to the degree of the stencil.<ref name="RBF">{{cite book|last1=Fornberg|first1=Bengt|last2=Flyer|first2=Natasha|author2-link=Natasha Flyer|title=A Primer on Radial Basis Functions with Applications to the Geosciences|date=2015|publisher=Society for Industrial and Applied Mathematics|isbn=9781611974027|url=http://epubs.siam.org/doi/book/10.1137/1.9781611974041|doi=10.1137/1.9781611974041.ch1|accessdate=9 April 2017|chapter=Brief Summary of Finite Difference Methods}}</ref> For equi-spaced nodes, they may be calculated efficiently as the [[Padé approximant]] of <math>x^s \cdot (\log x)^m</math>, where <math>m</math> is the order of the stencil and <math>s</math> is the ratio of the distance between the leftmost derivative and the left function entries divided by the grid spacing.<ref>{{cite journal|last1=Fornberg|first1=Bengt|title=Classroom Note: Calculation of Weights in Finite Difference Formulas|journal=SIAM Review|date=January 1998|volume=40|issue=3|pages=685–691|doi=10.1137/S0036144596322507|bibcode=1998SIAMR..40..685F }}</ref>

==See also==
*[[Compact stencil]]
*[[Non-compact stencil]]
*[[Five-point stencil]]
*[[Nine-point stencil]]
*[[Iterative Stencil Loops]]

== References ==
<references/>
* W. F. Spotz. [https://www.researchgate.net/profile/William_Spotz/publication/2591103_High-Order_Compact_Finite_Difference_Schemes_for_Computational_Mechanics/links/00463524456e49822a000000/High-Order-Compact-Finite-Difference-Schemes-for-Computational-Mechanics.pdf High-Order Compact Finite Difference Schemes for Computational Mechanics]. PhD thesis, University of Texas at Austin, Austin, TX, 1995.
* Communications in Numerical Methods in Engineering, Copyright © 2008 John Wiley & Sons, Ltd.

[[Category:Numerical differential equations]]