Polynomial Base Functions
The base module provides low-level helpers for manipulating multivariate polynomial coefficient arrays.
_factorial()
The _factorial() function calculates the factorial of a non-negative integer.
_combinations()
The _combinations() function calculates the binomial coefficient C(n,k).
- hiten.algorithms.polynomial.base._combinations()[source]
Calculate the binomial coefficient C(n,k) = n! / (k! * (n-k)!).
- Parameters:
- Returns:
The number of ways to choose k items from n items, which equals n! / (k! * (n-k)!)
- Return type:
Notes
Implementation uses an optimized approach to avoid calculating full factorials, which could cause numeric overflow for large values.
_init_index_tables()
The _init_index_tables() function initializes lookup tables for polynomial multi-index encoding and decoding.
- hiten.algorithms.polynomial.base._init_index_tables()[source]
Initialize lookup tables for polynomial multi-index encoding and decoding.
This function creates two data structures essential for polynomial operations: 1. A table of combinations (psi) that counts monomials for given degrees 2. A list of packed multi-indices (clmo) that efficiently stores monomial exponents
- Parameters:
degree (int) – Maximum polynomial degree to initialize tables for
- Returns:
psi (numpy.ndarray) – 2D array where psi[i, d] contains the number of monomials of degree d in i variables. Shape is (N_VARS+1, degree+1)
clmo (numba.typed.List) – List of arrays where clmo[d] contains packed representations of all multi-indices for monomials of degree d. Each multi-index is packed into a uint32 value for efficient storage and lookup.
Notes
The packing scheme allocates 6 bits for each variable x1 through x5, with x0’s exponent implicitly determined by the total degree.
_pack_multiindex()
The _pack_multiindex() function packs the exponents k_1 through k_5 into a 32-bit integer.
- hiten.algorithms.polynomial.base._pack_multiindex()[source]
Pack the exponents k_1 through k_5 into a 32-bit integer.
- Parameters:
k (numpy.ndarray) – Array of length N_VARS containing the exponents [k_0, k_1, k_2, k_3, k_4, k_5]
- Returns:
A packed 32-bit integer where: - k[1] uses bits 0-5 - k[2] uses bits 6-11 - k[3] uses bits 12-17 - k[4] uses bits 18-23 - k[5] uses bits 24-29
- Return type:
numpy.uint32
Notes
k[0] is not included in the packed value. Each exponent uses 6 bits, limiting its maximum value to 63.
_decode_multiindex()
The _decode_multiindex() function decodes a packed multi-index from its position in the lookup table.
- hiten.algorithms.polynomial.base._decode_multiindex()[source]
Decode a packed multi-index from its position in the lookup table.
- Parameters:
- Returns:
k – Array of length N_VARS containing the exponents [k_0, k_1, k_2, k_3, k_4, k_5] where k_0 + k_1 + k_2 + k_3 + k_4 + k_5 = degree
- Return type:
Notes
The function unpacks a 32-bit integer where: - k_1 uses bits 0-5 - k_2 uses bits 6-11 - k_3 uses bits 12-17 - k_4 uses bits 18-23 - k_5 uses bits 24-29
k_0 is calculated as (degree - sum of other exponents)
_fill_exponents()
The _fill_exponents() function fills an output array with decoded exponents.
_encode_multiindex()
The _encode_multiindex() function encodes a multi-index to find its position in the coefficient array.
- hiten.algorithms.polynomial.base._encode_multiindex()[source]
Encode a multi-index to find its position in the coefficient array.
- Parameters:
k (numpy.ndarray) – Array of length N_VARS containing the exponents [k_0, k_1, k_2, k_3, k_4, k_5]
degree (int) – Degree of the monomial (should equal sum of elements in k)
encode_dict_list (numba.typed.List) – The precomputed list of dictionaries (e.g., _ENCODE_DICT_GLOBAL) mapping packed exponents (int64) to indices (int32).
- Returns:
The position of the multi-index in the coefficient array for the given degree, or -1 if the multi-index is not found.
- Return type:
Notes
This function uses a precomputed dictionary list for O(1) lookup. It packs the exponents k_1 through k_5 into a 32-bit integer (uint32), casts it to int64 for lookup, and expects an int32 index.
_make_poly()
The _make_poly() function creates a new polynomial coefficient array of specified degree.
- hiten.algorithms.polynomial.base._make_poly()[source]
Create a new polynomial coefficient array of specified degree with complex128 dtype.
- Parameters:
degree (int) – Degree of the polynomial
psi (numpy.ndarray) – Combinatorial table from _init_index_tables
- Returns:
Array of zeros with complex128 data type and size equal to the number of monomials of degree ‘degree’ in N_VARS variables
- Return type:
Notes
The size of the array is determined by psi[N_VARS, degree], which gives the number of monomials of degree ‘degree’ in N_VARS variables. All polynomials use complex128 data type for consistency.
_create_encode_dict_from_clmo()
The _create_encode_dict_from_clmo() function creates a list of dictionaries mapping packed multi-indices to their positions.
- hiten.algorithms.polynomial.base._create_encode_dict_from_clmo()[source]
Create a list of dictionaries mapping packed multi-indices to their positions.
- Parameters:
clmo_table (numba.typed.List) – List of arrays where each array contains packed multi-indices for a specific degree
- Returns:
List of dictionaries where each dictionary maps a packed multi-index (int64) to its position (int32) in the corresponding clmo_table array
- Return type:
numba.typed.List
Notes
This is a helper function used to build the _ENCODE_DICT_GLOBAL structure. Each dictionary provides O(1) lookup time for finding the position of a multi-index in the coefficient array.