Algebrai számokkal kapcsolatos algoritmusok és számítások
Computer algebra
algebraic numbers
exact arithmetic
symbolic computation
coefficient explosion
Bareiss algorithm
LLL algorithm
expansive polynomials
Informatika D. I./Numerikus és szimbolikus számítások
Komputeralgebra
algebrai számok
egzakt aritmetika
szimbolikus számítás
együtthatórobbanás
Bareiss-algoritmus
LLL-algoritmus
expanzív polinomok
Abstract:
A doktori értekezés algebrai számokkal kapcsolatos különféle algoritmusokról és ezekhez kapcsolódó elméleti kérdésekről szól. A vizsgált algoritmusok fontos jellemzője, hogy nem numerikusan, hanem egzaktul számolnak. Ezzel elkerüljük a numerikus számolásokra jellemző kerekítési hibákat, viszont az egzakt algoritmusok általában lassabbak, és felléphet az ún. együtthatórobbanás. Ezért a futási idő kordában tartása (polinomiális idő garantálása) fontos szempont az egzakt algoritmusok tervezése során.
A disszertáció két nagy témakörre bontható. Az első felében algebrai számokon végzett műveletek és algoritmusok futási idejét vizsgáljuk. Egy-két korábbi eredményt is felhasználva kiszámítjuk a fontosabb műveletek hatékonyságát algebrai számtestekben, köztük olyanokét is, mint a valós algebrai számok összehasonlítása és az egészre kerekítés. Ezekre támaszkodva megvizsgáljuk két algoritmusnak, a Bareiss-algoritmusnak (amely a Gauss-elimináció módosítása) és az LLL-algoritmusnak (amely egy rácsredukciós algoritmus) a futási idejét, ha egzakt algebrai számokkal végezzük őket. Egész számokra mindkét algoritmusnak ismert a viselkedése, itt kiterjesztjük őket algebrai egészekre, és bebizonyítjuk, hogy ebben az esetben is polinomiális a futási idejük.
A dolgozat második felében speciális algebrai számokról van szó: olyan egész együtt- hatós polinomok gyökeiről, amelyek minden gyöke a komplex egységkörön kívül van. Az ilyen polinomokat expanzív polinomoknak nevezzük. Foglalkozunk azzal a kérdéssel, hogy hogyan tudjuk eldönteni egy polinomról, hogy expanzív-e (a gyökök kiszámítása nélkül). Erre léteznek módszerek, de itt bevezetünk egy új algoritmust, amely garantáltan nem vezet együtthatórobbanáshoz. Ezután megvizsgáljuk azt a kérdést, hogy egész együtthatós expanzív polinomok gyökei mennyire lehetnek közel az egységkörhöz. Erre kiszámítunk különféle alsó korlátokat a polinom paramétereinek függvényében, valamint konstruálunk egy expanzív polinomcsaládot, amelynek vannak az egységkörhöz nagyon közeli gyökei, és ezáltal megmutatjuk, hogy az alsó korlátok közel élesek.