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 low rank 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: Appl. Algebr. Eng. Comm.
Volume: 31
Pages: 101-133
Year: 2019

ArXiv: 1506.05897 PDF
Links: Publisher page, Full-view text-only


The problem of finding $m \times s$ matrices (with $m \leq s$) of rank $r$ in a real affine subspace of dimension n has many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is essentially polynomial in $n+m(s-r)$ ; it improves on the state-of-the-art in the field. Moreover, computer experiments show the practical efficiency of our approach.

Credits | Cookie policy | HTML 5 | CSS 2.1