A parallel sparse linear system solver based on Hermitian/skew-Hermitian splitting

详细信息    查看全文

• 作者：Zhengyi Zhang ; ^{zhang701@purdue.edu" class="auth_mail" title="E-mail the corresponding author} ; Ahmed H. Sameh ^{sameh@cs.purdue.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Numerical linear algebra ; Krylov subspace methods ; Preconditioners ; Hermitian/Skew-Hermitian splitting ; Parallel numerical algorithms
• 刊名：Computers & Mathematics with Applications
• 出版年：2016
• 出版时间：October 2016
• 年：2016
• 卷：72
• 期：8
• 页码：2000-2007
• 全文大小：565 K

文摘

In this paper we describe a parallel algorithm for solving large sparse nonsingular linear systems class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0898122116304709&_mathId=si17.gif&_user=111111111&_pii=S0898122116304709&_rdoc=1&_issn=08981221&md5=8e8ad95f4f6c9fb4dc166b4d6753d2b7">class="imgLazyJSB inlineImage" height="11" width="50" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0898122116304709-si17.gif">class="mathContainer hidden">class="mathCode">$Ax=f$, of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0898122116304709&_mathId=si18.gif&_user=111111111&_pii=S0898122116304709&_rdoc=1&_issn=08981221&md5=383bf5997556ca634dc33cf2580e3b43" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$, using the Hermitian Skew-Hermitian splitting approach for handling the augmented linear system, of order class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0898122116304709&_mathId=si19.gif&_user=111111111&_pii=S0898122116304709&_rdoc=1&_issn=08981221&md5=c58cde9066d1eaab583d15d861e20fee" title="Click to view the MathML source">2nclass="mathContainer hidden">class="mathCode">$2n$, that arises from the linear least problem of minimizing the 2-norm of class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0898122116304709&_mathId=si20.gif&_user=111111111&_pii=S0898122116304709&_rdoc=1&_issn=08981221&md5=df9723dc52ec9cd5306a94a5ab9f2f4c">class="imgLazyJSB inlineImage" height="15" width="58" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0898122116304709-si20.gif">class="mathContainer hidden">class="mathCode">$(f-Ax)$. We use the restarted GMRES as the outer iteration with the Hermitian Skew-Hermitian Splitting (HSS) preconditioner. In solving systems involving this preconditioner, the most time consuming part deals with handling shifted skew-symmetric systems. We solve such systems using the successive overrelaxation (SOR). Theoretical analysis shows that our solver always converges to the unique solution of class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0898122116304709&_mathId=si17.gif&_user=111111111&_pii=S0898122116304709&_rdoc=1&_issn=08981221&md5=8e8ad95f4f6c9fb4dc166b4d6753d2b7">class="imgLazyJSB inlineImage" height="11" width="50" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0898122116304709-si17.gif">class="mathContainer hidden">class="mathCode">$Ax=f$. We present several numerical experiments that demonstrate the robustness of our solver compared to other schemes, and show its parallel scalability on a single multicore node.