Rust workspace for Kalika's high-performance computer algebra kernel.
Crates#
kalika-cas-core: target-independent kernel primitives shared by all bridges.kalika-cas-wasm:wasm-bindgen/wasm-packbridge for browser and Node.js WASM targets.kalika-cas-native:napi-rsbridge for server-side native Node.js addons.
The workspace is intentionally split so the same kernel code can be optimized for WASM deployment and native Node deployment without duplicating CAS logic.
Core Expression System#
kalika-cas-core provides the Rust mirror of the @kalika/core TypeScript
expression AST, including arbitrary-precision integer fields, canonical ordering
for commutative operations, hash-consed arena storage, and the URN1 binary
envelope used by bridge payloads.
The WASM and native Node.js bridges expose the same expression transport
contracts: direct serde conversion for TypeScript-shaped expression objects,
JSON helpers, URN1 binary buffer helpers, batch canonicalization, and
streaming canonicalization with progress callbacks.
The canonical-form layer adds selectable normal forms for expanded, collected, and factored polynomial expressions, rational functions with univariate polynomial GCD cancellation, trigonometric forms over either sin/cos or tan-half-angle generators, and exponential/logarithmic product-sum normalization. Results carry the selected strategy, detected variables, and rewrite trace metadata through native Rust and JSON bridge APIs.
The equality-saturation layer builds a bounded e-graph for an input expression, applies algebraic rewrite rules until saturation or an e-node budget is reached, and extracts the cheapest equivalent expression by node count, operation complexity, or numerical-stability cost. It includes identity, inverse, distribution/factoring, and core trig inverse rewrites, with applied-rule, e-class, e-node, iteration, and saturation metadata exposed through Rust and JSON APIs.
Arbitrary-Precision Integers#
kalika-cas-core includes a pure-Rust arbitrary-precision integer layer over
num-bigint for WASM/native portability. It covers checked Euclidean and exact
division, GCD/extended GCD/LCM, factorials, binomial coefficients, fast-doubling
Fibonacci, primorials, and explicit strategy metadata for multiplication and GCD
algorithm selection.
The rational layer stores exact normalized numerator/denominator pairs, keeps denominators positive, preserves decimal-string serde transport, and includes exact arithmetic, comparison, floor/ceil/nearest rounding, continued fractions, best denominator-limited approximation, and modular rational reconstruction.
The ball layer provides rigorous midpoint-radius real balls and rectangular complex balls for certified numerical work. It propagates conservative enclosures through arithmetic, rejects division by intervals that may contain zero, evaluates exact and approximate expression trees, and automatically raises working precision with guard bits when a requested certification target is not yet met.
The p-adic layer represents Q_p values canonically as unit * p^valuation
with absolute and relative precision tracking. It supports Z_p/Q_p
construction, arithmetic, congruence checks, polynomial root lifting with Hensel
steps, Newton refinement in Q_p, p-adic logarithm/exponential on their
convergence domains, and Teichmuller representatives.
The Diophantine layer provides exact linear two-variable solving through
extended GCD parametrization, continued-fraction fundamental Pell solutions,
bounded binary quadratic searches, bounded binomial Thue searches with
Baker-bound metadata, and bounded Mordell integral-point searches for
y^2 = x^3 + k workflows.
The modular layer covers canonical Z/nZ arithmetic, binary modular
exponentiation, modular inverses, reusable fixed-modulus reducers with Barrett
and Montgomery strategy metadata, Chinese Remainder reconstruction, finite-field
arithmetic for prime and polynomial-extension fields, and discrete logarithms
via baby-step-giant-step, Pohlig-Hellman, and an index-calculus strategy entry
point.
The algebraic layer models elements of Q(alpha) with a monic minimal
polynomial and reduced rational coefficient vector. It supports field
arithmetic, inverses, norm/trace/characteristic polynomial invariants through
multiplication matrices, Sylvester-resultant workflows, and certified ball
enclosures by evaluating at an enclosing ball for alpha.
The dense univariate polynomial layer provides a generic coefficient trait and
concrete Z, Q, Z/nZ, and finite-field coefficient implementations. It
supports normalized dense coefficient vectors, addition, subtraction, negation,
schoolbook/Karatsuba/large-degree strategy selection for multiplication, exact
division, pseudo-division, Horner evaluation, multipoint evaluation through a
subproduct tree, and Lagrange/Newton interpolation.
The sparse multivariate polynomial layer stores sorted exponent-vector monomials under lexicographic or graded-lexicographic order. It supports sparse addition, subtraction, multiplication with a dense low-degree univariate path, multivariate division with remainder, pseudo-division over exact rings, full and partial evaluation, and symbolic substitution using sparse polynomial replacements.
The univariate GCD layer builds on dense polynomial division with subresultant pseudo-remainder sequences for exact integer arithmetic, primitive-content normalization, monic Euclidean GCD for field-like coefficient rings, and strategy-labelled modular and half-GCD entry points for large polynomial workflows.
The multivariate GCD layer treats sparse polynomials recursively as dense polynomials in a selected main variable over lower-dimensional sparse coefficient rings. It exposes Zippel sparse-interpolation, Brown evaluation-interpolation, and Extended EZ-GCD strategy-labelled entry points, normalizes monic gcds, verifies exact divisibility, and falls back to common monomial gcd extraction when recursive division is not exact.
The integer polynomial factorization layer exposes strategy-labelled Berlekamp-Zassenhaus, van Hoeij LLL recombination, Musser squarefree, and Hensel lifting entry points. It normalizes primitive content with sign preservation, extracts exact integer linear factors with multiplicity tracking, retains irreducible primitive remainders, and validates modular Hensel factor pairs against the reduced integer polynomial.
The finite-field polynomial factorization layer handles dense univariate
polynomials over prime fields F_p. It provides squarefree/multiplicity-aware
factorization, distinct-degree decomposition, Berlekamp nullspace splitting,
Cantor-Zassenhaus-style equal-degree split hooks, and Kaltofen-Shoup-labelled
entry points over the same exact modular arithmetic primitives used by the rest
of the CAS kernel.
The sparse multivariate factorization layer exposes Wang leading-coefficient, univariate Hensel-lift, and sparse Hensel-lift strategy entry points. It reuses the exact sparse division engine to extract monomial, affine, and sparse linear factors with multiplicity tracking while preserving irreducible sparse remainders for downstream factorization strategies.
The Groebner basis layer implements Buchberger's algorithm over sparse multivariate polynomial systems. It supports lexicographic, graded lexicographic, degree lexicographic, degree reverse lexicographic, elimination, and block-style monomial order metadata, S-polynomial construction, normal-form reduction, monic basis reduction, and normal or sugar-pair selection strategies.
The F4 Groebner layer batches same-degree critical pairs, reduces their S-polynomials through a shared sparse coefficient matrix, supports leftmost and sparsity-aware pivot choices, converts row-reduced matrices back into sparse normal forms, and feeds new monic rows into the Groebner basis loop.
The F5 Groebner layer adds signature-labelled polynomials, position-over-term and term-over-position module monomial orders, rewritten and syzygy criterion tracking, and a signature-aware pair loop that avoids redundant reductions before adding new monic basis elements.
The modular Groebner layer computes independent prime-field Groebner bases in
parallel, skips unlucky primes whose denominator images or basis shapes are
invalid, combines compatible coefficients with CRT, rationally reconstructs the
lift over Q, and certifies the reconstructed basis by reducing the original
generators and every reconstructed S-polynomial.
The ideal-theory layer provides sparse ideal objects, Groebner-normal-form membership certificates, elimination and monomial fast paths for intersections, monomial ideal quotients, monomial radical generation, Shimoyama-Yokoyama-style irreducible monomial primary decompositions, and associated-prime extraction.
The homological algebra layer derives Hilbert series and Hilbert polynomials from Groebner initial ideals using exact standard-monomial enumeration and Lagrange interpolation, constructs Schreyer-pair syzygies, models Taylor free resolutions over initial monomial ideals, and reports Betti tables, projective dimension, and Castelnuovo-Mumford regularity.
The elimination-theory layer reorders polynomial systems into lexicographic elimination blocks, projects Groebner bases back to remaining coordinate rings, constructs graph ideals for polynomial maps, implicitizes parametric varieties, and reports Zariski-closure image ideals with dimension metadata.
The polynomial-system solver composes the sparse Groebner and elimination layers into a zero-dimensional solve pipeline. It computes a lexicographic Groebner basis, extracts univariate eliminants for exact triangular back-substitution, exposes resultant-style projection data through elimination ideals, and reports Bertini-style numerical path endpoints with residual certification against the target equations.
The symbolic-calculus layer differentiates expression trees structurally with
constant, sum, product, quotient, chain, and general-power rules. Its built-in
function table covers elementary trigonometric, inverse trigonometric,
hyperbolic, inverse hyperbolic, exponential, logarithmic, gamma/zeta/polylog,
Bessel, Airy, hypergeometric, elliptic, Dirac delta, and Heaviside identities,
while preserving chain-rule placeholders for unsupported partial derivatives.
The same derivative engine is exposed through Rust, JSON, WASM, and native
Node.js bridge entry points. The Risch-transcendental integration layer returns
strategy-labelled elementary antiderivatives or explicit non-elementary proof
obligations for exp/log/tangent towers, including linearity, power cases,
logarithmic derivative/Rothstein-Trager-style certificates, exponential
argument-derivative cases, logarithmic cases, and tangent substitutions. The
algebraic-extension layer adds Trager-style radical tower handling for rational
powers and sqrt expressions, derivative-times-radical basis reductions,
algebraic logarithm cases such as inverse trigonometric and inverse hyperbolic
primitives, and explicit integral-basis proof obligations when a primitive is
outside the implemented radical tower. The Rubi-style rule engine adds a
priority-ordered integration dispatcher with traceable rule IDs and derivation
metadata across linearity, rational, algebraic, exponential, logarithmic,
trigonometric, hyperbolic, special-function, and piecewise classes, falling back
to the Risch/Trager layers when deterministic rule matching is not faster. The
heuristic integration layer adds LIATE-ranked integration by parts,
trigonometric and Euler substitutions for quadratic radicals, two-factor partial
fractions, recursive rational/logarithmic derivative handling, power-reduction
formulas for trigonometric powers, and Meijer-G/Mellin-style definite
recognizers for gamma and Gaussian integrals.
The Gruntz limit layer computes finite and infinite symbolic limits through
direct substitution, finite-point l'Hopital fallback, MRV extraction, exp/log
comparability ranking, exponential-decay dominance, and classic indeterminate
power rewrites such as x^(1/x) and (1 + 1/x)^x.
The symbolic series layer computes lazy Taylor coefficients by repeated differentiation, detects Laurent pole orders, represents Puiseux fractional power branch points, collects formal asymptotic monomials at infinity, and supports total-degree multivariate Taylor expansions through JSON bridge APIs. The symbolic summation layer adds Zeilberger-style recurrences for recognized hypergeometric sums, WZ certificate metadata, Gosper antidifferences for indefinite hypergeometric terms, and Karr Pi-Sigma metadata for polynomial and nested symbolic sums. The creative telescoping layer returns Ore-style shift/differential telescopers, certificates, boundary metadata, and holonomic annihilator obligations for definite sums and integrals, delegating hypergeometric sums to Zeilberger reduction and recognizing core D-finite exponential integral kernels.
The recurrence solver covers C-finite constant-coefficient recurrences through characteristic roots, including rational ordinary-generating-function denominators parameterized by initial conditions. It also dispatches P-finite recurrences with polynomial/rational symbolic coefficients, solves first-order Petkovsek hypergeometric right factors as finite products, and preserves higher-order holonomic recurrence operators with proof obligations for factorization and generating-function differential equations.
The resultant layer computes dense univariate resultants through Sylvester
matrices with fraction-free Bareiss determinants, exposes modular-CRT and
subresultant-chain strategy-labelled entry points, reuses PRS chains for
subresultant workflows, and derives discriminants from Res(f, f') with exact
division by the leading coefficient.
The root-finding layer combines exact rational-root testing over Z[x],
squarefree Sturm sequences for certified real-root isolation, a
Collins-Akritas/Descartes-labelled isolation entry point over the same certified
interval engine, and Durand-Kerner plus Aberth-Ehrlich complex approximations
with residual reporting. The polynomial equation solver composes those engines
with exact radical-form solutions through degree four, degree-six-bounded Galois
metadata, RootOf-style objects for higher degree, and Newton/Krawczyk-polished
approximations with certification flags.
The transcendental equation solver handles real-domain scalar equations by classifying exact exp/log, trigonometric-periodic, and Lambert W forms before falling back to sampled sign-change isolation, bisection refinement, and Newton polishing with symbolic derivatives. Returned solutions include exact expressions where available, approximations, residuals, certification flags, and the strategies used.
The symbolic ODE layer classifies equations by order, linearity, derivative orders, and recognized families including separable, Bernoulli/Riccati/Clairaut metadata, constant-coefficient, and named special-function classes. It solves first-order quadrature forms, first-order linear homogeneous constant coefficient equations, and second-order constant-coefficient harmonic or exponential equations, while exposing strategy hooks for Lie symmetry, variation-of-parameters, Laplace-transform, power-series, and special-function recognition workflows.
The symbolic PDE layer classifies multivariate equations by derivative variables, total order, linearity, and recognized heat, wave, Laplace, and characteristic families. It provides method-of-characteristics solutions for constant-coefficient first-order transport equations, D'Alembert-style wave templates, heat-equation separation/Green-function templates, and harmonic solution templates for Laplace equations with strategy metadata for Fourier/Laplace transforms and Lie-similarity workflows.
Current Verification#
cargo test --workspace
cargo check --target wasm32-unknown-unknown -p kalika-cas-wasm
pnpm exec nx run @kalika/cas-engine:test
Nx Targets#
pnpm exec nx run @kalika/cas-engine:build
pnpm exec nx run @kalika/cas-engine:build:native
pnpm exec nx run @kalika/cas-engine:build:wasm
pnpm exec nx run @kalika/cas-engine:test
pnpm exec nx run @kalika/cas-engine:typecheck
pnpm exec nx run @kalika/cas-engine:typecheck:wasm
WASM Builds#
scripts/build-wasm.sh --target nodejs
scripts/build-wasm.sh --target web
scripts/build-wasm.sh --target all
The WASM build script validates bulk-memory, simd128, and
nontrapping-fptoint support from rustc, applies
-C target-feature=+bulk-memory,+simd128,+nontrapping-fptoint, and uses the
wasm-pack release profile configured with wasm-opt -O3.
Native Node.js Addon#
scripts/build-native.sh --check
scripts/build-native.sh
The native bridge is built with napi-rs and the workspace enables N-API 8. It
exposes zero-copy Buffer/BufferSlice entry points for large expression
payloads and a thread-safe callback dispatch path for background parallel
computation. Release builds stage a Node-loadable .node addon in
dist/libs/kalika/cas-engine/native/<platform>-<arch>/.