The distribution of condition numbers of rational data of bounded bit length
bounded input lengthcondition numbersNorthcott-Schmidt heightpolynomial equationsrational datasystems of multivariate homogeneous
Well-distributed sequences and other variations (11K36) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Conditioning of matrices (15A12) Numerical computation of matrix norms, conditioning, scaling (65F35) Numerical computation of solutions to systems of equations (65H10) Complexity and performance of numerical algorithms (65Y20)
The authors prove that rational data of bounded input length are uniformly distributed with respect to the probability distribution of the condition numbers. For the linear algebra case, it is proved that when the bit length \(h\) (the logarithm of the Northcott-Schmidt height) of a randomly choosen \(n\times n\) matrix \(M\) satisfies \(h \geq 10 n^4 \log n + \log w\), where \(w>1\), then its condition number satisfies \(k(M)<wn^{5/2}\) with probability at least \(1-2/w\). A similar estimate is established for the condition number \(\mu_{{norm}}\) introduced by M. Shub and S. Smale when is applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, the techniques introduced are used to estimate the probability distribution of the precision, the number of bits of the denominator required to write approximate zeros of systems of multivariate polynomial equations of bounded input length.
- The distributions of individual bits in the output of multiplicative operations
- On integer-valued rational polynomials and depth distributions of binary codes
- Expected values for the rational complexity of finite binary sequences
- Distribution of one-error linear complexity of binary sequences for arbitrary prime period
- On a Conjecture about Binary Strings Distribution
- Distribution results for low-weight binary representations for pairs of integers
- Distribution of r-Patterns in the Most Significant Bit of a Maximum Length Sequence over ${\mathbb Z}_{2^l}$
- The distribution of 2ⁿ-periodic binary sequences with fixed k-error linear complexity
- On the distribution function of the complexity of finite sequences
- Limit probabilities for random sparse bit strings
- Systems of rational polynomial equations have polynomial size approximate zeros on the average
- Robust certified numerical homotopy tracking
- A concise proof of the Kronecker polynomial system solver from scratch
- Numerical stability of surface implicitization
- On the probability distribution of singular varieties of given corank
- Upper bounds on the distribution of the condition number of singular matrices
- The average condition number of most tensor rank decomposition problems is infinite
- On the zeta Mahler measure function of the Jacobian determinant, condition numbers and the height of the generic discriminant
- Bounds for the condition number of polynomials systems with integer coefficients. (invited talk)
- Some remarks on the condition number of a real random square matrix
- The distributions of individual bits in the output of multiplicative operations
This page was built for publication: The distribution of condition numbers of rational data of bounded bit length
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1601362)
