www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
Research publications >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/14863

Title: Evaluating geometric queries using few arithmetic operations
Authors: Grimson, Rafael
Heintz, Joos
Kuijpers, Bart
Issue Date: 2012
Citation: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 23 (3-4), p. 179-193
Abstract: Let P:=(P1,…,Ps) be a given family of n-variate polynomials with integer coefficients and suppose that the degrees and logarithmic heights of these polynomials are bounded by d and h, respectively. Suppose furthermore that for each 1 ≤ i ≤ s the polynomial P i can be evaluated using L arithmetic operations (additions, subtractions, multiplications and the constants 0 and 1). Assume that the family P is in a suitable sense generic. We construct a database D , supported by an algebraic computation tree, such that for each x∈[0,1]n the query for the signs of P 1(x), . . . , P s (x) can be answered using hdO(n2) comparisons and nL arithmetic operations between real numbers. The arithmetic-geometric tools developed for the construction of D are then employed to exhibit example classes of systems of n polynomial equations in n unknowns whose consistency may be checked using only few arithmetic operations, admitting, however, an exponential number of comparisons.
URI: http://hdl.handle.net/1942/14863
DOI: 10.1007/s00200-012-0172-x
ISI #: 000311495400005
ISSN: 0938-1279
Category: A1
Type: Journal Contribution
Validation: ecoom, 2013
Appears in Collections: Research publications

Files in This Item:

Description SizeFormat
Journal version938.93 kBAdobe PDF

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.