Differentiation, Integration & Interpolation

Numgrids provides numerical operators for differentiation, integration, and interpolation on structured grids. Each operator is available both as a class that can be reused across multiple evaluations and as a convenience function for one-off computations.

class numgrids.Diff(grid: Grid, order: int, axis_index: int | str = 0, acc: int = 4)[source]

Partial derivative operator on a numerical grid.

Automatically selects the best differentiation strategy (finite differences, FFT spectral, Chebyshev spectral, mapped Chebyshev spectral on unbounded axes, or log-scale) based on the axis type at axis_index.

Diff objects can be combined algebraically with each other, with scalars and with arrays (interpreted as multiplication operators); the result is an Operator.

Examples

>>> from numgrids import *
>>> ax = create_axis(AxisType.CHEBYSHEV, 30, 0, 1)
>>> grid = Grid(ax)
>>> d = Diff(grid, 1)      # first derivative
>>> df = d(grid.coords ** 2)    # apply to x**2
>>> L = Diff(grid, 2) - 4 * Diff(grid, 1) + 3   # an Operator

Constructor for partial derivative operator.

Parameters:
  • grid (Grid) – The numerical grid on which to apply the partial derivative.

  • order (positive int) – The order of the derivative.

  • axis_index (int or str) – The axis index (which axis in the grid), or the axis name.

  • acc (int) – The accuracy order for finite-difference based methods. Higher values use wider stencils for better accuracy. Ignored by spectral methods (Chebyshev). Default is 4.

as_matrix() → spmatrix[source]

Returns a matrix representation of the differential operator.

The data type is a scipy sparse matrix.

to_operator() → Operator[source]

Convert to a general Operator.

numgrids.diff(grid: Grid, f: NDArray, order: int = 1, axis_index: int | str = 0, acc: int = 4) → NDArray[source]

Differentiate a meshed function (with operator caching).

Creates a Diff operator on first call and caches it on the grid for subsequent calls with the same (order, axis_index, acc).

Parameters:
  • grid (Grid) – The grid on which f is defined.

  • f (NDArray) – Meshed function values with shape grid.shape.

  • order (int, optional) – Derivative order (default 1).

  • axis_index (int or str, optional) – Axis (index or name) along which to differentiate (default 0).

  • acc (int, optional) – Accuracy order for finite-difference methods (default 4).

Returns:

The derivative array, same shape as f.

Return type:

NDArray

class numgrids.Integral(grid: Grid, volume_element: bool = True)[source]

The integration operator for integrating over a grid.

\[\int_V f \, dV\]

Integration always runs over the whole grid. The integral is computed as a tensor product of one-dimensional quadrature rules, chosen per axis type:

  • Chebyshev axes: Clenshaw–Curtis quadrature (spectral accuracy),

  • periodic equidistant axes: trapezoidal rule (spectral accuracy),

  • unbounded axes (half line, whole line): the Chebyshev-type rule of the mapped points (spectral accuracy for integrands that decay fast enough),

  • other axes: weights obtained by inverting the axis’ differentiation matrix (same order of accuracy as differentiation).

On curvilinear grids (CurvilinearGrid and its subclasses) the integrand is multiplied by the volume element \(J = h_1 h_2 \cdots h_n\) by default, so that e.g. integrating 1 over a SphericalGrid yields the volume of the domain.

Examples

>>> import numpy as np
>>> from numgrids import Grid, Integral, chebyshev
>>> grid = Grid(chebyshev(20, 0, np.pi))
>>> I = Integral(grid)
>>> round(I(np.sin(grid.coords)), 10)
2.0

Constructor

Parameters:
  • grid (Grid) – The grid on which to integrate.

  • volume_element (bool) – Whether to include the volume element (Jacobian) of curvilinear grids. If False, the integral is taken in coordinate space, i.e. \(\int f\, dq_1 \cdots dq_n\). Has no effect on Cartesian grids. Default is True.

property weight_array: NDArray

Quadrature weights of all grid points, as an array of grid shape.

The integral of a meshed function f is np.sum(weight_array * f). The volume element is included (unless volume_element=False).

numgrids.integrate(grid: Grid, f: NDArray) → float[source]

Integrate a meshed function over the entire grid domain.

On curvilinear grids the volume element is included, i.e. the result is \(\int f\, dV\). The Integral operator is cached on the grid after the first call.

Parameters:
  • grid (Grid) – The grid on which f is defined.

  • f (NDArray) – Meshed function values.

Returns:

The definite integral over the grid domain.

Return type:

float

class numgrids.Interpolator(grid: Grid, f: NDArray, method: str = 'cubic')[source]

Interpolation of meshed function data on a grid.

Available methods:

  • "linear", "cubic" (default), "quintic" – spline interpolation via scipy.interpolate.RegularGridInterpolator ("quadratic" is available for 1D grids only),

  • "spectral" – interpolation that matches the axis type and keeps spectral accuracy: barycentric polynomial interpolation on Chebyshev axes, trigonometric interpolation on periodic axes, barycentric interpolation in the computational variable on unbounded axes, and high-order local polynomial interpolation on all other axes.

Periodic axes are handled correctly by all methods, including points between the last grid point and the end of the period. On unbounded axes (semi_infinite(), infinite()) all methods work in the computational variable and cover the whole domain, also beyond the outermost grid point.

Examples

>>> import numpy as np
>>> from numgrids import Grid, Interpolator, chebyshev, periodic
>>> grid = Grid(chebyshev(20, 0, 1), periodic(32, 0, 2 * np.pi))
>>> X, Y = grid.meshed_coords
>>> inter = Interpolator(grid, X ** 2 * np.cos(Y), method="spectral")
>>> value = inter((0.5, 6.25))    # also between the last point and 2*pi
>>> bool(abs(value - 0.25 * np.cos(6.25)) < 1e-12)
True

Create an interpolating function for the array data.

Call the Interpolator object like a normal function to interpolate.

Parameters:
  • grid (Grid) – The grid on which the array f is meshed.

  • f (numpy.ndarray) – The data to interpolate.

  • method (str) – One of "linear", "quadratic" (1D only), "cubic", "quintic" or "spectral".

numgrids.interpolate(grid: Grid, f: NDArray, locations, method: str = 'cubic') → NDArray[source]

Interpolate a meshed function at arbitrary locations.

Parameters:
  • grid (Grid) – The grid on which f is defined.

  • f (NDArray) – Meshed function values.

  • locations (float, tuple, list[tuple], array, zip, or Grid) – Point(s) at which to interpolate.

  • method (str) – "linear", "cubic" (default), "quintic" or "spectral". See Interpolator.

Returns:

Interpolated value(s).

Return type:

NDArray

Operator algebra and solvers

Linear operators on grids with an algebra and built-in solvers.

An Operator wraps a sparse matrix acting on functions meshed on a Grid. Operators can be combined with +, -, *, @, / and **:

  • op + c with a scalar c means op + c * I,

  • V * op with an array V of grid shape means “apply op, then multiply by V”,

  • op * V means “multiply by V, then apply op”,

  • op1 * op2 and op1 @ op2 mean composition.

Linear boundary value problems and eigenvalue problems can be solved directly with Operator.solve() and Operator.eig(). Functions of operators – fractional powers, square roots, exponentials, inverses – come from Operator.function(), Operator.power(), Operator.sqrt(), Operator.exp() and Operator.inverse().

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(30, 0, np.pi))
>>> L = grid.diff_operator(2)                     # d^2/dx^2
>>> u = L.solve(-np.sin(grid.coords), bcs=0)      # u'' = -sin(x), u(0) = u(pi) = 0
>>> bool(np.allclose(u, np.sin(grid.coords)))
True
>>> vals, vecs = (-L).eig(k=3, bcs=0)             # -u'' = lambda u
>>> np.round(vals, 6)
array([1., 4., 9.])
class numgrids.Operator(grid: Grid, matrix)[source]

A linear operator acting on meshed functions of a grid.

Parameters:
  • grid (Grid) – The grid on which the operator acts.

  • matrix (sparse matrix or array) – Square matrix of shape (grid.size, grid.size).

classmethod identity(grid: Grid) → Operator[source]

The identity operator on grid.

classmethod multiplication(grid: Grid, values) → Operator[source]

The operator “multiply by values” (a diagonal matrix).

as_matrix() → spmatrix[source]

The sparse matrix representation (CSR format).

toarray() → NDArray[source]

The matrix representation as a dense array.

property T: Operator

The transposed operator.

property H: Operator

The conjugate transposed operator (adjoint for the Euclidean inner product).

adjoint() → Operator[source]

The adjoint with respect to the \(L^2\) inner product of the grid.

\(\langle f, L g\rangle = \langle L^\dagger f, g\rangle\) with \(\langle f, g\rangle = \int \bar f g\, dV\) evaluated by the quadrature of the grid (Grid.inner), i.e. \(L^\dagger = W^{-1} L^H W\) with the diagonal matrix W of the quadrature weights. Boundary terms are part of the adjoint: operators such as the Laplacian are only self-adjoint on functions that satisfy suitable boundary conditions.

Examples

The derivative on a periodic grid is anti-self-adjoint:

>>> import numpy as np
>>> from numgrids import Grid, periodic
>>> D = Grid(x=periodic(16)).diff_operator()
>>> bool(np.allclose(D.adjoint().toarray(), -D.toarray()))
True
with_bcs(rhs=0.0, bcs=None) → tuple[spmatrix, NDArray][source]

Return the linear system (L, b) with boundary conditions applied.

Parameters:
  • rhs (float, NDArray or callable) – Right-hand side. Scalars are broadcast; callables are evaluated on the grid via evaluate().

  • bcs (see resolve_bcs()) – Boundary conditions.

Returns:

System matrix (CSC) and flattened right-hand side.

Return type:

tuple of (spmatrix, NDArray)

solve(rhs=0.0, bcs=None, method: str = 'auto') → NDArray[source]

Solve the linear problem L u = rhs subject to boundary conditions.

Parameters:
  • rhs (float, NDArray or callable) – Right-hand side. Scalars are broadcast; callables are called with the meshed coordinates (rhs(*grid.meshed_coords)).

  • bcs (optional) –

    Boundary conditions. Accepted forms (see resolve_bcs()):

    • None – no boundary conditions (e.g. fully periodic grids),

    • a scalar or callable – Dirichlet condition on all faces,

    • a dict mapping face keys ("0_low", "x_high", … or "all") to values or to Dirichlet, Neumann, Robin specs,

    • a list of bound boundary conditions (DirichletBC etc.).

  • method (str) –

    How to solve the linear system:

    • "fourier" – decouple the system by a Fourier transform along the periodic axes on which neither the operator nor the boundary conditions depend (e.g. the azimuthal angle of a disk or ball), and solve one small system per Fourier mode. By far the fastest method where it applies.

    • "dense" – dense LU factorization; faster than sparse LU for spectral discretizations of moderate size.

    • "sparse" – sparse LU factorization; best for finite differences.

    • "auto" (default) – the first of these that applies.

    To solve with many right-hand sides, use factorize().

Returns:

The solution, of shape grid.shape.

Return type:

NDArray

Examples

>>> import numpy as np
>>> from numgrids import Grid, Neumann, chebyshev
>>> grid = Grid(x=chebyshev(20, 0, 1))
>>> L = grid.diff_operator(2)
>>> u = L.solve(2, bcs={"x_low": 0, "x_high": Neumann(2)})   # u = x^2
>>> bool(np.allclose(u, grid.coords ** 2))
True
factorize(bcs=None, method: str = 'auto') → LinearSolver[source]

Factorize the linear problem L u = rhs for repeated solves.

Returns a LinearSolver: call it with a right-hand side to get the solution. The factorization is computed once, so each further solve is cheap – useful for implicit time stepping, iterations and parameter studies.

Parameters:
  • bcs – As for solve(). The boundary values are fixed.

  • method – As for solve(). The boundary values are fixed.

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(20, 0, np.pi))
>>> solver = grid.diff_operator(2).factorize(bcs=0)
>>> x = grid.coords
>>> bool(np.allclose(solver(-np.sin(x)), np.sin(x)))
True
>>> bool(np.allclose(solver(-4 * np.sin(2 * x)), np.sin(2 * x)))
True
eig(k: int = 6, bcs=None, sigma: float | complex | None = None, which: str = 'SM', dense_threshold: int = 2000, M=None, normalize: str = 'euclidean', method: str = 'auto') → tuple[NDArray, NDArray][source]

Solve the eigenvalue problem \(L u = \lambda u\) or \(L u = \lambda M u\).

Boundary conditions are treated as homogeneous (their values are ignored). Dirichlet points are eliminated from the problem, and Neumann/Robin rows turn it into a generalized eigenproblem \(L u = \lambda B u\) – so no spurious eigenvalues appear.

Parameters:
  • k (int) – Number of eigenpairs to compute (default 6).

  • bcs (optional) – Boundary conditions, in any form accepted by solve().

  • sigma (float or complex, optional) – If given, return the k eigenvalues closest to sigma.

  • which (str) – Which eigenvalues to return if sigma is not given: "SM" smallest magnitude (default), "LM" largest magnitude, "SR" smallest real part, "LR" largest real part.

  • dense_threshold (int) – Problems with at most this many unknowns are solved with dense linear algebra (robust); larger ones with sparse shift-invert Arnoldi iterations.

  • M (Operator, array, callable or scalar, optional) – Right-hand side operator of the generalized eigenvalue problem \(L u = \lambda M u\), e.g. a mass density or a weight function. An array of grid shape (or a callable evaluated on the grid) means multiplication by that function; an Operator or sparse matrix is used as is. Defaults to the identity.

  • normalize (str) – Normalization of the eigenvectors: "euclidean" (default) – unit Euclidean norm of the array of values; "l2" – unit \(L^2\) norm on the grid, \(\int |u|^2 dV = 1\) (see Grid.norm), as for wave functions; "max" – largest absolute value 1.

  • method (str) – "auto" (default) or "direct". With "auto", problems that do not depend on one or more periodic axes (e.g. the azimuthal angle of a disk or ball) are decoupled by a Fourier transform along these axes into one small eigenproblem per Fourier mode, which is much faster and gives all eigenvalues to full accuracy. "direct" always treats the problem as a whole (dense or sparse, see dense_threshold).

Returns:

  • eigenvalues (NDArray) – Shape (k,), sorted according to which / sigma. Real if all imaginary parts are negligible.

  • eigenvectors (NDArray) – Shape (k, *grid.shape); eigenvectors[i] belongs to eigenvalues[i]. Each eigenvector is normalized (see normalize) and its largest component is positive. For a real operator, eigenvectors of real eigenvalues are real, also for degenerate eigenvalues (e.g. symmetry-related modes on a disk or sphere): a degenerate eigenspace is returned as a real orthonormal basis.

Examples

A string with density \(\rho = 1/x^2\) on \([1, e]\), \(-u'' = \lambda \rho u\), has the eigenvalues \(1/4 + n^2 \pi^2\):

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(40, 1, np.e))
>>> vals, _ = (-grid.diff_operator(2)).eig(k=2, bcs=0, M=1 / grid.coords ** 2)
>>> bool(np.allclose(vals, 0.25 + np.pi ** 2 * np.array([1, 4])))
True
function(f: Callable[[NDArray], NDArray], bcs=None, *, max_size: int | None = None) → Operator[source]

The operator \(f(L)\) for a scalar function f.

\(f(L)\) has the eigenfunctions of \(L\) and the eigenvalues \(f(\lambda_n)\): with the eigenpairs \(L \varphi_n = \lambda_n \varphi_n\) subject to the boundary conditions, it maps \(u = \sum_n c_n \varphi_n\) to \(\sum_n f(\lambda_n)\, c_n \varphi_n\). See also power(), sqrt(), exp() and inverse().

Parameters:
  • f (callable) – The function. It is called with a one-dimensional array of eigenvalues (a real array if all eigenvalues are real, a complex one otherwise) and returns the array of its values, which may be complex.

  • bcs (optional) – Boundary conditions, in any form accepted by solve(). They are treated as homogeneous (their values are ignored), as in eig(). Not needed on periodic grids.

  • max_size (int, optional) – Largest size of the dense matrices to work with (default 4000); larger problems raise an error.

Returns:

\(f(L)\) on the functions that satisfy the boundary conditions. Applied to such a function, it gives \(f(L) u\) at the points without a condition and sets the boundary values such that the result satisfies the conditions: to zero for Dirichlet conditions, and for Neumann and Robin conditions to the values that follow from the condition. The values of the argument on the boundary points are not used (the matrix has zero columns there), since for a function that satisfies the conditions they follow from the other ones.

So L.function(lambda z: z, bcs) agrees with L on such functions except on the boundary points, where \(L u\) does not satisfy the conditions in general, and L.function(np.ones_like, bcs) is the projection that overwrites the boundary values such that the conditions hold. The results obey the functional calculus, L.function(f, bcs) @ L.function(g, bcs) is L.function(lambda z: f(z) * g(z), bcs). To use the result in solve(), eig() or evolve(), pass the same boundary conditions there.

Return type:

Operator

Notes

The computation needs dense matrices. If the operator and the boundary conditions are shift invariant along periodic axes – operators with constant coefficients on periodic grids, or the angles of disks, cylinders, spheres and balls – a Fourier transform along these axes leaves one small matrix per Fourier mode, and the result is a FourierOperator that is applied with fast Fourier transforms. Otherwise the matrix has the size of the grid.

The function of a matrix is evaluated with its eigendecomposition as long as the eigenvectors are well conditioned (1-norm condition number up to \(10^5\)), as for Laplacians, diffusion and Schrödinger operators. Operators further from normal, such as convection-dominated ones, are handled by the Schur-Parlett method scipy.linalg.funm(), which is less accurate for close eigenvalues; a warning tells if the estimated error is large. The named functions (power() etc.) use dedicated algorithms then.

Examples

A low-pass filter on a periodic grid, keeping the wave numbers \(|k| \le 4\) (the eigenvalues of \(-d^2/dx^2\) are \(k^2\)):

>>> import numpy as np
>>> from numgrids import Grid, periodic
>>> grid = Grid(x=periodic(64))
>>> x = grid.coords
>>> lowpass = (-grid.laplacian_operator()).function(lambda lam: lam <= 16)
>>> bool(np.allclose(lowpass(np.sin(2 * x) + np.sin(9 * x)), np.sin(2 * x)))
True
power(s: float, bcs=None, *, max_size: int | None = None) → Operator[source]

The power \(L^s\) for a real exponent s.

(-grid.laplacian_operator()).power(s, bcs=0) is the (spectral) fractional Laplacian \((-\Delta)^s\) with Dirichlet conditions. Negative exponents give powers of the inverse; where the operator has zero eigenvalues, such as the Laplacian on a periodic grid or with Neumann conditions on the whole boundary, the pseudo-inverse takes its place: the zero modes are mapped to zero, so that e.g. (-L).power(-1) solves \(-\Delta u = f\) for the part of \(f\) with zero mean and returns the solution with zero mean.

Parameters:
  • s (float) – The exponent. For a non-integer exponent the operator must not have negative eigenvalues: take the power of \(-L\) for a negative operator such as the Laplacian.

  • bcs – As for function(), which also describes the result and the numerical methods. If the eigenvectors are ill conditioned, scipy.linalg.fractional_matrix_power() is used.

  • max_size – As for function(), which also describes the result and the numerical methods. If the eigenvectors are ill conditioned, scipy.linalg.fractional_matrix_power() is used.

Examples

The fractional Poisson problem \((-d^2/dx^2)^{1/2} u = f\) on \([0, \pi]\) with \(u = 0\) at both ends:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(30, 0, np.pi))
>>> x = grid.coords
>>> L = -grid.laplacian_operator()
>>> half = L.power(0.5, bcs=0)
>>> bool(np.allclose(half(np.sin(3 * x)), 3 * np.sin(3 * x)))
True
>>> u = L.power(-0.5, bcs=0)(np.sin(3 * x))        # solves the problem ...
>>> bool(np.allclose(u, np.sin(3 * x) / 3))
True
>>> u = half.solve(np.sin(3 * x), bcs=0)           # ... and so does this
>>> bool(np.allclose(u, np.sin(3 * x) / 3))
True
sqrt(bcs=None, *, max_size: int | None = None) → Operator[source]

The square root \(L^{1/2}\): L.sqrt(bcs) @ L.sqrt(bcs) acts as L.

Same as power(0.5, bcs); scipy.linalg.sqrtm() is used if the eigenvectors are ill conditioned.

Examples

On a periodic grid, \((-d^2/dx^2)^{1/2}\) multiplies the Fourier mode \(e^{ikx}\) by \(|k|\):

>>> import numpy as np
>>> from numgrids import Grid, periodic
>>> grid = Grid(x=periodic(32))
>>> x = grid.coords
>>> root = (-grid.laplacian_operator()).sqrt()
>>> bool(np.allclose(root(np.cos(5 * x)), 5 * np.cos(5 * x)))
True
exp(t: float | complex = 1.0, bcs=None, *, max_size: int | None = None) → Operator[source]

The exponential \(e^{tL}\).

\(u(t) = e^{tL} u_0\) solves \(\partial_t u = L u\) with \(u(0) = u_0\) and homogeneous boundary conditions, so the result is the propagator over the time t. A complex t gives e.g. the propagator \(e^{-itH}\) of the Schrödinger equation as H.exp(-1j * t, bcs).

Parameters:
  • t (float or complex) – The factor in the exponent (default 1).

  • bcs – As for function(), which also describes the result and the numerical methods. If the eigenvectors are ill conditioned, scipy.linalg.expm() is used.

  • max_size – As for function(), which also describes the result and the numerical methods. If the eigenvectors are ill conditioned, scipy.linalg.expm() is used.

Examples

Heat conduction in a rod with fixed ends:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(30, 0, 1))
>>> x = grid.coords
>>> propagator = grid.laplacian_operator().exp(0.1, bcs=0)
>>> u = propagator(np.sin(np.pi * x))
>>> bool(np.allclose(u, np.exp(-0.1 * np.pi ** 2) * np.sin(np.pi * x)))
True
inverse(bcs=None, *, max_size: int | None = None) → Operator[source]

The inverse \(L^{-1}\) with homogeneous boundary conditions (Green’s operator).

L.inverse(bcs)(f) is the solution of \(L u = f\) that satisfies the homogeneous conditions, like L.solve(f, bcs) with zero boundary values. Unlike a factorization (factorize()), the inverse is an operator: it can be combined with others, and its matrix holds the discrete Green’s function. Same as power(-1, bcs), including the treatment of zero eigenvalues.

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(30, 0, 1))
>>> x = grid.coords
>>> G = grid.laplacian_operator().inverse(bcs=0)
>>> bool(np.allclose(G(np.ones(grid.shape)), x * (x - 1) / 2))     # u'' = 1
True

Functions of operators

Functions of operators: fractional powers, square roots, exponentials, inverses.

For an operator \(L\) with eigenpairs \(L \varphi_n = \lambda_n \varphi_n\) and a scalar function \(f\), the operator \(f(L)\) has the same eigenfunctions and the eigenvalues \(f(\lambda_n)\):

\[f(L)\, u = \sum_n f(\lambda_n)\, c_n\, \varphi_n \qquad \text{for} \qquad u = \sum_n c_n\, \varphi_n .\]

With \(f(\lambda) = \lambda^s\) this defines the fractional Laplacian \((-\Delta)^s\), with \(f(\lambda) = e^{t \lambda}\) the semigroup \(e^{tL}\) that solves \(u_t = L u\). The eigenfunctions depend on the boundary conditions, and so does \(f(L)\).

The functions are available as methods of Operator: function(), power(), sqrt(), exp() and inverse(). This module holds the numerical core.

Boundary conditions. The conditions are homogeneous, as in eig(). They express the values on the boundary points b through the values on the other points i: \(u_b = S u_i\) (\(S = 0\) for Dirichlet conditions). On the functions that satisfy the conditions, the operator acts as the matrix \(L_c = L_{ii} + L_{ib} S\) on the values \(u_i\), and

\[\begin{split}f(L) = \begin{pmatrix} f(L_c) & 0 \\ S f(L_c) & 0 \end{pmatrix}\end{split}\]

in the ordering \((i, b)\). The eigenvalues of \(L_c\) are those that eig() returns.

Numerical methods. Functions of matrices need dense linear algebra. Three paths keep the matrices small where the problem allows it:

  • Fourier symbol – an operator that is shift invariant along all axes (constant coefficients on a periodic grid) is diagonal in Fourier space; f is applied to its symbol.

  • Fourier blocks – if the operator and the boundary conditions are shift invariant along some periodic axes (the angles of disks, cylinders, spheres and balls), there is one small matrix per Fourier mode.

  • Dense – otherwise, one matrix for the whole problem.

In the first two cases the result is a FourierOperator, which is applied with fast Fourier transforms.

The function of each matrix comes from its eigendecomposition, \(f(A) = V f(\Lambda) V^{-1}\) (with orthonormal eigenvectors for Hermitian matrices). This is accurate as long as the eigenvectors are well conditioned, which holds for Laplacians, diffusion and Schrödinger operators also on spectral grids. For operators that are far from normal (e.g. dominated by convection), where the condition number of V exceeds \(10^5\), Schur-based algorithms take over: scipy.linalg.sqrtm(), scipy.linalg.fractional_matrix_power(), scipy.linalg.expm() and scipy.linalg.inv() for the named functions, and the Schur-Parlett method scipy.linalg.funm() for a general f.

class numgrids.funm.FourierOperator(grid: Grid, blocks: FourierBlocks, hat: NDArray, real: bool = False)[source]

An operator that is block diagonal in Fourier space.

The operator is shift invariant along one or more periodic axes of the grid. It is stored as one small matrix per Fourier mode of these axes (a single number per mode, the symbol, if it is shift invariant along all axes) and applied with fast Fourier transforms.

Functions of operators (Operator.function, power, sqrt, exp, inverse) return this type where the problem has the structure. It behaves like any other Operator. Sums, products and functions of such operators and multiples of them keep the Fourier form. Everything else (matrix, toarray, solve, eig, arithmetic with other operators or with arrays) uses the matrix, which is dense and built on first use.

Parameters:
  • grid (Grid) – The grid on which the operator acts.

  • blocks (FourierBlocks) – The Fourier decomposition along the shift-invariant axes.

  • hat (NDArray) – The matrices of the Fourier modes, shape (blocks.n_modes, blocks.n_rest, blocks.n_rest).

  • real (bool) – Whether the operator maps real functions to real functions.

Examples

>>> import numpy as np
>>> from numgrids import Grid, periodic
>>> grid = Grid(periodic(64), periodic(64))
>>> half = (-grid.laplacian_operator()).power(0.5)       # (-Laplacian)^(1/2)
>>> half
FourierOperator(grid=Grid(64, 64), modes=4096, block size=1)
>>> X, Y = grid.meshed_coords
>>> u = np.sin(3 * X) * np.cos(4 * Y)
>>> bool(np.allclose(half(u), 5 * u))
True
property matrix: csr_matrix

The matrix of the operator (dense in general; built on first use).

Linear solvers

Direct solvers for the linear systems of operators on grids.

The matrices of spectral methods are sparse only in the sense of having a tensor-product structure: along each axis they are dense. Sparse LU factorizations fill in heavily on them, so two other strategies are often much faster:

  • dense LU for moderate numbers of unknowns, and

  • Fourier decoupling: if the system does not change under shifts along one or more periodic axes (e.g. the azimuthal angle of a disk, cylinder or ball, as long as the coefficients do not depend on it), a discrete Fourier transform along these axes splits the system into small, independent systems, one per Fourier mode.

LinearSolver chooses between these and sparse LU, and keeps the factorization for solving with many right-hand sides.

Singular systems, such as a Poisson problem with Neumann conditions on the whole boundary (which determines the solution only up to a constant), are solved in the least-squares sense: if the system is consistent, the result is one of its solutions.

class numgrids.LinearSolver(operator: Operator, bcs=None, method: str = 'auto')[source]

A factorized linear boundary value problem L u = rhs.

Created by Operator.factorize. Calling the solver with a right-hand side returns the solution; the (expensive) factorization is done only once, so solving for many right-hand sides is cheap, e.g. in implicit time stepping.

Parameters:
  • operator (Operator) – The operator L.

  • bcs (optional) – Boundary conditions, in any form accepted by Operator.solve. Their values are fixed at construction.

  • method (str) – "auto" (default), "fourier", "dense" or "sparse"; see Operator.solve.

method

The method actually used.

Type:

str

Examples

Implicit Euler steps for the heat equation, with one factorization:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> grid = Grid(x=chebyshev(30, 0, 1))
>>> dt = 0.01
>>> step = (1 - dt * grid.laplacian_operator()).factorize(bcs=0)
>>> u = np.sin(np.pi * grid.coords)
>>> for _ in range(10):
...     u = step(u)
>>> bool(np.allclose(u, (1 + dt * np.pi ** 2) ** -10 * np.sin(np.pi * grid.coords)))
True
solve(rhs=0.0) → NDArray

Solve for a right-hand side (scalar, array of grid shape, or callable).

Nonlinear problems

Nonlinear boundary value problems.

solve_nonlinear() finds a solution of \(F(u) = 0\) on a grid, subject to boundary conditions, with a damped Newton method. The residual F is an ordinary function of grid-shaped arrays, written with the usual numgrids tools (grid.diff, grid.laplacian, operators, …).

continuation() follows the solutions of \(F(u, \lambda) = 0\) while the parameter \(\lambda\) changes (pseudo-arclength continuation), also around folds, where the branch turns back. It locates the folds and, on request, computes the stability of the solutions and detects the bifurcations along the branch. linear_stability() (see numgrids.stability) tells if a single solution is stable as a steady state of the evolution equation \(u_t = F(u)\).

Examples

The Bratu problem \(u'' + e^u = 0\), \(u(0) = u(1) = 0\):

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, solve_nonlinear
>>> grid = Grid(x=chebyshev(31, 0, 1))
>>> u = solve_nonlinear(grid, lambda u: grid.diff(u, 2) + np.exp(u), u0=0, bcs=0)
>>> round(float(u.max()), 8)
0.14053921
numgrids.solve_nonlinear(grid: Grid, residual: Callable, u0, bcs=None, jacobian: Callable | None = None, tol: float = 1e-10, maxiter: int = 50, verbose: bool = False)[source]

Solve the nonlinear boundary value problem \(F(u) = 0\).

A damped Newton method: each step solves the linear system \(J \, \delta u = -F(u)\) with the Jacobian \(J = \partial F / \partial u\) (boundary conditions included) and shortens the step if the residual would not decrease.

Parameters:
  • grid (Grid) – The grid.

  • residual (callable) – residual(u) returns \(F(u)\) as an array of grid shape. For coupled systems with initial guess (u0, v0, ...), residual(u, v, ...) returns a tuple of arrays. The residual is only used at interior points; on boundary points the boundary conditions take its place.

  • u0 (float, NDArray, callable, or tuple of these) – Initial guess (scalars are broadcast, callables evaluated on the grid). Newton’s method converges to the solution near the initial guess, so for problems with several solutions the guess selects the solution.

  • bcs (optional) – Boundary conditions, in any form accepted by resolve_bcs() (Dirichlet, Neumann, Robin). For coupled systems, a tuple with one specification per field (None for none); a single specification applies to every field.

  • jacobian (callable, optional) – jacobian(u) (or jacobian(u, v, ...)) returns the Jacobian \(\partial F / \partial u\) as an Operator, a sparse matrix or a dense array. For systems, return a nested list of blocks, J[i][j] = \(\partial F_i / \partial u_j\), each an Operator, matrix, array of grid shape (multiplication), scalar, or None (zero). If omitted, the Jacobian is approximated by finite differences, which costs one evaluation of the residual per grid point and Newton step: fine for small and medium grids, but an exact Jacobian is much faster for large ones.

  • tol (float) – Convergence tolerance: Newton stops when the update is smaller than tol * (1 + max|u|) (maximum norm).

  • maxiter (int) – Maximum number of Newton steps.

  • verbose (bool) – Print the residual after each step.

Returns:

The solution (a tuple for coupled systems).

Return type:

NDArray or tuple of NDArray

Raises:

NonlinearSolverError – If Newton’s method does not converge. The exception holds the last iterate and the residual history.

Examples

The Bratu problem with an exact Jacobian, written with operators:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, solve_nonlinear
>>> grid = Grid(x=chebyshev(31, 0, 1))
>>> D2 = grid.diff_operator(2)
>>> u = solve_nonlinear(grid, lambda u: D2(u) + np.exp(u), u0=0, bcs=0,
...                     jacobian=lambda u: D2 + np.exp(u))
>>> round(float(u.max()), 8)
0.14053921
exception numgrids.NonlinearSolverError(message: str, u, residuals: list[float])[source]

Raised when Newton’s method does not converge (see solve_nonlinear()).

u

The last iterate.

Type:

NDArray or tuple of NDArray

residuals

Maximum norm of the residual after each Newton step.

Type:

list of float

numgrids.continuation(grid: Grid, residual: Callable, u0, param: float, bcs=None, jacobian: Callable | None = None, *, ds: float = 0.1, max_steps: int = 100, param_range: tuple[float, float] | None = None, direction: int = 1, ds_min: float = 1e-06, ds_max: float | None = None, tol: float = 1e-10, maxiter: int = 20, callback: Callable | None = None, verbose: bool = False, stability: int | None = None, mass=None, sign: int = 1, refine: bool = True, tangent=None) → ContinuationResult[source]

Follow a branch of solutions of \(F(u, \lambda) = 0\) in the parameter.

Pseudo-arclength continuation: the branch is traced as a curve \((u(s), \lambda(s))\). Each step predicts the next point along the tangent of the curve and corrects it with Newton’s method, in the plane perpendicular to the tangent. As the parameter is an unknown like the solution, the method passes folds (turning points), where the branch turns back in the parameter and solving at a fixed parameter fails.

Parameters:
  • grid (Grid) – The grid.

  • residual (callable) – residual(u, lam) returns \(F(u, \lambda)\) as an array of grid shape, as in solve_nonlinear(), with the parameter as the last argument. For coupled systems with initial guess (u0, v0, ...), residual(u, v, ..., lam) returns a tuple of arrays.

  • u0 (float, NDArray, callable, or tuple of these) – Initial guess for the solution at the parameter param. The continuation starts from the solution that Newton’s method finds from this guess.

  • param (float) – Parameter at the start of the branch.

  • bcs (optional) – Boundary conditions, as in solve_nonlinear(). They must not depend on the parameter.

  • jacobian (callable, optional) – jacobian(u, lam) (or jacobian(u, v, ..., lam)) returns \(\partial F / \partial u\), in the forms that solve_nonlinear() accepts. If omitted, it is approximated by finite differences. The derivative with respect to the parameter always is a finite difference (one evaluation of the residual).

  • ds (float) – Step along the branch, measured in the arclength \(ds^2 = \overline{du^2} + d\lambda^2\) (mean over all grid points and fields), so the same ds resolves a branch equally on coarse and fine grids.

  • max_steps (int) – Maximum number of steps (points on the branch after the first).

  • param_range (tuple of float, optional) – (low, high): stop when the parameter leaves this interval. The last point then lies exactly on the end of the interval.

  • direction ({1, -1}) – Start towards increasing (1) or decreasing (-1) parameters.

  • ds_min (float) – Smallest step. The step is halved whenever the corrector fails; below ds_min the continuation stops with success=False.

  • ds_max (float, optional) – Largest step. The step grows again after a quickly converging corrector, up to ds_max. By default ds: the step only shrinks where the branch requires it.

  • tol (float) – Convergence tolerance of Newton’s method, as in solve_nonlinear().

  • maxiter (int) – Maximum number of Newton steps, for the first solution and for each corrector.

  • callback (callable, optional) – callback(u, lam) (or callback(u, v, ..., lam)) is called for every point of the branch. If it returns True, the continuation stops.

  • verbose (bool) – Print the parameter and the step size after each step.

  • stability (int, optional) – Compute this many leading eigenvalues of the linearization at every point of the branch (see linear_stability()), and detect the bifurcations where eigenvalues cross the imaginary axis. The result then has the attributes eigenvalues, stable and n_unstable, and bifurcations lists branch points and Hopf bifurcations besides the folds. The eigenvalues belong to the evolution equation \(u_t = F(u, \lambda)\).

  • mass (optional) – With stability: the operator \(M\) of the evolution equation \(M u_t = F(u, \lambda)\), as in linear_stability().

  • sign ({1, -1}) – With stability: -1 for the evolution equation \(u_t = -F(u, \lambda)\).

  • refine (bool) – Locate the folds and the other bifurcations on the branch, to the accuracy of the solver (a few additional solves for each of them). If False, they are only interpolated between the points of the branch.

  • tangent (NDArray or tuple of NDArray, optional) – Branch switching: start from u0 at param along this direction in the solution (fields like u0) instead of along the parameter; direction selects the side. For a branch point bp detected on another branch, u0=bp.u, param=bp.param, tangent=bp.mode follows the branch that bifurcates there. u0 is taken as the solution at param without correcting it (the Jacobian is singular at a branch point).

Returns:

The branch: parameters params, solutions u, the indices folds of the turning points with their accurate parameters fold_params, the bifurcations, and measure(func) to reduce each solution to a number for a bifurcation diagram.

Return type:

ContinuationResult

Raises:

NonlinearSolverError – If Newton’s method does not find the first solution at param.

Notes

The continuation stays on the branch it follows, also at branch points, where several branches cross. With stability the branch points are detected, and tangent starts a continuation of the other branch.

Bifurcations are found from the eigenvalues at neighbouring points of the branch: an eigenvalue that crosses the imaginary axis and returns within one step goes unnoticed, as does one that is not among the stability leading eigenvalues at these points. In particular, n_unstable cannot exceed the number of computed eigenvalues; choose it larger than the number of unstable modes of interest. Branch switching with tangent assumes that the new branch leaves the branch point roughly along the critical mode, as at a pitchfork bifurcation.

Examples

The Bratu problem \(u'' + \lambda e^u = 0\), \(u(0) = u(1) = 0\) has solutions only up to \(\lambda_c = 3.5138...\), where the branch folds back:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, continuation
>>> grid = Grid(x=chebyshev(31, 0, 1))
>>> D2 = grid.diff_operator(2)
>>> branch = continuation(grid, lambda u, lam: D2(u) + lam * np.exp(u), u0=0, param=0,
...                       bcs=0, jacobian=lambda u, lam: D2 + lam * np.exp(u),
...                       ds=0.05, max_steps=100)
>>> len(branch), len(branch.folds)
(101, 1)
>>> round(float(branch.params[branch.folds[0]]), 2)
3.51

The fold itself lies between two points of the branch and is located accurately:

>>> round(float(branch.fold_params[0]), 8)
3.51383072

Beyond the fold, the parameter decreases again, on the upper branch of solutions:

>>> max_u = branch.measure(np.max)
>>> bool(branch.params[-1] < 3.51 and max_u[-1] > max_u[branch.folds[0]])
True

With stability=k, the k leading eigenvalues of the linearization are computed along the branch. The solutions are stable up to the fold and unstable (with one growing mode) behind it:

>>> branch = continuation(grid, lambda u, lam: D2(u) + lam * np.exp(u), u0=0, param=0,
...                       bcs=0, jacobian=lambda u, lam: D2 + lam * np.exp(u),
...                       ds=0.05, max_steps=100, stability=4)
>>> branch
ContinuationResult(101 points, parameter from 0 to 2.42244, 1 fold(s), 74 stable point(s), success=True)
>>> branch.bifurcations
[Bifurcation(fold at param = 3.513830719, between the points 73 and 74)]
>>> bool(np.all(branch.stable[:74])), int(branch.n_unstable[-1])
(True, 1)
class numgrids.ContinuationResult(params: NDArray, u: Any, success: bool, message: str, eigenvalues: NDArray | None = None, stable: NDArray | None = None, n_unstable: NDArray | None = None, bifurcations: list[Bifurcation] | None = None)[source]

Result of continuation(): a branch of solutions.

params

The parameter at the points of the branch, shape (n,), in the order in which the branch was traced.

Type:

NDArray

u

The solutions, shape (n, *grid.shape): u[k] solves the problem for params[k]. For coupled systems, a tuple with one such array per field.

Type:

NDArray or tuple of NDArray

success

False if the continuation broke down (the corrector failed even with the smallest step size). The branch up to that point is still valid.

Type:

bool

message

Why the continuation stopped.

Type:

str

eigenvalues

With stability=k: the k leading eigenvalues of the linearization at each point, shape (n, k), largest real part first (see linear_stability()). A real array if all of them are real.

Type:

NDArray, optional

stable

With stability=k: whether the solution at each point is linearly stable (all computed eigenvalues have a negative real part).

Type:

NDArray of bool, optional

n_unstable

With stability=k: the number of eigenvalues with a positive real part at each point, among the computed ones.

Type:

NDArray of int, optional

bifurcations

The bifurcations in the order in which they occur along the branch: the folds and, with stability=k, the branch points and Hopf bifurcations (see Bifurcation).

Type:

list of Bifurcation, optional

property folds: NDArray

Indices of the points where the parameter turns around.

At a fold (turning point, saddle-node bifurcation) the branch reverses its direction in the parameter: \(d\lambda / ds\) changes sign. params[folds] are the largest (or smallest) parameters among the points of the branch; the folds themselves lie between the points, see fold_params.

property fold_params: NDArray

The parameters of the folds, one for each entry of folds.

continuation() locates each fold on the branch as the point where \(d\lambda / ds = 0\), to the accuracy of the solver (not of the step ds). Without that (refine=False), the values are estimates: the extremum of a parabola through the three points of the branch around the fold.

property fold_u

The solutions at the folds, shape (len(folds), *grid.shape).

A tuple with one such array per field for coupled systems. If the folds have not been located (see fold_params), the nearest points of the branch.

measure(func: Callable) → NDArray[source]

Evaluate a function on every solution of the branch.

Parameters:

func (callable) – func(u) (or func(u, v, ...) for coupled systems) maps one solution to a number, e.g. np.max or a norm.

Returns:

func of each solution, e.g. to plot against params in a bifurcation diagram.

Return type:

NDArray

Linear stability of steady states and the bifurcations along a branch.

A steady state \(u^*\) of an evolution equation \(u_t = F(u)\) with boundary conditions is a solution of the boundary value problem \(F(u^*) = 0\), as solve_nonlinear() finds it. A small perturbation of the steady state evolves like \(e^{\sigma t} v(x)\), where \(\sigma\) and \(v\) are an eigenvalue and an eigenfunction of the Jacobian,

\[F'(u^*) \, v = \sigma \, v ,\]

and \(v\) satisfies the homogeneous boundary conditions. The steady state is linearly stable if all eigenvalues have a negative real part. linear_stability() computes the leading eigenvalues, those with the largest real part.

Note

The sign convention is that of the evolution equation \(u_t = +F(u)\). A residual and its negative have the same solutions, but opposite stability. For a residual that is written as \(-F\), i.e. for the evolution \(u_t = -F(u)\), pass sign=-1.

Along a branch of steady states (see continuation()), the stability changes where eigenvalues cross the imaginary axis. These points are the bifurcations of the branch: folds, branch points and Hopf bifurcations, each described by a Bifurcation.

Examples

The steady state \(u = 0\) of \(u_t = u'' + a u\), \(u(0) = u(1) = 0\), is stable for \(a < \pi^2\):

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> from numgrids.stability import linear_stability
>>> grid = Grid(x=chebyshev(31, 0, 1))
>>> result = linear_stability(grid, lambda u: grid.diff(u, 2) + 5 * u, 0, bcs=0)
>>> result.stable
True
>>> bool(np.allclose(result.eigenvalues[:3], 5 - np.pi ** 2 * np.array([1, 4, 9])))
True
>>> linear_stability(grid, lambda u: grid.diff(u, 2) + 12 * u, 0, bcs=0)
StabilityResult(unstable, 1 unstable mode, growth rate 2.1304)
numgrids.linear_stability(grid: Grid, residual: Callable, u, bcs=None, jacobian: Callable | None = None, *, k: int = 6, mass=None, sign: int = 1, param: float | None = None, tol: float = 1e-08, sigma: float = 0.0) → StabilityResult[source]

Linear stability of a steady state of \(u_t = F(u)\).

Computes the leading eigenvalues \(\sigma\) of the Jacobian \(F'(u)\), restricted to perturbations that satisfy the homogeneous boundary conditions. Perturbations of the steady state grow like \(e^{\sigma t}\): the state is stable if all eigenvalues have a negative real part.

The arguments follow solve_nonlinear(), so that the residual, the boundary conditions and the Jacobian of the solve can be passed on unchanged.

Note

The eigenvalues belong to the evolution equation \(u_t = +F(u)\) (or \(M u_t = F(u)\) with mass). If the residual is the negative of the right-hand side of the evolution equation, pass sign=-1.

Parameters:
  • grid (Grid) – The grid.

  • residual (callable) – residual(u) returns \(F(u)\) as an array of grid shape; for coupled systems, residual(u, v, ...) returns a tuple of arrays.

  • u (float, NDArray, callable, or tuple of these) – The steady state, e.g. the result of solve_nonlinear(); a tuple for coupled systems. It is not checked that u solves \(F(u) = 0\).

  • bcs (optional) – Boundary conditions, as in solve_nonlinear(). Perturbations satisfy their homogeneous form (e.g. they vanish where the solution is prescribed).

  • jacobian (callable, optional) – jacobian(u) (or jacobian(u, v, ...)) returns the Jacobian, as in solve_nonlinear() (a nested list of blocks for systems). If omitted, it is approximated by finite differences.

  • k (int) – Number of eigenvalues to compute.

  • mass (optional) – The operator \(M\) in front of the time derivative, \(M u_t = F(u)\); the identity by default. A scalar or an array of grid shape (multiplication), an Operator or a matrix. For coupled systems, a tuple with one such entry per field (0 for an equation without time derivative, e.g. an algebraic constraint) or a nested list of blocks like the Jacobian.

  • sign ({1, -1}) – -1 for the evolution equation \(u_t = -F(u)\).

  • param (float, optional) – If given, the residual and the Jacobian are called with this parameter as their last argument, as in continuation().

  • tol (float) – Eigenvalues with a real part of at most tol in absolute value count as zero: the state then is neither stable nor is the mode counted as unstable.

  • sigma (float) – Only for large problems (more than 2000 unknowns), which are solved with shift-invert Arnoldi iterations: the eigenvalues closest to sigma are computed, and the k with the largest real part are returned. The default 0 finds the eigenvalues that decide on stability unless some lie far from the origin.

Returns:

The eigenvalues (largest real part first), the eigenfunctions, stable, growth_rate and n_unstable.

Return type:

StabilityResult

Examples

The Bratu problem \(u_t = u'' + \lambda e^u\), \(u(0) = u(1) = 0\) has two steady states for \(\lambda = 1\). The small one is stable, the large one unstable:

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, solve_nonlinear
>>> from numgrids.stability import linear_stability
>>> grid = Grid(x=chebyshev(31, 0, 1))
>>> x = grid.coords
>>> F = lambda u: grid.diff(u, 2) + np.exp(u)
>>> lower = solve_nonlinear(grid, F, 0, bcs=0)
>>> upper = solve_nonlinear(grid, F, 4 * np.sin(np.pi * x), bcs=0)
>>> linear_stability(grid, F, lower, bcs=0)
StabilityResult(stable, growth rate -8.7397)
>>> result = linear_stability(grid, F, upper, bcs=0)
>>> result.stable, result.n_unstable
(False, 1)
>>> result.eigenfunctions.shape
(6, 31)
class numgrids.StabilityResult(eigenvalues: NDArray, eigenfunctions: Any, stable: bool, growth_rate: float, n_unstable: int)[source]

Result of linear_stability().

eigenvalues

The leading eigenvalues \(\sigma\), largest real part first. Perturbations grow like \(e^{\sigma t}\). A real array if all of them are real. Complex eigenvalues come in conjugate pairs, the one with the positive imaginary part first.

Type:

NDArray

eigenfunctions

The eigenfunctions, shape (k, *grid.shape): eigenfunctions[j] belongs to eigenvalues[j]. For coupled systems, a tuple with one such array per field. They satisfy the homogeneous boundary conditions, have unit Euclidean norm (over all fields) and a positive largest component.

Type:

NDArray or tuple of NDArray

stable

True if all eigenvalues have a negative real part.

Type:

bool

growth_rate

The largest real part: the rate at which a generic perturbation grows in the long run (decays, if negative).

Type:

float

n_unstable

Number of eigenvalues with a positive real part, among the computed ones.

Type:

int

class numgrids.Bifurcation(kind: str, param: float, index: int, u: Any, mode: Any = None, frequency: float = 0.0, multiplicity: int = 1, refined: bool = True)[source]

A bifurcation on a branch of steady states (see continuation()).

kind

"fold": the branch turns back in the parameter (turning point, saddle-node bifurcation); a real eigenvalue is zero there. "branch_point": a real eigenvalue crosses zero away from a fold; another branch of steady states crosses (transcritical or pitchfork bifurcation). "hopf": a complex conjugate pair of eigenvalues crosses the imaginary axis; a branch of oscillations starts.

Type:

str

param

The parameter at the bifurcation.

Type:

float

index

The bifurcation lies between the points index and index + 1 of the branch.

Type:

int

u

The steady state at the bifurcation. At a branch point, where two branches of solutions cross, it is only determined up to a small multiple (about 1e-6) of the critical mode.

Type:

NDArray or tuple of NDArray

mode

The critical eigenfunction, normalized as in StabilityResult (complex at a Hopf bifurcation). At a branch point, the new branch leaves along this direction.

Type:

NDArray or tuple of NDArray, optional

frequency

Angular frequency \(\omega\) of the oscillation that sets in at a Hopf bifurcation (the eigenvalues are \(\pm i \omega\)); zero otherwise.

Type:

float

multiplicity

Number of eigenvalues that cross together (more than one for degenerate eigenvalues, e.g. symmetry-related modes on a square).

Type:

int

refined

True if the bifurcation was located by solving for points on the branch: the parameter then is as accurate as the solutions and their eigenvalues, whatever the step of the continuation. False if it is only interpolated between the two neighbouring points of the branch.

Type:

bool

Spectral coefficients

Spectral coefficients, resolution diagnostics and filtering.

On a spectral axis a meshed function is, besides its values at the grid points, a sum of basis functions: complex exponentials on periodic axes and Chebyshev polynomials on Chebyshev axes and on the axes for unbounded domains. The coefficients of this expansion tell how well the function is represented on the grid. For a smooth function they decay rapidly; the function is resolved as soon as the coefficients of the highest modes are negligible. Coefficients that are still large at the end of the spectrum mean that the grid is too coarse.

This module provides

All of them are available as methods of Grid.

Expansions

axis

expansion

periodic

\(f(x) = \sum_k c_k\, e^{i \kappa_k x}\), \(\kappa_k = 2\pi k / P\)

Chebyshev

\(f(x) = \sum_k a_k\, T_k(\xi)\), \(\xi = (2x - a - b)/(b - a)\)

semi-infinite, infinite

\(f(x) = \sum_k a_k\, T_k(\xi(x))\) with the computational variable \(\xi\) of the axis

radial (through the origin)

Chebyshev series in \(\xi = s/R\) on the diameter \(-R \le s \le R\)

colatitude (through the poles)

Fourier series in \(\theta\) on the great circle \(0 \le \theta < 2\pi\)

equidistant (not periodic), logarithmic

none: finite differences have no spectral expansion

Fourier coefficients are stored in the order of numpy.fft.fftfreq() (mode numbers \(0, 1, \ldots, -2, -1\)) and are normalized such that \(|c_k|\) is the amplitude of the mode: \(c_0\) is the mean value, and a real oscillation \(A\cos(\kappa_k x + \varphi)\) contributes \(\tfrac{A}{2} e^{\pm i\varphi}\) to \(c_{\pm k}\). The phases refer to the coordinate \(x\) itself, not to the first grid point. For an even number of points \(n\), the entry at index \(n/2\) belongs to the Nyquist mode, which the grid cannot tell from its mirror image; it is the amplitude of \(\cos\bigl(\kappa_{n/2}(x - x_0)\bigr)\), which is \(\pm 1\) at the grid points.

Along a radial or colatitude axis with \(n\) points there are \(2n\) coefficients: the field is continued to the far side of the origin or the poles (as a scalar), and the coefficients are those of the function on the whole diameter or great circle.

See mode_numbers() for the mode number that belongs to each coefficient.

numgrids.spectral.coefficients(grid: Grid, f: NDArray, axis: int | str | Sequence[int | str] | None = None) → NDArray[source]

Expansion coefficients of a meshed function.

Transforms along one axis, several axes or (by default) all axes; in the last case the result holds the coefficients of the tensor-product expansion. See the module documentation for the expansion that belongs to each axis type and for the ordering and normalization of the coefficients.

Parameters:
  • grid (Grid) – The grid.

  • f (NDArray) – Meshed function of shape grid.shape (real or complex).

  • axis (int, str, sequence of those, or None) – The axis or axes to transform (default: all). The other axes keep the values at their grid points.

Returns:

The coefficients. The array has the shape of the grid, except along radial and colatitude axes, which have twice as many coefficients as points. It is complex if f is complex or a Fourier series is involved.

Return type:

NDArray

Raises:

ValueError – If one of the axes is discretized with finite differences (equidistant and not periodic, or logarithmic).

See also

from_coefficients

the inverse transform.

Examples

Chebyshev coefficients: \(2x^2 - 1 = T_2(x)\) on \([-1, 1]\).

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, periodic
>>> grid = Grid(x=chebyshev(6, -1, 1))
>>> x = grid.coords
>>> grid.coefficients(2 * x ** 2 - 1 + 0.5 * x).round(12) + 0
array([0. , 0.5, 1. , 0. , 0. , 0. ])

Fourier coefficients: \(3\cos 2x\) has \(c_{\pm 2} = 3/2\).

>>> grid = Grid(x=periodic(8))
>>> c = grid.coefficients(1 + 3 * np.cos(2 * grid.coords))
>>> c.real.round(12) + 0
array([1. , 0. , 1.5, 0. , 0. , 0. , 1.5, 0. ])
numgrids.spectral.from_coefficients(grid: Grid, c: NDArray, axis: int | str | Sequence[int | str] | None = None) → NDArray[source]

Values on the grid of a function given by its expansion coefficients.

The inverse of coefficients(): grid.from_coefficients( grid.coefficients(f, axis), axis) returns f up to round-off.

Parameters:
  • grid (Grid) – The grid.

  • c (NDArray) – The coefficients, as returned by coefficients() for the same axis argument.

  • axis (int, str, sequence of those, or None) – The axis or axes along which c holds coefficients (default: all).

Returns:

Meshed function of shape grid.shape. Along periodic and colatitude axes the result is complex; take the real part if the coefficients are those of a real function (\(c_{-k} = \bar c_k\)).

Return type:

NDArray

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, periodic
>>> grid = Grid(x=chebyshev(12, 0, 1), y=periodic(16))
>>> X, Y = grid.meshed_coords
>>> f = np.exp(X) * np.sin(Y)
>>> c = grid.coefficients(f)
>>> bool(np.allclose(grid.from_coefficients(c), f, atol=1e-13))
True

Differentiation with respect to y in coefficient space:

>>> from numgrids.spectral import mode_numbers
>>> dc = 1j * mode_numbers(grid, "y") * c
>>> bool(np.allclose(grid.from_coefficients(dc).real, np.exp(X) * np.cos(Y), atol=1e-12))
True
numgrids.spectral.mode_numbers(grid: Grid, axis: int | str = 0) → NDArray[source]

The mode number of each coefficient along an axis.

Parameters:
  • grid (Grid) – The grid.

  • axis (int or str) – Axis index or name.

Returns:

Integer array with one entry per coefficient: the degree \(k\) of \(T_k\) for Chebyshev series, and the signed mode number \(k\) of \(e^{2\pi i k x / P}\) in the order of numpy.fft.fftfreq() for Fourier series (multiply by \(2\pi/P\) to get wavenumbers).

Return type:

NDArray

Examples

>>> from numgrids import Grid, chebyshev, periodic
>>> from numgrids.spectral import mode_numbers
>>> grid = Grid(x=chebyshev(5, 0, 1), y=periodic(6))
>>> mode_numbers(grid, "x")
array([0, 1, 2, 3, 4])
>>> mode_numbers(grid, "y")
array([ 0,  1,  2, -3, -2, -1])
numgrids.spectral.resample(grid: Grid, f: NDArray, target: Grid | int | Sequence[int]) → NDArray[source]

Transfer a meshed function to a grid with other numbers of points.

The change of resolution is done in coefficient space: for more points the coefficients are padded with zeros, which is the same as spectral interpolation; for fewer points the series is truncated. A function that is resolved on both grids is transferred without loss.

Parameters:
  • grid (Grid) – The grid on which f is given.

  • f (NDArray) – Meshed function of shape grid.shape.

  • target (Grid, int or sequence of int) – The new numbers of points per axis, or a grid that differs from grid in the numbers of points only.

Returns:

The function on the new grid.

Return type:

NDArray

Raises:

ValueError – If the number of points of a finite-difference axis changes; use Grid.interpolate for those.

See also

Resolution.suggested_grid

a grid on which the function is resolved.

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> coarse, fine = Grid(x=chebyshev(16, 0, 1)), Grid(x=chebyshev(40, 0, 1))
>>> f = coarse.resample(np.exp(coarse.coords), fine)
>>> bool(np.allclose(f, np.exp(fine.coords), atol=1e-13))
True
>>> coarse.resample(np.exp(coarse.coords), 8).shape
(8,)
numgrids.spectral.resolution(grid: Grid, f: NDArray, tol: float = 1e-08) → Resolution[source]

Check whether a meshed function is resolved on its grid.

The check looks at the expansion coefficients of the function along each axis (see coefficients()); it needs neither a finer grid nor another evaluation of the function. For each axis, the magnitude of each mode is maximized over the other axes and divided by the largest one. The function is resolved along the axis if the magnitudes of the highest modes (a tenth of all, at least two) add up to less than tol. The sum of the magnitudes of all modes that a truncated series lacks bounds its error, so adding points then changes the function by no more than about tol times its size.

The number of points needed follows from the same rule. A resolved series can be chopped where the sum of the dropped modes falls below tol; the number of points is the number of modes kept plus the negligible ones required at the end. For a function that is not resolved, the decay of the spectrum is extrapolated to that point. The extrapolation assumes a geometric decay \(e^{-ck}\), as for smooth functions, unless a power law \(k^{-p}\) describes the spectrum clearly better; this is the mark of a kink or another singularity, and the number of points becomes very large. The estimate is only a guide: repeat the check on the finer grid. If the highest modes do not decay at all, no estimate is possible: the number of points is far too small, or the data contains noise or jumps.

Parameters:
  • grid (Grid) – The grid.

  • f (NDArray) – Meshed function of shape grid.shape (real or complex).

  • tol (float) – Tolerance for the highest modes, relative to the largest mode (default 1e-8). It cannot be smaller than the round-off level of the coefficients, which is taken as ten times the machine epsilon per mode.

Returns:

The verdict, with the details for each axis. Axes that are discretized with finite differences are not assessed.

Return type:

Resolution

Raises:

ValueError – If the grid has no spectral axis at all.

Notes

The rule follows the idea with which Chebfun chops Chebyshev series, in a simpler form and for a tolerance chosen by the user. Like every check that only sees the values on the grid, it can be fooled: a function that oscillates so fast that the grid takes it for a slow one (aliasing) passes as resolved.

Reference: Aurentz & Trefethen, Chopping a Chebyshev series, ACM Trans. Math. Softw. 43 (2017).

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev, periodic
>>> grid = Grid(x=chebyshev(40, -1, 1), y=periodic(16))
>>> X, Y = grid.meshed_coords
>>> grid.resolution(np.exp(X) * np.sin(Y))
Resolution at tol=1e-08: resolved
  axis x: resolved, 11 of 40 points needed
  axis y: resolved, 6 of 16 points needed

A function with a steep front in x and short waves in y is not resolved on this grid. The result suggests a finer one:

>>> func = lambda x, y: np.tanh(8 * x) * np.exp(np.sin(3 * y))
>>> result = grid.resolution(grid.evaluate(func))
>>> result.resolved, result["x"].resolved, result["y"].resolved
(False, False, False)
>>> print(result["y"])
axis y: NOT resolved, tail at 4e-02 and not decaying (16 points: too few, or the data is noisy or not smooth)
>>> finer = result.suggested_grid
>>> bool(finer.shape[0] > 100), finer.shape[1]
(True, 32)
>>> finer.resolution(finer.evaluate(func))["x"].resolved
True
numgrids.spectral.is_resolved(grid: Grid, f: NDArray, tol: float = 1e-08) → bool[source]

Whether a meshed function is resolved on its grid to the given tolerance.

Short for resolution(grid, f, tol).resolved; see resolution().

Examples

>>> import numpy as np
>>> from numgrids import Grid, chebyshev
>>> f = lambda x: 1 / (1 + 25 * x ** 2)
>>> [Grid(chebyshev(n, -1, 1)).is_resolved(f(Grid(chebyshev(n, -1, 1)).coords)) for n in (40, 80, 160)]
[False, False, True]
class numgrids.spectral.Resolution(resolved: bool, tol: float, axes: tuple[AxisResolution, ...], grid: Grid)[source]

Result of resolution(): is a meshed function resolved on its grid?

Printing the object gives a summary with one line per axis.

resolved

True if the function is resolved along all axes that can be assessed.

Type:

bool

tol

The tolerance of the assessment.

Type:

float

axes

The details for each axis. result[axis] returns the entry of an axis given by index or name.

Type:

tuple of AxisResolution

grid

The grid.

Type:

Grid

property needed: tuple[int | None, ...]

The estimated number of points needed along each axis (None where unknown).

property suggested_shape: tuple[int, ...]

Numbers of points to try next.

The estimate AxisResolution.needed where there is one, but at most four times the present number, because an estimate for an unresolved function is an extrapolation; twice the present number where the spectrum does not decay; the present number for axes that cannot be assessed.

property suggested_grid: Grid

A grid of the same type with suggested_shape points.

summary() → str[source]

The verdict and one line per axis.

plot(ax=None, **kwargs)[source]

Plot the spectrum of each axis on a logarithmic scale (requires matplotlib).

The magnitudes are relative to the largest one of each axis; the dashed line marks the tolerance. The modes are drawn as dots without a connecting line: the coefficients of even and odd functions alternate between their true size and round-off.

Parameters:
  • ax (matplotlib.axes.Axes, optional) – Axes to draw into; a new figure is created if omitted.

  • **kwargs – Passed on to ax.semilogy.

Return type:

matplotlib.axes.Axes

class numgrids.spectral.AxisResolution(axis: int, name: str | None, kind: str, num_points: int, resolved: bool | None, needed: int | None, tail: float, decay: str, rate: float, order: float, spectrum: NDArray, tol: float = 1e-08)[source]

Resolution of a function along one axis; part of a Resolution.

axis

Index of the axis.

Type:

int

name

Name of the axis.

Type:

str or None

kind

"fourier" or "chebyshev"; empty for finite-difference axes, which cannot be assessed.

Type:

str

num_points

Number of grid points of the axis.

Type:

int

resolved

Whether the highest modes are below the tolerance; None if the axis cannot be assessed.

Type:

bool or None

needed

Estimated number of points needed for the tolerance, including the modes that have to be negligible at the end. For a resolved function it is at most num_points; otherwise it is extrapolated from the decay of the spectrum, or None if the spectrum does not decay (or the axis cannot be assessed).

Type:

int or None

tail

Sum of the magnitudes of the highest modes (a tenth of all modes, at least two), relative to the largest magnitude of all modes.

Type:

float

decay

"geometric" (the normal case) or "algebraic" (if a power law describes the decay of the spectrum clearly better: the function is not smooth); "none" if an unresolved spectrum does not decay; empty if there are too few modes to tell.

Type:

str

rate

Fitted rate c of a geometric decay exp(-c k) with the mode number k (from the upper half of the decaying modes).

Type:

float

order

Fitted order p of an algebraic decay k**(-p).

Type:

float

spectrum

Magnitude of each mode number 0, 1, 2, …, maximized over the other axes. On Fourier axes mode k collects the coefficients of \(e^{\pm i\kappa_k x}\), so that the magnitude is the amplitude of a real oscillation. On radial and colatitude axes the modes are those of the whole diameter or great circle.

Type:

NDArray

tol

The tolerance of the assessment.

Type:

float

numgrids.spectral.spectral_filter(grid: Grid, f: NDArray, method: str = 'lowpass', *, keep: float | int = 0.6666666666666666, alpha: float = 36.0, order: float = 8, axis: int | str | Sequence[int | str] | None = None) → NDArray[source]

Damp or remove the high modes of a meshed function.

Available as Grid.filter. The coefficient of mode number \(k\) is multiplied by a factor \(\sigma(k)\):

  • "lowpass" – sharp truncation: \(\sigma = 1\) for the lowest modes, 0 for the others. The default keeps two thirds of the modes. This is the 2/3 rule for dealiasing: the product of two functions filtered in this way has no aliasing errors in the modes that are kept, so filtering the product again gives its exact truncation.

  • "exponential" – the smooth filter \(\sigma = \exp\bigl(-\alpha\,(k/k_{\max})^p\bigr)\). With the defaults \(\alpha = 36\), \(p = 8\) the lowest modes are practically unchanged and the highest one is damped to round-off level. This stabilizes time stepping of nonlinear equations with much less loss of accuracy than a sharp truncation.

On periodic axes \(k\) is the absolute mode number, so a real function stays real.

Filtering changes the function everywhere, in general also at the boundary points of non-periodic axes: impose boundary conditions after filtering, not before.

Parameters:
  • grid (Grid) – The grid.

  • f (NDArray) – Meshed function of shape grid.shape (real or complex).

  • method (str) – "lowpass" (default) or "exponential".

  • keep (float or int) – For "lowpass": a float in (0, 1] is the fraction of the mode numbers that is kept on each axis (default 2/3); an int is the number of mode numbers that is kept, i.e. the modes \(k = 0, \ldots, \mathtt{keep} - 1\).

  • alpha (float) – For "exponential": the strength \(\alpha \ge 0\).

  • order (float) – For "exponential": the exponent \(p > 0\). The larger it is, the more modes are left untouched.

  • axis (int, str, sequence of those, or None) – The axis or axes to filter. By default all spectral axes; finite-difference axes are left alone.

Returns:

The filtered function.

Return type:

NDArray

Raises:

ValueError – If a selected axis is discretized with finite differences, or if the grid has no spectral axis.

Examples

>>> import numpy as np
>>> from numgrids import Grid, periodic
>>> grid = Grid(x=periodic(16))
>>> x = grid.coords
>>> f = np.cos(2 * x) + 0.1 * np.cos(7 * x)
>>> bool(np.allclose(grid.filter(f), np.cos(2 * x)))           # modes 0 to 5 are kept
True
>>> smooth = grid.filter(f, "exponential")
>>> abs(grid.coefficients(smooth)[[2, 7]]).round(4)             # 0.5 and 0.05 before
array([0.4997, 0.    ])