Abstract | ||
---|---|---|
We prove that rational data of bounded input length are uniformly distributed (in the classical sense of H. Weyl, in [42]) with respect to the probability distribution of condition numbers of numerical analysis. We deal both with condition numbers of linear algebra and with condition numbers for systems of multivariate polynomial equations. For instance, we prove that for a randomly chosen n\\times n rational matrix M of bit length O(n 4 log n) + log w , the condition number k(M) satisfies k(M) ≤ w n 5/2 with probability at least 1-2w -1 . Similar estimates are established for the condition number μ_ norm of M. Shub and S. Smale when applied to systems of multivariate homogeneous polynomial equations of bounded input length. Finally, we apply these techniques to estimate the probability distribution of the precision (number of bits of the denominator) required to write approximate zeros of systems of multivariate polynomial equations of bounded input length. |
Year | DOI | Venue |
---|---|---|
2002 | 10.1007/s002080010017 | Foundations of Computational Mathematics |
Keywords | Field | DocType |
Condition numbers,Linear algebra,Multivariate polynomial equations,Probability and uniform distribution,Discrepancy bounds,Approximate zeros,Height of projective points,11H99,15Aff12,65H10,65F35,65Y20 | Binary logarithm,Linear algebra,Mathematical analysis,Probability distribution,Discrete mathematics,Mathematical optimization,Condition number,Combinatorics,Homogeneous polynomial,Numerical analysis,Mathematics,Fraction (mathematics),Bounded function | Journal |
Volume | Issue | ISSN |
2 | 1 | 1615-3375 |
Citations | PageRank | References |
10 | 1.02 | 7 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
D. Castro | 1 | 27 | 2.58 |
Josè L. Montaña | 2 | 82 | 15.50 |
Luis Miguel Pardo | 3 | 141 | 15.63 |
Jorge San Martín | 4 | 19 | 3.37 |