อัลกอริทึม SPIKEเป็น ตัวแก้ปัญหาแบบ ขนานไฮบริ ด สำหรับระบบเชิงเส้นแบบแถบ ที่พัฒนาโดย Eric Polizzi และAhmed Sameh ^[1] ^ ^[2]

อัลกอริทึม SPIKE จัดการกับระบบเชิงเส้นAX = Fโดยที่Aเป็นเมทริกซ์แบบแถบที่ มี แบนด์วิดท์น้อยกว่ามากและFเป็นเมทริกซ์ที่มีด้านขวา โดยแบ่งออกเป็นขั้นตอนการประมวลผลล่วงหน้าและขั้นตอนการประมวลผลภายหลัง ${\displaystyle n\times n}$${\displaystyle n}$${\displaystyle n\times s}$${\displaystyle s}$

ในขั้นตอนการประมวลผลเบื้องต้น ระบบสมการเชิงเส้นAX = Fจะถูกแบ่งออกเป็นรูปแบบ บล็อกสามแถว

${\displaystyle {\begin{bmatrix}{\boldsymbol {A}}_{1}&{\boldsymbol {B}}_{1}\\{\boldsymbol {C}}_{2}&{\boldsymbol {A}}_{2}&{\boldsymbol {B}}_{2}\\&\ddots &\ddots &\ddots \\&&{\boldsymbol {C}}_{p-1}&{\boldsymbol {A}}_{p-1}&{\boldsymbol {B}}_{p-1}\\&&&{\boldsymbol {C}}_{p}&{\boldsymbol {A}}_{p}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}\\{\boldsymbol {X}}_{2}\\\vdots \\{\boldsymbol {X}}_{p-1}\\{\boldsymbol {X}}_{p}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {F}}_{1}\\{\boldsymbol {F}}_{2}\\\vdots \\{\boldsymbol {F}}_{p-1}\\{\boldsymbol {F}}_{p}\end{bmatrix}}.}$

สมมติไว้ก่อนว่าบล็อกแนวทแยงA _j ( j = 1,..., pโดยที่p ≥ 2 ) ไม่ เป็นเมทริกซ์เอกฐาน กำหนดเมทริกซ์ บล็อกแนวทแยง

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

ดังนั้นDจึงเป็นเมทริกซ์ไม่เอกฐานเช่นกัน การคูณD ⁻¹ทางซ้ายทั้งสองข้างของระบบจะได้

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}&{\boldsymbol {V}}_{1}\\{\boldsymbol {W}}_{2}&{\boldsymbol {I}}&{\boldsymbol {V}}_{2}\\&\ddots &\ddots &\ddots \\&&{\boldsymbol {W}}_{p-1}&{\boldsymbol {I}}&{\boldsymbol {V}}_{p-1}\\&&&{\boldsymbol {W}}_{p}&{\boldsymbol {I}}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}\\{\boldsymbol {X}}_{2}\\\vdots \\{\boldsymbol {X}}_{p-1}\\{\boldsymbol {X}}_{p}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}\\{\boldsymbol {G}}_{2}\\\vdots \\{\boldsymbol {G}}_{p-1}\\{\boldsymbol {G}}_{p}\end{bmatrix}},}$

ซึ่งจะต้องแก้ไขในขั้นตอนการประมวลผลภายหลัง การคูณทางซ้ายด้วยD ⁻¹เทียบเท่ากับการแก้ระบบสมการในรูปแบบ ${\displaystyle p}$

A _j [ V _j W _j G _j ] = [ B _j C _j F _j ]

(โดยละเว้นW ₁และC ₁สำหรับและV _pและB _pสำหรับ) ซึ่งสามารถดำเนินการแบบขนานได้ ${\displaystyle j=1}$${\displaystyle j=p}$

เนื่องจากลักษณะเป็นแถบของAทำให้มีเพียงไม่กี่คอลัมน์ซ้ายสุดของแต่ละV _jและเพียงไม่กี่คอลัมน์ขวาสุดของแต่ละW _jเท่านั้นที่จะมีค่าไม่เป็นศูนย์ คอลัมน์เหล่านี้เรียกว่าสไปค์ (spikes )

โดยไม่เสียความเป็นทั่วไปสมมติว่าแต่ละสไปค์ประกอบด้วยคอลัมน์จำนวนหนึ่ง ( ซึ่งน้อยกว่ามาก) (เติมคอลัมน์ศูนย์ให้กับสไปค์หากจำเป็น) แบ่งสไปค์ในV _jและW _j ทั้งหมด ออกเป็น ${\displaystyle m}$${\displaystyle m}$${\displaystyle n}$

${\displaystyle {\begin{bmatrix}{\boldsymbol {V}}_{j}^{(t)}\\{\boldsymbol {V}}_{j}'\\{\boldsymbol {V}}_{j}^{(b)}\end{bmatrix}}}$และ${\displaystyle {\begin{bmatrix}{\boldsymbol {W}}_{j}^{(t)}\\{\boldsymbol {W}}_{j}'\\{\boldsymbol {W}}_{j}^{(b)}\\\end{bmatrix}}}$

โดยที่V ( t ) j , วี ( ข ) j , ว ( t ) j และดับเบิลยู ( ข ) j มีมิติ แบ่ง X _jและG _jทั้งหมดในลักษณะเดียวกันออกเป็น ${\displaystyle m\times m}$

${\displaystyle {\begin{bmatrix}{\boldsymbol {X}}_{j}^{(t)}\\{\boldsymbol {X}}_{j}'\\{\boldsymbol {X}}_{j}^{(b)}\end{bmatrix}}}$และ${\displaystyle {\begin{bmatrix}{\boldsymbol {G}}_{j}^{(t)}\\{\boldsymbol {G}}_{j}'\\{\boldsymbol {G}}_{j}^{(b)}\\\end{bmatrix}}.}$

โปรดสังเกตว่าระบบที่ได้จากขั้นตอนการประมวลผลเบื้องต้นสามารถลดขนาดลงเป็นระบบบล็อกห้าเหลี่ยมที่มีขนาดเล็กกว่ามาก (โปรดจำไว้ว่ามีขนาดเล็กกว่ามาก) ${\displaystyle m}$${\displaystyle n}$

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{1}^{(t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{2}^{(t)}\\&{\boldsymbol {W}}_{2}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{2}^{(b)}&{\boldsymbol {0}}\\&&\ddots &\ddots &\ddots &\ddots &\ddots \\&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p-1}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{p-1}^{(t)}\\&&&&{\boldsymbol {W}}_{p-1}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{p-1}^{(b)}&{\boldsymbol {0}}\\&&&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&&&&&&{\boldsymbol {W}}_{p}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(t)}\\{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\\{\boldsymbol {X}}_{2}^{(b)}\\\vdots \\{\boldsymbol {X}}_{p-1}^{(t)}\\{\boldsymbol {X}}_{p-1}^{(b)}\\{\boldsymbol {X}}_{p}^{(t)}\\{\boldsymbol {X}}_{p}^{(b)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(t)}\\{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\\{\boldsymbol {G}}_{2}^{(b)}\\\vdots \\{\boldsymbol {G}}_{p-1}^{(t)}\\{\boldsymbol {G}}_{p-1}^{(b)}\\{\boldsymbol {G}}_{p}^{(t)}\\{\boldsymbol {G}}_{p}^{(b)}\end{bmatrix}}{\text{,}}}$

ซึ่งเราเรียกว่าระบบลดรูปและใช้สัญลักษณ์S̃X̃ = G̃แทน

เมื่อX ทั้งหมด ( t ) j และX ( ข ) j หากพบX ′ _j ทั้งหมด จะสามารถกู้คืนได้ด้วยความขนานที่สมบูรณ์แบบผ่านทาง

${\displaystyle {\begin{cases}{\boldsymbol {X}}_{1}'={\boldsymbol {G}}_{1}'-{\boldsymbol {V}}_{1}'{\boldsymbol {X}}_{2}^{(t)}{\text{,}}\\{\boldsymbol {X}}_{j}'={\boldsymbol {G}}_{j}'-{\boldsymbol {V}}_{j}'{\boldsymbol {X}}_{j+1}^{(t)}-{\boldsymbol {W}}_{j}'{\boldsymbol {X}}_{j-1}^{(b)}{\text{,}}&j=2,\ldots ,p-1{\text{,}}\\{\boldsymbol {X}}_{p}'={\boldsymbol {G}}_{p}'-{\boldsymbol {W}}_{p}{\boldsymbol {X}}_{p-1}^{(b)}{\text{.}}\end{cases}}}$

แม้ว่าในเชิงตรรกะจะแบ่งออกเป็นสองขั้นตอน แต่ในเชิงการคำนวณแล้ว อัลกอริทึม SPIKE ประกอบด้วยสามขั้นตอน:

1. แยกตัวประกอบของบล็อกแนวทแยง
2. การคำนวณค่าสูงสุด
3. แก้ระบบสมการที่ลดรูปแล้ว

แต่ละขั้นตอนเหล่านี้สามารถดำเนินการได้หลายวิธี ทำให้เกิดรูปแบบที่หลากหลาย สองรูปแบบที่โดดเด่นคือ อัลกอริทึม SPIKE แบบเรียกซ้ำ สำหรับกรณี ที่เมทริกซ์ไม่ เด่นที่แนวทแยง และ อัลกอริทึม SPIKE แบบตัดทอนสำหรับกรณีที่เมทริกซ์เด่นที่แนวทแยง ขึ้นอยู่กับรูปแบบ ระบบอาจได้รับการแก้ไขอย่างแม่นยำหรือโดยประมาณ ในกรณีหลัง SPIKE จะถูกใช้เป็นตัวปรับสภาพเบื้องต้นสำหรับวิธีการวนซ้ำ เช่นวิธีการของปริภูมิย่อย Krylovและการปรับปรุงแบบวนซ้ำ

ขั้นตอนแรกของขั้นตอนการประมวลผลล่วงหน้าคือการแยกตัวประกอบของบล็อกแนวทแยงA _jเพื่อความเสถียรเชิงตัวเลขเราสามารถใช้รูทีนของLAPACK ในการแยกตัวประกอบ LUโดยใช้การสลับแกนบางส่วน หรืออีกทางเลือกหนึ่ง เราสามารถแยกตัวประกอบโดยไม่ต้องใช้การสลับแกนบางส่วน แต่ใช้กลยุทธ์ "การเพิ่มความแข็งแกร่งของแนวทแยง" วิธีหลังนี้จะช่วยแก้ปัญหาของบล็อกแนวทแยงที่เป็นเอกฐานได้ XGBTRF

ในทางปฏิบัติ กลยุทธ์การเพิ่มประสิทธิภาพแนวทแยงมีดังนี้ ให้0 _εแทน "ศูนย์เครื่องจักร" ที่กำหนดค่าได้ ในแต่ละขั้นตอนของการแยกตัวประกอบ LU เราต้องการให้ตัวหมุนเป็นไปตามเงื่อนไข

|pivot| > 0 _ε ‖ A ‖ ₁ .

หากจุดหมุนไม่ตรงตามเงื่อนไข ก็จะได้รับการเสริมกำลังโดย

${\displaystyle \mathrm {pivot} ={\begin{cases}\mathrm {pivot} +\epsilon \lVert {\boldsymbol {A}}_{j}\rVert _{1}&{\text{if }}\mathrm {pivot} \geq 0{\text{,}}\\\mathrm {pivot} -\epsilon \lVert {\boldsymbol {A}}_{j}\rVert _{1}&{\text{if }}\mathrm {pivot} <0\end{cases}}}$

โดยที่ε เป็นพารามิเตอร์บวกที่ขึ้นอยู่กับ การปัดเศษของหน่วยของเครื่องและการแยกตัวประกอบจะดำเนินต่อไปด้วยตัวหมุนที่ได้รับการเพิ่มประสิทธิภาพ ซึ่งสามารถทำได้โดยใช้รูทีนของ ScaLAPACK เวอร์ชันที่ดัดแปลงแล้วหลังจากที่XDBTRFบล็อกแนวทแยงได้รับการแยกตัวประกอบแล้ว ค่าสูงสุดจะถูกคำนวณและส่งต่อไปยังขั้นตอนการประมวลผลภายหลัง

ในกรณีสองพาร์ติชัน กล่าวคือ เมื่อp = 2ระบบที่ลดรูปS̃X̃ = G̃จะมีรูปแบบดังนี้

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{1}^{(t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&{\boldsymbol {W}}_{2}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(t)}\\{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\\{\boldsymbol {X}}_{2}^{(b)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(t)}\\{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\\{\boldsymbol {G}}_{2}^{(b)}\end{bmatrix}}{\text{.}}}$

สามารถแยกระบบที่เล็กลงไปอีกได้จากจุดศูนย์กลาง:

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}\\{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\end{bmatrix}}{\text{,}}}$

ซึ่งสามารถแก้ไขได้โดยใช้การแยกตัวประกอบแบบบล็อก LU

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}\\{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {I}}_{m}\\{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}\\&{\boldsymbol {I}}_{m}-{\boldsymbol {W}}_{2}^{(t)}{\boldsymbol {V}}_{1}^{(b)}\end{bmatrix}}{\text{.}}}$

เมื่อX ( ข ) 1 และX ( t ) 2 พบX ( t ) 1 และX ( ข ) 2 สามารถคำนวณได้ผ่านทาง

X ( t ) 1 = จี ( t ) 1 − วี ( t ) 1 X ( t ) 2 ,

X ( ข ) 2 = จี ( ข ) 2 − ว ( ข ) 2 X ( ข ) 1 .

สมมติว่าpเป็นกำลังของสอง นั่นคือp = 2d ^{พิจารณา}เมทริกซ์บล็อกแนวทแยง

D̃ ₁ = diag( D̃ [1] 1 ,..., D̃ [1] หน้า /2 )

ที่ไหน

${\displaystyle {\boldsymbol {\tilde {D}}}_{k}^{[1]}={\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{2k-1}^{(t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{2k-1}^{(b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2k}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&{\boldsymbol {W}}_{2k}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}\end{bmatrix}}}$

สำหรับk = 1,..., p /2สังเกตว่าD̃ ₁ประกอบด้วยบล็อกแนวทแยงมุมลำดับ4 mที่ดึงมาจากS̃ตอนนี้เราแยกตัวประกอบS̃เป็น

S̃ = D̃ ₁ S̃ ₂ .

เมทริกซ์ใหม่S̃ ₂มีรูปแบบดังนี้

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{3m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{1}^{[2](t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{[2](b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2}^{[2](t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{2}^{[2](t)}\\&{\boldsymbol {W}}_{2}^{[2](b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{3m}&{\boldsymbol {V}}_{2}^{[2](b)}&{\boldsymbol {0}}\\&&\ddots &\ddots &\ddots &\ddots &\ddots \\&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p/2-1}^{[2](t)}&{\boldsymbol {I}}_{3m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{p/2-1}^{[2](t)}\\&&&&{\boldsymbol {W}}_{p/2-1}^{[2](b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{p/2-1}^{[2](b)}&{\boldsymbol {0}}\\&&&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p/2}^{[2](t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&&&&&&{\boldsymbol {W}}_{p/2}^{[2](b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{3m}\end{bmatrix}}{\text{.}}}$

โครงสร้างของมันคล้ายคลึงกับโครงสร้างของS̃ ₂ มาก โดยแตกต่างกันเพียงจำนวนหนามแหลมและความสูงของหนามแหลมเท่านั้น (ความกว้างยังคงเท่าเดิมที่m ) ดังนั้น ขั้นตอนการแยกตัวประกอบที่คล้ายกันจึงสามารถดำเนินการกับS̃ ₂เพื่อสร้างได้

S̃ ₂ = D̃ ₂ S̃ ₃

และ

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

ขั้นตอนการแยกตัวประกอบดังกล่าวสามารถทำซ้ำได้ หลังจากd − 1ขั้นตอน เราจะได้การแยกตัวประกอบ

S̃ = D̃ ₁ ⋯ D̃ _{d −1} S̃ _d ,

โดยที่S̃ _dมีเพียงสองจุดสูงสุด ระบบที่ลดขนาดลงจะได้รับการแก้ไขโดยวิธีต่อไปนี้

X̃ = S̃ −1 วัน D̃ −1 d −1 ⋯ D̃ −1 1 จี .

เทคนิคการแยกตัวประกอบ LU แบบบล็อกในกรณีสองพาร์ติชันสามารถใช้จัดการขั้นตอนการแก้ปัญหาที่เกี่ยวข้องกับD̃ ₁ , ..., D̃ _{d −1}และS̃ _d ได้ เนื่องจากขั้นตอนเหล่านี้โดยพื้นฐานแล้วเป็นการแก้ระบบอิสระหลายระบบของรูปแบบสองพาร์ติชันทั่วไป

การสรุปผลไปยังกรณีที่pไม่ใช่กำลังของสองนั้นแทบไม่ต้องทำอะไรเพิ่มเติมเลย

เมื่อAเป็นเมทริกซ์เด่นในแนวทแยงมุม ในระบบที่ลดรูปแล้ว

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{1}^{(t)}\\{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}&{\boldsymbol {0}}\\{\boldsymbol {0}}&{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{2}^{(t)}\\&{\boldsymbol {W}}_{2}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{2}^{(b)}&{\boldsymbol {0}}\\&&\ddots &\ddots &\ddots &\ddots &\ddots \\&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p-1}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}&{\boldsymbol {V}}_{p-1}^{(t)}\\&&&&{\boldsymbol {W}}_{p-1}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{p-1}^{(b)}&{\boldsymbol {0}}\\&&&&&{\boldsymbol {0}}&{\boldsymbol {W}}_{p}^{(t)}&{\boldsymbol {I}}_{m}&{\boldsymbol {0}}\\&&&&&&{\boldsymbol {W}}_{p}^{(b)}&{\boldsymbol {0}}&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(t)}\\{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\\{\boldsymbol {X}}_{2}^{(b)}\\\vdots \\{\boldsymbol {X}}_{p-1}^{(t)}\\{\boldsymbol {X}}_{p-1}^{(b)}\\{\boldsymbol {X}}_{p}^{(t)}\\{\boldsymbol {X}}_{p}^{(b)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(t)}\\{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\\{\boldsymbol {G}}_{2}^{(b)}\\\vdots \\{\boldsymbol {G}}_{p-1}^{(t)}\\{\boldsymbol {G}}_{p-1}^{(b)}\\{\boldsymbol {G}}_{p}^{(t)}\\{\boldsymbol {G}}_{p}^{(b)}\end{bmatrix}}{\text{,}}}$

บล็อกV ( t ) j และดับเบิลยู ( ข ) j โดยทั่วไปแล้วค่าเหล่านี้มักน้อยมาก เมื่อตัดค่าเหล่านี้ออกไป ระบบที่ลดรูปจะกลายเป็นระบบบล็อกแนวทแยง

${\displaystyle {\begin{bmatrix}{\boldsymbol {I}}_{m}\\&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{1}^{(b)}\\&{\boldsymbol {W}}_{2}^{(t)}&{\boldsymbol {I}}_{m}\\&&&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{2}^{(b)}\\&&&\ddots &\ddots &\ddots \\&&&&{\boldsymbol {W}}_{p-1}^{(t)}&{\boldsymbol {I}}_{m}\\&&&&&&{\boldsymbol {I}}_{m}&{\boldsymbol {V}}_{p-1}^{(b)}\\&&&&&&{\boldsymbol {W}}_{p}^{(t)}&{\boldsymbol {I}}_{m}\\&&&&&&&&{\boldsymbol {I}}_{m}\end{bmatrix}}{\begin{bmatrix}{\boldsymbol {X}}_{1}^{(t)}\\{\boldsymbol {X}}_{1}^{(b)}\\{\boldsymbol {X}}_{2}^{(t)}\\{\boldsymbol {X}}_{2}^{(b)}\\\vdots \\{\boldsymbol {X}}_{p-1}^{(t)}\\{\boldsymbol {X}}_{p-1}^{(b)}\\{\boldsymbol {X}}_{p}^{(t)}\\{\boldsymbol {X}}_{p}^{(b)}\end{bmatrix}}={\begin{bmatrix}{\boldsymbol {G}}_{1}^{(t)}\\{\boldsymbol {G}}_{1}^{(b)}\\{\boldsymbol {G}}_{2}^{(t)}\\{\boldsymbol {G}}_{2}^{(b)}\\\vdots \\{\boldsymbol {G}}_{p-1}^{(t)}\\{\boldsymbol {G}}_{p-1}^{(b)}\\{\boldsymbol {G}}_{p}^{(t)}\\{\boldsymbol {G}}_{p}^{(b)}\end{bmatrix}}}$

และสามารถแก้ไขได้อย่างง่ายดายแบบขนาน^[3 ]

อัลกอริทึม SPIKE ที่ถูกตัดทอนสามารถนำไปใช้ร่วมกับวิธีการวนซ้ำภายนอกบางอย่าง (เช่นBiCGSTABหรือการปรับปรุงแบบวนซ้ำ ) เพื่อเพิ่มความแม่นยำของคำตอบได้

การแบ่งพาร์ติชันและอัลกอริทึม SPIKE ครั้งแรกได้รับการนำเสนอใน^[4]และได้รับการออกแบบมาเพื่อปรับปรุงคุณสมบัติความเสถียรของตัวแก้ปัญหาแบบขนานที่ใช้การหมุน Givens สำหรับระบบสามแถว อัลกอริทึมเวอร์ชันหนึ่งที่เรียกว่า g-Spike ซึ่งใช้การหมุน Givens แบบอนุกรมที่ใช้แยกกันในแต่ละบล็อกได้รับการออกแบบสำหรับ GPU ของ NVIDIA ^[5]อัลกอริทึมแบบ SPIKE สำหรับ GPU ที่ใช้กลยุทธ์การหมุนแนวทแยงของบล็อกแบบพิเศษได้รับการอธิบายไว้ใน^[6 ]

อัลกอริทึม SPIKE ยังสามารถทำหน้าที่เป็นตัวปรับสภาพเบื้องต้น (preconditioner) สำหรับวิธีการวนซ้ำในการแก้ระบบสมการเชิงเส้นได้อีกด้วย ในการแก้ระบบสมการเชิงเส้นAx = bโดยใช้ตัวแก้แบบวนซ้ำที่ปรับสภาพเบื้องต้นด้วย SPIKE นั้น จะทำการดึงแถบตรงกลางจากAเพื่อสร้างตัวปรับสภาพเบื้องต้นแบบแถบMและแก้ระบบสมการเชิงเส้นที่เกี่ยวข้องกับMในแต่ละรอบการวนซ้ำด้วยอัลกอริทึม SPIKE

เพื่อให้ตัวปรับสภาพมีประสิทธิภาพ มักจำเป็นต้องมีการสลับแถวและ/หรือคอลัมน์เพื่อย้ายองค์ประกอบ "หนัก" ของเมทริกซ์ Aไปใกล้กับแนวทแยงมุม เพื่อให้ครอบคลุมโดยตัวปรับสภาพ ซึ่งสามารถทำได้โดยการคำนวณการเรียงลำดับสเปกตรัมแบบถ่วงน้ำหนักของ เมทริก ซ์ A

อัลกอริทึม SPIKE สามารถขยายให้ครอบคลุมมากขึ้นได้โดยไม่จำกัดตัวปรับสภาพเบื้องต้นให้เป็นแบบแถบอย่างเคร่งครัด โดยเฉพาะอย่างยิ่ง บล็อกแนวทแยงในแต่ละพาร์ติชันสามารถเป็นเมทริกซ์ทั่วไปได้ และสามารถจัดการได้โดยตรงด้วยตัวแก้ระบบสมการเชิงเส้นทั่วไป แทนที่จะใช้ตัวแก้แบบแถบ ซึ่งจะช่วยเพิ่มประสิทธิภาพของตัวปรับสภาพเบื้องต้น จึงทำให้มีโอกาสในการลู่เข้าที่ดีขึ้นและลดจำนวนรอบการคำนวณลง

Intelนำเสนอการใช้งานอัลกอริทึม SPIKE ภายใต้ชื่อIntel Adaptive Spike-Based Solver ^[7]นอกจากนี้ยังมีการพัฒนาตัวแก้ปัญหาแบบไตรไดอะโกนัลสำหรับ GPU ของ NVIDIA ^{[8] [9]}และ ตัวประมวลผลร่วม Xeon Phiวิธีการใน ^[10]เป็นพื้นฐานสำหรับตัวแก้ปัญหาแบบไตรไดอะโกนัลในไลบรารี cuSPARSE ^{[ 1 ]}ตัวแก้ปัญหาแบบหมุน Givens ก็ได้รับการใช้งานสำหรับ GPU และ Intel Xeon Phi เช่นกัน^{[ 2 ]}

• Gallopoulos, E.; Philippe, B.; Sameh, AH (2015). การประมวลผลแบบขนานในเมทริกซ์ Springer. ISBN 978-94-017-7188-7.