ISLs perform a sequence of sweeps (called timesteps) through a given array. More formally, we may define ISLs as a
5-tuple (I, S, S_0, s, T) with the following meaning: • I = \prod_{i=1}^k [0, \ldots, n_i] is the index set. It defines the topology of the array. • S is the (not necessarily finite) set of states, one of which each cell may take on any given timestep. • S_0\colon \Z^k \to S defines the initial state of the system at time 0. • s \in \prod_{i=1}^l \Z^k is the stencil itself and describes the actual shape of the neighborhood. There are l elements in the stencil. • T\colon S^l \to S is the transition function which is used to determine a cell's new state, depending on its neighbors. Since
I is a
k-dimensional integer interval, the array will always have the topology of a finite regular grid. The array is also called simulation space and individual cells are identified by their index c \in I. The stencil is an ordered set of l relative coordinates. We can now obtain for each cell c the tuple of its neighbors indices I_c : I_c = \{j \mid \exists x \in s: j = c + x\} \, Their states are given by mapping the tuple I_c to the corresponding tuple of states N_i(c), where N_i\colon I \to S^l is defined as follows: : N_i(c) = (s_1, \ldots, s_l) \text{ with } s_j = S_i(I_c(j)) \, This is all we need to define the system's state for the following time steps S_{i+1}\colon \Z^k \to S with i \in \N: : S_{i+1}(c) = \begin{cases}T(N_i(c)), & c \in I\\ S_i(c), & c \in \Z^k \setminus I \end{cases} Note that S_i is defined on \Z^k and not just on I since the boundary conditions need to be set, too. Sometimes the elements of I_c may be defined by a vector addition modulo the simulation space's dimension to realize toroidal topologies: : I_c = \{j \mid \exists x \in s: j = ((c + x) \mod(n_1, \ldots, n_k))\} This may be useful for implementing
periodic boundary conditions, which simplifies certain physical models.
Example: 2D Jacobi iteration To illustrate the formal definition, we'll have a look at how a two dimensional
Jacobi iteration can be defined. The update function computes the arithmetic mean of a cell's four neighbors. In this case we set off with an initial solution of 0. The left and right boundary are fixed at 1, while the upper and lower boundaries are set to 0. After a sufficient number of iterations, the system converges against a saddle-shape. : \begin{align} I & = [0, \ldots, 99]^2 \\ S & = \R \\ S_0 &: \Z^2 \to \R \\ S_0((x, y)) & = \begin{cases} 1, & x {{multiple image | width = 100 | align = center | image_gap = 10 | footer = 2D Jacobi Iteration on a 100^2 Array | image1 = 2D_Jacobi_t_0000.png | alt1 = S_0 | caption1 = S_{0} | image2 = 2D_Jacobi_t_0200.png | alt2 = S_200 | caption2 = S_{200} | image3 = 2D_Jacobi_t_0400.png | alt3 = S_400 | caption3 = S_{400} | image4 = 2D_Jacobi_t_0600.png | alt4 = S_600 | caption4 = S_{600} | image5 = 2D_Jacobi_t_0800.png | alt5 = S_800 | caption5 = S_{800} | image6 = 2D_Jacobi_t_1000.png | alt6 = S_1000 | caption6 = S_{1000} }} ==Stencils==