Jaki jest obecny stan wielomianowych warunków wstępnych?

15

Zastanawiam się, co stało się z wielomianowymi warunkami wstępnymi. Interesuję się nimi, ponieważ wydają się być względnie eleganckie z matematycznego punktu widzenia, ale o ile czytałem w ankietach na temat metod kryłowa, generalnie wypadają bardzo słabo jako warunki wstępne. Według słów Saada i van der Hosta „obecne zainteresowanie tymi technikami prawie zniknęło” (tutaj) . Niemniej jednak w niedawnej przeszłości istniały zastosowania do obliczeń wielordzeniowych i GPU.

Czy ktoś może mi powiedzieć, a raczej wyjaśnić, w jakich kontekstach te metody są wciąż żywe i gdzie znaleźć dobrą ankietę na temat obecnego stanu techniki?

shuhalo
źródło
Niedawny papieru na arXiv ( arxiv.org/pdf/1806.08020.pdf ) bada wielomianowych przygotowujące do Arnoldi. W szczególności testują go pod kątem różnych problemów i uzyskują dobre przyspieszenie. Wnioskują, że ograniczenie operacji wektorowych z powodu wielomianowego wstępnego kondycjonowania „ma wielką nadzieję na unikanie komunikacji obliczania wartości własnych na komputerach o wysokiej wydajności”. Nie jestem jednym z autorów.
amarney

Odpowiedzi:

12

Aby uzyskać rozsądne wyniki, wielomianowe warunki wstępne wymagają dość dokładnych oszacowań spektralnych. W przypadku źle uwarunkowanych problemów eliptycznych najmniejsze wartości własne są zwykle oddzielane, tak że metody takie jak Czebyshev są dalekie od optymalnych. Najciekawszą właściwością metod wielomianowych jest to, że nie wymagają one żadnych produktów wewnętrznych.

W rzeczywistości dość popularne jest stosowanie wygładzaczy wielomianowych w przypadku wielu sieci. Główną różnicą w stosunku do warunku wstępnego jest to, że wygładzacz ma celować tylko w część widma. Na przykład wygładzacz wielomianowy jest obecnie domyślny w multigracie PETSc. Zobacz także Adams i in., Parallel multigrid smoother: wielomian versus Gauss-Seidel (2003) dla porównania.

Wstępne kondycjonery wielomianowe można stosować wyłącznie w celu zmniejszenia częstotliwości redukcji. Chociaż trzeba je ponownie dostroić dla każdej matrycy, oszczędności mogą być znaczące na sprzęcie, w którym redukcje są drogie (powszechne w dużych superkomputerach). Więcej informacji na ten temat zawiera McInnes, Smith, Zhang i Mills, Hierarchical and Nested Krylov Methods for Extreme-Scale Computing (2012) .

Jed Brown
źródło