Electronic Thesis and Dissertation Repository

Thesis Format

Monograph

Degree

Doctor of Philosophy

Program

Computer Science

Collaborative Specialization

Scientific Computing

Supervisor

Marc Moreno Maza

Abstract

The RegularChains library in Maple offers a collection of commands for solving polynomial systems symbolically with taking advantage of the theory of regular chains. The primary goal of this thesis is algorithmic contributions, in particular, to high-performance computational schemes for subresultant chains and underlying routines to extend that of RegularChains in a C/C++ open-source library.

Subresultants are one of the most fundamental tools in computer algebra. They are at the core of numerous algorithms including, but not limited to, polynomial GCD computations, polynomial system solving, and symbolic integration. When the subresultant chain of two polynomials is involved in a client procedure, not all polynomials of the chain, or not all coefficients of a given subresultant, may be needed. Based on that observation, we design so-called speculative and caching strategies which yield great performance improvements within our polynomial system solver.

Our implementation of these techniques has been highly optimized. We have implemented optimized core arithmetic routines and multithreaded subresultant algorithms for univariate, bivariate and multivariate polynomials. We further examine memory access patterns and data locality for computing subresultants of multivariate polynomials, and study different optimization techniques for the fraction-free LU decomposition algorithm to compute subresultants based on determinant of Bezout matrices.

Our code is publicly available at www.bpaslib.org as part of the Basic Polynomial Algebra Subprograms (BPAS) library that is mainly written in C, with concurrency support and user interfaces written in C++.

Summary for Lay Audience

One of the most fundamental subjects in scientific computing is polynomial system solving; accordingly, almost all available computer algebra systems rely on polynomial system solvers. The RegularChains library in Maple offers a collection of commands for solving polynomial systems symbolically with taking advantage of the theory of regular chains. The primary goal of this thesis is algorithmic contributions, in particular, to high-performance computational schemes for subresultant chains and underlying routines to extend that of RegularChains as part of the Basic Polynomial Algebra Subprograms (BPAS) library that is mainly written in C, with concurrency support and user interfaces written in C++.

Subresultants are one of the most fundamental tools in computer algebra. They are at the core of numerous algorithms including, but not limited to, polynomial GCD computations, polynomial system solving, and symbolic integration. When the subresultant chain of two polynomials is involved in a client procedure, not all polynomials of the chain, or not all coefficients of a given subresultant, may be needed. Based on that observation, we design so-called speculative and caching strategies which yield great performance improvements within our polynomial system solver.

The notion of speculative algorithm is inspired by the definition of speculative execution on computer hardware. We mean an algorithm that would normally compute a sequence S of items but assumes that only a prescribed sub-sequence S' of those may be needed. It manages to increase performance by taking this observation into account, while being able to recover S from the calculations of S' if the whole S turns out to be needed. Thus, the cost of that recovery along with computing S' is essentially that of computing S directly.

Our implementation of these techniques has been highly optimized through developing asymptotically fast core arithmetic routines and multithreaded subresultant algorithms for univariate, bivariate and multivariate polynomials. We further examine memory access patterns and data locality for computing subresultants of multivariate polynomials. For matrices over multivariate polynomials, we make use of the Bareiss fraction-free LU decomposition and further optimize this algorithm with a so-called smart-pivoting technique to reduce the cost of the decomposition and compute subresultants based on determinant of Bezout and Hybrid Bezout matrices.

Download

Share

COinS