Real root finding for low rank linear matrices

Autor: Simone Naldi, Mohab Safey El Din, Didier Henrion
Přispěvatelé: Équipe Méthodes et Algorithmes en Commande (LAAS-MAC), Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Faculty of Electrical Engineering [Prague] (FEL CTU), Czech Technical University in Prague (CTU), Mathématiques & Sécurité de l'information (XLIM-MATHIS), XLIM (XLIM), Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS)-Université de Limoges (UNILIM)-Centre National de la Recherche Scientifique (CNRS), Technische Universität Dortmund [Dortmund] (TU), Polynomial Systems (PolSys), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Computer Science - Symbolic Computation
FOS: Computer and information sciences
Polynomial
Rank (linear algebra)
Dimension (graph theory)
0102 computer and information sciences
02 engineering and technology
Symbolic Computation (cs.SC)
01 natural sciences
Mathematics - Algebraic Geometry
Symbolic computation
Real algebraic geometry
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
FOS: Mathematics
0202 electrical engineering
electronic engineering
information engineering
Algebraic Geometry (math.AG)
Finite set
Mathematics
Discrete mathematics
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Algebra and Number Theory
Applied Mathematics
020206 networking & telecommunications
010201 computation theory & mathematics
Affine space
13-XX
14Q20
12Y05
68W30
[MATH.MATH-AG]Mathematics [math]/Algebraic Geometry [math.AG]
Root-finding algorithm
Low rank matrices
Zdroj: Applicable Algebra in Engineering, Communication and Computing
Applicable Algebra in Engineering, Communication and Computing, 2020, 31, pp.101-133. ⟨10.1007/s00200-019-00396-w⟩
Applicable Algebra in Engineering, Communication and Computing, Springer Verlag, 2020, 31, pp.101-133. ⟨10.1007/s00200-019-00396-w⟩
ISSN: 0938-1279
1432-0622
DOI: 10.1007/s00200-019-00396-w⟩
Popis: We consider $m \times s$ matrices (with $m\geq s$) in a real affine subspace of dimension $n$. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, 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 polynomial in $\binom{n+m(s-r)}{n}$. It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
Comment: Final published version in Appl. Algebr. Eng. Comm
Databáze: OpenAIRE
Externí odkaz: