Multigrid na siatce „nie idealnie prostokątnej”

9

Wprowadzenia wielosiatkowe zwykle używają prostokątnej siatki. Interpolacja wartości jest wówczas prosta: wystarczy interpolować liniowo na krawędzi między dwoma sąsiednimi węzłami grubej siatki, aby znaleźć wartość cienkiego węzła siatki na tej krawędzi.

Dla aplikacji MES mam siatkę, która jest „topologicznie” prostokątna, tak że połączenia węzłów są jak na prostokątnej siatce. Jednak węzły nie są idealnie wyrównane na siatce, ale mogą pokonywać niewielkie odległości w celu lepszego dopasowania do geometrii, jednocześnie zachowując połączenia jak w idealnej prostokątnej siatce.

Siatka wygląda mniej więcej tak: Przykład siatki . Widzisz: Połączenia są „zwykłe prostokątne”, ale pozycje węzłów nie.

Mogę sobie wyobrazić kilka „rozsądnych” schematów interpolacji geometrycznej dla takiego ustawienia.

Ogólne pytanie brzmi: czy multigrid wymaga idealnie wyrównanej prostokątnej siatki, czy też będzie działał w sytuacji opisanej powyżej, o ile interpolacja jest „dobra”? A może lepiej w takim przypadku użyć algebraicznej wielosiatki? (Którego nie wolę, ponieważ nie jest tak intuicyjny jak geometryczna wielosiatka.)

Michał
źródło
Nie jestem pewien, czy rozumiem, co masz na myśli mówiąc, że siatka jest prostokątnie topologiczna, ale gdzie węzły nie są wyrównane jak w siatce prostokątnej. Czy siatka jest strukturalną prostokątną siatką? Czy możesz to wyjaśnić, być może za pomocą rysunku? Czy problem polega na tym, że używasz prostokątnych elementów, które nie są w jednej linii, tak jak w przypadku korzystania ze strukturalnej siatki kartezjańskiej?
James
@James, zinterpretowałem pytanie OP jako bardziej podobne: „Co się stanie, jeśli mam trapezoidalną siatkę w trapezie?”.
Bill Barth

Odpowiedzi:

6

Multigrid nie potrzebuje kartezjańskiej (prostokątnej), jednolitej siatki. Potrzebne jest zdefiniowanie dokładnego i zgrubnego poziomu (ewentualnie rekurencyjnie, jeśli chcesz przejść ze schematu dwupoziomowego do wielopoziomowego) oraz zdefiniowanie operatorów interpolacji między tymi poziomami. Najłatwiej to wyjaśnić, jeśli rzeczywiście masz siatkę kartezjańską, ale w rzeczywistości możesz zacząć od dowolnej grubej siatki, udoskonal ją raz i po prostu tak: masz drobniejszą siatkę.

Innymi słowy, najłatwiej jest myśleć o siatkach pasujących do wielu siatek nie o drobnych oczkach i o tym, jak znaleźć grubsze oczka, ale zacząć od grubej siatki, z której uzyskuje się wyższe poziomy przez jednolite wyrafinowanie (tj. Każdy czworokąt jest podzielony na cztery mniejsze). Ponieważ zawsze możliwe jest jednolite udoskonalenie, łatwo można uzyskać hierarchię. Jest to przeciwieństwo zgrubienia, co nie zawsze jest możliwe, jeśli otrzymujesz konkretną siatkę, co znacznie utrudnia zdefiniowanie hierarchii siatki. (Dlatego ludzie wymyślili algebraiczne metody wielosieciowe do definiowania zgrubnych poziomów na podstawie samej macierzy, bez myślenia o siatce, z której została utworzona).

Wolfgang Bangerth
źródło
Zredagowałem przykład obrazu w pytaniu. Zakładam, że zgrubienie jest w moim przypadku wyjątkowo łatwe, biorąc tylko co 2 węzeł (na wymiar) i przeliczam MES dla tej siatki, aby uzyskać zgrubną macierz / operator. Zgrubny wektor danych można uzyskać, biorąc po prostu co 2 wartość węzła.
Michael
1
To może, ale nie musi, działać tak, jak chcesz (przypuszczam, że prawdopodobnie tak będzie, ale nie jestem do końca pewien). Chodzi o to, że w twoim przykładzie zgrubne komórki siatki nie pokrywają tego samego obszaru co dzieci, a zatem nie ma właściwości zagnieżdżania przestrzeni elementów skończonych: funkcje, które możesz reprezentować na grubej siatce, nie są podzbiorem funkcje, które możesz reprezentować na drobnej siatce. Joe Pasciak i Jim Bramble napisali artykuły na temat takich przypadków i myślę, że pamiętam, że można je zmusić do pracy. Ale nie jest to dla mnie od razu oczywiste.
Wolfgang Bangerth,
4

Powiedzmy, że masz następującą siatkę złożoną z prostokątnych elementów:

wprowadź opis zdjęcia tutaj

Jeśli interpolacja zostanie przeprowadzona przy założeniu normalnej strukturalnej prostokątnej siatki, wprowadzone zostaną błędy związane z tą niedokładną interpolacją. Innymi słowy, gdy ograniczysz wektor szczątkowy i przedłużając wektor błędu, wystąpią błędy z interpolacji.

Teraz, jeśli twoja siatka jest „bliska” byciu normalną strukturalną kartezjańską siatką, to może to działać, przynajmniej na początku, ale podejrzewam, że jedna z dwóch rzeczy wydarzy się w zależności od tego, jak daleko od ciebie siatka jest prostokątna:

1) Może się okazać, że multigrid zaczyna zbiegać się na początku. Mimo wszystko początkowo błąd jest duży, a „przybliżona” interpolacja oznacza po prostu, że niektóre węzły są nieco nadreprezentowane, podczas gdy niektóre są nieco niedostatecznie reprezentowane. Jednak może się okazać, że konwergencja ulega stagnacji, gdy rozwiązanie staje się dokładniejsze, a błędy interpolacji stają się ważniejsze.

2) Inną możliwością jest to, że multigrid kończy się zbieżnością, ale nie tak szybko, jak powinien, jeśli użyłeś poprawnej interpolacji.

Zasadniczo, nie korzystając z interpolacji, niedokładnie ważycie znaczenie niektórych węzłów. Na przykład w 2D, jeśli dany węzeł jest ważony jako:

[0,250,50,250,51.00,50,250,50,25]

w rzeczywistości, ponieważ twoja siatka nie jest dokładnie kartezjańska, powinna być:

[0,250,550,250,551.00,490,280,520,30]

spowoduje to błąd. To, czy ten błąd zapobiega konwergencji, będzie prawdopodobnie zależeć od tego, jak daleko od siatki jest kartezjań.

Chociaż AMG jest trudniejszy do zrozumienia / wdrożenia, wydaje się, że jest to poprawna metoda dla twojej sieci. Zastosowanie geometrycznej wielosiatki do „przybliżonej” prostokątnej siatki może działać, ale sądzę, że jest to w najlepszym przypadku rozwiązanie wspomagające pasmo. Mam nadzieję że to pomoże.

Aktualizacja : Myślę, że w mojej odpowiedzi mogło być trochę zamieszania. Nie twierdzę, że geometryczna wielosiatka będzie działać tylko z siatkami kartezjańskimi, ale raczej, że zdefiniowanie interpolacji (a zatem i ograniczenia) w siatkach kartezjańskich jest łatwe, natomiast w przypadku siatek niestrukturalnych może to być trudne. Rozważmy na przykład przypadek nawet prostej domeny 2D z trójkątną siatką. Udoskonalenie tej siatki jest łatwe - przynajmniej koncepcyjnie - ale jak zdefiniowałbyś operator interpolacji między grubą i cienką siatką? Wolę AMG po prostu dlatego, że działa bardziej jak solver „czarnej skrzynki”, tzn. Nie potrzebuje informacji na temat nieoczekiwanej siatki, jednak jest to tylko stronniczość / dziwactwo mojej osoby. Geometryczna wielosiatka może działać, o ile można zapewnić dokładne operatory interpolacji.

James
źródło
Mogę to przeczytać jako „zależy od tego, jak dobra jest twoja interpolacja”, prawda? Więc jeśli mogę wymyślić „idealny” schemat interpolacji, to powinienem być w porządku?
Michael
1
Myślę, że ta odpowiedź jest prawdziwa, ale myląca - mówi, że jeśli udajesz, że twoja siatka jest zwykła kartezjańska, kiedy nie jest, otrzymasz błędną odpowiedź. To prawda, ale można powiedzieć to samo o każdej metodzie numerycznej. Chodzi o to, że geometryczna wielosiatka jest dokładna na bardziej ogólnych siatkach, jeśli jest poprawnie zaimplementowana .
David Ketcheson,
Zgadzam się, że geometrycznej wielosiatki można używać z siatkami niekartezjańskimi, o ile są one wykonane poprawnie. Właśnie wziąłem pytanie OP jako pytanie, czy zadziałałoby użycie „w przybliżeniu” siatki kartezjańskiej, przy jednoczesnym zastosowaniu interpolacji zaprojektowanej dla rzeczywistej siatki kartezjańskiej.
James
@Michael Zasadniczo potrzebujesz jakiegoś sposobu definiowania operatorów interpolacji między różnymi poziomami siatki. Z kartezjańskimi siatkami jest to łatwe. W przypadku siatek niekartezjańskich może to szybko stać się trudniejsze w zależności od tego, jak nieuporządkowane są Twoje siatki. Jak mówi Wolfgang w swojej odpowiedzi, zawsze możesz stworzyć bardziej wyrafinowaną siatkę z grubej siatki, ale zdefiniowanie znaczących operatorów interpolacji może być trudne. Zaletą AMG jest to, że zachowuje się bardziej jak solver „czarnej skrzynki”, ponieważ nie potrzebujesz danych siatki do definiowania operatorów interpolacji. Wszystko czego potrzebujesz to matryca
James
@MIchael Tak, aby odpowiedzieć na twoje pytanie. Tak, jeśli możesz wymyślić dokładne operatory interpolacji, geometryczna wielosiatka będzie działać dobrze. Mam nadzieję że to pomoże.
James