Electronic Thesis and Dissertation Repository

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Marc Moreno Maza

Abstract

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

of magnitude.

Download

Share

COinS