Complexity of computation on real algebraic numbers
Improving on earlier results a new and more efficient algorithm for coding real algebraic numbers is proposed. First, given finitely many polynomials \(P,Q_ 1,...,Q_ k\in {\mathbb{Z}}[X]\) and sign conditions \(\epsilon_ 1,...,\epsilon_ k\in \{-1,0,+1\}\) an algorithm is developed to count the real roots \(\alpha\) of P with side conditions \(Q_ i(\alpha)<0\), \(=0\) or \(>0\) according as \(\epsilon_ i=-1\), \(=0\) or \(=+1.\) Then this is applied to P and all of its derivatives \(P^{(1)},...,P^{(k)}\) (if \(\deg (P)=k)\). It is known that the root \(\alpha\) of P is uniquely determined by the signs of \(P^{(k)}(\alpha),...,P^{(1)}(\alpha)\) computed in this order. The increased efficiency of the new algorithm depends on the fact that usually not all of these signs have to be computed. The first algorithm can be used to determine when the computation may be stopped.
- scientific article; zbMATH DE number 4142180 (Why is no real title available?)
- scientific article; zbMATH DE number 3922806 (Why is no real title available?)
- scientific article; zbMATH DE number 4029737 (Why is no real title available?)
- scientific article; zbMATH DE number 3785018 (Why is no real title available?)
- scientific article; zbMATH DE number 3497890 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3445421 (Why is no real title available?)
- scientific article; zbMATH DE number 3307642 (Why is no real title available?)
- The complexity of elementary algebra and geometry
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Cauchy index computation
- Determinantal formulae for the solution set of zero-dimensional ideals
- NC algorithms for real algebraic numbers
- On the complexity of quadratic programming in real number models of computation
- Polar varieties, real equation solving, and data structures: the hypersurface case
- Computing in the field of complex algebraic numbers
- Does computer algebra help at all learning about real numbers?
- Generic computation of the real closure of an ordered field.
- Dynamic evaluation and real closure.
- A new graph characteristic and its application to numerical computability
- Polynomial-time presentations of algebraic number fields
- On the complexity of algebraic numbers
- Towards faster real algebraic numbers
- Effective asymptotics of linear recurrences with rational coefficients
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- On the complexity of conversion between classic real number representations
- Intrinsic complexity estimates in polynomial optimization
- Computation of algebraic numbers and arithmetic operations over them with linear memory
- A theorem on random polynomials and some consequences in average complexity
- Zero-nonzero and real-nonreal sign determination
- Computing bits of algebraic numbers
- Algebraic certificates for Budan's theorem
- Polynomial Time Algorithms for Finding Integer Relations among Real Numbers
- scientific article; zbMATH DE number 4132288 (Why is no real title available?)
- An exact real algebraic arithmetic with equality determination
- scientific article; zbMATH DE number 66626 (Why is no real title available?)
- scientific article; zbMATH DE number 1263362 (Why is no real title available?)
- scientific article; zbMATH DE number 1276817 (Why is no real title available?)
- Computing the Additive Complexity of Algebraic Circuits with Root Extracting
- scientific article; zbMATH DE number 2151239 (Why is no real title available?)
- Sensing as a complexity measure
- Codes and adjustment in digraphs of root simplexes of real polynomials
- Algorithms – ESA 2004
- Topics in real and complex number complexity theory
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Linear solving for sign determination
- Stability versus speed in a computable algebraic model
- On the complexity of computing the logarithm and square root functions on a complex domain
- On Newton's rule and Sylvester's theorems
This page was built for publication: Complexity of computation on real algebraic numbers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757065)
