Kernel

A kernel, also called a generalized variable, is the unit that polynomial algorithms in a computer algebra system treat as a variable^[1]^[2]. The algorithms for expanding, factoring, taking gcds or simplifying rational functions work on polynomials in variables, but expressions contain other things: $sin x$ , $e^{x + 1}$ , $x$ , $1/ x$ . Each maximal subexpression of this kind is replaced by a fresh variable, the polynomial algorithm runs, and the variables are replaced back. To expand $(sin x + 1)^{2}$ , the system expands $(k + 1)^{2} = k^{2} + 2 k + 1$ and returns $sin^{2} x + 2 sin x + 1$ . The approach is simple and underlies the rational-function forms of REDUCE and Macsyma^[2]^[3], but it sees no relations among kernels: as polynomials in their kernels, $e^{2 x}$ and $(e^{x})^{2}$ , or $sin^{2} x + cos^{2} x$ and $1$ , are different, and recognizing their equality needs more than polynomial arithmetic.

§ 01

Identifying kernels

The kernels of an expression are found by descending through sums, products and non-negative integer powers; whatever else is met, a symbol, a function application, a negative or fractional power, is a kernel. Equal kernels must become the same variable, or nothing would combine, so the arguments of each kernel are simplified to canonical form first, recursively, and the kernel is then identified by its canonical printed form. With that, $sin (x + x)$ and $sin (2 x)$ are one kernel^[1].

The expression sin(x)·(x + 1)² + sin(x) as a tree. Its kernels are the two occurrences of sin(x), which are the same kernel, and the symbol x inside the power. As a polynomial in the kernels the expression is k₁k₂² + 2k₁k₂ + 2k₁.

Expressions as polynomials in kernels: the conversion, which simplifies the arguments of each kernel before naming it, and the conversion back.

(* A polynomial in kernels: terms map an exponent list over the kernel
   table to a rational coefficient. *)
module M = Map.Make (struct type t = int list let compare = compare end)
type poly = Q.t M.t
 
(* Kernels are identified by their canonical printed form, so equal
   subexpressions become the same variable. *)
let kernels : (string * e) list ref = ref []
let kernel_index (k : e) (key : string) =
  let rec find i = function
    | [] -> kernels := !kernels @ [ (key, k) ]; i
    | (s, _) :: rest -> if s = key then i else find (i + 1) rest in
  find 0 !kernels
 
let mono_of i = List.init (i + 1) (fun j -> if j = i then 1 else 0)
let rec pad a b = match a, b with
  | [], [] -> [] | x :: a, [] -> x :: pad a [] | [], y :: b -> y :: pad [] b | x :: a, y :: b -> (x + y) :: pad a b
let trim m = let r = List.rev m in let rec drop = function 0 :: t -> drop t | l -> l in List.rev (drop r)
 
let padd p q = M.union (fun _ a b -> let s = Q.add a b in if Q.equal s Q.zero then None else Some s) p q
let pmul p q = M.fold (fun m1 c1 acc -> M.fold (fun m2 c2 acc ->
    padd acc (M.singleton (trim (pad m1 m2)) (Q.mul c1 c2))) q acc) p M.empty
let pconst c = if Q.equal c Q.zero then M.empty else M.singleton [] c
let rec ppow p n = if n = 0 then pconst Q.one else pmul p (ppow p (n - 1))
 
(* The canonical polynomial form, with kernels simplified recursively
   before they are named. *)
let rec to_poly (x : e) : poly =
  match x with
  | Num q -> pconst q
  | Add l -> List.fold_left (fun acc t -> padd acc (to_poly t)) M.empty l
  | Mul l -> List.fold_left (fun acc t -> pmul acc (to_poly t)) (pconst Q.one) l
  | Pow (b, n) when n >= 0 -> ppow (to_poly b) n
  | Sym _ | Pow _ | App _ ->
    let k = match x with App (f, a) -> App (f, of_poly (to_poly a)) | Pow (b, n) -> Pow (of_poly (to_poly b), n) | k -> k in
    let key = show_kernel k in
    M.singleton (mono_of (kernel_index k key)) Q.one
and show_kernel k = show k
(* Back to an expression, terms in decreasing total degree. *)
and of_poly (p : poly) : e =
  let term (m, c) =
    let factors = List.concat (List.mapi (fun i d ->
        if d = 0 then [] else let k = snd (List.nth !kernels i) in [ if d = 1 then k else Pow (k, d) ]) m) in
    match factors with
    | [] -> Num c
    | fs -> if Q.equal c Q.one then (match fs with [ f ] -> f | fs -> Mul fs) else Mul (Num c :: fs) in
  let terms = List.sort (fun (a, _) (b, _) -> compare (List.fold_left ( + ) 0 b, b) (List.fold_left ( + ) 0 a, a)) (M.bindings p) in
  match List.map term terms with [] -> Num Q.zero | [ t ] -> t | ts -> Add ts
 
let simplify x = of_poly (to_poly x)
let is_zero x = M.is_empty (to_poly x)

Expanding with kernels, and recognizing kernels that differ only in how their arguments are written.

open Expr

Running it.

(sin(x) + 1)^2                 -> sin(x)^2 + 2·sin(x) + 1   kernels: sin(x)
(sqrt(x) + 1)^2                -> sqrt(x)^2 + 2·sqrt(x) + 1 kernels: sqrt(x)
(x^-1 + 1)^2                   -> x^(-2) + 2·x^(-1) + 1     kernels: x^(-1)
sin(x + x) - sin(2x)           -> 0                          kernels: none
exp((x+1)^2) - exp(x^2+2x+1)   -> 0                          kernels: none

§ 02

Relations between kernels

Treating kernels as independent variables is correct only if they are algebraically independent. Often they are not. $e^{2 x} = (e^{x})^{2}$ , $(x)^{2} = x$ , $lo g (x^{2}) = 2 lo g x$ for positive $x$ , and $sin^{2} x + cos^{2} x = 1$ . A polynomial form in dependent kernels is still a correct representation, but not a canonical one: expressions equal to zero may not be recognized^[9].

Rewriting exponentials of integer multiples and squares of square roots before naming kernels.

open Expr
 
(* exp(2x) and exp(x) are different kernels but not independent. Rewriting
   exp(n u) as exp(u)^n for integer n, and sqrt(u)^2 as u, before naming
   kernels removes these relations. *)
let rec normalize_kernels (x : e) : e =
  match x with
  | App ("exp", a) ->
    (match simplify (normalize_kernels a) with
     | Mul (Num n :: rest) when Z.equal (Q.den n) Z.one && Q.sign n > 0 ->
       let u = match rest with [ u ] -> u | us -> Mul us in
       Pow (App ("exp", u), Z.to_int (Q.num n))
     | a -> App ("exp", a))
  | Pow (App ("sqrt", a), n) when n >= 2 ->
    Mul [ Pow (normalize_kernels a, n / 2); Pow (App ("sqrt", normalize_kernels a), n mod 2) ]
  | App (f, a) -> App (f, normalize_kernels a)
  | Add l -> Add (List.map normalize_kernels l)
  | Mul l -> Mul (List.map normalize_kernels l)
  | Pow (b, n) -> Pow (normalize_kernels b, n)
  | Num _ | Sym _ -> x

Running it.

exp(2x) - exp(x)^2             zero as written: false after normalizing kernels: true
exp(3x) - exp(x)exp(2x)        zero as written: false after normalizing kernels: true
sqrt(x)^2 - x                  zero as written: false after normalizing kernels: true
sin(x)^2 + cos(x)^2 - 1        zero as written: false after normalizing kernels: false

The rewriting reduces $e^{n u}$ to a power of $e^{u}$ and algebraic kernels modulo their defining equations, which removes these relations. The trigonometric identity survives, because $sin x$ and $cos x$ are related by a polynomial equation that is not a rewriting of one kernel into another; it is handled either by reducing modulo $sin^{2} x + cos^{2} x - 1$ with a Gröbner basis, or by rewriting both in terms of $e^{i x}$ .

§ 03

Structure theorems

For elementary functions, built from $x$ and constants by arithmetic, exponentials, logarithms and algebraic operations, the question of which kernels are independent has a precise answer. Risch's structure theorem of 1979 states that a set of exponentials and logarithms is algebraically dependent over the rational functions only through linear relations among their arguments and the logarithms: $e^{f_{1}}, \dots, e^{f_{n}}$ are dependent exactly when some integer combination of the $f_{i}$ is constant, and similarly for logarithms^[4]. Rosenlicht gave a related account of Liouville's theory^[5]. Algorithms can therefore choose an algebraically independent set of kernels and express the others in terms of them, which gives canonical forms for large classes of exponential and logarithmic expressions. Brown had studied the rational exponential expressions in this way in 1969^[6]. These results are also the foundation of the Risch integration algorithm, which works in a tower of such independent extensions.

§ 04

In computer algebra systems

REDUCE calls such objects kernels and represents expressions as rational functions in them, ordering kernels to make the representation canonical up to kernel dependence^[2]. Macsyma's canonical rational expressions, created by its rat command, do the same, and Moses described the design choices in 1971^[3]. Textbooks call them generalized variables^[1]^[7], and every general system has an equivalent: an expression is a polynomial or rational function in whatever it cannot look inside^[8].

§ 05

History

REDUCE, Anthony Hearn's system begun in the 1960s, uses the term kernel for the operator expressions that its simplifier treats as the variables of polynomials^[2]. The Macsyma project at MIT developed canonical rational expressions in the same period^[3]. The theoretical questions of independence were taken up by Caviness^[9], Brown^[6] and Risch^[4], and their structure theorems made it possible to choose independent kernels systematically for elementary functions.