Symbolic polynomial manipulation on distributed memory machines: Towards a library-based approach

Exact computation and manipulation of polynomial equations can be performed by symbolic polynomial manipulation facilities on computers. This is useful in many scientific and engineering applications. The time and memory requirements of large problems arising in symbolic polynomial manipulation cannot be efficiently met by current sequential machines. A library-based approach and techniques developed in this thesis attempt to answer the question of how distributed-memory computing can be used to efficiently exploit parallelism in basic symbolic polynomial manipulation methods. The distinguishing features of the library-based approach developed include: optimization of basic coarse-grain operations, parametric polymorphic routines representing different abstract execution models, library-based load balancing, efficient encoding/decoding of list-based data structures used, and efficient memory management. For an important class of basis computations, techniques are incrementally developed. First, an approach based on relaxation of dependencies present in the sequential computation is developed to exploit coarse-grain parallelism. Then, an algorithm-specific synchronization technique, named quasi-barrier, is developed to improve the performance of the relaxation approach. The quasi-barrier technique provides a two-fold advantage. First, it improves the dynamic load balance. Second, it provides an early update model that can speed up convergence to a solution. A modified quasi-barrier technique is further developed to reduce unnecessary synchronizations and yet preserve the advantages of the quasi-barrier technique. Finally, for this class of basis computations, various task distribution strategies are developed and their effect on the performance is studied. The experiments performed in this thesis provide evidence of the efficacy of the developed techniques for the class of basis computations. For two other important methods, real root isolation and Grobner factorization, a master-slave framework is provided and its performance is evaluated. A methodology is developed to determine whether a master-slave approach is suitable for the given method. A prototype library with limited functionality has been developed to demonstrate the effectiveness of the library-based approach and the techniques developed in this thesis. The prototype library reuses routines of the sequential libraries, SACLIB and GROBNER, and is extensible, flexible, and portable. The library contains parametric polymorphic routines supporting relaxation, relaxation with quasi-barriers, relaxation with modified quasi-barriers, and master-slave execution models