Real root finding for low rank linear matrices (Q2175227)

In this paper, authors consider \(m\times s\) matrices (with \(m\geq s\)) in a real affine subspace of dimension \(n\), and they design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve the following 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 the algorithm is polynomial in \(\binom{n+m(s-r)}{n}\) and thus, it improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Computer experiments show the practical efficiency of the presented approach.