Real root finding for determinants of linear matrices. (May 2016)

• Record Type: Journal Article
• Authors: Henrion, Didier; Naldi, Simone; Safey El Din, Mohab
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 205
• Page End: 238
• Publication Date: 2016-05
• Subjects: Computer algebra -- Real algebraic geometry -- Determinantal varieties; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.06.010
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: Let A 0, A 1, …, 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 ∈ R n : det ⁡ ( A 0 + x 1 A 1 + ⋯ + x n A n ) = 0 } . Such a problem finds applications in many areas such as control theory, computational geometry, optimization, etc. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially polynomial in the binomial coefficient ( n + m n ) . 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 .