Eve library

Kalika CAS Engine

Other

Revision 1

On this page

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-pack bridge for browser and Node.js WASM targets.
  • kalika-cas-native: napi-rs bridge 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#

sh
cargo test --workspace
cargo check --target wasm32-unknown-unknown -p kalika-cas-wasm
pnpm exec nx run @kalika/cas-engine:test

Nx Targets#

sh
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#

sh
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#

sh
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>/.