## D. Henrion - S. Naldi - M. Safey El Din

# Real root finding for rank defects in linear Hankel matrices

created by naldi on 16 Mar 2018

modified on 18 May 2020

[

BibTeX]

*Published Paper*

**Inserted:** 16 mar 2018

**Last Updated:** 18 may 2020

**Journal:** ISSAC '15: Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation

**Pages:** 221-228

**Year:** 2015

**Doi:** https://doi.org/10.1145/2755996.2756667

**Links:**
Publisher page

**Abstract:**

Let $H_0, ..., H_n$ be $m \times m$ matrices with entries in $\mathbb{Q}$ and
Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel
matrix $H(x)=H_0+X_1H_1+...+X_nH_n$ and the problem of computing
sample points in each connected component of the real algebraic set defined by
the rank constraint $rank(H(x))\leq r$, for a given integer $r \leq
m-1$. Computing sample points in real algebraic sets defined by rank defects in
linear matrices is a general problem that finds applications in many areas such
as control theory, computational geometry, optimization, etc. Moreover, Hankel
matrices appear in many areas of engineering sciences. Also, since Hankel
matrices are symmetric, any algorithmic development for this problem can be
seen as a first step towards a dedicated exact algorithm for solving
semi-definite programming problems, i.e. linear matrix inequalities. Under some
genericity assumptions on the input (such as smoothness of an incidence
variety), we design a probabilistic algorithm for tackling this problem. It is
an adaptation of the so-called critical point method that takes advantage of
the special structure of the problem. Its complexity reflects this: it is
essentially quadratic in specific degree bounds on an incidence variety. We
report on practical experiments and analyze how the algorithm takes advantage
of this special structure. A first implementation outperforms existing
implementations for computing sample points in general real algebraic sets: it
tackles examples that are out of reach of the state-of-the-art.