Richard Fateman
Abstract
How should one design and implement a program for the multiplication of sparse polynomials? This is a simple question, necessarily addressed by the builders of any computer algebra system (CAS). To examine a few options we start with a single easily-stated computation which we believe represents a useful benchmark of "medium difficulty" for CAS designs. We describe a number of design options and their effects on performance. We also examine the performance of a variety of commercial and freely-distributed systems. Important considerations include the cost of high-precision (exact) integer arithmetic and the effective use of cache memory.
- A. D. Hall. "The ALTRAN System for Rational Function Manipulation - A Survey", CACM 14(8):517--521 (Aug 1971). Google Scholar
Digital Library
- R. Fateman. "A Lisp-language Mathematica-to-Lisp Translator," SIGSAM Bulletin 24 no. 2 p 19--21 (April, 1990). Also reprinted in Computer Algebra Nederland Nieuwsbrief 6, October, 1990. Google ScholarDigital Library
- R. Fateman. "Importing Pre-packaged Software into Lisp: Experience with Arbitrary-Precision Floating-Point Numbers," Poster session, ISSAC 2000 International Symposium on Symbolic and Algebraic Computation, St. Andrews, Scotland, UK, August 2000., http://www.cs.berkeley.edu/~fateman/papers/mpflis.pdfGoogle Scholar
- R. Fateman. "Memory Cache and Lisp: Faster list processing via automatically rearranging memory," Draft, May 2002.Google Scholar
- Yozo Hida. "Data Structures and Cache Behavior of Sparse Polynomial Multiplication," Class project CS282, UC Berkeley, May, 2002.Google Scholar
Recommendations
Essentially optimal sparse polynomial multiplication
ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic ComputationWe present a probabilistic algorithm to compute the product of two univariate sparse polynomials over a field with a number of bit operations that is quasi-linear in the size of the input and the output. Our algorithm works for any field of ...
Parallel sparse polynomial multiplication using heaps
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computationWe present a high performance algorithm for multiplying sparse distributed polynomials using a multicore processor. Each core uses a heap of pointers to multiply parts of the polynomials using its local cache. Intermediate results are written to buffers ...
Certain classes of polynomial expansions and multiplication formulas
The authors first present a class of expansions in a series of Bernoulli polyomials and then show how this general result can be applied to yield various (known or new) polynomial expansions. The corresponding expansion problem involving the Euler ...
Comments