What’s New in 0.3

symplex 0.3 is an additive release. Nothing in the public API changed signature; the CHANGELOG has the complete list, and the behaviour changes at the end of this page are the only things an upgrading program might notice.

The theme of the release is polynomials and certificates as data. 0.2 could tell you that (x + 1)² = 2(x + 1) + (x² − 1); 0.3 lets you ask for the multipliers — exactly, over ℚ, with non-negativity constraints if you need them — and hand back a proof a reader can check by expanding. Around that core sit four new public modules: poly_ex (the Poly view), linprog (exact simplex), normalforms (Hermite and Smith forms over ℤ) and optimize (deterministic f64 root finding, minimisation and fitting).

By the numbers

Measured while preparing this page (grep -c '#[test]' over src/ and tests/; wc -l over src/**/*.rs):

Polynomial views

Ex::as_poly(&[&x, &y]) (or Poly::new) views an expression as a sparse polynomial in explicit generators, with coefficients that are Ex values — exact rationals or symbolic parameters such as a + 1. Terms come back in lex-descending order (SymPy’s Poly.terms()), and you get coeff_monomial, total_degree, degree_in, degree_list, leading_coeff, all_coeffs, exact eval at any point, partial evaluation eval_gen, add/sub/mul/pow/derivative/scale, content_and_primitive, monic, nroots, and round-trips to the Gröbner-basis representation (to_multipoly / from_multipoly). Poly::monomial_basis and Poly::coefficient_matrix turn a family of polynomials into a Matrix — one row per monomial, one column per polynomial — so “find λ with goal = Σ λᵢhᵢ” becomes a call to linsolve_matrix or to the LP solver.

→ Polynomials as Data

Rational normal forms and solve output

Ex::ratsimp is a canonical form for rational expressions in all variables at once: one fraction, common factors cancelled by a multivariate GCD, integer-primitive numerator and denominator, positive leading coefficient in the denominator. Non-rational subexpressions (sin x, π, √x) are opaque indeterminates, as in SymPy’s cancel. simplify_rational now is ratsimp, and solve applies it to solutions with symbolic coefficients, so ((3r − 1)/(j + 1) − (r + 1)/(2j)).solve(&r) returns (3*j + 1)/(5*j - 1) instead of a fraction of fractions. degree, coeffs, coeff, leading_coeff and is_polynomial accept parameter coefficients. poly_is_nonnegative_on(&x, &lo, &hi) and poly_is_positive_on decide the sign of a univariate polynomial on an interval exactly (square-free decomposition + Sturm count), with endpoints that may be ±∞.

→ Algebra: ratsimp · Solving: symbolic coefficients · Sign on an interval

Exact linear programming

symplex::linprog is a two-phase dense simplex over Ratio<BigInt> with Bland’s rule (no cycling), a builder (LpProblem::maximize(c).le(row, rhs).ge(…).eq(…).bounds(j, lo, hi).free(j).solve()), a SciPy-shaped linprog, a Matrix front end linprog_matrix, and feasible_nonneg for the question “is there an x ≥ 0 with A·x = b?”. LpStatus is Optimal / Infeasible / Unbounded — none of them an error. An optimal solution carries exact shadow prices (duals, with complementary slackness and strong duality holding as identities); an infeasible one carries an exact Farkas certificate (farkas) proving that no feasible point exists. Sizes up to about 100 rows × 200 variables solve in seconds in release builds.

→ Exact Linear Programming · Cookbook: Polynomial Inequality Certificates

Integer lattices and normal forms

symplex::normalforms computes, over BigInt, the row-style Hermite normal form H = U·A (unique; hermite_normal_form_with_transform returns the unimodular U), the column-style H = A·V in SymPy’s convention (column_hermite_normal_form), the Smith normal form S = U·A·V with its invariant factors (smith_normal_form[_with_transforms]), a ℤ-basis of the integer kernel (integer_nullspace — strictly more than the rational nullspace scaled up), is_unimodular and lattice_determinant (the index of a column lattice in ℤᵐ). Matrix gained hermite_normal_form, smith_normal_form and integer_nullspace methods. Non-integer entries are an InvalidArgument, never a rounding. ntheory gained gcd_many, lcm_many, igcd, ilcm and rational_lcm_of_denominators.

→ Integer Lattices and Normal Forms

Matrix ergonomics

extract(&rows, &cols), select_rows, select_cols, delete_row, delete_col; the three-valued is_integer_matrix (next to the existing is_zero); nnz; subs_map (simultaneous substitution); and exact conversions to and from the num types — to_rational_rows, to_bigint_rows, Matrix::from_ratio, Matrix::from_bigint, Matrix::from_f64_rows (each float becomes the exact dyadic rational it denotes). These are the glue between Matrix and the LP / normal-form modules.

→ Matrices: selecting sub-matrices · Integer normal forms

Numerical optimisation and fitting

symplex::optimize: brent_root (Brent–Dekker), bisect, newton_root; nelder_mead (dimension-adaptive coefficients, NaN treated as +∞); minimize_scalar (Brent) and golden_section; differential_evolution (DE/rand/1/bin with a Nelder–Mead polish, seeded SplitMix64 — bit-identical results for the same seed); poly_fit (Householder QR, ascending coefficients — NumPy’s polyfit is highest-degree first), poly_fit_exact over ℚ, linear_fit, eval_poly, trapezoid. On Ex: find_root_bracket, minimize_numeric, minimize_scalar_numeric, minimize_global_numeric, poly_fit_points — each compiles the expression first, so a stray free symbol is a FreeSymbol error rather than a NaN. Every routine is bounded by an explicit iteration budget and never panics; the minimisers report an exhausted budget through MinimizeResult::converged so the best point is never discarded.

→ Numerical Optimisation

0.3.5: the exact matrix core

Everything numeric that used to run through the expression arena — RREF, rank, nullspace, determinant, inverse, linear solves, the integer normal forms and the simplex tableau — now runs on plain BigInt / Ratio<BigInt> storage with fraction-free algorithms. Nothing changed signature (cargo-semver-checks 223/223); the speed-ups apply to existing code automatically.

QMatrix and ZMatrix (in the prelude and in symplex::matrix) are dense row-major matrices with Ratio<BigInt> / BigInt entries: constructors (new, from_i64, from_fn, identity, zeros, diag, row_vector, col_vector, from_flat), indexing and slicing (get, try_get, row, col, submatrix, hstack, vstack), arithmetic (add, sub, matmul, scale, transpose, trace, the operators + − *) and Display/Debug in the same layout as Matrix. QMatrix computes rref, rank, nullspace, columnspace, rowspace, det, inv and solve fraction-free: rows are scaled to integers and reduced with Bareiss’s Gauss–Jordan rule, whose intermediate values are minors of the input, so all divisions are exact and no gcd runs in the inner loop. ZMatrix carries the Bareiss determinant, rank, content, the Hermite and Smith normal forms with transforms, integer_nullspace, is_unimodular and lattice_determinant. Conversions are explicit and lossless: ZMatrix::try_from(&matrix) / QMatrix::try_from(&matrix) (constant arithmetic is folded first; a symbolic entry is an error, not an approximation), to_matrix(&ctx), to_qmatrix, to_zmatrix, clear_denominators.

Matrix routes rational input through the core. Matrix::{rref, rank, nullspace, columnspace, rowspace, left_nullspace, det, inv, solve, solve_least_squares, pinv}, linsolve, linsolve_matrix and every function in symplex::normalforms detect an all-rational matrix and run on QMatrix/ZMatrix. Results are unchanged (the RREF is unique; parametric linsolve solutions print identically); only the time changes. Measured in a release build on random integer matrices with entries in [−9, 9]:

Integer-pivoting simplex. The LP tableau in symplex::linprog is now integral with a common denominator (Bareiss / Edmonds integer pivoting): each constraint row is scaled once to clear its denominators, every pivot keeps all entries integers, and the ratio and sign tests are cross-multiplied integer comparisons. The entering and leaving choices are made on the same rational values as before, so the pivot sequence is the same — on 4,000 random LPs with fractional data, degenerate rows, all three relations and free/two-sided-bounded variables, x, objective, duals and Farkas vectors are byte-identical to 0.3.4 — and certificate-sized problems run 5–30× faster (40 rows × 100 variables: 1.1 s → 40 ms; 60 × 160: 2.8 s → 80 ms; the degree-5 three-variable Handelman search: 3.6 s → 0.9 s).

Why not a faster bignum crate? Before building this, num-bigint 0.4 was benchmarked against dashu 0.6 on these kernels. dashu was ~9× faster on Gauss–Jordan over rationals but only 1.2–2× faster on integer kernels — the gap was Ratio’s per-operation gcd normalisation, not raw bignum speed. Fraction-free elimination over num-bigint beat dashu’s rational elimination by 5× and the old code by 40×, with no change to the public Ratio<BigInt> types (as_rational, linprog::Q, the num_* re-exports). So num-bigint stays.

→ Matrices: exact matrices over ℚ and ℤ · Exact Linear Programming: performance

Behaviour changes

There are no signature-breaking changes in 0.3. Two behaviours changed in ways an existing program could observe:

• degree, coeffs, coeff, leading_coeff and is_polynomial now succeed for polynomials whose coefficients are symbolic parameters (a·x² + (a + 1)·x + 3 in x). In 0.2 they returned None / false. Code that used None from these methods to mean “has parameters” should test Poly::has_rational_coeffs or free_symbols instead.
• simplify_rational and the results of solve with symbolic coefficients are now put into rational normal form with ratsimp. The values are mathematically equal to the 0.2 results; only the printed form differs (a single cancelled fraction, e.g. (3*j + 1)/(5*j - 1)). Tests that compare against a string may need updating; tests that compare with equals or by substitution do not.

Everything else on this page is new API.