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ý ${displaystyle n imes n}$ matice šířka pásma mnohem méně než ${displaystyle n}$, a F je ${displaystyle n imes s}$ matice obsahující ${displaystyle s}$ 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ář

${displaystyle {egin {bmatrix} {oldsymbol {A}} _ {1} & {oldsymbol {B}} _ {1} {oldsymbol {C}} _ ​​{2} & {oldsymbol {A}} _ {2} & {oldsymbol {B}} _ {2} & ddots & ddots & ddots && {oldsymbol {C}} _ ​​{p-1} & {oldsymbol {A}} _ {p-1} & {oldsymbol {B}} _ {p-1} &&& {oldsymbol {C}} _ ​​{p} & {oldsymbol {A}} _ {p} konec {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} { oldsymbol {X}} _ {2} vdots {oldsymbol {X}} _ {p-1} {oldsymbol {X}} _ {p} konec {bmatrix}} = {egin {bmatrix} {oldsymbol {F }} _ {1} {oldsymbol {F}} _ {2} vdots {oldsymbol {F}} _ {p-1} {oldsymbol {F}} _ {p} konec {bmatrix}}.}$

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

D = diag (A₁,...,A_str),

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

${displaystyle {egin {bmatrix} {oldsymbol {I}} a {oldsymbol {V}} _ {1} {oldsymbol {W}} _ {2} & {oldsymbol {I}} & {oldsymbol {V}} _ {2} & ddots & ddots & ddots && {oldsymbol {W}} _ {p-1} & {oldsymbol {I}} & {oldsymbol {V}} _ {p-1} &&& old old symbol {W}} _ {p} & {oldsymbol {I}} end {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} {oldsymbol {X}} _ {2} vdots {oldsymbol {X}} _ {p-1} {oldsymbol {X}} _ {p} end {bmatrix}} = {egin {bmatrix} {oldsymbol {G}} _ {1} {oldsymbol {G}} _ {2} vdots {oldsymbol {G}} _ {p-1} {oldsymbol {G}} _ {p} konec {bmatrix}},}$

který má být vyřešen ve fázi postprocesingu. Násobení doleva D⁻¹ je ekvivalentní řešení ${displaystyle p}$ systémy formuláře

A_j[PROTI_j Ž_j G_j] = [B_j C_j F_j]

(vynechání Ž₁ a C₁ pro ${displaystyle j = 1}$, a PROTI_str a B_str pro ${displaystyle j = p}$), které lze provádět paralelně.

Vzhledem k pruhované povaze A, jen několik sloupců zcela vlevo PROTI_j 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ě ${displaystyle m}$ sloupce (${displaystyle m}$ je mnohem méně než ${displaystyle n}$) (v případě potřeby podložte hrot sloupci nul). Rozdělte hroty do všech PROTI_j a Ž_j do

${displaystyle {egin {bmatrix} {oldsymbol {V}} _ {j} ^ {(t)} {oldsymbol {V}} _ {j} ' {oldsymbol {V}} _ {j} ^ {(b )} konec {bmatrix}}}$ a ${displaystyle {egin {bmatrix} {oldsymbol {W}} _ {j} ^ {(t)} {oldsymbol {W}} _ {j} ' {oldsymbol {W}} _ {j} ^ {(b )} end {bmatrix}}}$

kde PROTI (t)
j , PROTI (b)
j , Ž (t)
j  a Ž (b)
j  jsou rozměrů ${displaystyle m imes m}$. Rozdělte podobně všechny X_j a G_j do

${displaystyle {egin {bmatrix} {oldsymbol {X}} _ {j} ^ {(t)} {oldsymbol {X}} _ {j} ' {oldsymbol {X}} _ {j} ^ {(b )} konec {bmatrix}}}$ a ${displaystyle {egin {bmatrix} {oldsymbol {G}} _ {j} ^ {(t)} {oldsymbol {G}} _ {j} ' {oldsymbol {G}} _ {j} ^ {(b )} end {bmatrix}}.}$

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 ${displaystyle m}$ je mnohem méně než ${displaystyle n}$)

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {1} ^ {(t)} {oldsymbol {0}} & { oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} & {oldsymbol {0}} {oldsymbol {0}} & {oldsymbol {W}} _ {2 } ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {2} ^ {(t)} & {oldsymbol {W}} _ {2} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {2} ^ {(b)} & {oldsymbol {0 }} && ddots & ddots & ddots & ddots & ddots &&& {oldsymbol {0}} & {oldsymbol {W}} _ {p-1} ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol { 0}} & {oldsymbol {V}} _ {p-1} ^ {(t)} &&&& {oldsymbol {W}} _ {p-1} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {p-1} ^ {(b)} & {oldsymbol {0}} &&&&& {oldsymbol {0}} & {oldsymbol {W} } _ {p} ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} &&&&&& {oldsymbol {W}} _ {p} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} end {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} ^ {(t)} {oldsymbol {X}} _ { 1} ^ {(b)} {oldsymbol {X}} _ {2} ^ {(t)} {oldsymbol {X}} _ {2} ^ {(b)} vdots {oldsymbol {X} } _ {p-1} ^ {(t)} {olds ymbol {X}} _ {p-1} ^ {(b)} {oldsymbol {X}} _ {p} ^ {(t)} {oldsymbol {X}} _ {p} ^ {(b) } end {bmatrix}} = {egin {bmatrix} {oldsymbol {G}} _ {1} ^ {(t)} {oldsymbol {G}} _ {1} ^ {(b)} {oldsymbol {G }} _ {2} ^ {(t)} {oldsymbol {G}} _ {2} ^ {(b)} vdots {oldsymbol {G}} _ {p-1} ^ {(t)} {oldsymbol {G}} _ {p-1} ^ {(b)} {oldsymbol {G}} _ {p} ^ {(t)} {oldsymbol {G}} _ {p} ^ {( b)} konec {bmatrix}} {ext {,}}}$

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 X′_j lze obnovit pomocí dokonalého paralelismu pomocí

${displaystyle {egin {cases} {oldsymbol {X}} _ {1} '= {oldsymbol {G}} _ {1}' - {oldsymbol {V}} _ {1} '{oldsymbol {X}} _ { 2} ^ {(t)} {ext {,}} {oldsymbol {X}} _ {j} '= {oldsymbol {G}} _ {j}' - {oldsymbol {V}} _ {j} ' {oldsymbol {X}} _ {j + 1} ^ {(t)} - ​​{oldsymbol {W}} _ {j} '{oldsymbol {X}} _ {j-1} ^ {(b)} {ext {,}} & j = 2, ldots, p-1 {ext {,}} {oldsymbol {X}} _ {p} '= {oldsymbol {G}} _ {p}' - {oldsymbol {W}} _ {p} {oldsymbol {X}} _ {p-1} ^ {(b)} {ext {.}} konec {případů}}}$

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ů A_j. 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_ε‖A‖₁.

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

${displaystyle mathrm {pivot} = {egin {cases} mathrm {pivot} + epsilon lVert {oldsymbol {A}} _ {j} Vert _ {1} & {ext {if}} mathrm {pivot} geq 0 {ext { ,}} mathrm {pivot} -epsilon lVert {oldsymbol {A}} _ {j} Vert _ {1} & {ext {if}} mathrm {pivot} <0end {cases}}}$

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

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {1} ^ {(t)} {oldsymbol {0}} & { oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} & {oldsymbol {0}} {oldsymbol {0}} & {oldsymbol {W}} _ {2 } ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {W}} _ {2} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} end {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} ^ {(t)} {oldsymbol {X}} _ {1} ^ { (b)} {oldsymbol {X}} _ {2} ^ {(t)} {oldsymbol {X}} _ {2} ^ {(b)} konec {bmatrix}} = {egin {bmatrix} { oldsymbol {G}} _ {1} ^ {(t)} {oldsymbol {G}} _ {1} ^ {(b)} {oldsymbol {G}} _ {2} ^ {(t)} {oldsymbol {G}} _ {2} ^ {(b)} konec {bmatrix}} {ext {.}}}$

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

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} {oldsymbol {W}} _ {2} ^ {(t) } & {oldsymbol {I}} _ {m} end {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} ^ {(b)} {oldsymbol {X}} _ {2} ^ {(t)} konec {bmatrix}} = {egin {bmatrix} {oldsymbol {G}} _ {1} ^ {(b)} {oldsymbol {G}} _ {2} ^ {(t)} konec {bmatrix}} {ext {,}}}$

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

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} {oldsymbol {W}} _ {2} ^ {(t) } & {oldsymbol {I}} _ {m} end {bmatrix}} = {egin {bmatrix} {oldsymbol {I}} _ {m} {oldsymbol {W}} _ {2} ^ {(t)} & {oldsymbol {I}} _ {m} end {bmatrix}} {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} & {oldsymbol {I}} _ {m} - {oldsymbol {W}} _ {2} ^ {(t)} {oldsymbol {V}} _ {1} ^ {(b)} end {bmatrix}} {ext {.}}}$

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 = 2^d. Zvažte blokovou diagonální matici

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

kde

${displaystyle {oldsymbol {ilde {D}}} _ {k} ^ {[1]} = {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V} } _ {2k-1} ^ {(t)} {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {2k-1} ^ {(b)} & {oldsymbol {0}} {oldsymbol {0}} & {oldsymbol {W}} _ {2k} ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {W}} _ {2k} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} end {bmatrix}}}$

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

S̃ = D̃₁S̃₂.

Nová matice S̃₂ má formu

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {3m} & {oldsymbol {0}} & {oldsymbol {V}} _ {1} ^ {[2] (t)} {oldsymbol {0} } & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {[2] (b)} & {oldsymbol {0}} {oldsymbol {0}} & {oldsymbol { W}} _ {2} ^ {[2] (t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {2} ^ {[2] (t)} & {oldsymbol {W}} _ {2} ^ {[2] (b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {3m} & {oldsymbol {V}} _ {2} ^ {[2] (b)} & {oldsymbol {0}} && ddots & ddots & ddots & ddots & ddots &&& {oldsymbol {0}} & {oldsymbol {W}} _ {p / 2-1} ^ {[2] (t)} & {oldsymbol {I}} _ {3m} & {oldsymbol {0}} & {oldsymbol {V}} _ {p / 2-1} ^ {[2] (t)} &&&& {oldsymbol {W}} _ {p / 2-1} ^ {[2] (b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {p / 2-1} ^ {[2] (b)} & {oldsymbol {0}} &&&&& {oldsymbol {0}} & {oldsymbol {W}} _ {p / 2} ^ {[2] (t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} &&&&&& {oldsymbol {W}} _ {p / 2} ^ {[2] (b)} & {oldsymbol {0 }} & {oldsymbol {I}} _ {3m} konec {bmatrix}} {ext {.}}}$

Jeho struktura je velmi podobná struktuře S̃₂, 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 S̃₂ k výrobě

S̃₂ = D̃₂S̃₃

a

S̃ = D̃₁D̃₂S̃₃.

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

S̃ = D̃₁⋯D̃_d−1S̃_d,

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

X = S̃ −1
d D̃ −1
d−1 ⋯D̃ −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í D̃₁, ..., D̃_d−1 a S̃_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

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {1} ^ {(t)} {oldsymbol {0}} & { oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} & {oldsymbol {0}} {oldsymbol {0}} & {oldsymbol {W}} _ {2 } ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} & {oldsymbol {V}} _ {2} ^ {(t)} & {oldsymbol {W}} _ {2} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {2} ^ {(b)} & {oldsymbol {0 }} && ddots & ddots & ddots & ddots & ddots &&& {oldsymbol {0}} & {oldsymbol {W}} _ {p-1} ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol { 0}} & {oldsymbol {V}} _ {p-1} ^ {(t)} &&&& {oldsymbol {W}} _ {p-1} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {p-1} ^ {(b)} & {oldsymbol {0}} &&&&& {oldsymbol {0}} & {oldsymbol {W} } _ {p} ^ {(t)} & {oldsymbol {I}} _ {m} & {oldsymbol {0}} &&&&&& {oldsymbol {W}} _ {p} ^ {(b)} & {oldsymbol {0}} & {oldsymbol {I}} _ {m} end {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} ^ {(t)} {oldsymbol {X}} _ { 1} ^ {(b)} {oldsymbol {X}} _ {2} ^ {(t)} {oldsymbol {X}} _ {2} ^ {(b)} vdots {oldsymbol {X} } _ {p-1} ^ {(t)} {olds ymbol {X}} _ {p-1} ^ {(b)} {oldsymbol {X}} _ {p} ^ {(t)} {oldsymbol {X}} _ {p} ^ {(b) } end {bmatrix}} = {egin {bmatrix} {oldsymbol {G}} _ {1} ^ {(t)} {oldsymbol {G}} _ {1} ^ {(b)} {oldsymbol {G }} _ {2} ^ {(t)} {oldsymbol {G}} _ {2} ^ {(b)} vdots {oldsymbol {G}} _ {p-1} ^ {(t)} {oldsymbol {G}} _ {p-1} ^ {(b)} {oldsymbol {G}} _ {p} ^ {(t)} {oldsymbol {G}} _ {p} ^ {( b)} konec {bmatrix}} {ext {,}}}$

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

${displaystyle {egin {bmatrix} {oldsymbol {I}} _ {m} & {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {1} ^ {(b)} & {oldsymbol {W}} _ {2} ^ {(t)} & {oldsymbol {I}} _ {m} &&& {oldsymbol {I}} _ {m} & {oldsymbol {V}} _ {2} ^ { (b)} &&&ddots & ddots & ddots &&&& {oldsymbol {W}} _ {p-1} ^ {(t)} & {oldsymbol {I}} _ {m} &&&&& {oldsymbol {I}} _ {m } & {oldsymbol {V}} _ {p-1} ^ {(b)} &&&&&& {oldsymbol {W}} _ {p} ^ {(t)} & {oldsymbol {I}} _ {m} &&&&&&&& {oldsymbol {I}} _ {m} konec {bmatrix}} {egin {bmatrix} {oldsymbol {X}} _ {1} ^ {(t)} {oldsymbol {X}} _ {1} ^ { (b)} {oldsymbol {X}} _ {2} ^ {(t)} {oldsymbol {X}} _ {2} ^ {(b)} vdots {oldsymbol {X}} _ {p -1} ^ {(t)} {oldsymbol {X}} _ {p-1} ^ {(b)} {oldsymbol {X}} _ {p} ^ {(t)} {oldsymbol {X }} _ {p} ^ {(b)} konec {bmatrix}} = {egin {bmatrix} {oldsymbol {G}} _ {1} ^ {(t)} {oldsymbol {G}} _ {1} ^ {(b)} {oldsymbol {G}} _ {2} ^ {(t)} {oldsymbol {G}} _ {2} ^ {(b)} vdots {oldsymbol {G}} _ {p-1} ^ {(t)} {oldsymbol {G}} _ {p-1} ^ {(b)} {oldsymbol {G}} _ {p} ^ {(t)} {oldsymbol {G}} _ {p} ^ {(b)} konec {bmatrix}}}$

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í

• Gallopoulos, E .; Philippe, B .; Sameh, A.H. (2015). Rovnoběžnost v maticových výpočtech. Springer. ISBN  978-94-017-7188-7.