Istotność obliczeń o stałej i dowolnej precyzji

Widzę bardzo niewiele bibliotek / pakietów obliczeniowych o zmiennoprzecinkowym charakterze. Biorąc pod uwagę różne nieścisłości reprezentacji zmiennoprzecinkowej, powstaje pytanie, dlaczego nie ma przynajmniej niektórych pól, w których ta zwiększona dokładność mogłaby być warta zawiłości pracy z punktem stałym.

Czy są jakieś NAJWAŻNIEJSZE trudności w korzystaniu z, powiedzmy, solwera stałej wartości własnej? Jak powolne / szybkie, niedokładne / dokładne byłyby?

Powiązane: to i to

Zastosowanie arytmetyki punktu stałego może być odpowiednie w pewnych okolicznościach. Zasadniczo w przypadku obliczeń naukowych (przynajmniej w tym sensie, że większość ludzi o tym myśli) nie jest to właściwe ze względu na potrzebę wyrażenia napotkanych dużych zakresów dynamicznych. Jako przykład wymieniasz problemy z wartością własną, ale bardzo często w nauce interesują się najmniejsze wartości własne macierzy (np. Obliczenie stanu podstawowego układu kwantowego). Dokładność małych wartości własnych na ogół ulegnie pogorszeniu w porównaniu z dużymi wartościami własnymi, jeśli użyjesz stałego punktu. Jeśli macierz zawiera wpisy, które różnią się dużymi stosunkami, małe wartości własne mogą być całkowicie niewyrażalne w precyzji roboczej. Jest to problem z reprezentacją liczb; argumenty te zachowują się niezależnie od sposobu wykonywania obliczeń pośrednich. Możesz ewentualnie opracować skalowanie, aby zastosować je do obliczonych wyników, ale teraz właśnie wymyśliłeś zmiennoprzecinkowe. Łatwo jest konstruować macierze, których elementy są dobrze zachowane, ale których wartości własne są wyjątkowo źle zachowane (jakMacierze Wilkinsona , a nawet macierze z całkowicie liczbami całkowitymi ). Przykłady te nie są tak patologiczne, jak mogą się wydawać, a wiele problemów na najwyższym poziomie nauki wiąże się z bardzo źle zachowanymi matrycami, więc użycie stałego punktu w tym kontekście jest złym pomysłem (TM).

Możesz argumentować, że znasz wielkość wyników i nie chcesz marnować bitów na wykładnik, więc porozmawiajmy o półproduktach. Użycie punktu stałego ogólnie zaostrzy skutki katastrofalnych odwołań i zaokrągleń, chyba że naprawdę ciężko pracujesz z większą precyzją. Kara za wydajność byłaby ogromna i przypuszczam, że użycie reprezentacji zmiennoprzecinkowej o tej samej szerokości bitu mantysy byłoby szybsze i dokładniejsze.

Jednym z obszarów, w którym punkt stały może świecić, są określone obszary obliczeń geometrycznych. Zwłaszcza jeśli potrzebujesz dokładnej arytmetyki lub znasz wcześniej zakres dynamiczny wszystkich liczb, stały punkt pozwala wykorzystać wszystkie bity w twojej reprezentacji. Załóżmy na przykład, że chcesz obliczyć przecięcie dwóch linii, a punkty końcowe tych dwóch linii są znormalizowane, aby usiąść w kwadracie jednostkowym. W takim przypadku punkt przecięcia można przedstawić z większą dokładnością niż przy użyciu równoważnej liczby zmiennoprzecinkowej (co spowoduje marnowanie bitów na wykładniku). Teraz prawie na pewno jest tak, że liczby pośrednie wymagane w tym obliczeniu muszą być obliczone z większą precyzją lub przynajmniej wykonane bardzo ostrożnie (np. dzieląc iloczyn dwóch liczb przez inną liczbę, musisz bardzo uważać ). Pod tym względem punkt stały jest korzystniejszy bardziej z punktu widzenia reprezentacji niż z punktu widzenia obliczeń, i posunąłbym się do stwierdzenia, że ​​jest to ogólnie prawdą, gdy można ustalić wyraźne górne i dolne granice zakresu dynamicznego wyników algorytmu . Zdarza się to rzadko.

Kiedyś myślałem, że reprezentacje zmiennoprzecinkowe są surowe lub niedokładne (po co marnować bity na wykładnik ?!). Ale z czasem zdałem sobie sprawę, że to naprawdę jedna z najlepszych możliwych reprezentacji liczb rzeczywistych. Rzeczy w naturze pojawiają się na skalach dziennika, więc rzeczywiste dane kończą się na wielu wykładnikach. Również osiągnięcie najwyższej możliwej dokładności wymaga pracy na skalach logów, dzięki czemu śledzenie wykładnika jest bardziej naturalne. Jedynym innym konkurentem dla „naturalnej” reprezentacji jest symetryczny wskaźnik poziomu . Jednak dodawanie i odejmowanie w tej reprezentacji jest znacznie wolniejsze i brakuje w niej wsparcia sprzętowego IEEE 754. Ogromną uwagę poświęcono standardom zmiennoprzecinkowym, przez filar numerycznej algebry liniowej. Wydaje mi się, że wie, czym jest „właściwa” reprezentacja liczb.

Jako przykład tego, dlaczego arytmetyka dokładna / arytmetyka punktów stałych jest tak rzadko stosowana, rozważ to:

• W metodzie elementów skończonych, podobnie jak w prawie każdej innej metodzie stosowanej w obliczeniach naukowych, dochodzimy do układów liniowych lub nieliniowych, które są jedynie przybliżeniami do świata rzeczywistego. Na przykład w MES rozwiązany układ liniowy jest jedynie przybliżeniem pierwotnego równania różniczkowego cząstkowego (które samo w sobie może być jedynie przybliżeniem świata rzeczywistego). Po co więc wkładać ogromny wysiłek w rozwiązanie czegoś, co jest jedynie przybliżeniem?

• Większość używanych dziś algorytmów ma charakter iteracyjny: metoda Newtona, gradienty sprzężone itp. Te iteracje kończymy, ilekroć jesteśmy przekonani, że dokładność iteracyjna przybliżona do rozwiązania problemu jest wystarczająca. Innymi słowy, kończymy zanim będziemy mieli dokładne rozwiązanie. Jak poprzednio, po co używać dokładnej arytmetyki dla schematu iteracyjnego, skoro wiemy, że obliczamy tylko przybliżenia?

Jeśli spojrzysz na tę bibliotekę pod kątem poprawnego zaokrąglania: CRlibm , zobaczysz w dokumentacji, że ogólnie algorytmy muszą być udowodnione jako dokładne (z uzasadnionymi dowodami). Dlaczego? Stabilność i szybkość zbieżności wyniku funkcji nie ma odpowiedzi „jeden rozmiar dla wszystkich”. Krótko mówiąc, nie ma „darmowego lunchu” - musisz pracować, aby udowodnić swoje uzasadnienie. Wynika to z zachowania modelowanych funkcji, a nie z leżącego u ich podstaw sprzętu (niezależnie od tego, czy używasz jednostek całkowitych czy zmiennoprzecinkowych, chociaż tak, oba mają „gotchas”, takie jak przepełnienie / niedopełnienie, liczby normalne itp.) Nawet jeśli wynik szukasz zbieżności do liczby całkowitej, algorytm używany do znalezienia wyniku niekoniecznie jest bardzo stabilny.

Eigen to biblioteka C ++, która ma wiele algorytmów rozwiązywania macierzy, z których każda ma inne właściwości. Ta strona zawiera tabelę omawiającą kompromisy między szybkością a dokładnością dla różnych algorytmów używanych do rozwiązywania macierzy. Podejrzewam, że biblioteka Eigen może robić, co chcesz. :-)

Kilka ciekawych przykładów zastosowania arytmetyki precyzyjnej w matematyce znajduje się w książce Mathematics by Experiment autorstwa Jonathana Borweina i Davida Baileya. Jest też ta kontynuacja , której nie przeczytałem.