algebraicElimination

Method of mdss.

Eliminate algebraic variables and their equality equations from an mdss model while preserving the implicit multilinear structure.

Source: src/model/@mdss/algebraicElimination.m

Syntax

reducedSystem = algebraicElimination(sys)
reducedSystem = algebraicElimination(sys, analysisPoints)
reducedSystem = algebraicElimination(sys, analysisPoints, Name, Value)

Description

algebraicElimination removes algebraic variables and their corresponding equality equations from an mdss model, wherever doing so keeps the model multilinear (no variable ends up squared). The result is an equivalent, smaller model in the same CP-tensor representation. Variables listed in analysisPoints are protected and never eliminated.

Two convenience guards are on by default and can leave more variables unreduced than analysisPoints alone: ProtectInequalities protects every algebraic variable that appears on an inequality/switching row, and GuardBlockGrowth skips any elimination that would grow a row of the cyclic core (so small blocks do not fuse into one large implicit loop).

Input arguments

Name-value arguments

Output arguments

Overview

The algebraic elimination algorithm removes algebraic variables and their corresponding equality equations from an mdss model, while preserving the implicit multilinear (CP-tensor) structure. The model is represented in a CP-tensor format:

$$\text{model} = \sum_k \phi(:,k) \cdot \prod_{i \in \text{supp}(F(:,k))} x_i$$

where each column $k$ of the structure matrix $F$ encodes which variables appear in that monomial term (its support), and the corresponding column $k$ of the parameter matrix $\phi$ encodes the coefficient per equation.

Two local functions implement the core logic: checkReducability determines whether a variable can safely be eliminated, and reduction performs the actual elimination.

checkReducability

Purpose

Determines whether substituting varIdx (using eqIdx) into all other equations in eqOthers preserves multilinearity — i.e. no variable ends up appearing twice in any term after substitution.

Mathematical Derivation

The substitution produces new terms by pairing each column $k$ from the other equations with each column $m$ from eqIdx. For each pair $(k, m)$, the contribution to equation $i$ is:

$$\text{reducable}(i) = \sum_k \sum_m \phi_\text{eq}(m) \cdot \phi_\text{others}(i,k) \cdot S(k,m) \cdot D(k,m)$$

where the two factor matrices are defined as:

Scalar factor $S(k,m)$ — encodes that exactly one of $(k, m)$ must involve varIdx for a valid substitution term to arise:

$$S(k,m) = (1 - |F_\text{var}(k)|) \cdot F_\text{var}(m) - F_\text{var}(k) \cdot (1 - |F_\text{var}(m)|)$$

• First term: column $k$ does not contain varIdx, column $m$ does
• Second term: column $k$ does contain varIdx, column $m$ does not
• When $S(k,m) \neq 0$, the substitution produces a valid new monomial

Dot product $D(k,m)$ — captures whether columns $k$ and $m$ share any active variable rows:

$$D(k,m) = F_\text{others}(:,k)^\top \cdot F_\text{others}(:,m)$$

$D(k,m) \neq 0$ means that after substitution, some variable would appear in both column $k$ and column $m$, creating a squared variable — a multilinearity violation.

Vectorised Form

The double sum over $(k, m)$ is a matrix triple product:

$$\text{reducable} = \underbrace{\Phi_\text{others}}_{n_\text{eq} \times n_\text{cols}} \cdot \underbrace{(S \odot D)}_{n_\text{cols} \times n_\text{cols}} \cdot \underbrace{\phi_\text{eq}^\top}_{n_\text{cols} \times 1}$$

This replaces the original entry-by-entry double loop with three BLAS matrix operations.

Result

If reducable is the zero vector, no multilinearity violation occurs and the variable is safe to eliminate:

$$\text{isReducable} = \texttt{all}(\text{reducable} = 0)$$

reduction

Purpose

Performs the actual algebraic substitution: eliminates varIdx from all equations by expressing it via eqIdx and substituting into eqOthers. Returns updated structure and parameter matrices with one fewer variable and one fewer equation.

Step 1 — Sign normalisation

The sign of eqIdx is normalised so that the coefficient of varIdx is positive. This makes the substitution direction unambiguous — varIdx is always expressed as a function of the other terms in eqIdx, not the negative.

Step 2 — Column classification

Two sets of columns are identified:

• colsContainingVar: columns whose support includes varIdx. These disappear after substitution, since varIdx is consumed.
• colsInfluencedByEqs: columns that appear in either eqIdx or eqOthers. Only these can produce new terms during substitution; all others pass through unchanged.

Step 3 — Base output construction

The base output matrices are built by:

1. Zeroing out the eqOthers rows in the parameter matrix — they will be replaced by substituted terms
2. Removing the eqIdx row entirely — it is consumed by the substitution
3. Removing columns in colsContainingVar — they are absorbed into the eliminated variable

What remains are the monomial terms unaffected by this substitution.

Step 4 — Substitution loop

For each pair of columns $(k, m)$ from the restricted matrices, the new monomial term arising from the substitution has:

Coefficient per equation $i$:

$$\phi_\text{new}(i) = \phi_\text{bar}(i,k) \cdot \phi_\text{eq}(m) \cdot S(k,m)$$

where $S(k,m)$ is the same scalar factor as in checkReducability.

Variable support — union of the supports of columns $k$ and $m$:

$$F_\text{new} = F(:,k) + F(:,m)$$

Multiple pairs $(k, m)$ may produce the same monomial support $F_\text{new}$. These are like terms whose coefficients are summed into the same output column.

Step 5 — Like-term collection via numeric hash map

Identifying like terms requires checking whether $F_\text{new}$ already exists as a column in the growing output matrix. A naive comparison scans all existing columns — O(n) per lookup.

Instead, each column is projected onto a fixed random probe vector to obtain a scalar fingerprint:

$$h_c = \text{probe}^\top \cdot F(:,c)$$

Two identical columns always produce the same scalar. Two different columns produce the same scalar only with negligible probability (floating-point collision on a random projection). A MATLAB dictionary keyed on those (plain-double) fingerprints then provides O(1) lookup:

• Miss (new support pattern): append as a new column, register its hash
• Hit (existing support pattern): accumulate the coefficient into that column

Step 6 — Row normalisation

Each equation row is scaled so its largest absolute coefficient is 1:

$$\phi_\text{new}(i,:) \leftarrow \frac{\phi_\text{new}(i,:)}{\max_k |\phi_\text{new}(i,k)|}$$

This keeps the representation numerically consistent across successive reductions.

See also

mdss · trivialReduction · determineParallizedSolvingOrder

MyToolbox Documentation | Generated automatically by CI/CD pipeline