Kernel

also: generalized variable

A maximal subexpression that is not polynomial, treated as an opaque variable so that polynomial machinery still applies around it. It is what lets expand handle sin(x)*(x+1)^2: sin(x) becomes a variable, the expansion proceeds, and the variable is substituted back afterwards.

A kernel is a maximal subexpression that is not polynomial, treated as an opaque variable so that polynomial machinery applies around it. Without the idea, every polynomial operation would have to refuse anything containing a function call.

The substitution is mechanical: pick the non-polynomial subterms, replace each with a fresh variable, run the algorithm, substitute back.

(sin x + 1)^{2} ⟼ (k + 1)^{2} ⟼ k^{2} + 2 k + 1 ⟼ sin^{2} x + 2 sin x + 1

Three kinds of kernel, verbatim from the REPL: a function call, a fractional power, a negative power.

> expand (sin(x) + 1)^2
1 + sin(x)^2 + 2*sin(x)
> expand (x^(1/2) + 1)^2
1 + x + 2*x^(1/2)
> expand (1/x + 1)^2
1 + x^(-2) + 2*x^(-1)

The requirement is that equal subexpressions map to the same variable, or nothing would ever combine. Using the printed form of the simplified subexpression as the variable name gets this for free, since the printer is injective on canonical forms.

What the approach cannot see is any relation between kernels. $sin^{2} x + cos^{2} x$ has two independent variables as far as the polynomial layer is concerned, and stays as written; recognising it needs a rewrite system that knows the identity.

Building a CAS in OCaml Part 3Sparse multivariate polynomials, pseudo-division, the subresultant PRS against a modular GCD that is a thousand times faster, resultants, and a parser to drive it all.