{"id":{"repo_id":"uwo","oai_identifier":"oai:uwo.scholaris.ca:20.500.14721/38616"},"canonical_url":"https://search.dev.ndltd.org/etd/uwo/oai:uwo.scholaris.ca:20.500.14721/38616","repository":{"repo_id":"uwo","name":"Western University","base_url":"https://uwo.scholaris.ca/server/oai/request"},"display":{"title":"Fast Algorithms, Modular Methods, Parallel Approaches and Software Engineering for Solving Polynomial Systems Symbolically","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Xie, Yuzhen"],"institution":"The University of Western Ontario","degree_name":"Ph D","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Maza, Marc Moreno","Watt,Stephen M."],"committee_chairs":[],"committee_members":[],"year":2007,"date_issued":"2007","date_published":"2007","updated_at":"2026-07-27T21:56:16Z","subjects":["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"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14721/38616","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Maza, Marc Moreno","Watt,Stephen M."]},{"key":"dc:creator","label":"Author","values":["Xie, Yuzhen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-08-27T16:58:14Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-08-27T16:58:14Z"]},{"key":"dc:date.issued","label":"Date","values":["2007"]},{"key":"dc:publisher","label":"Institution","values":["The University of Western Ontario"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph D"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The University of Western Ontario"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["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"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14721/38616"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Fast Algorithms, Modular Methods, Parallel Approaches and Software Engineering for Solving Polynomial Systems Symbolically"]}]}],"canonical_facts":{"dc:contributor.advisor":["Maza, Marc Moreno","Watt,Stephen M."],"dc:creator":["Xie, Yuzhen"],"dc:date.accessioned":["2025-08-27T16:58:14Z"],"dc:date.available":["2025-08-27T16:58:14Z"],"dc:date.issued":["2007"],"dc:description.abstract":["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."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14721/38616"],"dc:language.iso":["en"],"dc:publisher":["The University of Western Ontario"],"dc:subject":["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"],"dc:title":["Fast Algorithms, Modular Methods, Parallel Approaches and Software Engineering for Solving Polynomial Systems Symbolically"],"dc:type":["Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["Ph D"],"thesis:institution_name":["The University of Western Ontario"]},"updated_at":"2026-07-27T21:56:16Z"}