View in EDS

Real root finding for determinants of linear matrices.

Saved in:
Bibliographic Details
Title: Real root finding for determinants of linear matrices.
Authors: Henrion, Didier1,2,3 henrion@laas.fr, Naldi, Simone1,2 snaldi@laas.fr, Safey El Din, Mohab4,5,6,7 Mohab.Safey@lip6.fr
Source: Journal of Symbolic Computation. May2016, Vol. 74, p205-238. 34p.
Subjects: Determinants (Mathematics), Matrices (Mathematics), Coefficients (Statistics), Mathematical connectedness, Control theory (Engineering), Computational geometry, Mathematical optimization
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 . [ABSTRACT FROM AUTHOR]
Copyright of Journal of Symbolic Computation is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
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 . [ABSTRACT FROM AUTHOR]
ISSN:07477171
DOI:10.1016/j.jsc.2015.06.010