Real root finding for determinants of linear matrices

DOI10.1016/J.JSC.2015.06.010MaRDI QIDQ898255zbMATHOpenAlexFDO

Authors Didier Henrion, Simone Naldi, Mohab Safey El Din

Publication date 8 December 2015

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.5873

zbMATH Keywords

algorithmcomplexitycomputer algebradeterminantal varietiesreal algebraic geometry

Mathematics Subject Classification ID

Numerical computation of roots of polynomial equations (65H04) Computational aspects of higher-dimensional varieties (14Q15) Numerical computation of determinants (65F40)

Abstract: Let $A_0,A_1,ldots,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 $XinR{R}^n:::det(A_0+x_1{A}_1+cdots+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^{O(n)}$ 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+mchoosen}^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$.

Recommendations

• Real root finding for low rank linear matrices
• Real polynomial root-finding by means of matrix and polynomial iterations
• Real polynomial root-finding by means of matrix and polynomial iterations
• On Matrix Polynomials with Real Roots
• Computation of roots of real and complex matrices
• Computing real square roots of a real matrix
• Finding the determinant of a matrix via complex analysis
• Finding all real roots of a polynomial by matrix algebra and the Adomian decomposition method

Cites work

• scientific article; zbMATH DE number 4101329 (Why is no real title available?)
• scientific article; zbMATH DE number 3673938 (Why is no real title available?)
• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 2151204 (Why is no real title available?)
• scientific article; zbMATH DE number 939802 (Why is no real title available?)
• scientific article; zbMATH DE number 5050658 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• A Gröbner free alternative for polynomial system solving
• A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
• A new efficient algorithm for computing Gröbner bases \((F_4)\)
• Advances in convex optimization: conic programming
• Algebraic geometry. An introduction. Transl. from the French by Catriona Maclean
• Algorithms in real algebraic geometry
• Bipolar varieties and real solving of a singular polynomial equation
• Computing loci of rank defects of linear matrices using Gröbner bases and applications to cryptology
• Critical points and Gröbner bases: the unmixed case
• Determinantal rings
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• FGb: A Library for Computing Gröbner Bases
• Fast algorithm for change of ordering of zero-dimensional Gröbner bases with sparse multiplication matrices
• Generalized polar varieties and an efficient real elimination.
• Generalized polar varieties: geometry and algorithms
• Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree \((1,1)\): algorithms and complexity
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Likelihood geometry
• Linear Matrix Inequalities in System and Control Theory
• Maximum likelihood for matrices with rank constraints
• Moments, positive polynomials and their applications
• On sign conditions over real multivariate polynomials
• On the complexity of the generalized MinRank problem
• Polar varieties and efficient real elimination
• Polar varieties, real equation solving, and data structures: the hypersurface case
• Semidefinite Optimization and Convex Algebraic Geometry
• Sufficient and necessary conditions for semidefinite representability of convex hulls and sets
• Sums of squares, moment matrices and optimization over polynomials
• Testing sets for properness of polynomial mappings
• The Euclidean distance degree of an algebraic variety
• The algebraic degree of semidefinite programming
• The state-of-the-art in conic optimization software

Cited in

(4)

• Real root finding for low rank linear matrices
• Real root finding for rank defects in linear Hankel matrices
• Exact algorithms for linear matrix inequalities
• Solving rank-constrained semidefinite programs in exact arithmetic

Describes a project that uses

Uses Software

• FGb
• Kronecker
• RAGlib

This page was built for publication: Real root finding for determinants of linear matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q898255)