MITACS Seminar Series on Mathematics of Computer Algebra and Analysis

Solving Polynomial Systems Symbolically and in Parallel.

Yuzhen Xie, University of Western Ontario

11:30am, Wednesday December 5th, 2007, in K9509.

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.