`grid` Module¶

This file contains a class that builds a Smolyak Grid. The hope is that it will eventually contain the interpolation routines necessary so that the given some data, this class can build a grid and use the Chebychev polynomials to interpolate and approximate the data.

Method based on Judd, Maliar, Maliar, Valero 2013 (W.P)

Authors¶

Chase Coleman (ccoleman@stern.nyu.edu)
Spencer Lyon (slyon@stern.nyu.edu)

References¶

Judd, Kenneth L, Lilia Maliar, Serguei Maliar, and Rafael Valero. 2013.: “Smolyak Method for Solving Dynamic Economic Models: Lagrange Interpolation, Anisotropic Grid and Adaptive Domain”.
Krueger, Dirk, and Felix Kubler. 2004. “Computing Equilibrium in OLG: Models with Stochastic Production.” Journal of Economic Dynamics and Control 28 (7) (April): 1411-1436.

smolyak.grid.num_grid_points(d, mu)¶

Checks the number of grid points for a given d, mu combination.

Parameters:

d, mu : int

The parameters d and mu that specify the grid

Returns:

num : int

The number of points that would be in a grid with params d, mu

Notes

This function is only defined for mu = 1, 2, or 3

smolyak.grid.m_i(i)¶

Compute one plus the “total degree of the interpolating polynoimals” (Kruger & Kubler, 2004). This shows up many times in Smolyak’s algorithm. It is defined as:

\[\begin{split}m_i = \begin{cases} 1 \quad & \text{if } i = 1 \\ 2^{i-1} + 1 \quad & \text{if } i \geq 2 \end{cases}\end{split}\]

Parameters:

i : int

The integer i which the total degree should be evaluated

Returns:

num : int

Return the value given by the expression above

smolyak.grid.cheby2n(x, n, kind=1.0)¶

Computes the first \(n+1\) Chebychev polynomials of the first kind evaluated at each point in \(x\) .

Parameters:

x : float or array(float)

A single point (float) or an array of points where each polynomial should be evaluated

n : int

The integer specifying which Chebychev polynomial is the last to be computed

kind : float, optional(default=1.0)

The “kind” of Chebychev polynomial to compute. Only accepts values 1 for first kind or 2 for second kind

Returns:

results : array (float, ndim=x.ndim+1)

The results of computation. This will be an \((n+1 \times dim \dots)\) where \((dim \dots)\) is the shape of x. Each slice along the first dimension represents a new Chebychev polynomial. This dimension has length \(n+1\) because it includes \(\phi_0\) which is equal to 1 \(\forall x\)

smolyak.grid.s_n(n)¶

Finds the set \(S_n\) , which is the \(n\) th Smolyak set of Chebychev extrema

Parameters:

n : int

The index \(n\) specifying which Smolyak set to compute

Returns:

s_n : array (float, ndim=1)

An array containing all the Chebychev extrema in the set \(S_n\)

smolyak.grid.a_chain(n)¶

Finds all of the unidimensional disjoint sets of Chebychev extrema that are used to construct the grid. It improves on past algorithms by noting that \(A_{n} = S_{n}\) [evens] except for \(A_1 = \{0\}\) and \(A_2 = \{-1, 1\}\) . Additionally, \(A_{n} = A_{n+1}\) [odds] This prevents the calculation of these nodes repeatedly. Thus we only need to calculate biggest of the S_n’s to build the sequence of \(A_n\) ‘s

Parameters:

n : int

This is the number of disjoint sets from Sn that this should make

Returns:

A_chain : dict (int -> list)

This is a dictionary of the disjoint sets that are made. They are indexed by the integer corresponding

smolyak.grid.phi_chain(n)¶

For each number in 1 to n, compute the Smolyak indices for the corresponding basis functions. This is the \(n\) in \(\phi_n\)

Parameters:

n : int

The last Smolyak index \(n\) for which the basis polynomial indices should be found

Returns:

aphi_chain : dict (int -> list)

A dictionary whose keys are the Smolyak index \(n\) and values are lists containing all basis polynomial subscripts for that Smolyak index

smolyak.grid.smol_inds(d, mu)¶

Finds all of the indices that satisfy the requirement that \(d \leq \sum_{i=1}^d \leq d + \mu\).

Parameters:

d : int

The number of dimensions in the grid

mu : int or array (int, ndim=1)

The parameter mu defining the density of the grid. If an array, there must be d elements and an anisotropic grid is formed

Returns:

true_inds : array

A 1-d Any array containing all d element arrays satisfying the constraint

Notes

This function is used directly by build_grid and poly_inds

smolyak.grid.build_grid(d, mu, inds=None)¶

Use disjoint Smolyak sets to construct Smolyak grid of degree d and density parameter \(mu\)

The return value is an \(n \times d\) Array, where \(n\) is the number of points in the grid

Parameters:

d : int

The number of dimensions in the grid

mu : int

The density parameter for the grid

inds : list (list (int)), optional (default=None)

The Smolyak indices for parameters d and mu. Should be computed by calling smol_inds(d, mu). If None is given, the indices are computed using this function call

Returns:

grid : array (float, ndim=2)

The Smolyak grid for the given d, \(mu\)

smolyak.grid.build_B(d, mu, pts, b_inds=None, deriv=False)¶

Compute the matrix B from equation 22 in JMMV 2013 Translation of dolo.numeric.interpolation.smolyak.SmolyakBasic

Parameters:

d : int

The number of dimensions on the grid

mu : int or array (int, ndim=1, legnth=d)

The mu parameter used to define grid

pts : array (float, dims=2)

Arbitrary d-dimensional points. Each row is assumed to be a new point. Often this is the smolyak grid returned by calling build_grid(d, mu)

b_inds : array (int, ndim=2)

The polynomial indices for parameters a given grid. These should be computed by calling poly_inds(d, mu).

deriv : bool

Whether or not to compute the values needed for the derivative matrix B_prime.

Returns:

B : array (float, ndim=2)

The matrix B that represents the Smolyak polynomial corresponding to grid

B_Prime : array (float, ndim=3), optional (default=false)

This will be the 3 dimensional array representing the gradient of the Smolyak polynomial at each of the points. It is only returned when deriv=True

class smolyak.grid.SmolyakGrid(d, mu, lb=None, ub=None)¶

Bases: object

This class currently takes a dimension and a degree of polynomial and builds the Smolyak Sparse grid. We base this on the work by Judd, Maliar, Maliar, and Valero (2013).

Parameters:

d : int

The number of dimensions in the grid

mu : int or array(int, ndim=1, length=d)

The “density” parameter for the grid

Examples

>>> s = SmolyakGrid(3, 2)
>>> s
Smolyak Grid:
    d: 3
    mu: 2
    npoints: 25
    B: 0.65% non-zero
>>> ag = SmolyakGrid(3, [1, 2, 3])
>>> ag
Anisotropic Smolyak Grid:
    d: 3
    mu: 1 x 2 x 3
    npoints: 51
    B: 0.68% non-zero

Attributes

d	int	This is the dimension of grid that you are building
mu	int	mu is a parameter that defines the fineness of grid that we want to build
lb	array (float, ndim=2)	This is an array of the lower bounds for each dimension
ub	array (float, ndim=2)	This is an array of the upper bounds for each dimension
cube_grid	array (float, ndim=2)	The Smolyak sparse grid on the domain \([-1, 1]^d\)
grid:	array (float, ndim=2)	The sparse grid, transformed to the user-specified bounds for the domain
inds	list (list (int))	This is a lists of lists that contains all of the indices
B	array (float, ndim=2)	This is the B matrix that is used to do lagrange interpolation
B_L	array (float, ndim=2)	Lower triangle matrix of the decomposition of B
B_U	array (float, ndim=2)	Upper triangle matrix of the decomposition of B

Methods

`cube2dom`(pts)	Takes a point(s) and transforms it(them) from domain [-1, 1]^d
`dom2cube`(pts)	Takes a point(s) and transforms it(them) into the [-1, 1]^d domain
`plot_grid`()	Beautifully plots the grid for the 2d and 3d cases

cube2dom(pts)¶: Takes a point(s) and transforms it(them) from domain [-1, 1]^d back into the desired domain

dom2cube(pts)¶: Takes a point(s) and transforms it(them) into the [-1, 1]^d domain

plot_grid()¶

Beautifully plots the grid for the 2d and 3d cases

Parameters:	None :
Returns:	None :

grid Module¶

Authors¶

References¶

`grid` Module¶