On a condition number of general random polynomial systems

DOI10.1090/MCOM/2993MaRDI QIDQ2792338zbMATH OpenOpenAlexFDO

Authors Hoi Nguyen

Publication date 9 March 2016

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

Full work available at URL https://arxiv.org/abs/1403.4293, https://semanticscholar.org/paper/caad406d78fdf9172474612b891fe482386748fe

zbMATH Keywords

singularitycondition numberssystem of equations

Mathematics Subject Classification ID

Numerical computation of solutions to systems of equations (65H10) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Abstract: Condition numbers of random polynomial systems have been widely studied in the literature under certain coefficient ensembles of invariant type. In this note we introduce a method that allows us to study these numbers for a broad family of probability distributions. Our work also extends to perturbed systems.

Recommendations

• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• Condition length and complexity for the solution of polynomial systems
• A numerical algorithm for zero counting. III: Randomization and condition
• High probability analysis of the condition number of sparse polynomial systems
• Smoothed analysis for the condition number of structured real polynomial systems

Cites work

• scientific article; zbMATH DE number 421657 (Why is no real title available?)
• scientific article; zbMATH DE number 503393 (Why is no real title available?)
• scientific article; zbMATH DE number 1096865 (Why is no real title available?)
• scientific article; zbMATH DE number 1962932 (Why is no real title available?)
• A numerical algorithm for zero counting. I: Complexity and accuracy
• A numerical algorithm for zero counting. II: Distance to ill-posedness and smoothed analysis
• A numerical algorithm for zero counting. III: Randomization and condition
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• Complexity of Bezout's Theorem I: Geometric Aspects
• Complexity of Bezout's theorem. III: Condition number and packing
• Complexity of Bezout's theorem. V: Polynomial time
• Complexity of Bezout’s Theorem IV: Probability of Success; Extensions
• Condition. The geometry of numerical algorithms
• Eigenvalues and Condition Numbers of Random Matrices
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• Invertibility of random matrices: norm of the inverse
• Numerical inverting of matrices of high order
• On the Probability That a Random ± 1-Matrix Is Singular
• On the number of real roots of random polynomials
• Random matrices: The distribution of the smallest singular values
• Small ball probability, inverse theorems, and applications
• Smallest singular value of a random rectangular matrix
• Smooth analysis of the condition number and the least singular value
• Smoothed analysis of \(\kappa(A)\)
• Smoothed analysis of algorithms
• The Littlewood-Offord problem and invertibility of random matrices

Cited in

(7)

• Smoothed analysis for the condition number of structured real polynomial systems
• A numerical algorithm for zero counting. III: Randomization and condition
• High probability analysis of the condition number of sparse polynomial systems
• A condition number theorem for underdetermined polynomial systems
• Probabilistic condition number estimates for real polynomial systems. I: A broader family of distributions
• The generalized polynomial Moon-Rand system
• Conditioning of random conic systems under a general family of input distributions

This page was built for publication: On a condition number of general random polynomial systems

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