MITACS Seminar Series on Mathematics of Computer Algebra and Analysis
Solving Polynomial Systems Symbolically and in Parallel.
Yuzhen Xie, University of Western Ontario
Abstract: We present algorithms and an implementation framework for solving polynomial systems symbolically and in parallel. Symbolic methods are powerful tools in scientific computing. The implementation of symbolic solvers is, however, highly difficult. Indeed, they are extremely space and time consuming when applied to large examples. The increasing availability of parallel and distributed architectures offers the opportunity to realize high-performance solvers that can largely expand the range of solvable problems. We have developed a high-level categorical parallel framework, written in the Aldor language, to support high-performance computer algebra on symmetric multi-processor machines and multicores. A component-level parallel solver for computing triangular decompositions has been realized using this framework. Our solutions address the following challenges: (1) creation of coarse-grained level parallelism aiming to achieve multi-level parallelization for symbolic solving over clusters of multiprocessor machines; (2) efficient management and scheduling of highly dynamic and irregular tasks; and (3) effective data-communication of sophisticated mathematical objects. Our work in progress focuses on the study of efficient memory usage in parallel symbolic solving. Memory consumption appears to be one of the bottlenecks in our parallel solver: the concurrent threads or processes incur more space usage than a sequential execution due to distribution and/or duplication of mathematical objects. We discuss approaches to face this new challenge.