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 | Source: | 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. | Keywords: | Algebraic Geometry; Complexity; Databases | Document URI: | http://hdl.handle.net/1942/14863 | ISSN: | 0938-1279 | e-ISSN: | 1432-0622 | DOI: | 10.1007/s00200-012-0172-x | ISI #: | 000311495400005 | Rights: | Journal (Applicable Algebra in Engineering, Communication and Computing) copyright | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2013 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
AAECC.pdf Restricted Access | Published version | 938.93 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
1
checked on Oct 14, 2024
Page view(s)
130
checked on Sep 5, 2022
Download(s)
114
checked on Sep 5, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.