License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.06271.15
URN: urn:nbn:de:0030-drops-7933
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2006/793/
|
Go to the corresponding Portal |
Watt, Stephen M.
Two Families of Algorithms for Symbolic Polynomials
Abstract
We wish to work with polynomials where the exponents are not known
in advance, such as $x^{2n} - 1$. There are various operations we will
want to be able to do, such as squaring the value to get $x^{4n}-2x^{2n}+1$,
or differentiating it to get $2nx^{2n-1}$. Expressions of this sort
arise frequently in practice, for example in the analysis of algorithms,
and it is very difficult to work with them effectively in current computer
algebra systems.
We consider the case where multivariate polynomials can have exponents
which are themselves integer-valued multivariate polynomials, and we present
algorithms to compute their GCD and factorization. The algorithms fall into
two families: algebraic extension methods and interpolation methods.
The first family of algorithms uses the algebraic independence of $x$, $x^n$,
$x^{n^2}$, $x^{nm}, etc, to solve related problems with more indeterminates.
Some subtlety is needed to avoid problems with fixed divisors of the exponent
polynomials. The second family of algorithms uses evaluation and interpolation
of the exponent polynomials. While these methods can run into unlucky
evaluation points, in many cases they can be more appealing. Additionally,
we also treat the case of symbolic exponents on rational coefficients
(e.g. $4^{n^2+n}-81$) and show how to avoid integer factorization.
BibTeX - Entry
@InProceedings{watt:DagSemProc.06271.15,
author = {Watt, Stephen M.},
title = {{Two Families of Algorithms for Symbolic Polynomials}},
booktitle = {Challenges in Symbolic Computation Software},
pages = {1--20},
series = {Dagstuhl Seminar Proceedings (DagSemProc)},
ISSN = {1862-4405},
year = {2006},
volume = {6271},
editor = {Wolfram Decker and Mike Dewar and Erich Kaltofen and Stephen Watt},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2006/793},
URN = {urn:nbn:de:0030-drops-7933},
doi = {10.4230/DagSemProc.06271.15},
annote = {Keywords: Computer algebra, symbolic computation, factorization, gcd, symbolic exponents}
}
|
Keywords: |
|
Computer algebra, symbolic computation, factorization, gcd, symbolic exponents |
|
Collection: |
|
06271 - Challenges in Symbolic Computation Software |
|
Issue Date: |
|
2006 |
|
Date of publication: |
|
07.11.2006 |
