Thesis Format

Monograph

The Design and Implementation of a High-Performance Polynomial System Solver

Alexander Brandt, The University of Western OntarioFollow

Degree

Doctor of Philosophy

Program

Computer Science

Supervisor

Moreno Maza, Marc

Abstract

This thesis examines the algorithmic and practical challenges of solving systems of polynomial equations. We discuss the design and implementation of triangular decomposition to solve polynomials systems exactly by means of symbolic computation.

Incremental triangular decomposition solves one equation from the input list of polynomials at a time. Each step may produce several different components (points, curves, surfaces, etc.) of the solution set. Independent components imply that the solving process may proceed on each component concurrently. This so-called component-level parallelism is a theoretical and practical challenge characterized by irregular parallelism. Parallelism is not an algorithmic property but rather a geometrical property of the particular input system’s solution set.

Despite these challenges, we have effectively applied parallel computing to triangular decomposition through the layering and cooperation of many parallel code regions. This parallel computing is supported by our generic object-oriented framework based on the dynamic multithreading paradigm. Meanwhile, the required polynomial algebra is sup- ported by an object-oriented framework for algebraic types which allows type safety and mathematical correctness to be determined at compile-time.

Our software is implemented in C/C++ and have extensively tested the implementation for correctness and performance on over 3000 polynomial systems that have arisen in practice.

The parallel framework has been re-used in the implementation of Hensel factorization as a parallel pipeline to compute roots of a polynomial with multivariate power series coeﬀicients. Hensel factorization is one step toward computing the non-trivial limit points of quasi-components.

Summary for Lay Audience

Solving systems of polynomial equations and inequations is a fundamental problem in scientific computing, required by practically all scientific disciplines. Expanding research in these disciplines demands solving larger and more complex problems than ever before. Only relatively recently has technological advances in computer hardware performance (processor speeds, computer memory, and computer architectures) and in algorithmic methods made it feasible to obtain exact solutions to such practical polynomial systems by solving them symbolically. In contrast, scientists have traditionally relied on numerical methods to obtain approximate solutions. Nonetheless, exact solutions are desirable, and often necessary, in many fields such as cryptography, theoretical physics, robotics, and signal processing.

Solving systems of polynomial equations symbolically is, by its very nature, a very hard problem. The algorithms involved are highly sophisticated, computationally ex- pensive, and require numerous supporting sub-algorithms. In this thesis we examine the design and implementation of a symbolic polynomial system solver which is very eﬀicient in practice. We consider implementation techniques including parallel computing to achieve performance. In particular, multiple areas of parallelism are combined cooperatively. We also consider so-called dynamic evaluation, which allows for the branches of a case discussion to dynamically evolve. Such case discussions evolve in solving systems where the geometry of the solution set splits into multiple pieces (points, curves, sur- faces). The implementation has been extensively tested on over 3000 polynomial systems which have arisen in practice.

This solver is part of an open-source computer algebra library called BPAS (Basic Polynomial Algebra Subprograms). In this thesis we also discuss software design strategies for this library and the solver which look to achieve both high performance and high levels of software quality. We obtain desirable quality attributes including extensibility and maintainability. A major result in this direction is a computer implementation of a mathematical framework called the algebraic hierarchy. We implement an extensible hierarchy that has the added benefit that mathematical correctness is automatically enforced before the program is even executed (i.e. at compile-time).

Recommended Citation

Brandt, Alexander, "The Design and Implementation of a High-Performance Polynomial System Solver" (2022). Electronic Thesis and Dissertation Repository. 8733.
https://ir.lib.uwo.ca/etd/8733