Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Berberich, Eric
Emeliyanenko, Pavel
Kobel, Alexander
Sagraloff, Michael

dblp
dblp
dblp
dblp



BibTeX cite key*:

Berberich20131

Title

Title*:

Exact symbolic–numeric computation of planar algebraic curves

Journal

Journal Title*:

Theoretical Computer Science

Journal's URL:

http://www.journals.elsevier.com/theoretical-computer-science

Download URL
for the article:

http://www.sciencedirect.com/science/article/pii/S0304397513002983

Language:

English

Publisher

Publisher's
Name:

Elsevier

Publisher's URL:

http://www.elsevier.com/

Publisher's
Address:

Amsterdam

ISSN:

0304-3975

Vol, No, pp, Date

Volume*:

491

Number:


Publishing Date:

June 2013

Pages*:

1-32

Number of
VG Pages:

28

Page Start:

1

Page End:

32

Sequence Number:


DOI:

10.1016/j.tcs.2013.04.014

Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:


Categories,
Keywords:

Algebraic curves, Topology computation, Arrangement, Polynomial systems, Numerical solver, Hybrid methods, Symbolic–numeric algorithms, Exact computation

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

MPG Subsubunit:

Geometry, Topology, and Algebra

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{Berberich20131,
AUTHOR = {Berberich, Eric and Emeliyanenko, Pavel and Kobel, Alexander and Sagraloff, Michael},
TITLE = {Exact symbolic–numeric computation of planar algebraic curves},
JOURNAL = {Theoretical Computer Science},
PUBLISHER = {Elsevier},
YEAR = {2013},
VOLUME = {491},
PAGES = {1--32},
ADDRESS = {Amsterdam},
MONTH = {June},
ISBN = {0304-3975},
DOI = {10.1016/j.tcs.2013.04.014},
}


Entry last modified by Alexander Kobel, 02/17/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/14/2014 03:50:28 PM
Revisions
2.
1.
0.

Editor(s)
Alexander Kobel
Alexander Kobel
Alexander Kobel

Edit Dates
01/14/2014 03:52:11 PM
01/14/2014 03:50:59 PM
01/14/2014 03:50:28 PM