Complexity of computation on real algebraic numbers
type: Item
instance of: scholarly article
title: Complexity of computation on real algebraic numbers
zbMATH Open document ID: 0723.68054
DOI: 10.1016/S0747-7171(08)80035-1
author: Aviva Szpirglas
author: Marie-Françoise Roy
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
review text: 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.
reviewed by: Niels Schwartz
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11R04
zbMATH DE Number: 4193123
zbMATH Keywords: real algebraic numbers
MaRDI profile type: Publication
cites work: Q4091421
cites work: The complexity of elementary algebra and geometry
cites work: Q3770650
cites work: Q4079605
cites work: Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
cites work: Q3474749
cites work: Q4771385
cites work: Q5588717
cites work: Q3698903
cites work: Q3963114
full work available at URL: s0747-7171(08)80035-1
OpenAlex ID: W2016506651
description: scientific article; zbMATH DE number 4193123