MITACS Seminar Series on Mathematics of Computer Algebra and Analysis

Triangular decomposition of polynomial systems: from practice to high performance.

Marc Moreno Maza, Computing Science, University of Western Ontario

9:30am, Wednesday December 5th, 2007, in K9509.

Abstract: 

Triangular decompositions are one of the most studied techniques for solving
polynomial systems symbolically. Invented by J. F. Ritt in the early '30s for
systems of differential polynomials, their stride started in the late '80s
with the method of W. T. Wu dedicated to algebraic systems.
Different concepts and algorithms extended the work of Wu.
At the end of the '90s the notion of a regular chain, introduced by M. Kalkbrener,
led to important algorithmic improvements. The era of polynomial system solvers
based on triangular decompositions could commence.

Since 2000, several promising complexity results and algorithmic discoveries have
stimulated the development of implementation techniques. These have permitted
fast polynomial arithmetic and parallelism to speed up key subroutines substantially.
Today, new algorithms for computing triangular decompositions are being invented to
make the best use of these techniques. I anticipate that triangular decomposition
solvers will become an invaluable and irreplaceable support to scientific computing.

The talk will introduce the subject (triangular decompositions and regular
chains), its (short) history, challenges, and main theoretical results.