RISC Forum

(Exact) Algebraic Algorithms and (Some) Applications

Dr. Elias Tsigaridas

Abstract

Real algebraic numbers are the numbers that are real solutions of a
univariate polynomial with integer coefficients. We present algorithmic
and complexity results about exact computations with real algebraic
numbers and applications of these algorithms. We represent the real
algebraic numbers using the isolating interval representation, i.e. a
square-free polynomial and an isolating interval. In order to construct
a real algebraic number we need to isolate the real roots of a
univariate polynomial. We will present recent advances in the problem of
real root isolation, and we will sketch on going work on random
polynomials, as well as experimental evaluation.

Algebraic algorithms, and in particular computations with real algebraic
numbers and polynomial system (real) solving, are powerful tools that
could be used in many applications. We will present some recent advances
in the problem of symmetric tensor decomposition, and in non-linear
computational geometry. The latter includes the arrangement of conic
arcs, the Voronoi diagram of convex smooth pseudo-circles. and the
computation of the topology of a real plane algebraic curve.
Finally, we consider algorithms that given a convex lattice polygon,
test whether it can be decomposed into a Minkowski sum of two other such
polygons and if so, find one or all such decompositions. The problem is
closely related to the problem of bivariate polynomial factorization.