smolyak Package¶

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.

class smolyak.grid.SmolyakGrid(d, mu)[source]¶

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
grid	array (float, ndim=2)	This is the sparse grid that we need to build
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

plot_grid()

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

plot_grid()[source]¶

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

Parameters :	None :
Returns :	None :

smolyak.grid.a_chain(n)[source]¶

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.build_B(d, mu, grid, inds=None)[source]¶

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 grid : array (float, dims=2) The smolyak grid returned by calling build_grid(d, mu) 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 :

B : array (float, 2) The matrix B that represents the Smolyak polynomial corresponding to grid

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

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.cheby2n(x, n, kind=1.0)[source]¶

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.m_i(i)[source]¶

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.num_grid_points(d, mu)[source]¶

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.phi_chain(n)[source]¶

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.poly_inds(d, mu, inds=None)[source]¶

Build indices specifying all the Cartesian products of Chebychev polynomials needed to build Smolyak polynomial

Parameters :	d : int The number of dimensions in grid / polynomial mu : int The parameter mu defining the density of 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 :	phi_inds : array A two dimensional array of integers where each row specifies a new set of indices needed to define a Smolyak basis polynomial

Notes

This function uses smol_inds and phi_chain. The output of this function is used by build_B to construct the B matrix

smolyak.grid.s_n(n)[source]¶

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.smol_inds(d, mu)[source]¶

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