Zagnieżdżony podział na regularnej siatce

Podczas rozwiązywania rzadkich układów liniowych przy użyciu metod bezpośredniego faktoryzacji zastosowana strategia porządkowania znacząco wpływa na współczynnik wypełnienia niezerowych elementów w czynnikach. Jedną z takich strategii porządkowania jest rozbiór zagnieżdżony. Zastanawiam się, czy możliwe jest wcześniejsze wymyślenie zagnieżdżonej sekcji, biorąc pod uwagę tylko parametry siatki (załóżmy kwadratową różnicę skończonych różnic M x N z różnicami pierwszego rzędu).

Edytuj Właśnie odkryłem, że istnieje kod, który to robi: http://www.cise.ufl.edu/research/sparse/meshnd/

linear-algebra

— Victor Liu
źródło

Tak. Niedawno napisałem kod, aby to dokładnie zrobić.

Załóżmy, że masz siatkę i że dopuszczalne jest posiadanie węzłów liści o 100 wierzchołkach. Następnie można zdefiniować funkcję rekurencyjną, w której argumentami są: $n_x \times n_y$

wymiary i przesunięcia prostokątnej subdomeny
wskaźnik do tablicy, która będzie przechowywać zmiany kolejności

Procedura musi wtedy po prostu obliczyć iloczyn lokalnych wymiarów, aby zdecydować, czy domena jest akceptowalnie mała, aby być liściem, a następnie, jeśli tak, napisz naturalne wskaźniki węzła liścia (powiedz dla siatki ), w przeciwnym razie wytnij największy wymiar poddomeny, powtórz po lewej i prawej stronie, a następnie napisz naturalne wskaźniki separatora. $\mathrm{natural}(x,y)=x+y n_x$ $n_x \times n_y$

— Jack Poulson
źródło

Wydaje mi się, że moje pytanie brzmi bardziej: czy rozwarstwienie zagnieżdżone naprawdę rekurencyjnie przecina przestrzeń na pół? Ponadto, czy nakaz umieszczania wskaźników granicznych przed każdą prawą i lewą połową? Nigdy nie znalazłem prostego wyjaśnienia tego, co się dzieje.

— Victor Liu

Tak, zagnieżdżone rozwarstwienie jest bardzo proste, ale wskaźniki graniczne przechowujesz po lewej i prawej połowie. Chodzi o to, aby dwie subdomeny nie były bezpośrednio połączone, dlatego w przypadku różnic skończonych ważne jest, aby wziąć pod uwagę rozmiar szablonu przy podejmowaniu decyzji o grubości separatora. Zalecam przeczytanie przeglądu Liu metody wielopłaszczyznowej i nawiązanie połączenia, że każdy separator jest traktowany jako supernoda.

— Jack Poulson,

Ach tak, zdałem sobie sprawę, że krótko po tym, jak skomentowałem, a następnie dokonałem edycji. Dzięki za referencje.

— Victor Liu