Vi presenterar algoritmiska, komplexa och implementationsresultat för problemet med att isolera de verkliga rötterna till en univariat polynom i Bα  på L[y], där L = ( Q(α) är en enkel algebraisk förlängning av de rationella talen. Vi ser över två tillvägagångssätt för problemet. I den första metoden, med hjälp av resulterande beräkningar, utför vi en minskning till ett polynom med heltal koefficienter och vi drar en gräns för OB(N 10 ) för att isolera de verkliga rötterna av Bα, där N är en övre gräns på alla mängder (grad och bitstorlek) av ingång polynomials. I det andra tillvägagångssättet isolerar vi de verkliga rötterna som arbetar direkt på polynomet av inmatningen. Vi beräknar förbättrade separationsgränser för rötterna och vi bevisar att de är optimala, under milda antaganden. För att isolera de verkliga rötterna anser vi en modifierad Sturm algoritm, och en modifierad version av descartes algoritm som infördes av Sagraloff. För den förra visar vi en komplexitet som är bunden av OB(N 8 ) och för den senare en gräns för OB(N 7 ). Vi implementerade algoritmerna i C som en del av huvudbiblioteket i matematika och vi illustrerar deras effektivitet över olika datamängder. Slutligen lägger vi fram komplexa resultat för det allmänna fallet med den första metoden, där koefficienterna tillhör flera utvidgningar.
Det senare påståendet har redan bevisats genom en nyligen genomförd implementering från A. Strzebonski och E. Tsigaridas REF "i C som en del av MATHEMATICA:s kärnbibliotek".
Univariate real root isolation in an extension field
{'venue': "ISSAC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}