Minimalizacja problemu z ponownym zamawianiem płytek:

Załóżmy, że mam następującą symetryczną macierz 9x9, oddziaływania N^2 między cząstkami N:

(1,2) (2,9) (4,5) (4,6) (5,8) (7,8), 

Są to interakcje symetryczne, więc implikuje to, że istnieje:

(2,1) (9,2) (5,4) (6,4) (8,5) (8,7),

W moim zadaniu załóżmy, że są one ułożone w formie macierzowej, gdzie pokazany jest tylko górny trójkąt:

t       0     1     2     (tiles)
  #   1 2 3 4 5 6 7 8 9   
  1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 0 0 0 0 0 0 1 ]
  3 [ x x 0 0 0 0 0 0 0 ]
  4 [ x x x 0 1 1 0 0 0 ] 
1 5 [ x x x x 0 0 0 1 0 ]
  6 [ x x x x x 0 0 0 0 ]
  7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
  9 [ x x x x x x x x 0 ] (x's denote symmetric pair)

Mam pewną operację, która jest obliczona na kafelkach 3x3, a każdy 3x3, który zawiera co najmniej jedną 1, musi być obliczony w całości. Powyższy przykład wymaga co najmniej 5 płytek: (0,0), (0,2), (1,1), (1,2), (2,2)

Jeśli jednak zamienię trzecią i dziewiątą kolumnę (i razem z wierszami, ponieważ jest to macierz symetryczna), permutując moje dane wejściowe:

t       0     1     2
  #   1 2 9 4 5 6 7 8 3 
  1 [ 0 1 0 0 0 0 0 0 0 ]
0 2 [ x 0 1 0 0 0 0 0 0 ]
  9 [ x x 0 0 0 0 0 0 0 ]
  4 [ x x x 0 1 1 0 0 0 ] 
1 5 [ x x x x 0 0 0 1 0 ]
  6 [ x x x x x 0 0 0 0 ]
  7 [ x x x x x x 0 1 0 ]
2 8 [ x x x x x x x 0 0 ]
  3 [ x x x x x x x x 0 ] (x's denote symmetric pair)

Teraz muszę tylko obliczyć 4 kafelki: (0,0), (1,1), (1,2), (2,2).

Ogólny problem:

Biorąc pod uwagę rzadką macierz NxN, znalezienie zmiany kolejności w celu zminimalizowania liczby płytek TxT, które należy obliczyć. Załóżmy, że N jest wielokrotnością T. Optymalne, ale niewykonalne rozwiązanie można znaleźć, wypróbowując N! permutacje porządku wejściowego.

W przypadku heurystyki wypróbowałem procedury minimalizacji przepustowości (takie jak Reverse CutHill McKee), procedury AMD Tima Davisa, jak dotąd bezskutecznie. Nie sądzę, że diagonalizacja jest tutaj właściwym podejściem.

Oto przykładowa macierz początkowa:

http://proteneer.com/misc/out2.dat

Krzywa Hilberta: Krzywa Hilberta

RCM: RCM

Krzywa Mortona: Krzywa Mortona

4
proteneer 28 wrzesień 2012, 01:05

2 odpowiedzi

Najlepsza odpowiedź

Istnieje kilka dobrze znanych opcji, które możesz wypróbować (niektóre z nich masz, ale nadal):

  • (Reverse) Cuthill-McKee zmniejszył przepustowość macierzy, zachowując wpisy blisko przekątnej.
  • Przybliżony stopień minimalny – lekkie przestawianie zmniejszające wypełnienie.
  • zmiana kolejności z redukcją wypełnienia dla rzadkiej dekompozycji LU/LL (METIS, SCOTCH) - dość ciężkie obliczeniowo.
  • zmiana kolejności krzywych wypełniania przestrzeni (coś w te linie)
  • drzewa czworokątne dla 2D lub drzewa octowe dla problemów 3D - przypisujesz cząstki do quadów/oktantów, a następnie numerujesz je zgodnie z identyfikatorem quad/oktant, podobnie jak w pewnym sensie krzywe wypełniania przestrzeni.
  • Samodzielny spacer jest używany na siatkach strukturalnych do przemierzania punktów siatki w takiej kolejności, że wszystkie punkty są odwiedzane tylko raz
  • wiele badań nad blokowaniem wpisów macierzy rzadkich zostało wykonanych w kontekście mnożenia macierzy rzadkiej-wektorowej. Wielu badaczy próbowało znaleźć dobrą zmianę kolejności w tym celu (nie mam idealnego rozeznania na ten temat, ale spójrz np. na ten artykuł)

Wszystkie one mają tendencję do znajdowania struktury w twojej macierzy iw pewnym sensie grupowania niezerowych wpisów. Skoro mówisz, że masz do czynienia z cząstkami, oznacza to, że twój wykres łączności jest w pewnym sensie „lokalny” z powodu przestrzennej lokalizacji interakcji cząstek. W takim przypadku metody te powinny być dobrze wykorzystane.

Oczywiście nie dostarczają one dokładnego rozwiązania problemu :) Ale są powszechnie stosowane właśnie w takich przypadkach, ponieważ w praktyce dają bardzo dobre zmiany kolejności. Zastanawiam się, co masz na myśli, mówiąc, że metody, których próbowałeś, zawiodły? Oczekujesz znalezienia optymalnego rozwiązania? Z pewnością poprawiają sytuację w porównaniu z losowym porządkowaniem macierzy.

Edytuj Proszę o krótkie omówienie kilku zdjęć. Stworzyłem trójwymiarową siatkę kartezjańską złożoną z 20-węzłowych elementów ceglanych. Dopasowałem rozmiar siatki tak, aby był podobny do twojego (~1000 węzłów). Również liczba niezerowych wpisów w wierszu nie jest zbyt odległa (51-81 w moim przypadku, 59-81 w twoim przypadku, jednak oba mają bardzo różne rozkłady). Poniższe zdjęcia pokazują RCM i Zmiana kolejności METIS dla siatki nieokresowej (po lewej) i siatki z pełną okresowością xyz (po prawej):Zmiana kolejności RCM

Następne zdjęcie przedstawia tę samą macierz zmienioną kolejnością za pomocą METIS i zmiany kolejności redukującej wypełnienie

metis reordering

Różnica jest uderzająca - zły wpływ okresowości jest wyraźny. Teraz kolejność Twojej matrycy za pomocą RCM i METIS

enter image description here

WOW. Masz problem :) Przede wszystkim myślę, że coś jest nie tak z twoim rcm, bo mój wygląda inaczej ;) Jestem też pewien, że nie możesz wywnioskować niczego ogólnego i sensownego na temat zmiany kolejności w oparciu o tę konkretną matrycę. Dzieje się tak, ponieważ rozmiar twojego systemu jest bardzo mały (mniej niż z grubsza 10x10x10 punktów) i wydaje się, że masz stosunkowo dalekosiężne interakcje między twoimi cząstkami. Dlatego wprowadzenie okresowości do tak małego systemu ma znacznie silniejszy zły wpływ na zmianę kolejności niż w moim ustrukturyzowanym przypadku.

Rozpoczęłbym poszukiwania dobrego ponownego uporządkowania od wyłączenia okresowości. Po zmianie kolejności, która Cię satysfakcjonuje, wprowadź okresowe interakcje. W systemie, który pokazałeś, nie ma prawie nic oprócz okresowości: ponieważ jest bardzo mała i ponieważ twoje interakcje są dość dalekosiężne, przynajmniej w porównaniu z moją siatką. W znacznie większych systemach okresowość będzie miała mniejszy wpływ na środek modelu.

Mniejszy, ale wciąż negatywny. Może mógłbyś zmienić swoje podejście do okresowości? Zamiast włączać okresowe spójności wprost do macierzy, skonstruuj i zmień kolejność macierzy bez tych splotów i wprowadź jawne równania wiążące ze sobą cząstki okresowe, np.:

V_particle1 = V_particle100

Lub innymi słowy

V_particle1 - V_particle100 = 0

I dodaj te równania na końcu swojej macierzy. Ta metoda nazywa się mnożnikami Lagrange'a. Oto jak to wygląda w moim systemie

enter image description here

Zachowujesz kolejność systemu nieokresowego, a okresowe połączenia są zlokalizowane w bloku na końcu macierzy. Oczywiście możesz go użyć do innych zmian kolejności.

Następny pomysł polega na tym, że zaczynasz od uporządkowanego systemu nieokresowego i wyraźnie eliminujesz wiersze macierzy dla okresowych węzłów, dodając je do wierszy, na które są mapowane. Powinieneś oczywiście wyeliminować również kolumny.

To, czy możesz ich użyć, zależy od tego, co robisz ze swoją matrycą. Na przykład mnożnik Lagrange'a wprowadza 0 na przekątnej - nie wszystkie solvery tak..

Zresztą to bardzo ciekawe badanie. Myślę, że ze względu na specyfikę Twojego problemu (tak jak rozumiem - nieregularnie rozmieszczone cząstki w 3D, z dość dalekosiężnymi oddziaływaniami) bardzo trudno jest pogrupować wpisy w macierzach. Ale jestem bardzo ciekawa, co w końcu robisz. Proszę daj mi znać!

3
angainor 29 wrzesień 2012, 23:15

Możesz szukać struktury danych, takiej jak kd-tree, R-tree, quadtree lub krzywa wypełniania przestrzeni. Zwłaszcza krzywa wypełniania przestrzeni może pomóc, ponieważ zmniejsza wymiar, a także zmienia kolejność płytek, a tym samym może dodać nowe informacje do siatki. Przy siatce 9x9 prawdopodobnie dobrze jest przyjrzeć się krzywym peano. Krzywa Mortona rzędu z jest lepsza dla mocy 2 siatek.

0
Micromega 28 wrzesień 2012, 16:31