CECM Colloquium, November 26 in K9509 at 3.30

Speaker: Dr Michael Monagan (Director CAG)

Title: Uniquification and Fast Simplification of Algebraic Expressions.

The most important operation in a computer algebra system is how equality of two algebraic expressions is implemented. In Maple, during simplification of algebraic expressions, Maple uniquely represents all ````equal'''' expressions and sub-expressions. Because expressions are represented uniquely, testing whether two expressions are equal costs one machine instruction -- you just compare machine addresses.

The mathematical/computing contribution of this technology is the application of hashing functions to algebraic formule, in this case functions Z -> Z mod 2^n, which are used to do the uniquification in expected linear time.

Because of this uniquification, operations like substitution, set operations, and simplification, all of which require testing for equality, are sped up by an order of magnitude. They could not execute faster!

In the talk I will explain how these hashing functions are designed, how simplification is done, and also give an honest appraisal of the disadvantages of this model for algebraic simplification.