Real root finding for determinants of linear matrices

DOI10.1016/J.JSC.2015.06.010zbMATH Open1329.65090arXiv1412.5873OpenAlexW1559760555MaRDI QIDQ898255FDOQ898255

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)

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$.

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

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

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)

Cites Work

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

Cited In (5)

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

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)