English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Exact Symbolic-numeric Computation of Planar Algebraic Curves

Berberich, E., Emeliyanenko, P., Kobel, A., & Sagraloff, M. (2013). Exact Symbolic-numeric Computation of Planar Algebraic Curves. Theoretical Computer Science, 491, 1-32. doi:10.1016/j.tcs.2013.04.014.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Berberich, Eric1, Author           
Emeliyanenko, Pavel1, Author           
Kobel, Alexander1, Author           
Sagraloff, Michael1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: We present a certified and complete algorithm to compute arrangements of real planar algebraic curves. It computes the decomposition of the plane induced by a finite number of algebraic curves in terms of a cylindrical algebraic decomposition. From a high-level perspective, the overall method splits into two main subroutines, namely an algorithm denoted BiSolve to isolate the real solutions of a zero-dimensional bivariate system, and an algorithm denoted GeoTop to compute the topology of a single algebraic curve. Compared to existing approaches based on elimination techniques, we considerably improve the corresponding lifting steps in both subroutines. As a result, generic position of the input system is never assumed, and thus our algorithm never demands for any change of coordinates. In addition, we significantly limit the types of symbolic operations involved, that is, we only use resultant and gcd computations as purely symbolic operations. The latter results are achieved by combining techniques from different fields such as (modular) symbolic computation, numerical analysis and algebraic geometry. We have implemented our algorithms as prototypical contributions to the C++-project CGAL. We exploit graphics hardware to expedite the remaining symbolic computations. We have also compared our implementation with the current reference implementations, that is, LGP and Maple�s Isolate for polynomial system solving, and CGAL�s bivariate algebraic kernel for analyses and arrangement computations of algebraic curves. For various series of challenging instances, our exhaustive experiments show that the new implementations outperform the existing ones.

Details

show
hide
Language(s): eng - English
 Dates: 2013-062013
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: Other: Local-ID: FBA5865E6C876B20C1257C6000518688-Berberich20131
DOI: 10.1016/j.tcs.2013.04.014
BibTex Citekey: Berberich20131
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Theoretical Computer Science
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: Amsterdam : Elsevier
Pages: - Volume / Issue: 491 Sequence Number: - Start / End Page: 1 - 32 Identifier: ISSN: 0304-3975
CoNE: https://pure.mpg.de/cone/journals/resource/954925512450