API REFERENCE/omnibias-core

omnibias.core.bell

0.5.0rc1Release candidatePython >=3.10Apache-2.0

Coefficient recurrences, activation contracts, jet algebra, and verified arithmetic shared by the numerical backends.

import omnibias.core.bell

Module contract & mathematical conventions

Bell polynomials and Faà di Bruno coefficients (pure Python).

This module supplies the combinatorial core of the *multi-layer jet composition* primitive. It is backend-agnostic (no torch / jax / numpy), in the same spirit as omnibias.core.polynomials: only integer combinatorics live here, so the torch and jax jet kernels are bit-identical by construction.

Faà di Bruno's formula expresses the n-th derivative of a composition b(t) = sigma(u(t)) in terms of the derivatives of sigma and u:

b^{(n)} = \sum_{k=1}^{n} \sigma^{(k)}\!\big(u^{(0)}\big)\, B_{n,k}\!\big(u^{(1)}, u^{(2)}, \dots, u^{(n-k+1)}\big),

where B_{n,k} is the *partial (incomplete) exponential Bell polynomial*

B_{n,k}(x_1,\dots,x_{n-k+1}) = \sum \frac{n!}{j_1!\,j_2!\cdots}\, \prod_{i\ge 1}\Big(\frac{x_i}{i!}\Big)^{j_i},

the sum taken over all non-negative integer sequences (j_i) with \sum_i j_i = k and \sum_i i\,j_i = n. Each such sequence is a partition of n into exactly k parts; its coefficient n! / \big(\prod_i (i!)^{j_i}\, j_i!\big) is an integer.

Representation

A Bell polynomial is returned as a dict mapping an *exponent tuple* e = (e_1, ..., e_n) (the exponent of x_i = u^{(i)}) to its integer coefficient. Trailing zeros are kept so every key has length n and the partial polynomials for different k share the same key space, making bell_complete a straight merge.

The heavy combinatorics are cached as immutable tuples of (exps, coeff) pairs; the public functions return fresh dict / list copies so callers may mutate them safely.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

FUNCTION

bell_complete

omnibias.core.bell_completeSource ↗

bell_complete(n: int) -> dict[ExpKey, int]

Complete exponential Bell polynomial B_n = \sum_{k} B_{n,k}.

Returns a dict keyed by exponent tuple of length n. Evaluated at x_i = 1 for all i it equals the Bell number Bell(n) (see bell_number).

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnsdict[ExpKey, int]

Executed regression · complete at ones is bell number

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_complete_at_ones_is_bell_number(n: int) -> None:
    total = sum(bell_complete(n).values())
    assert total == _BELL[n]

python -m pytest "packages/omnibias-core/tests/test_bell.py::test_complete_at_ones_is_bell_number[0]" -q

Regression example · complete is sum of partials

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_complete_is_sum_of_partials() -> None:
    for n in range(7):
        merged: dict[tuple[int, ...], int] = {}
        for k in range(n + 1):
            for key, coeff in bell_partial(n, k).items():
                merged[key] = merged.get(key, 0) + coeff
        assert merged == bell_complete(n)

python -m pytest packages/omnibias-core/tests/test_bell.py -k test_complete_is_sum_of_partials -q

Read the implementation

def bell_complete(n: int) -> dict[ExpKey, int]:
    """Complete exponential Bell polynomial :math:`B_n = \\sum_{k} B_{n,k}`.

    Returns a ``dict`` keyed by exponent tuple of length ``n``. Evaluated at
    ``x_i = 1`` for all ``i`` it equals the Bell number ``Bell(n)``
    (see :func:`bell_number`).
    """
    return dict(_bell_complete_pairs(n))

Other public import paths

• omnibias.core.bell_complete
• omnibias.core.bell.bell_complete

FUNCTION

bell_number

omnibias.core.bell_numberSource ↗

bell_number(n: int) -> int

The n-th Bell number Bell(n) = B_n(1, 1, ..., 1).

Computed by the **Bell triangle** (Aitken's array): O(n^2) exact big-integer additions. This returns the identical integer as sum(bell_complete(n).values()) but without enumerating the p(n) partition terms of the complete Bell polynomial (which is exponential in n -- p(100) ~ 1.9e8), so it stays fast for large n.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnsint

Executed regression · bell number matches known

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_bell_number_matches_known(n: int) -> None:
    assert bell_number(n) == _BELL[n]

python -m pytest "packages/omnibias-core/tests/test_bell.py::test_bell_number_matches_known[0]" -q

Regression example · bell number negative raises

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_bell_number_negative_raises() -> None:
    with pytest.raises(ValueError, match="must be >= 0"):
        bell_number(-1)

python -m pytest packages/omnibias-core/tests/test_bell.py -k test_bell_number_negative_raises -q

Read the implementation

def bell_number(n: int) -> int:
    """The ``n``-th Bell number ``Bell(n) = B_n(1, 1, ..., 1)``.

    Computed by the **Bell triangle** (Aitken's array): ``O(n^2)`` exact
    big-integer additions. This returns the identical integer as
    ``sum(bell_complete(n).values())`` but without enumerating the ``p(n)``
    partition terms of the complete Bell polynomial (which is exponential in
    ``n`` -- ``p(100) ~ 1.9e8``), so it stays fast for large ``n``.
    """
    _check_bell_order(n, MAX_BELL_NUMBER_ORDER)
    row = [1]
    for _ in range(n):
        nxt = [row[-1]]
        for value in row:
            nxt.append(nxt[-1] + value)
        row = nxt
    return row[0]

Other public import paths

• omnibias.core.bell_number
• omnibias.core.bell.bell_number

FUNCTION

bell_partial

omnibias.core.bell_partialSource ↗

bell_partial(n: int, k: int) -> dict[ExpKey, int]

Partial exponential Bell polynomial B_{n,k}.

Returns a dict mapping an exponent tuple (e_1, ..., e_n) (the exponent of x_i) to its integer coefficient. B_{0,0} = 1 (key ()); B_{n,k} = 0 (empty dict) when k > n or when exactly one of n/k is zero.

Examples

B_{n,1} is the single monomial x_n with coefficient 1; B_{n,n} is x_1^n with coefficient 1.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.
kpositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnsdict[ExpKey, int]

Executed regression · bell partial 0 0

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_bell_partial_0_0() -> None:
    assert bell_partial(0, 0) == {(): 1}

python -m pytest "packages/omnibias-core/tests/test_bell.py::test_bell_partial_0_0" -q

Regression example · bell partial zero when k gt n

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_bell_partial_zero_when_k_gt_n() -> None:
    assert bell_partial(3, 4) == {}

python -m pytest packages/omnibias-core/tests/test_bell.py -k test_bell_partial_zero_when_k_gt_n -q

Read the implementation

def bell_partial(n: int, k: int) -> dict[ExpKey, int]:
    """Partial exponential Bell polynomial :math:`B_{n,k}`.

    Returns a ``dict`` mapping an exponent tuple ``(e_1, ..., e_n)`` (the
    exponent of ``x_i``) to its integer coefficient. ``B_{0,0} = 1`` (key
    ``()``); ``B_{n,k} = 0`` (empty dict) when ``k > n`` or when exactly one of
    ``n``/``k`` is zero.

    Examples
    --------
    ``B_{n,1}`` is the single monomial ``x_n`` with coefficient 1;
    ``B_{n,n}`` is ``x_1^n`` with coefficient 1.
    """
    return dict(_bell_partial_pairs(n, k))

Other public import paths

• omnibias.core.bell_partial
• omnibias.core.bell.bell_partial

FUNCTION

faa_di_bruno_terms

omnibias.core.bell.faa_di_bruno_termsSource ↗

faa_di_bruno_terms(n: int) -> list[tuple[int, ExpKey, int]]

Faà di Bruno decomposition of the n-th composition derivative.

Returns a list of (k, exps, coeff) triples such that

(\sigma \circ u)^{(n)} = \sum (\text{coeff})\;\sigma^{(k)}(u^{(0)})\; \prod_{i=1}^{n} \big(u^{(i)}\big)^{e_i},

where exps = (e_1, ..., e_n). For n = 0 the list is empty (the zeroth "derivative" is the value sigma(u^{(0)}) itself, handled by the caller).

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnslist[tuple[int, ExpKey, int]]

Executed regression · faa di bruno textbook n3

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_faa_di_bruno_textbook_n3() -> None:
    s = [0.0, 2.0, 3.0, 4.0]
    u = [0.0, 5.0, 7.0, 11.0]
    # sigma''' u'^3 + 3 sigma'' u' u'' + sigma' u'''.
    expected = 4.0 * 5.0**3 + 3.0 * 3.0 * 5.0 * 7.0 + 2.0 * 11.0
    assert _faa_eval(s, u, 3) == expected

python -m pytest "packages/omnibias-core/tests/test_bell.py::test_faa_di_bruno_textbook_n3" -q

Regression example · compose jet matches bell oracle

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_compose_jet_matches_bell_oracle() -> None:
    rng = np.random.default_rng(11)
    order = 6
    u_jet = torch.as_tensor(rng.normal(size=(order + 1, 3)))
    sigma_tower = torch.as_tensor(rng.normal(size=(order + 1, 3)))
    out = jet_to_tower(compose_jet(u_jet, sigma_tower)).numpy()

    u_jet_np = u_jet.numpy()
    sigma_np = sigma_tower.numpy()
    u_deriv = np.array([math.factorial(i) * u_jet_np[i] for i in range(order + 1)])
    expected = np.empty_like(sigma_np)
    expected[0] = sigma_np[0]
    for n in range(1, order + 1):
        acc = np.zeros(u_jet_np.shape[1])
        for k, exps, coeff in faa_di_bruno_terms(n):
            prod = np.ones(u_jet_np.shape[1])
            for i, e in enumerate(exps, start=1):
                if e:
                    prod = prod * u_deriv[i] ** e
            acc = acc + coeff * sigma_np[k] * prod
        expected[n] = acc
    assert np.allclose(out, expected, rtol=1e-10, atol=1e-10)

python -m pytest packages/omnibias-torch/tests/test_jet.py -k test_compose_jet_matches_bell_oracle -q

Read the implementation

def faa_di_bruno_terms(n: int) -> list[tuple[int, ExpKey, int]]:
    """Faà di Bruno decomposition of the ``n``-th composition derivative.

    Returns a list of ``(k, exps, coeff)`` triples such that

    .. math::

        (\\sigma \\circ u)^{(n)}
            = \\sum (\\text{coeff})\\;\\sigma^{(k)}(u^{(0)})\\;
              \\prod_{i=1}^{n} \\big(u^{(i)}\\big)^{e_i},

    where ``exps = (e_1, ..., e_n)``. For ``n = 0`` the list is empty (the
    zeroth "derivative" is the value ``sigma(u^{(0)})`` itself, handled by the
    caller).
    """
    return list(_faa_di_bruno_pairs(n))

← Package overviewRunnable learning examples →