Published Paper
Inserted: 16 mar 2018
Last Updated: 18 may 2020
Journal: Appl. Algebr. Eng. Comm.
Volume: 31
Pages: 101-133
Year: 2019
Doi: https://doi.org/10.1007/s00200-019-00396-w
Abstract:
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.