Real root finding for determinants of linear matricesReportar como inadecuado

Real root finding for determinants of linear matrices - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 LAAS-MAC - Équipe Méthodes et Algorithmes en Commande LAAS - Laboratoire d-analyse et d-architecture des systèmes Toulouse 2 CTU - Czech Technical University in Prague 3 PolSys - Polynomial Systems LIP6 - Laboratoire d-Informatique de Paris 6, Inria de Paris

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 : detA 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. Using standard complexity results this problem can be solved using m^{On} arithmetic operations. Under some genericity assumptions on the coefficients of the matrices, we provide an algorithm solving this problem whose runtime is essentially quadratic in {{n+m}\choose{n}}^{3} . 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.

Keywords : real algebraic geometry computer algebra determinantal varieties

Autor: Didier Henrion - Simone Naldi - Mohab Safey El Din -



Documentos relacionados