Doctor of Philosophy
Marc Moreno Maza
Regular chains, introduced about twenty years ago, have emerged as one of the major
tools for solving polynomial systems symbolically. In this thesis, we focus on different
algorithmic aspects of the theory of regular chains, from theoretical questions to high-
performance implementation issues.
The inclusion test for saturated ideals is a fundamental problem in this theory.
By studying the primitivity of regular chains, we show that a regular chain generates
its saturated ideal if and only if it is primitive. As a result, a family of inclusion tests
can be detected very efficiently.
The algorithm to compute the regular GCDs of two polynomials modulo a regular
chain is one of the key routines in the various triangular decomposition algorithms. By
revisiting relations between subresultants and GCDs, we proposed a novel bottom-up
algorithm for this task, which improves the previous algorithm in a significant manner
and creates opportunities for parallel execution.
This thesis also discusses the accelerations towards fast Fourier transform (FFT)
over finite fields and FFT based subresultant chain constructions in the context of
massively parallel GPU architectures, which speedup our algorithms by several orders
Pan, Wei, "Algorithmic Contributions to the Theory of Regular Chains" (2011). Electronic Thesis and Dissertation Repository. 80.