Stephen M. Watt

Stephen M. Watt

David R. Cheriton School of Computer Science

University of Waterloo, Canada

A Review of Algorithms on Symbolic Domains

This talk is about computing with mathematical quantities where the sizes or shapes are not known in advance.  We consider
  • polynomials where the exponents can be given by symbolic expressions,
  • matrices with blocks or other internal structure of symbolic size, and
  • piece-wise functions where the shapes of the domains are given by symbolic expressions.

For polynomials with symbolic exponents, there are various straightforward operations, such as squaring $x^{2n} – 1$ to get $x^{4n}-2x^{2n}+1$, or differentiating to get $2nx^{2n-1}$.  We review algorithms to compute more sophisticated operations such as the GCD, factorization and functional decomposition of such polynomials.

For symbolic matrices, we show how to do arithmetic on matrices with blocks, bands and other structures where the dimensions are given by symbolic expressions.

Finally, we consider the case of piece-wise functions, where the regions of definition are given symbolically.   We show how hybrid sets, a generalization of multi-sets allowing negative multiplicities, can be used to reduce the computational complexity of working with these objects, and lead to a particularly elegant formulation of Stokes’ theorem.