MEGA 2007Effective Methods in Algebraic Geometry Strobl, Austria, June 25th - 29th |
 |
Electronic Proceedings
Abstract
| Title | Polynomial Division using Dynamic Arrays, Heaps, and Packed Exponent Vectors |
| Keywords | polynomial division, data structures, heaps, polynomial GCD, Groebner bases, |
| Abstract | A common data structure that is used for multivariate polynomials
is a linked list of terms sorted in a term ordering. When dividing polynomials using this data structure, polynomial addition and subtraction is done using merging. This can result in poor performance on some kinds of divisons that commonly arise in practice. In this paper we consider using an auxilliary heap of pointers to reduce the number of monomial comparisons needed in the worst case where the size of the heap is linear in the number of terms in the quotient(s). We present variations that are designed to improve performance for dense polynomials and divisions with large quotients. We have implemented the heap algorithms in C with an interface from Maple. We also encode and pack monomials to speed up monomial comparisons. We give some timings demonstrating that a heap of pointers is efficient. |
The Institute is named after the famous Austrian mathematician Johann Radon (1887-1956)
Medieninhaber:
Österreichische Akademie der Wissenschaften
Juristische Person öffentlichen Rechts (BGBl 569/1921 idF BGBl I 130/2003)
Dr. Ignaz Seipel-Platz 2, 1010 Wien
Diese Website dient zur Information über die wissenschaftlichen Aktivitäten der Österreichischen Akademie der Wissenschaften und setzt somit den gesetzlichen Auftrag um, die Wissenschaft in jeder Hinsicht zu fördern.
This RICAM page was made with 100% valid HTML & CSS - Send comments to Webmaster
Today's date and time is 03/20/10 - 01:04 CET and this file ( /mega2007/electronic/47-abs.html ) was last modified on 06/19/07 - 14:54 CEST