Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

On the complexity of change of order
Eric Schost, Ecole Polytechnique, France
Friday, September 9, 2005, at U. of Western Ontario.


I will discuss algorithms to change variable order, for triangular representations of varieties of dimension zero. In an attempt to keep the presentation simple, I will only talk about the bivariate case, where the main ideas are already present: duality, following the work of Kaltofen and Shoup, and trace formulas, after Diaz Toca and Gonzalez Vega.

As an application, I will point out the connection with the Lazard-Rioboo-Rothstein-Trager integration algorithm, and discuss the complexity of rational function integration.


Last modified on Sunday, 04 November 2012, at 15:42 hours.