JACAL2
These are some quick notes about major enhancements I would like to
see implemented in JACAL2.
-=-=-=-=-
* http://swissnet.ai.mit.edu/~jaffer/ratint or
http://swissnet.ai.mit.edu/~jaffer/ratint.pdf
Rational Function Integration
is my plan for JACAL integration. Implementing integration had been
gated by polynomial factoring which JACAL now has.
A transcendental function created by indefinite integration will
become the canonical representative for the (polynomial) field
extension it induces. This is similar to the way JACAL handles
algebraic field extension.
But if first-order differential forms are canonical, can't the same be
done for first-order difference equations? I believe so:
KARR, M. Summation in Finite Terms. Journal of the Association for
Computing Machinery. Vol. 28, No. 2, April 1981, pp. 305-350.
GOSPER, R.W. Jr. Decision procedure for indefinite hypergeometric
summation. Proc. Nat. Acad. Sci. USA 75,1 (1978), 40-42.
More troubling is the prospect of the Gamma function being reached
through either a differential or a finite-difference recurrence, which
would require identifying these as identical to retain canonicity.
I believe that integrals defining the Gamma function are always
definite; and I make no claims to canonicalize the results of definite
integrals.
-=-=-=-=-
* http://swissnet.ai.mit.edu/~jaffer/slib_4.html#SEC113
Commutative Rings
Canonical differential algebra was the prime motivation for JACAL. I
have mellowed with age and plan for JACAL2 to manipulate both
canonical and non-canonical forms.
I developed a "Commutative Rings" package for SLIB which does fast
arithmetic on numeric and symbolic expressions. The user can define
rules (in its database) specifying how operators act on their
arguments. Dr. Allan Adler helped shape the package's capabilities by
using it to verify a lengthy calculation done in REDUCE.
With the addition of variable-elimination, commutative-rings will be
part of JACAL2.
-=-=-=-=-
* Grobner Basis (ideas -- work not started)
Variable elimination (ideals) in JACAL is done using resultants;
which sometimes introduces spurious factors. Grobner Basis is
planned for JACAL2.
Grobner Basis is the basis for a conjunction of equations. Equations
with factors express disjunction, but the reduction algorithm is
oblivious to them, carrying the the exponent multiples through its
calculations. Square factors are particularly wasteful.
Therefore, equations should be factored before calculating basis; and
only primitive factors used for each basis calculation. Should they be
factored over integers or with field extension? Aye, there's the rub!
[This seems related to deep-square-free.]
Factoring with field extensions may move too much structure out of the
equations; will Grobner base reduction then rebuild the product (of
factors) polynomials?
Both elimination ideals and Grobner Bases should not contain sets of
equations involving disjoint sets of variables.
Variable ordering should make algebraic constant's priority so low
that their defining equations are never scheduled for reduction.
Memoized reductions also can accomplish this.
-=-=-=-=-
* New Polynomial Encoding (ideas -- work not started)
For JACAL2 I would like a polynomial-equation encoding which is:
* idempotent for variable renaming;
* usable as database key; and
* supports total-degree term-ordering.
Such a representation can be used for Grobner bases. Because it is
idempotent for renaming, the database of polys and their reductions
need not be replicated for each permutation of variables.
Encode monic polys as sum (list) of product terms; and a variable
mapping (vector). Product term is:
(coefficient . exponent-vector)
EXPONENT-VECTOR has non-negative integer for each variable.
EXPONENT-VECTORs must be unique in poly; COEFFICIENTs must be non-zero.
Variable ordering depends only on the poly, not on variables. When
polynomial is symmetric in some variables, then the order of those
variables is arbitrary.
For canonical form, content( GCD( coeffs )) = 1 and LC (coeff of highest
total-degree term) must be positive.
Order first by highest degree of vars in poly
if same, order by number of terms of highest degree in poly.
if same, order by max total-degree of highest degree terms.
if same, order by number of terms having max total-degree.
if same, sort degree vectors of terms; sort those vectors as n-digit
integers; and compare sorted collections of vectors as n-digit
integers.
if same, sort coefficients of collection of terms and compare as
n-digit integers.
if same, then repeat process with next-to highest degree terms.
""
""
Equivalently, make copies of poly; segregate by degrees in var;
segregate by total-degree; sort all exp-vects; segregate by exp-vects;
sort by coeff; then compare recursively.