Vi presenterar en algoritm för att isolera rötterna av en godtycklig komplex polynom p som också fungerar för polynom med flera rötter förutsatt att antalet k av distinkta rötter ges som en del av inmatningen. Den ger k pairwise isär diskar var och en innehåller en av de distinkta rötterna av p, och dess mångfald. Algoritmen använder ungefärlig faktorisering som subrutin. Dessutom tillämpar vi den nya rotisoleringsalgoritmen för en ny algoritm för att beräkna topologin för en verklig planar algebraisk kurva specificerad som nolluppsättningen av ett bivariat heltal polynom och för att isolera de verkliga lösningarna i ett bivariat polynomsystem. För inmatningspolynom av grad n och bitsize τ, förbättrar vi den för närvarande bästa körtiden från Õ(n 9 τ + n 8 τ 2 ) (deterministiska) till Õ(n 6 + n 5 τ) (randomized) för topologi beräkning och från Õ(n 8 + n 7 τ) (deterministiska) till Õ(n 6 + n 5 τ) (randomized) för att lösa bivariatsystem.
Pans faktoriseringsalgoritm är också en viktig subrutin i en nyligen genomförd algoritm REF för att isolera alla rötter av ett komplext polynom i den tid som är bundet av vårt huvudteoret.
From Approximate Factorization to Root Isolation with Application to Cylindrical Algebraic Decomposition
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}