Symbolic Computation Group

Although piecewise functions and matrices are common objects of interest in symbolic computation, the "symbolic" aspects of computation with them still suffer from significant limitations. In current
systems, the dimensions of the matrices have to be fixed as numeric quantities, the region or block structure of the matrices must be fully specified and, in the case of piecewise functions, the component pieces must be equipped with a strict linear order.

A direct approach to lifting these restrictions leads to a combinatorial explosion of disjoint cases. This results in an exponential growth in expression size with respect to the number of operations performed on the objects of interest. Reducing this growth to something more tractable is not straightforward. One approach to this problem is to use negative memberships in sets to capture multiple different cases in a single expression that is typically of the size of a single case. So long as all debts are paid in the end, the combinatorial explosion is avoided and term size grows polynomially in many cases of interest.

In this talk I will explain the problem, describe some of our previous work in the area and discuss progress on our latest approach.

This is joint work with Jacques Carette, Volker Sorge and Stephen Watt