Group-Ring Foundations¶
This chapter introduces the algebraic layer behind the optimization modules.
Algebraic Setting¶
Let \(S\) be a finitely generated commutative semigroup and let \(\mathbb{R}[S]\) denote its semigroup algebra. In Irene, elements of \(\mathbb{R}[S]\) are represented as finite sums
where \(\alpha\) is a semigroup element and \(c_\alpha \in \mathbb{R}\). This perspective generalizes classical polynomial notation and keeps support, degree, and structural operations explicit for optimization routines.
When relations are present, the algebra is effectively handled modulo those relations through reduction in the semigroup representation. This is useful for modeling quotient structures that arise naturally in symbolic formulations.
Commutative Semigroup and Semigroup Algebra¶
The module grouprings.py provides:
CommutativeSemigroup: generator-based semigroup representation.SemigroupAlgebra: algebra construction over that semigroup.AtomicSGElementandSemigroupAlgebraElement: monomial and polynomial-like elements.
This representation is used by higher layers to extract supports, exponents, and structural information required by geometric and SONC relaxations.
Support and Geometry¶
The support of \(f\) is central in both geometric and SONC constructions. By converting semigroup monomials to exponent tuples, Irene can compute Newton polytope information and barycentric relations directly from algebraic input.
This is the key bridge from symbolic algebra to convex-geometric objects used in lower-bound certificates.
Symbolic Engine: SymEngine Primary with SymPy Fallback¶
Irene uses a dual-engine design for symbolic computation, implemented in
symbolic_engine.py as the SymbolicEngine class (imported as engine).
Design Rationale. SymEngine provides a C++ backend that is significantly faster
for polynomial expansion, numeric evaluation, and matrix construction. However, it
lacks several advanced APIs required by SDP relaxation pipelines — notably Gröbner
basis computation, the full Poly API (as_dict(), domain arithmetic),
PolyMatrix/DomainMatrix, and lambdify. The dual-engine router resolves
this by attempting SymEngine first and falling back to SymPy transparently when an
operation is unsupported.
Fallback Mechanism. Every routed operation follows this pattern:
Attempt the SymEngine C++ path (e.g.,
se.expand(),se.DenseMatrix).On
AttributeError,NotImplementedError, orLibExpressionException, cast all SymEngine inputs to SymPy viato_sympy()and call the native SymPy equivalent.Return the result (SymPy objects are accepted downstream; no forced cast-back).
The to_sympy() helper short-circuits when the input is already a SymPy object,
avoiding redundant tree conversions. The fallback_log attribute records which
calls fell back, and engine.fallback_stats() returns per-operation counts for
profiling.
Performance Profile. Instrumented traces show that SymEngine handles the bulk of
expand/matrix/symbol operations, while Gröbner basis, Poly, and lambdify
always route to SymPy (these APIs simply do not exist in SymEngine). The net effect
is faster polynomial manipulation with no loss of advanced algebraic functionality.
Usage Pattern. Existing modules import the unified engine rather than raw SymPy/SymEngine:
from Irene.symbolic_engine import engine
x = engine.Symbol('x')
expr = engine.expand((x + 1)**2) # SymEngine C++ expand
g = engine.groebner([f1, f2], x) # auto-fallback to SymPy
p = engine.Poly(expr, x) # SymPy Poly (SymEngine lacks this)
This pattern ensures that all symbolic code in Irene benefits from the dual-engine routing without importing either backend directly.
Selecting the Symbolic Backend. Users can choose between SymEngine and pure SymPy at runtime, either programmatically or via the environment:
# Programmatic selection (applies to the default `engine` singleton):
from Irene.symbolic_engine import engine, set_symbolic_backend, get_symbolic_backend
set_symbolic_backend('symengine') # or 'sympy' / 'auto'
assert get_symbolic_backend() == 'symengine'
# Environment variable (read once at import time):
# IRENE_SYMBOLIC_BACKEND=symengine python3 my_script.py
# IRENE_SYMBOLIC_BACKEND=sympy python3 my_script.py
# IRENE_SYMBOLIC_BACKEND=auto python3 my_script.py (default)
Accepted values: symengine (default when installed), sympy, and
auto (prefer SymEngine when available, else SymPy). When symengine is
not installed the engine automatically runs in SymPy mode and
engine.available_backends() reports ['sympy']; installing the package
with the optional extra pip install .[symengine] enables the C++ backend.
Operations that only exist in SymPy (Gröbner basis, Poly, lambdify,
DomainMatrix) are backend-independent and always run on SymPy.
Differential Operators¶
Beyond static algebraic representation, SemigroupAlgebra supports derivations.
Given a base map, derivatives are propagated through expressions using product-rule behavior.
For factors \(u\) and \(v\), the implementation follows:
This enables a workflow where optimization is not only over algebraic objects, but also over structures enriched with differential operators.
In code, the derivative path is organized as:
SemigroupAlgebra.add_derivativeregisters a derivation map.SemigroupAlgebra.derivativeselects a registered derivation by index.SemigroupAlgebra.diffapplies recursive product-rule expansion.
This method-level design makes differentiation explicit and extensible for problem formulations where algebraic structure and operator behavior are coupled.
Multiple Derivation Support. The derivatives attribute is a list, so the
algebra can carry several independent derivation operators simultaneously. Each call
to add_derivative(base_map) appends a new map at index len(derivatives).
The derivative(expr, idx) method then selects operator idx by position:
where each \(d_i\) is registered independently via its own base map on the generators. This supports systems with up to ~10 derivation generators (sufficient for holonomic function representations and multi-variable differential constraints).
Notation. The derivation operators \(d_x\), \(d_y\), etc., are linear maps
on the semigroup algebra satisfying Leibniz rules. They are not Leibniz fractions
(\(dy/dx\) is notation for a ratio of differentials; \(d_x\) is an operator).
In code, derivative(expr, 0) applies the first registered derivation (e.g.,
\(d_x\)), while derivative(expr, 1) applies the second (e.g., \(d_y\)).
From a theoretical viewpoint, derivations are linear maps
\(D: \mathbb{R}[S] \to \mathbb{R}[S]\) that satisfy Leibniz rules. Irene’s
add_derivative and diff pipeline implements this behavior directly on
semigroup-algebra elements.
Formal Lie Prolongations and Multi-Derivation Framework¶
The derivation framework generalizes naturally to a system of commuting derivation operators \(D_1, \dots, D_m : \mathbb{R}[S] \to \mathbb{R}[S]\), each satisfying the Leibniz rule
These operators generate an operator semigroup \(\Theta = \langle\delta_1, \dots, \delta_m\rangle\) where each \(\delta_i\) is a formal derivation symbol. The jet space of the algebra is the set
where \(y_1, \dots, y_n\) are the original semigroup generators. An element \(\theta y_j\) represents the result of applying the differential operator \(\theta\) to \(y_j\).
The multi-derivation rule acts on products of jet-space elements via the multi-index Leibniz formula:
This formulation is the algebraic backbone of differential SDP (DSDP): applying the \(D_i\) to a set of algebraic differential relations \(\mathcal{F}\) programmatically constructs the truncated differential ideal
without symbolic expression tree traversal. The resulting quotient algebra \(\mathbb{R}[S]/\mathcal{I}_{\le 2d}\) is then used as the monomial basis for the moment matrix in the differential SDP hierarchy — see Differential SDP and Mean Relaxations.
Implementation Status. The current grouprings.py implementation
supports single-derivation operators via recursive product-rule traversal
(see the diff method). The multi-derivation operator semigroup
\(\Theta\) and the full multi-index Leibniz product rule described above
represent the natural extension required for the DSDP research track. The
existing infrastructure (derivatives list, add_derivative,
derivative with index dispatch) is designed to accommodate this
generalization.
Why This Matters for POP¶
The shift from polynomial-only notation to group-ring structures improves the connection between symbolic representation and geometric computation:
Exponent vectors are directly accessible for convex hull and delta-set routines.
Algebraic reductions remain explicit and programmatic.
The same representation supports SDP, GP, and SONC method families.