Fast Algorithms, Modular Methods, Parallel Approaches and Software Engineering for Solving Polynomial Systems Symbolically

Symbolic methods are powerful tools in scientific computing. The implementation of symbolic solvers is, however, a highly difficult task due to the extremely high time and space complexity of the problem. In this thesis, we study and apply fast algorithms, modular methods, parallel approaches and software engineering techniques to improve the efficiency of symbolic solvers for computing triangular decomposition, one of the most promising methods for solving non-linear systems of equations symbolically. We first adapt nearly optimal algorithms for polynomial arithmetic over fields to direct products of fields for polynomial multiplication, inversion and GCD compu tations. Then, by introducing the notion of equiprojectable decomposition, a sharp modular method for triangular decompositions based on Hensel lifting techniques is obtained. Its implementation also brings to the Maple computer algebra system a unique capacity for automatic case discussion and recombination. A high-level categorical parallel framework is developed, written in the Al- DOR language, to support high-performance computer algebra on symmetric multi processors and multicore processors. A component-level parallelization of triangular decompositions by the Triade algorithm is realized using this framework. Parallelism is created by applying modular methods, and task scheduling is guided by the geo metric information discovered during the solving process. By reviewing the RegularChains library in MAPLE, the challenges for the con ception and implementation of triangular decompositions are analyzed. The software engineering techniques for developing a solver in three computer algebra systems targeting different communities of users are compared. We also prove and add two methods for efficiently computing irredundant triangular decompositions and for ver ifying symbolic solvers. Our experimentation shows that the software developed, based on our approaches, helps solving application problems that are out of the scope of other comparable solvers. We believe that the algorithms and methods and the framework and our implementation techniques could benefit other areas of scientific computing.

Name thesis:degree_name

Ph D

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

The University of Western Ontario

Year dc:date.issued

2007

Author dc:creator

• Xie, Yuzhen

Advisors dc:contributor.advisor

• Maza, Marc Moreno
• Watt,Stephen M.

• polynomial system solving
• non-linear equations
• triangular decom position
• equiprojectable decomposition
• fast algorithm
• modular method
• multi processed parallelism
• component-level parallelization
• categorical parallel framework
• irredundant triangular decomposition
• verification of solvers

Language dc:language.iso

en

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14721/38616

OAI identifier oai:identifier

oai:uwo.scholaris.ca:20.500.14721/38616