Evaluation of "Performance Enhancements" in Algebraic Manipulation Systems

Carl Glen Ponder

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-88-438
August 1988

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/CSD-88-438.pdf

This thesis examines several proposed ways to speed up symbolic algebraic computation: hashing techniques, parallel processing, application of the FFT, and alternative representations of polynomial expressions.

Polynomials, and variants like rational functions, truncated power series, and Poisson series, represent an important class of expressions in algebraic manipulation. Parallel algorithms are analyzed for multiplying and powering sparse and dense polynomials, including parallel forms of the FFT. Alternative polynomial representations are compared and it is suggested that an efficient algebraic manipulation system might use a family of polynomial representations rather than one general form.

Grobner-basis reduction is an inherently hard problem, yet can be used as a powerful tool in computational mathematics. Contrary to recent claims, empirical studies show that it is difficult to exploit parallelism in Grobner-basis computation.

A variety of hashing mechanisms have been proposed for performing operations in symbolic computation, including memo functions for recognizing and eliminating redundant computations. The proposed mechanisms are presented in summary; empirical study shows that memo functions, except in certain circumstances, may not be an advantage.

Additional summary of relevant results in parallel algorithm design and parallel processing machines and languages is presented.

Advisor: Richard J. Fateman and Clark D. Thompson


BibTeX citation:

@phdthesis{Ponder:CSD-88-438,
    Author = {Ponder, Carl Glen},
    Title = {Evaluation of "Performance Enhancements" in Algebraic Manipulation Systems},
    School = {EECS Department, University of California, Berkeley},
    Year = {1988},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6042.html},
    Number = {UCB/CSD-88-438},
    Abstract = {This thesis examines several proposed ways to speed up symbolic algebraic computation: hashing techniques, parallel processing, application of the FFT, and alternative representations of polynomial expressions. <p>Polynomials, and variants like rational functions, truncated power series, and Poisson series, represent an important class of expressions in algebraic manipulation. Parallel algorithms are analyzed for multiplying and powering sparse and dense polynomials, including parallel forms of the FFT. Alternative polynomial representations are compared and it is suggested that an efficient algebraic manipulation system might use a family of polynomial representations rather than one general form. <p>Grobner-basis reduction is an inherently hard problem, yet can be used as a powerful tool in computational mathematics. Contrary to recent claims, empirical studies show that it is difficult to exploit parallelism in Grobner-basis computation. <p>A variety of hashing mechanisms have been proposed for performing operations in symbolic computation, including memo functions for recognizing and eliminating redundant computations. The proposed mechanisms are presented in summary; empirical study shows that memo functions, except in certain circumstances, may not be an advantage. <p>Additional summary of relevant results in parallel algorithm design and parallel processing machines and languages is presented.}
}

EndNote citation:

%0 Thesis
%A Ponder, Carl Glen
%T Evaluation of "Performance Enhancements" in Algebraic Manipulation Systems
%I EECS Department, University of California, Berkeley
%D 1988
%@ UCB/CSD-88-438
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1988/6042.html
%F Ponder:CSD-88-438