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.
Title
Evaluation of "Performance Enhancements" in Algebraic Manipulation Systems
Published
1988-08-01
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-88-438
Type
Text
Extent
142 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
