Algoritmus SPIKE - SPIKE algorithm

The Algoritmus SPIKE je hybrid paralelní řešitel pro svázaný lineární systémy vyvinuli Eric Polizzi a Ahmed Sameh[1]^ [2]

Přehled

Algoritmus SPIKE se zabývá lineárním systémem SEKERA = F, kde A je pruhovaný matice šířka pásma mnohem méně než , a F je matice obsahující pravé strany. Je rozdělena na fázi předzpracování a fázi po zpracování.

Fáze předběžného zpracování

Ve fázi předzpracování lineární systém SEKERA = F je rozdělen do blokovat tridiagonální formulář

Předpokládejme, že úhlopříčka zatím blokuje Aj (j = 1,...,str s str ≥ 2) jsou nesmyslný. Definovat a úhlopříčka bloku matice

D = diag (A1,...,Astr),

pak D je také nesmyslná. Násobení doleva D−1 na obě strany systému dává

který má být vyřešen ve fázi postprocesingu. Násobení doleva D−1 je ekvivalentní řešení systémy formuláře

Aj[PROTIj Žj Gj] = [Bj Cj Fj]

(vynechání Ž1 a C1 pro , a PROTIstr a Bstr pro ), které lze provádět paralelně.

Vzhledem k pruhované povaze A, jen několik sloupců zcela vlevo PROTIj a několik sloupců zcela vpravo Žj může být nenulová. Tyto sloupce se nazývají hroty.

Fáze po zpracování

Bez ztráty obecnosti Předpokládejme, že každý hrot obsahuje přesně sloupce ( je mnohem méně než ) (v případě potřeby podložte hrot sloupci nul). Rozdělte hroty do všech PROTIj a Žj do

a

kde PROTI (t)
j
 
, PROTI (b)
j
 
, Ž (t)
j
 
a Ž (b)
j
 
jsou rozměrů . Rozdělte podobně všechny Xj a Gj do

a

Všimněte si, že systém produkovaný fází předzpracování lze zredukovat na blok pentadiagonální systém mnohem menší velikosti (připomeňme si to je mnohem méně než )

kterému říkáme snížený systém a označit S̃X̃ = G.

Jednou všechno X (t)
j
 
a X (b)
j
 
jsou nalezeny, všechny Xj lze obnovit pomocí dokonalého paralelismu pomocí

SPIKE jako polyalgoritmický pásový řešič lineárního systému

Přesto, že je logicky rozdělen do dvou fází, výpočetně, algoritmus SPIKE zahrnuje tři fáze:

  1. faktorizující diagonální bloky,
  2. výpočet hrotů,
  3. řešení redukovaného systému.

Každá z těchto fází může být provedena několika způsoby, což umožňuje velké množství variant. Dvě pozoruhodné varianty jsou rekurzivní SPIKE algoritmus pro ne-úhlopříčně dominantní případy a zkrácený SPIKE algoritmus pro úhlopříčně dominantní případy. V závislosti na variantě lze systém vyřešit buď přesně, nebo přibližně. V druhém případě se SPIKE používá jako předpoklad pro iterační schémata jako Krylovské podprostorové metody a iterativní upřesnění.

Rekurzivní SPIKE

Fáze předběžného zpracování

Prvním krokem fáze předzpracování je faktorizace diagonálních bloků Aj. Pro numerickou stabilitu lze použít LAPACK je XGBTRF rutiny LU faktorizovat je s částečným otočením. Alternativně je lze také faktorizovat bez částečného otáčení, ale se strategií „posílení úhlopříčky“. Druhá metoda řeší problém singulárních diagonálních bloků.

Konkrétně jde o strategii posílení úhlopříčky následovně. Nechat 0ε označuje konfigurovatelnou „nulu stroje“. V každém kroku faktorizace LU požadujeme, aby pivot splnil podmínku

| pivot | > 0εA1.

Pokud čep nevyhovuje podmínce, je posílen o

kde ε je kladný parametr v závislosti na stroji zaokrouhlení jednotky a faktorizace pokračuje s posíleným pivotem. Toho lze dosáhnout upravenými verzemi ScaLAPACK je XDBTRF rutiny. Poté, co jsou diagonální bloky faktorizovány, jsou hroty vypočítány a předány do fáze postprocesingu.

Fáze po zpracování

Pouzdro se dvěma oddíly

V případě dvou oddílů, tj. Když str = 2, redukovaný systém S̃X̃ = G má formu

Ze středu lze extrahovat ještě menší systém:

které lze vyřešit pomocí blokovat faktorizaci LU

Jednou X (b)
1
 
a X (t)
2
 
Jsou nalezeny, X (t)
1
 
a X (b)
2
 
lze vypočítat pomocí

X (t)
1
 
= G (t)
1
 
PROTI (t)
1
 
X (t)
2
 
,
X (b)
2
 
= G (b)
2
 
Ž (b)
2
 
X (b)
1
 
.
Pouzdro s více oddíly

Předpokládat, že str je síla dvou, tj. str = 2d. Zvažte blokovou diagonální matici

1 = diag ( [1]
1
 
,..., [1]
str/2
 
)

kde

pro k = 1,...,str/2. Všimněte si toho 1 v zásadě sestává z diagonálních bloků řádu 4m extrahováno z . Teď to rozložíme tak jako

= 12.

Nová matice 2 má formu

Jeho struktura je velmi podobná struktuře 2, liší se pouze počtem hrotů a jejich výškou (jejich šířka zůstává stejná) m). Lze tedy provést podobný faktorizační krok 2 k výrobě

2 = 23

a

= 123.

Takové faktorizační kroky lze provádět rekurzivně. Po d − 1 kroky, získáme faktorizaci

= 1d−1d,

kde d má jen dva hroty. Zmenšený systém bude poté vyřešen pomocí

X =  −1
d
 
 −1
d−1
 
 −1
1
 
G
.

Techniku ​​blokování LU faktorizace v případě dvou oddílů lze použít ke zpracování zahrnujících kroků řešení 1, ..., d−1 a d protože v podstatě řeší několik nezávislých systémů zobecněných dvoudílných forem.

Zobecnění na případy, kdy str není síla dvou je téměř triviální.

Zkrácený SPIKE

Když A je diagonálně dominantní, v redukovaném systému

bloky PROTI (t)
j
 
a Ž (b)
j
 
jsou často zanedbatelné. S jejich vynecháním se zmenšený systém stane úhlopříčkou bloku

a lze je snadno vyřešit paralelně [3].

Zkrácený algoritmus SPIKE lze zabalit do nějakého vnějšího iteračního schématu (např. BiCGSTAB nebo iterativní upřesnění ) ke zlepšení přesnosti řešení.

SPIKE pro tridiagonální systémy

První rozdělení a algoritmus SPIKE byl představen v [4] a byl navržen jako prostředek ke zlepšení vlastností stability paralelního řešiče Givens založeného na rotacích pro tridiagonální systémy. Pro NVIDIA GPU byla navržena verze algoritmu s názvem g-Spike, která je založena na sériových rotacích Givens aplikovaných nezávisle na každém bloku. [5]. Algoritmus založený na SPIKE pro GPU, který je založen na speciální blokové diagonální otočné strategii, je popsán v [6].

SPIKE jako předpoklad

Algoritmus SPIKE může také fungovat jako předpoklad pro iterační metody řešení lineárních systémů. Řešit lineární systém Sekera = b pomocí iteračního řešiče s předpřipraveným SPIKE se extrahuje středové pásmo A vytvořit pásový předkondicionér M a řeší lineární systémy zahrnující M v každé iteraci s algoritmem SPIKE.

Aby byl předběžný kondicionér efektivní, je obvykle nutná permutace řádků a / nebo sloupců k přesunu „těžkých“ prvků A blízko úhlopříčky tak, aby byly zakryty preconditionerem. Toho lze dosáhnout výpočtem vážené spektrální přeskupení z A.

Algoritmus SPIKE lze zobecnit tím, že neomezuje striktně pásmový předpoklad. Zejména může být diagonální blok v každé přepážce obecná matice, a proto s ní může pracovat spíše přímý obecný řešič lineárního systému než pásmový řešič. To zvyšuje preconditioner, a proto umožňuje větší šanci na konvergenci a snižuje počet iterací.

Implementace

Intel nabízí implementaci algoritmu SPIKE pod jménem Intel Adaptive Spike-Based Solver [7]. Tridiagonální řešiče byly vyvinuty také pro GPU NVIDIA [8][9] a koprocesory Xeon Phi. Metoda v [10] je základem pro třířadý řešič v knihovně cuSPARSE.[1] Řešitel založený na rotacích Givens byl také implementován pro GPU a Intel Xeon Phi.[2]

Reference

  1. ^ Polizzi, E .; Sameh, A. H. (2006). "Paralelní hybridní pásmový systémový řešič: algoritmus SPIKE". Parallel Computing. 32 (2): 177–194. doi:10.1016 / j.parco.2005.07.005.
  2. ^ Polizzi, E .; Sameh, A. H. (2007). "SPIKE: Paralelní prostředí pro řešení pásmových lineárních systémů". Počítače a kapaliny. 36: 113–141. doi:10.1016 / j.compfluid.2005.07.005.
  3. ^ Mikkelsen, C. C. K .; Manguoglu, M. (2008). "Analýza zkráceného SPIKE algoritmu". SIAM J. Matrix Anal. Appl. 30 (4): 1500–1519. CiteSeerX  10.1.1.514.8748. doi:10.1137/080719571.
  4. ^ Manguoglu, M .; Sameh, A. H .; Schenk, O. (2009). "PSPIKE: Paralelní hybridní řídký lineární systémový řešič". Přednášky z informatiky. 5704: 797–808. Bibcode:2009LNCS.5704..797M. doi:10.1007/978-3-642-03869-3_74. ISBN  978-3-642-03868-6.
  5. ^ „Intel Adaptive Spike-Based Solver - Intel Software Network“. Citováno 2009-03-23.
  6. ^ Sameh, A. H .; Kuck, D. J. (1978). "Na stabilních paralelních lineárních systémových řešeních". Deník ACM. 25: 81–91. doi:10.1145/322047.322054.
  7. ^ Venetis, I.E .; Kouris, A .; Sobczyk, A .; Gallopoulos, E .; Sameh, A. H. (2015). "Přímý třírozměrný řešič založený na rotacích Givens pro architektury GPU". Parallel Computing. 25: 101–116. doi:10.1016 / j.parco.2015.03.008.
  8. ^ Chang, L.-W .; Stratton, J .; Kim, H .; Hwu, W.-M. (2012). "Škálovatelný, numericky stabilní, vysoce výkonný třířadý řešič využívající GPU". Proc. Int'l. Konf. Vysoce výkonné výpočty, síťové úložiště a analýza (SC'12). Los Alamitos, CA, USA: IEEE Computer Soc. Tisk: 27: 1–27: 11. ISBN  978-1-4673-0804-5.

Další čtení