Benchmarki dla baz Gröbnera i wielomianowego rozwiązania systemowego

W ostatnim pytaniu System rozwiązywania 7 nieliniowych równań algebraicznych symbolicznie Brian Borchers eksperymentalnie potwierdził, że Maple może rozwiązać układ wielomianowy, z którym Matlab / Mupad nie może sobie poradzić. W przeszłości słyszałem od ludzi pracujących w tej dziedzinie, że Maple ma wysokiej jakości implementację baz Gröbnera i powiązanych algorytmów (które, jak zakładam, są tutaj używane).

Mam więc pokusę, by zasugerować: „Matlab jest powolny w tego rodzaju problemach, przełącz się na Maple”, ale chciałbym mieć dane, aby wykonać kopię zapasową tego stwierdzenia.

Czy istnieje zestaw wyników porównawczych, które porównują szybkość i skuteczność wdrożeń podstawowych Gröbnera i wielomianowych rozwiązań systemowych w różnych systemach algebry komputerowej? (Klon, Mathematica, symboliczny zestaw narzędzi Matlaba i tak dalej).

Opublikowałem tutaj kilka testów porównawczych: http://www.cecm.sfu.ca/~rpearcea/mgb.html

Są to zamówienia na całkowity stopień. Aby rozwiązać systemy, zwykle musisz wykonać więcej pracy. Czasy dotyczą typowego pulpitu średniotonowego z 2015 roku (czterordzeniowy Haswell Core i5).

Najszybszym systemem na jednym rdzeniu jest Magma, która wykorzystuje arytmetykę zmiennoprzecinkową i SSE / AVX. Magma jest najsilniejszym systemem, ponieważ ma dobre implementacje FGLM i spacer Groebnera (nie testowano). Algorytmy te są używane do konwersji podstawy całkowitego stopnia na podstawę leksykograficzną, która ma kształt trójkąta. Następnie zazwyczaj uwzględniałbyś wielomiany w najniższych zmiennych.

mgb to biblioteka C w Maple 2016, która implementuje algorytm F4 dla całkowitego stopnia i zamówień eliminacyjnych. Jego wydajność jest porównywalna z Magmą, gdy używa wielu rdzeni.

FGb to implementacja F4 firmy Faugere. Testowana tutaj wersja pochodzi z jego strony internetowej i jest szybsza niż wersja w Maple.

Giac to system open source z implementacją F4. Jest artykuł opisujący to http://arxiv.org/abs/1309.4044

Singular to system typu open source do wielu obliczeń w geometrii algebraicznej. Testy porównawcze wykorzystują tutaj „modStd”, który jest wielomodularną wersją algorytmu Buchberger. Widać, że algorytm Buchbergera nie konkuruje z F4. Podstawowym powodem jest to, że F4 amortyzuje koszt wszystkich operacji monomialnych. Poza tym Singular ma całkiem dobre implementacje FGLM i Groebner Walk, a także inne algorytmy przydatne do rozwiązywania.

Googling benchmark polynomial systemsprowadzi do kilku hitów, w tym do inicjatywy Computer Algebra Benchmark Initiative Uniwersytetu Mannheim . Niestety większość z nich jest nieaktualna lub nie działa. Najbardziej aktywna wydaje się być Wiki SymbolicData , ale o ile wiem, zbiera tylko problemy z testami porównawczymi , a nie wyniki testów .

Niektóre porównania (sięgające 1996 r.) Systemów wielomianowych Axiom, Macsyma, Maple, Mathematica, MuPAD i Reduce solver można znaleźć w Hans-Gert Gräbe, About the Polynomial System Solve Facility of Axiom, Macsyma, Maple, Mathematica, MuPAD, and Reduce , Preprint 11/96 des Instituts für Informatik, Universität Leipzig, Niemcy, grudzień 1996 . Wniosek jest taki, że Axiom, Maple i Reduce wygrywają z powodu korzystania z baz Gröbnera (inni tego nie zrobili w tym momencie), a Maple wychodzi nieco przed innymi.

Istnieje również stare porównanie na stronie SINGULAR pokazujące, że SINGULAR 2.0 (aktualny stan na grudzień 2015 r. To 4.0.2) pokonuje Maple, między innymi.

Z drugiej strony, nowsza publikacja ( Yao Sun, Dongdai Lin i Dingkang Wang. 2015. O implementacji opartych na sygnaturach algorytmów Gröbnera z wykorzystaniem liniowych procedur algebraicznych z M4RI. ACM Commun. Comput. Algebra 49, 2 (sierpień 2015) , 63–64 porównują implementację algorytmu Gröbnera przez autorów z algorytmem Maple, Singular i Magma, przy czym Magma jest szybsza od pozostałych dwóch pakietów o rząd wielkości (i wiąże się z implementacją autorów).

Wygląda więc na to, że zależy to w dużej mierze od problemu (wielkości i struktury) oraz wersji oprogramowania, który pakiet jest najszybszy. Niemniej jednak zalecenie, aby używać aktywnie opracowanego specjalnego systemu algebry komputerowej, takiego jak Singular, Magma lub Maple, zamiast ogólnego oprogramowania do obliczeń symbolicznych, jest rozsądne. Podwojone w przypadku zestawu narzędzi w postaci liczbowej zestawu oprogramowaniu , które dodaje kolejny poziom narzutu i zwykle jest o kilka wersji za samodzielnym oprogramowaniem, na którym się opiera (MuPAD, wcześniej Maple, w przypadku zestawu narzędzi Matlaba).

Zawsze należy pamiętać, że wyniki jakiegokolwiek testu porównawczego będą zależeć, oprócz wielkości problemu, od pola podstawowego, na którym zdefiniowany jest pierścień wielomianowy (liczby wymierne lub liczby całkowite modulo pewną potęgę liczby pierwszej).

Biblioteka LBG jest aktywnie rozwijany i wydajna realizacja algorytmu F5. Benchmark porównujący FGb z Magmą można znaleźć w:

Faugère, J.-C. (2010). FGb: Biblioteka do obliczania baz Gröbnera (str. 84–87). doi: 10.1007 / 978-3-642-15582-6_17