Algoritmus Lindsey – Fox - Lindsey–Fox algorithm - Wikipedia

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Srpna 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

The Algoritmus Lindsey – Fox, pojmenovaná podle Pat Lindsey a Jim Fox, je číselná algoritmus pro nalezení kořenů nebo nul vysokého stupně polynomiální se skutečnými koeficienty nad komplexní pole. Je určen zejména pro náhodné koeficienty, ale dobře funguje i na polynomech s koeficienty ze vzorků řeči, seismických signálů a dalších měřených jevů. A Matlab implementace tohoto zohlednila polynomy stupně přes milion na stolním počítači.

Algoritmus Lindsey – Fox

Algoritmus Lindsey – Fox používá FFT (rychlá Fourierova transformace) k velmi efektivnímu provedení mřížkového hledání ve složité rovině k nalezení přesné aproximace k N kořeny (nuly) an Npolynom th-stupně. Síla tohoto hledání mřížky umožňuje nový polynomiální factoring strategie, která se ukázala jako velmi účinná pro určitou třídu polynomů. Tento algoritmus vymyslel Pat Lindsey a implementoval ho Jim Fox v balíčku počítačových programů vytvořených pro výpočet polynomů vysokého stupně. Původně byl navržen a byl dále vyvinut, aby byl zvláště vhodný pro polynomy se skutečnými náhodnými koeficienty. V této formě se ukázalo jako velmi úspěšné rozdělováním tisíců polynomů stupňů od jednoho tisíce do stovek tisíc, stejně jako několika stupňů jeden milion a po jednom stupni dva miliony a čtyři miliony. Kromě zpracování polynomů velmi vysokého stupně je přesný, rychlý, využívá minimální paměť a je naprogramován v široce dostupném jazyce Matlab. Existují praktické aplikace, často případy, kdy jsou koeficienty vzorky nějakého přirozeného signálu, jako jsou řečové nebo seismické signály, kde je algoritmus vhodný a užitečný. Určitě je však možné vytvořit speciální, špatně podmíněné polynomy, které nedokáže zohlednit, ani ty nízké. Základní myšlenky algoritmu byly poprvé publikovány Lindsey a Fox v roce 1992^[1] a dotisk v roce 1996.^[2] Po dalším vývoji byly v roce 2003 publikovány další práce^[3][4] a online brožuru.^[5] Program byl veřejnosti zpřístupněn v březnu 2004 na webových stránkách Rice University.^[6] Robustnější verze-2 byla vydána v březnu 2006 a aktualizována později v tomto roce.

Tři fáze programu Lindsey – Fox

Strategie implementovaná v algoritmu Lindsey – Fox pro faktorování polynomů je organizována ve třech fázích. První vyhodnotí polynom nad mřížkou v komplexní rovině a provede přímé hledání potenciálních nul. Druhá fáze vezme tyto potenciální nuly a „vyleští“ je aplikací Laguerrova metoda přiblížit je skutečným nulám polynomu. Třetí fáze tyto nuly znásobí dohromady nebo je „odfaktoruje“ a vytvoří tak polynom, který je ověřen proti originálu. Pokud některé z nul nebyly nalezeny, původní polynom je „vyfouknut“ vydělením polynomem vytvořeným z nalezených nul. Tento kvocient polynomu bude obecně nízkého řádu a lze jej započítat konvenčními metodami s dalšími novými nulami přidanými do množiny těch, které byly poprvé nalezeny. Pokud stále chybí nuly, provede se deflace, dokud nebudou nalezeny všechny nebo bude nutné celý program restartovat s jemnější mřížkou. Tento systém se ukázal jako rychlý, přesný a robustní ve třídě polynomů se skutečnými náhodnými koeficienty a dalšími podobnými, dobře podmíněnými polynomy.

Fáze jedna: vyhledávání potenciálních nul v mřížce

1. Postavte a polární souřadnice mřížka na komplexní rovině s roztečí odvozenou od stupně zohledňovaného polynomu
2. Použijte FFT k vyhodnocení polynomu v každém uzlu podél soustředných kruhů mřížky.
3. Hledejte relativní minima v každé sadě hodnot 3x3. Pokud je hodnota středu menší než hodnoty okraje, je to potenciální nula od Věta o minimálním modulu komplexní analýzy.

Fáze dvě: vyleštěte potenciální nuly

1. Aplikujte Laguerrův algoritmus na každou potenciální nulu a opravte ji tak, aby lépe aproximovala „skutečnou“ nulu polynomu
2. Vyzkoušejte jedinečnost sady leštěných nul a zahoďte všechny duplikáty, abyste získali sadu kandidátských nul

Fáze třetí: nefaktor, možná deflaci a ověření

1. Zfaktorujte vyleštěné nuly, tj. Rekonstruujte kandidátský polynom ve formě koeficientu z vyleštěných kandidátských nul
2. Pokud je stupeň rekonstruovaného polynomu stejný jako u původního polynomu a rozdíly v jejich koeficientech jsou malé, je factoring úspěšný a dokončený
3. Pokud některé nuly chyběly, vyfoukněte a faktorujte kvocientový polynom. Pokud to nenajde všechny zmeškané nuly, proveďte deflaci a faktor znovu, dokud nebudou nalezeny všechny nebo dokud nebudou nalezeny žádné nové.
4. Pokud deflace najde všechny nuly, které dokáže, a přesto je nenalezla všechny, navrhněte novou mřížku s jemnějším rozestupem a vraťte se k první fázi. Pokud čtyři restarty nenajdou všechny a / nebo chyba při rekonstrukci není malá, deklarujte selhání.

Popis tří fází

První fáze je důvod, proč je tento algoritmus tak efektivní a je tím, čím se odlišuje od většiny ostatních factoring algoritmy. Protože k vyhodnocení polynomu se používá FFT (rychlá Fourierova transformace), je možné rychlé vyhodnocení přes hustou mřížku v komplexní rovině. Aby bylo možné použít FFT, je mřížka strukturována v polárních souřadnicích. V první fázi této fáze je navržena mřížka se soustřednými kružnicemi určitého poloměru protínanými množinou radiálních čar. Pozice a rozteč radiálních čar a kruhů jsou vybrány tak, aby poskytovaly mřížku, která snad odděluje očekávané kořeny. Protože nuly polynomu s náhodnými koeficienty mají poměrně rovnoměrné úhlové rozložení a jsou seskupeny blízko jednotkové kružnice, je možné navrhnout vyhodnocovací mřížku, která velmi dobře odpovídá očekávané hustotě kořenů. Ve druhé fázi této fáze je polynom vyhodnocen v uzlech mřížky pomocí rychlé Fourierovy transformace (FFT). Přímé vyhodnocení je možné díky mimořádné účinnosti a přesnosti FFT. Ve třetí fázi této první fáze se provádí vyhledávání ve všech buňkách uzlu 3 x 3 vytvořených v mřížce. Pro každou buňku 3 x 3 (viz obrázek níže), pokud je hodnota polynomu ve středním uzlu buňky („x“) menší než hodnoty ve všech 8 uzlech na okrajích buňky ( "o"), střed je označen jako kandidát nula. Toto pravidlo je založeno na „teorémě minimálního modulu“, která uvádí, že pokud je relativní minimum absolutní hodnoty an analytická funkce přes otevřenou oblast existuje, minimum musí být nula funkce. Nakonec je tato sada perspektivních nul předána do druhé fáze. Počet je obvykle o něco větší než titul, protože některé byly nalezeny dvakrát nebo byly učiněny chyby. Počet by mohl být menší, pokud by některé nuly chyběly.

Obrázek 1: Řez polární souřadnicové sítě zobrazující buňku 3 uzly po 3 uzlech

Fáze dvě je tradičnější než ostatní dva. „Leští“ každou z potenciálních nul nalezených vyhledáním v mřížce. První fáze spočívá v použití iteračního algoritmu pro zlepšení přesnosti polohy nalezené při hledání mřížky. V dřívějších verzích programu Newtonova metoda byla použita, ale analýza a experiment to ukázaly Laguerrova metoda byl robustnější i přesnější. I když to vyžadovalo více výpočtů než Newtonova metoda pro každou iteraci, konvergovalo to v méně iteracích. Druhá fáze druhé fáze kontroluje duplikace. „Fuzzy“ test jedinečnosti se aplikuje na každou nulu, aby se vyloučily případy, kdy na dvou nebo více budoucích nulách iterace konvergovaly ke stejné nule. Pokud je počet jedinečných vyleštěných nul menší než stupeň polynomu, bude později nutná deflace. Pokud je číslo větší, došlo k nějaké chybě. Tato fáze spotřebovává největší část doby provádění celkové faktorizace, ale je zásadní pro konečnou přesnost kořenů. Jedním ze dvou kritérií úspěchu při factoringu polynomu je, že každý kořen musel být úspěšně vyleštěn oproti původnímu polynomu.

Fáze tři má několik fází a možné iterace nebo dokonce restart. První fáze třetí fáze přebírá všechny jedinečné vyleštěné nuly, které byly nalezeny v prvních dvou fázích, a znásobuje je dohromady do podoby koeficientu kandidátského polynomu („vyřazuje nuly“). Pokud je stupeň tohoto rekonstruovaného polynomu stejný jako u původního polynomu a pokud je rozdíl v jejich koeficientech malý, je faktorizace považována za úspěšnou. Často však při hledání mřížky a polských procesech první a druhé fáze chybělo několik nul, nebo test jedinečnosti zahodil legitimní nulu (možná je více), takže původní polynom je „deflován“ (rozdělen) rekonstruovanou polynom a výsledný kvocient (nízký stupeň) je započítán pro chybějící nuly. Pokud je nenajde všechny, proces deflace se opakuje, dokud nejsou všechny nalezeny. To umožňuje najít více kořenů (nebo velmi těsně seskupených kořenů), i když některé z nich byly vyřazeny dříve. Pokud v neobvyklém případě tyto další iterace deflace nenajdou všechny chybějící nuly, vytvoří se nová, jemnější mřížka a celý proces začal znovu v první fázi. Další podrobnosti o třetí fázi jsou v jiném modulu.

Vícenásobná objednávka a seskupené kořeny jsou neobvyklé v polynomech s náhodnými koeficienty. Pokud k nim ale dojde, nebo pokud se pokusíme o factoring špatně podmíněného polynomu, kořeny se ve většině případů najdou u programu Lindsey – Fox, ale se sníženou přesností. Pokud existuje nula několika objednávek (M-ta objednávka s M není příliš vysoká), vyhledá je mřížka, ale s multiplicitou jedna. Leštění se sblíží s kořenem vícenásobného řádu, ale ne tak rychle jako se zřetelným kořenem. V případě klastru s Q nuly, které spadají do jedné buňky, jsou chybně identifikovány jako jedna nula a leštění bude konvergovat pouze k jedné z nich. V některých případech mohou být dvě nuly blízko sebe v sousedních buňkách a vyleštit do stejného bodu. Ve všech těchto případech bude po testu jedinečnosti a deflaci kvocientový polynom obsahovat a M - 1 objednávka nula a / nebo Q - 1 nuly seskupeny dohromady. Každá z těchto nul bude nalezena později M - 1 nebo Q - 1 deflace. Mohou zde být problémy, protože Laguerreův lešticí algoritmus není tak přesný a nekonverguje tak rychle pro vícenásobnou nulu a může se dokonce lišit, když se použije na těsně seskupené nuly. Podmínka kvocientového polynomu bude také horší, pokud se jedná o vícenásobné a seskupené nuly. Pokud jsou nuly s více řády extrémně daleko od kruhu jednotek, používají se speciální metody pro manipulaci s více kořeny vyvinuté Zhonggang Zeng. Zengova metoda je silná, ale pomalá, a proto se používá pouze ve zvláštních případech [6]. Reference

Úspěšné dokončení faktorizace polynomu vyžaduje shodu nul na komplexní rovině měřené konvergencí Laguerrova algoritmu na každé z nul. Vyžaduje také porovnání polynomu rekonstruovaného z nalezených nul s původním polynomem měřením maximálního rozdílu v každém koeficientu.

Charakteristika algoritmu Lindsey – Fox

Protože FFT je tak účinným prostředkem pro vyhodnocení polynomu, lze použít velmi jemnou mřížku, která v rozumném čase oddělí všechny nebo téměř všechny nuly. A kvůli jemnosti mřížky je výchozí bod blízko skutečné nule a leštění téměř vždy konverguje v malém počtu kroků (konvergence je často vážným problémem v tradičních přístupech). A protože vyhledávání a leštění se provádí na původním polynomu, lze je provádět na každém kořenu současně na počítači s paralelní architekturou. Protože se vyhledávání provádí na buňce mřížky 3 x 3, nemusí být v paměti uchovávány více než tři soustředné kruhy mřížky najednou, tj. Není nutné mít v paměti celou mřížku. Lze provést určitou paralelizaci výpočtů FFT.

Deflace je často hlavním zdrojem chyby nebo selhání v tradičním iterativním algoritmu. Tady, kvůli dobrým výchozím bodům a výkonnému leštiči, je obecně zapotřebí velmi málo stupňů deflace a vytvářejí kvocient polynomu nízkého řádu, který je obecně dobře podmíněn. Kromě toho se pro kontrolu chyby provádí nefaktoring (vynásobení nalezených kořenů dohromady) v doméně FFT (pro stupeň větší než 500) a deflace se provádí částečně v doméně FFT a částečně v doméně koeficientů, v závislosti na kombinaci stabilita, akumulace chyb a rychlostní faktory.

U polynomů s náhodným koeficientem se počet nul zmeškaných vyhledávacím a polským stupněm pohybuje od 0 do 10 nebo příležitostně více. Při factoringu jednoho polynomu o 2 milionech stupňů nalezly fáze vyhledávání a leštění všechny 2 miliony nul v jednom hledání mřížky a nevyžadovaly žádnou deflaci, která by ukazovala sílu hledání mřížky v této třídě polynomu. Pokud je potřeba deflace, stačí jeden průchod téměř vždy. Pokud však máte několik nul nebo dvě (nebo více) velmi, velmi blízko sebe nul, test jedinečnosti zahodí legitimní nulu, ale bude nalezen pozdější deflací. Fáze tři má dostatek testů a alternativ, aby zvládla téměř všechny možné podmínky. Avšak podle samotné definice náhodných koeficientů je těžké absolutně zaručit úspěch.

Načasování programu Lindsey – Fox a příklady kořenových distribucí polynomů s náhodnými koeficienty jsou tady.

Reference