Pavel Trutman presents A General Solver Based on Sparse Resultants

On 2019-08-30 13:00 at G205, Karlovo náměstí 13, Praha 2
Reading group on the work by I. Emiris, in PoSSo 1995 presented by Pavel

Paper abstract:
Sparse elimination exploits the structure of polynomials by measuring their
complexity in terms of Newton polytopes instead of total degree. The sparse, or
Newton, resultant generalizes the classical homogeneous resultant and its
degree is a function of the mixed volumes of the Newton polytopes. We sketch
sparse resultant constructions of Canny and Emiris and show how they reduce the
problem of root-finding to an eigenproblem. A novel method for achieving this
reduction is presented which does not increase the dimension of the problem.
Together with an implementation of the sparse resultant construction, it
provides a general solver for polynomial systems. We discuss the overall
implementation and illustrate its use by applying it to concrete problems from
vision, robotics
and structural biology. The high efficiency and accuracy of the solutions
that sparse elimination may be the method of choice for systems of moderate

Paper url:

Instructions for participants: The reading group studies the literature in the
field of pattern recognition and computer vision. At each meeting one or more
papers are prepared for presentation by a single person, the presenter. The
meetings are open to anyone, regarding their background. It is assumed that
everyone attending the reading group has, at least briefly, read the paper –
not necessarily understanding everything. Attendants should preferably send
questions about the unclear parts to the speaker at least one day in advance.
During the presentation we aim to have a fruitful discussion, a critical
analysis of the paper, as well as brainstorming for creative extensions.

See the page of reading groups
Responsible person: Petr Pošík