Algebrai számokkal kapcsolatos algoritmusok és számítások

Uray, Marcell János

Algebrai számokkal kapcsolatos algoritmusok és számítások

Kulcsszó: Műszaki tudományok/Informatikai tudományok
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

URI: http://hdl.handle.net/10831/86124

Könyvtári katalógus link: https://opac.elte.hu/Record/opac-EUL01-1107389

MTMT: 33864161

DOI: 10.15476/ELTE.2021.151

Absztrakt:

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.

Abstract:

The dissertation is about algorithms of algebraic numbers and related theoretical questions. An important aspect of the discussed algorithms is that they calculate exactly, not numerically. In this way we avoid the usual problem of numerical calculations, the rounding errors, but the exact algorithms are usually slower, and they often suffer from coefficient explosion. Avoiding this problem and maintaining the running time (i.e. ensuring polynomial time) is an important aspect of exact algorithms. The dissertation has two major parts. The first half deals with the computational complexity of operations and algorithms involving algebraic numbers. We calculate the running time of the main operations in algebraic number fields (using some existing results). We also analyse some special operations like comparison between real algebraic numbers and integer rounding. These results enable us to analyse two algorithms, the Bareiss algorithm (a generalisation of the Gaussian elimination) and the LLL algorithm (a lattice reduction algorithm) on algebraic numbers using exact arithmetic, and analyse their complexity. Their behaviour is well-known for integers, but we extend them to algebraic integers, and prove that their running time remains polynomial. The second half of the dissertation is about special algebraic numbers: roots of integer polynomials whose all roots are outside of the complex unit circle. Such polynomials are called expansive polinomials. We examine the question how to decide whether a polynomial with integer coefficients is expansive (without calculating its roots). There are some existing methods for this, but we introduce a new method that is guaranteed to avoid coefficient explosion. Then we examine how close the roots of an expansive integer polynomial can be to the unit circle, and give lower bounds on this distance in terms of the parameters of the polynomial. Then we construct a family of expansive polynomials that have roots very close to the unit circle, thus showing that the lower bounds are almost sharp.

A tétel részletes adatai