Geometria Complessa e Geometria Differenziale
Geometria Complessa e Geometria Differenziale
home | mail | papers | authors | news | seminars | events | open positions | login

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

Real root finding for determinants of linear matrices

created by naldi on 16 Mar 2018
modified on 18 May 2020


Published Paper

Inserted: 16 mar 2018
Last Updated: 18 may 2020

Journal: J. Symb. Comput.
Volume: 74
Pages: 205-238
Year: 2016

ArXiv: 1412.5873 PDF
Links: Publisher page


Let $A_0, A_1, \ldots, A_n$ be given square matrices of size $m$ with rational coefficients. The paper focuses on the exact computation of one point in each connected component of the real determinantal variety $\{X \in\mathbb{R}^n \: :\: \det(A_0+x_1A_1+\cdots+x_nA_n)=0\}$. Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Using standard complexity results this problem can be solved using $m^{O(n)}$ arithmetic operations. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially quadratic in ${{n+m}\choose{n}}^{3}$. We also report on experiments with a computer implementation of this algorithm. Its practical performance illustrates the complexity estimates. In particular, we emphasize that for subfamilies of this problem where $m$ is fixed, the complexity is polynomial in $n$.

Credits | Cookie policy | HTML 5 | CSS 2.1