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
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.