Sonneveld Typed SOR Method vs. Classical SORMethod

全文

(1)九州大学学術情報リポジトリ Kyushu University Institutional Repository. Sonneveld Typed SOR Method vs. Classical SOR Method 日下部, 雄三 九州大学大学院システム情報科学府情報工学専攻 : 修士課程. 藤野, 清次 九州大学情報基盤研究開発センター. 春松, 正敏 本田技術研究所. https://doi.org/10.15017/1517963 出版情報:九州大学大学院システム情報科学紀要. 14 (2), pp.71-76, 2009-09-25. Faculty of Information Science and Electrical Engineering, Kyushu University バージョン: 権利関係:.

(2) 九州 大 学大 学 院 シ ステ ム情 報 科学 紀要 第14巻. 第2号. Research. Reports. Electrical. on. Information. Engineering. 平 成21年9月. Vol.14,. Sonneveld型SOR法vs.古 日 下 部 雄 三*・. Sonneveld. Typed. of. Science. Kyushu. No.2,. and. University. September. 2009. 典 的SOR法. 藤 野 清 次**・ 春 松 正 敏***. SOR. Method. vs.. Classical. SOR. Method. Yuzo KUSAKABE , Seiji FUJINO and Masatoshi HARUMATSU (Received June 12, 2009) Abstract: The classical SOR (Successive Over-Relaxation) method is originated from the dissertation by D. Young in 1950. After that, the SOR method has been often used for the solution of problems which stem from various applications. The SOR method, however, has many issues on possibility of the solution. Since the SOR method greatly depends on spectrum of iteration matrix, applicability of the SOR method is not robust. In this paper, we extend IDR (Induced Dimension Reduction) Theorem proposed by Sonneveld and van Gijzen to designing of the residual of the SOR method, and accelerate its convergence rate and stability. Through numerical experiments, we make reveal significant effect of accelerated residual of the proposed Sonneveld typed SOR method. Keywords: Iterative methods, IDR Theorem, Gauss-Seidel method, SOR method GS法 1.は. じ. め. に. IDR‑basedSOR法. 大 規 模 な 連 立 一 次 方 程 式 の 解 法 と して 反 復 法 が あ る.古. 典 的 逐 次 過 剰 緩 和 法(以. Over‑Relaxation)と. 下,SOR(Successive. 略 す)は1950年DavidYoungの. 論 文9)に 端 を 発 す る 反 復 解 法 で あ る.発 でSOR法. は 利 用 さ れ て き た が,そ. 表 後,多. の 反 復 法 な ど に 比 べ る と,そ. くの分野. の 収 束 性 は反 復 行 列 の. 使 用 に 止 ま り,SOR法. で,. の 導 出 お よ び 算 法 を 記 述 す る.ま. 法 中 の 係 数 の 選 択 に つ い て 考 察 す る.第4節 と古 典 的 なSOR法. やBiCG法. 型 反 復 法 と の 演 算 量 を 比 較 す る.第5節 て,IDR‑basedGS法 か に す る.最. お よ び 同SOR法. 後 に,第6節. で,数. で,. 系統 の 積 値実験 に. の収束特性を明 ら. で ま とめ る.. 系統. の 利用 範 囲 は限 定 され た も. の た め,他. た,算. IDR‑basedSOR法 学位. ス ペ ク トラ ム の 大 き さ に 強 く依 存 す る た め,BiCG法. の に な っ て い た.そ. の 概 要 と そ の 算 法 を 記 述 す る7).第3節. の 解 法 と組 み 合 わせ て の. 単 独 で使 用 さ れ る こ とは 少 な い の. 2.IDR‑basedGauss‑Seidel法 2.1一. 般 化 反復 法. 解 くべ き 線 形 方 程 式 を. が 現 状 で あ っ た. 2008年,P.SonneveldとM.vanGijzenら 理 と そ れ に 基 づ く反 復 解 法IDR(s)法. が 発 表 さ れ,そ. 期 的 な 着 想 と収 束 性 の す ば ら し さ か ら,非 て い る4)6).そ. し て,IDR定. のGauss‑‑Seidel(以. 下,GSと. 常 に 注 目さ れ. 理 を 応 用 した新 しい タ イ プ. が 提 案 さ れ た1)3).そ. 々 は そ の 方 法 の 拡 張 お よ び 古 典 的 なGS法. 性 を 調 べ た.そ. の 結 果,一. の画. こ. との 関連. 般 形 の行 列 に 適 用 可能 な形 に. IDR‑basedGS法. を 拡 張 す る こ とが で き た7).そ. こ で,本. 研 究 で は,GS法. の 加 速 版 で あ るSOR法. 理 を適 用. し,そ. とす る.こ. こ で,行. 列Aは 大 き さn×nの. の 結 果 新 し いIDR‑basedSOR法. 本 稿 の 構 成 は 次 の と お りで あ る.第2節. にIDR定. が 導 出 で きた の で. A=:M‑1V(2) と分 離 す る.こ き,解. こ で,行. で,IDR‑based. **九 ***本. 受付. Mx=1>x十b.(3) さ ら に,. x=M一iNx+M‑ib 十b'(4). と変 形 す る.こ. こ で,. 報 工学 専 攻修 士課 程 州 大学 情 報基 盤 研究 開 発セ ンター 田技術 研 究所. 列M,1Vは. 正 則 とす る.こ. くべ き 方 程 式(1)は 次 の よ う に 表 わ さ れ る.. =Bgじ 平 成21年6月12日. 般的. な 場 合 へ 拡 張 を 考 え 係 数 行 列Aを. 評 価 結 果 を 報 告 す る.. *情. 実 数 行 列,xとb. は η次 元 の 解 ベ ク トル と 右 辺 ベ ク トル と各 々 す る.一. 略 す)法 に 関 す る 素 朴 な 雛 形. の ま ま の 反 復 法IDR‑basedGS法 で,我. Ax=b(1). に よ りIDR定. B‑M‑11V,b'‑M"'b(5). の と.

(3) であ る。 こ こ で,次. の 漸 化 式 を 考 え る.こ. こ で,Xoは. 初期近似 Xk+1==xic十rk十7kdrh十. 解 ベ ク トル で あ る.. 伽d晦,(17). ㌘解1=B(rte÷7kdrk) =M}1!V(rk十ryhdrk).(18). Xh+1=BXIe十b',k==0,1,2,....(6) ス ペ ク トル 半 径p(β)<ω. の 関 係 が 成 り立 つ と き こ の 漸. た だ し,上. 化 式 は 収 束 す る.ま. 差 ベ ク トル 恥 は 次 の 式 で 定 義. 収 束 し た 相 対 残 差 と真 の 相 対 残 差 に 相 違 が 生 じ る 場 合 が. た,残. あ る.そ. す る.. 記 の 漸 化 式 で はrk:M‑1(b‑.4職)と. こ で,rkを. 〆 たと置 き 換 え,〆 鳶 ・ ・M‑irkと. と次 の 近 似 解 ベ ク トルXk+1と rk=:BXk十b'‑Xk.(7) 上 記 の 式(7)に ルrk+1は. な り,. する. 残 差 ベ ク トルrk÷1の 漸 化 式. が 得 られ る.. よ り 近 似 解 ベ ク トルXk+xと. 残 差ベ ク ト. 次 の 漸 化 式 で 表 す こ と が で き る.た. re=M‑1(b‑AXe)で. だ し,. 晦+1=Xk十M一1(rk十tykdrh)十7kdXk,(19) 7纏1=・B(rk+7kdrk). あ る.. ‑NW‑i(rfe十7kdrk).(2o) Xk+1=Xk+rk,(8). こ の と き,反. 復 行 列 は 従 来 のB==M. rk÷1=Brk.(9). B=NM‑1と. な る が,ス. こ の と き,上. 記 の2つ の 漸 化 式 か ら構 成 さ れ る 算 法 は 定 常. 反 復 法 の 漸 化 式 を反 復 アル ゴ リズ ム に置 き換 え た もの で あ る.そ. の 収 束 性 は 反 復 行 列Bに. 位 行 列 の と きRichardsonの 次 に,IDR定. 依 存 す る.ま. た,Bが. 差rfe+1が 式(9)を 拡 張 し た. 次 の 関 係 式 を 満 た す と す る. rk+1=B(rk+7k(rk‑rk̲1)).(10) 係 数 鰯 は,原. 論 文3)に 従 い,IDR定. 理 で導 入 され た任 意. ベ ク トルpと の 直 交 関 係,. 蹴+繁(rk‑rk̲1)⊥P(11) す な わ ち,. (P,rib十 〇 γh(rk‑rk̲1))ニ0(12) か ら 求 め られ る.式(10)か. ら次 の 漸 化 式 が 導 け る.. 関. 係 は 同 様 に 成 り立 ち 上 記 の 漸 化 式 も収 束 す る8).一 一般 化 反 復 法の 算法 を以 下 に示 す。 一般化 反 復法 の算 法. Let xo be an initial solution, put ro = b - Axo, Let p be a random vector, set -yo=0, for k= 0, 1, 2, .. . sk = M-1 (rk +'Ykdrk), dxk+1 = sk + ''kdxk, drk+1 = Nsk - Tk, rk+1 = Tk+ drk+1, xk+1 = Xk + dxk+1, ifIlrk+1U2< ro112 E stop 11 ,/k+1= (p, rk+1) 03, drk+1)' end for.. (B‑1)(Xk+1‑Xk) =rk÷1一. は な く. 単. 算 法 に な る2).. 理 に 基 づ き,残. 11>で. ペ ク トル 半 径p(B)<1.oの. 僧海. =B(rκ+7k(rle‑rk‑・))‑rh ==(B‑∫)(rk‑十. 一tγkβ(Xk‑Xh̲1)).(13). 共 通 因 子(B‑1)を. Xk畢1一. 両 辺 か ら 除 去 す る と,. β(Xk‑Xk̲1). =rk十%(rk‑riC̲i)・ と な る.よ. 係 数 行 列Aを 以 下 の よ うに 分 離 す る 。. メ 隻==L÷D十. 灘海. =rk+伽. 2.21DR‑basedGS法. こ こ で,五 は 狭 義 下 三 角 行 列,Dは 十%(Xk‑Xk̲1)(14). 三 角 行 列 とす る.GS法. 狭 義上. と お く と,IDR定. 僧ん̲1(16). と 定 義 し,そ. 理 に 基 づ い た 場 合 の 近 似 解 ベ ク トル. 残 差 ベ ク ト ルrk+1は. ト1),(22). ノ 〉=・‑U(23). 一Xfe̲1,(15). drtC=rk一. Xk+1と. 対 角 行 列,Uは. で は 反 復 行 列B瓢1VM『1は. っ て,. M=L一 d簸=簸. 乙乙(21). 次 の 漸 化 式 で 表 せ る.. れ に よ りIDR‑basedGS法(以. 略 す)が 得 られ る.. 下,IGS法. と.

(4) 3.IDR‑basedSOR法 3.11DR‑basedSOR法 第2節 と 同 様 に,一. 般 化 反 復 法 の 算 法 をSOR法. る こ と を 考 え る.SOR法 Xk+1の. 7・一 一(騎. の導 出. は,GS法. 更 新 の 際 に,近. に適 用す. の 近 似 解 ベ ク トル. 似 解 ベ ク トル の 修 正 量 を 加 速 係 数. と係 数7kを 決 定 す る.こ. あ る が,pは. SOR法. 方,後. 1. ハ4=L十. で 定 義 さ れ る.以. 意 ベ ク トルpとrh+1を. 直交 させ. のpはp=(NM‑1)‑Tpと. する必要が. 元 々任 意 で あ る た め そ の 必 要 性 が な い.一. 者 の 選 択2の 場 合,llrk+il12を. 最 小 化 す る た め に は,. 式(28)中 のrk,drkは,riC=NM‑irk,drk=NM‑idrk. 一D,(24). 1ω 一1)D一. 1V=(一. 加 速 係 数 ωを 含 む. れ を 選 択2と 呼 ぶ.. 前 者 の 選 択1の 場 合,任 る に は,式(27)中. ω で 緩 和 す る こ と に よ り 収 束 を 速 め る 反 復 法 で あ る. の 反 復 行 列B=1VM‑1は. 錦(28). と各 々 お く必 要 が あ る.し σ(25). 算 量 が 増 加 す る た め,. あ ま り得 策 で は な い と思 わ れ る.. 下 に,IDR‑basedSOR法. の 算 法 を 示 す.. 4.反 IDR‑basedSOR法. か し,演. の 算 法. 復1回. あ た りの演算 量. Table1に,SOR法,ISOR法,積. 型 反 復 法 の 反 復1回. あ た り の 演 算 量 を 示 す.積. 型 反 復 法 は,実. 非対称行列を. Letxobeaninitialsolution,. 解 く と き よ く 使 用 さ れ るBiCGStab法,GPBiCG法, putro=b‑AXo,. BiCGSafe法. を 選 ん だ.表. 中 の"NNZ"は. 非 零 要 素 数,Av. Letpbearandomvector,. は行列・ ベ ク トル 積 計 算,(u,v)は. ベ ク トル の 内 積 計 算,. set戸 γo=0,. u±vは. ベ ク トル 同 士 の 加 減 算,a"は. 定 数 と ベ ク トル の. fork=0,1,2,.... 積 を 各 々 意 味 す る.ま Sk‑(L+LD)一. た,各. 計算の右側の括弧は必要な. ・(rk+7kd,k),. 演 算 量 の 単 位 を 意 味 す る.た dXh+1=Sk十tykdXle,. だ し,SOR法. で は行 列 ・ ベ ク. トル 積 お よ び ベ ク トル 同 士 の 加 減 算(表 中 の"*"つ. 1d τ ・k+1=一((1‑一)D十. σ)Sk‑rk,. 1回,3回. で あ る.た. だ し,収. き)は 各. 束 判 定 の た め に は 残 差rkの. rk+1=rk十drk+1,. 更 新 が 必 要 で あ る が,SOR法 い.そ. 階1需ll'伽1,. 1fll. の た め,実. ク トル. 同 士 の 加 減 算 は4回 に 増 え る こ と を 付 記 す る.. 。。ll、 ≦̀stop (P,riC+1)7. k+1=一(. P,drk+、), endfor.. Table 1 Computational method. method. 3.2係. の算 法 中 にそ れ が存 在 しな. 際 に は 行 列 ベ ク トル 積 が2回,ベ. 数7kの. 選 択. 残 差 ベ ク トルrk+1の. IGS1 SOR1* ISOR1 BiCGStab GPBiCG2 BiCGSafe. 更 新 の 式 は 中 間 ベ ク トル を 用 い な. い 場 合,. rk+、‑NM"'(rk+tykdrk)(26) と 書 き 表 せ る,こ. Av (x2NNZ). の と き 任 意 ベ ク ト ルpとrk+%dTん. 2 2. cost per one iteration. of each. (u, v). u+ v. ay. (x2n) 2 0 2 4 7 7. (xn) 5 3* 5 6 16 14. (xn) 2 2 2 6 13 13. との. 直 交 条 件 か ら,. ツー. 辮)(27). と係 数7kが 決 ま る.こ. 5.数. 一方. れ を 選 択1と 呼 ぶ.. ,残 差 ベ ク トルrk+1の. 中 の 式 の ノ ル ム:II晦+伽 め る.す. 5.1テ. 値. 更 新 の 式 に お い て,括. 弧の. 伽 副2の 最 小 化 か ら 係 数"〉 ・iCを 決. 実. 験. Table2に. ス ト問 題 テ ス ト行列(12個)の 仕様 を示 す.テ ス ト行 列. はフ ロ リダ大 学 の疎 行列 デ ー タベー ス か ら選 出 した5).各 行 列 の 解 析 分 野 は,構 造 解 析,流 体 力 学,回 路 解 析,音. な わ ち,. 響 解析 と し,こ れ らの行 列 でISOR法. の性能 を 評価 す る.. (rh十tykdriC,rk十7kdrk) 一(rk ,rk)+2ッ を 係 数%の2次. 、(rk,drk)+ッ. 竃(drk,drk). 式 と考 え て7kで 偏 微 分 す る.そ. れ た 式(rk,drk)+tyk(drk,drk)の. 5.2計 し て,得. ら. 値 が0で あ る こ と か ら,. 算 機 環 境 と計 算 条 件. 計 算 機 環 境 と計 算 条 件 は 次 の 通 り で あ る.計 す べ て 倍 精 度 浮 動 小 数 点 演 算 で 行 った.計. 算は. 算機 は.

(5) Table. 2 Specifications. of test. matrices.. Table. 3 Convergence. matrix matrix. dimension. NNZ. ave.. field. 95,053. 6.45. epb225,228. 175,027. 6.94. epb384,617. 463,625. 5.48. structural. 352,762. 26.10. poisson3Db. 85,623. 2,374,949. 27.74. xenonl48,600. 1,181,120. 24.30. raefsky23,242. 294,276. 90.77. hydro-. 1,488,768. 70.22. dynamic. 126,150. 7.10. electrical. 177,168. 6.80. memplus. 17,758. wang326,064. -. IIM SOR.. 13,514. 21,200. GS. ISOR. p (7) -. Rill=. ISORrand const. wang426,068. 177,196. 6.80. k3plates11,107. 378,927. 34.12. シ ョ ン は一〇3を 使 用 し た.時 間 計 測eetWetimeを. 用 い,最. 適化オ プ. 間 の 計 測 に は,Fortranの. 密 解 がth:(1,…,1)Tと. う に,b=A企. と 定 め た.調. 法,IGS法,古. 典 的SOR法,ISOR法,BiCGStab法,. 時. なるよ. べ た 反 復 法 は,古. GPI3iCG法,BiCGSafe法 ISOR法. Elm.. ンパ イ. 用 い た 。 計 算 時 間 の 単 位 は 秒 と す る.. 右 辺 項 ベ ク トルbは,厳. の 計7種. re←b‑AXo),区 与 え た.SOR法,ISOR法 0.1刻 み で11通. 典 的GS. 定 条 件 は,相. ism.. ism=. BiCGStab (const) GPBiCG (all)BiCGSafe (r0) nalIMEMINIIIMIIII. りを. 速 の も の を 表 に 示 し た.収. 束判. ≦le‑6. SOR. poisson-ro 3Da. ism.. 期 近似 解 コ 陰oはす べ てoと し た.行. ISORrand. 列 は予 め 対角. p.m. 大 反 復 回 数 は10o00回. Tables3‑4に た だ し,表 Residual)の. MI. 真 の 相 対 残 差(TrueReiative. 常 用 対 数(loglo)の 値 を 意 味 し,近 似 解Xk+1に. 対 す る 馳̲舳. 醗1恥/Ilb‑4meU2の. 中 の"rakd","coxst?1は. 値 で あ る.ま. SOR. poisson-r 3Db. た,表. 選 択1のISOR法. が ω=1.0で. raefsky2,reefsky3,k3platesに. お け る 選 択1のISOR法. の ωに よ る 反 復 回 数 の 変 動 の 様 子 を 示 す 。 Fig.1に. 行 列poiSSGn3Dbに. 差 履 歴 を 示 す.Fig.2に. お け る4つ の 解 法 の 相 対 残. 行 列epb2に. お け る4つ の 解 法 の. -6.44 -6.61. 1.06 -6.00. 157 152. 0,30 0.28. 1.0. 136 0.24 -6.01. -6.06 -6.22. 116 0.28 -6.18 114 0.37 -6.21 116 0.35 -6.06 60. 4 -4.59. 1563 384. 11.24. -6.28. 10.01. -6.09. 60.34 -4.59. 1.0 1.0. 1379 1406. 9.14 9.24. 1.0. max 63.52 -4.75. -6.00 -6.16. 1122 9.37 -6.02 1031 10.65 -6.01 2148MU -6.00. 1.8 1.8 1.8. 7-0819 rand. 0.47 -6.04. 74 76 74. 0.16 0.18 0.17. 124. -6.01 -6.08 -6.01. 0.28 -6.02. 0.27 -6.02 70 0.28 -6.04 0.28 -6.05 breakMill 67415.496.9 12.73-6.97. 744 14.0616.98 breakMEI -. const.. mmirli. ISORrand. 134. 1.8 1.8 1.8. 239 249 253 514. BiCGStab (rand)I max. 4.50 4.69 4.78 9.53. -6.03 -6.18 -6.11 -6.00. 63.90. -5.50. 11111111 rand II 5343 34.21 -4.10. り. 最 速 と な っ た 行 列epb3,. 0.40 0.41. 193 9.25 -6.02 GPBiCG(all)BiCGSafe(const.) 175 7.19 -6.00 11131=111111M11111111 breakMIIIII -. 行 列 ご とに収 束 まで の 計 算時 間が 最. 短 の も の を 太 字 で 表 示 し た.Table5}UTables3‑4よ. -6.17 -6.60 -6.16 -6.00. 529. ilimmou. バ ー フ ロ ー の た め 計 算 が 途 申 で 強 制 終 了 した こ と を 各 々 た,各. 0.31 0.44 0.39 1.89. 1.2 1.2. 1.9. const. 一 一ec乱 数(raRdomRumber),定. 数LO(constant)を 各 々 意 味 す る.さ ら に,表 中 の"max", "break"は 最 大 反 復 回 数 ま で で 未 収 束 ,そ して 計 算 の オ ー. 意 味 す る.ま. -6.01 -6.05 -6.04. 0.54 -6.00. 259 260 256 951. 1111. と した.. 各 行 列 に お け る 各 解 法 の 収 束 性 を 示 す. 中 の"TRR"は. 518 464 466. 586. BiCGStab ( a d)74 GPBiCG (rand) BiCGSafe (const)70 EMOINIIIIMIIIIIIIIIII. ス ケ ー一リ ン グ に よ っ て 対 角 項 を す べ て1.oに 正 規 化 し た. ま た,最. 0.49 0.42 0.46. 1.9. const. と し た.初. 2.29 -6.00. 1.5 1.5 1.5. Il constIII 237 0.53-6.32 IIIII0 Irand1111-19100..43. 期 残 差. 数1.0の3通. 対 残 差 の2ノ ル ム:iirk+1112/財o帳. 1.6 2049. 1.0 mgi. ISORrand. の 加 速 係 数 ωは 区 間[1.0,2.0]で. り与 え,最. -6.40 157621.180-6.56 const76.6 -6.30. const. SOR. 類 で あ る.IGS法,. 間{0,1】の 一 様 乱 数,定. -6.00. r0. const. の 初 期 シ ャ ド ウ 残 差 は,初. 8.49. BiCGStab ( a d) GPBiCG (const) BiCGSafe con t) MIIIMIIIIIMIIIIMITIZI. の 補 助 ベ ク トルpお よ びBiCGStab法,GPBiCG. 法,BiCGSafe法. 7614. 111.mmigu. ISORrand. 用 い た.コ. ラ はlntelFortranCompi}erver.8.1を. -. III Mg0205 0.38 -6.64 ll on1.28 0.29 -6.30 1111 11111 and 1373 9.83 -6.15 epb3II ro 1.01537 10.19 -6.29 SOR. モ リ:3Gbytes,OS:Suse. ス ト名:mizar)を. TRR. rand208 cons214. HPWaksta糠onxw42o0(CPU:1航el(R)PeRtium(R)4,. Linuxversion9.2,ホ. time. BiCGStab (rand) GPBiCG (rand) BiCGSafe (rand) MIIIIMMIII.111.11.1. acoustics. methods.. itr.. alimiNgu. epb2r0. ク ロ ッ ク 周 波 数:3.8GHz,メ. and other. co. rand16001.62. epblr0. poisson3Da. raefsky3. Yk. analytical. NNZ epbl14,734. of SOR,. method. const. SOR. xenon. max. iliimEmmi. 1r0. 1.8 1.9. ISORrand const.1.6. simmou BiCGStab - (const) GPBiCG - (const) BiCGSafe (r0). 64.36. -5.27. break mil. -. 1246 1377 1157. 8.24 9.11 7.70. 1020 6.60 436 4.76 418 5.36 361 4.40. -. -6.08 -6.21 -4.44. -6.00 -6.06 -6.00 -6.01.

(6) Table. matrix. 4. Convergence. method. ryk. GSIGS1 SORraef-ro1.0 sky2 ISOR1 2 BiCGStabGPBiCGBiCGSafeGSIGS1 SORraef-ro1.0 sky3 ISOR1 2 BiCGStabGPBiCGBiCGSafeGSIGS1 SORmem-ro1.9 plus ISOR1 2 BiCGStabGPBiCGBiCGSafeGSIGS1 SOR-wang3ro1.8 ISOR1. of SOR,. ISOR. p (rq) ro rand const -. w 1.0. rand const (const) (rand) (r0) r0 rand const -. 1.0 1.0 1.2 all. rand const (rand) (rand) (rand) ro rand const -. 1.0 1.0 1.0 1.9. rand const (r0) (ro) (ro) ro rand const. 1.9 1.9 1.2 1.9. rand const. 1.8 1.8 1.9 -. 2BiCGStabGPBiCGBiCGSafeGS-. (r0) (r0) (ro) r0 rand const. IGS1 SOR--1.9 wang4ro1.8 ISOR1. rand const 2-. BiCGStabGPBiCGBiCGSafeGS--. (r0) (TO) (rand) ro rand const. IGS1. rand const 2-. BiCGStabGPBiCGBiCGSafe-. (rand) (const) (const). other. itr.. methods.. time. Table. 5. TRR. Variation. 7k. 1.8 1.8 1.9 -. 1.3 1.2 1.0 -. max 308 321 329 max 339 353 349 4101 304 289 291 break 1832 1979 1804 break 1915 1907 1899 max 1435 1395 1407 max 4954 7164 6092 1782 444 472 431 1203 152 96 110 4499 375 551 531 221 106 114 111 222 96 97 98 2473 448 530 541 246 134 134 135 179 98 101 96 max max max max max 6020 5219 8387 786 176 162 156. 19.74 111.36 0.35 -5.78 0.36 -5.70 0.38 -5.91 19.74 111.36 0.40 -6.16 0.41 -6.02 0.42 -6.06 4.73 -6.00 0.65 -6.02 0.64 -6.15 0.63 -6.17 9.81 -6.08 10.52 -6.09 9.59 -6.12 10.77 -6.13 10.71 -6.05 10.65 -6.01 55.69 65.73 15.00 -6.00 15.92 -6.00 15.61 -6.01 14.97 -5.11 5.95 -6.21 8.67 -5.37 7.33 -4.99 2.69 -6.00 0.53 -6.05 0.56 -6.15 0.53 -6.04 1.37 -6.00 0.24 -6.08 0.21 -6.01 0.22 -6.01 8.84 -6.00 0.72 -6.31 1.06 -6.42 1.01 -6.26 0.45 -6.02 0.19 -6.36 0.21 -6.22 0.22 -6.34 0.39 -6.02 0.23 -6.12 0.35 -6.10 0.30 -6.15 4.87 -6.00 0.85 -6.67 1.01 -6.30 1.04 -6.43 0.50 -6.01 0.26 -6.02 0.26 -6.00 0.26 -6.29 0.34 -6.04 0.23 -6.29 0.37 -6.24 0.30 -6.21 28.18 -5.94 16.43 -5.27 16.55 -5.82 16.42 -5.45 28.18 -5.94 9.95 -5.51 8.68 -5.13 14.18 -5.23 1.33 -6.00 0.52 -6.00 0.54 -6.00 0.50 -6.00. of. : 1 when. matrices. SOR--1.0 k3-ro1.0 plates ISOR1. and. epb3,. matrix. 0.8 0.9 1.0 0.5 0.6 0.7 0.8 0.9 1.0 0.5 0.6 0.7 0.8 0.9 1.0 0.5 0.6 0.7 0.8 0.9 1.0. raefsky2 (p=ro). raefsky3 (p=ro). k3plates (p=const). 1. History ods. of relative. for matrix. of as. ISOR. method. co = 0.5,. raefsky2,. w 0.5 0.6. epb30.7 (p=rand). Fig.. iterations. co varies. raefsky3. itr. 8308 3395 2485 1977 1730 1379 945 726 652 477 389 339 2941 2863 2200 1642 1543 1915 7406 2522 3881 8776 3313 max. residual. and. time 53.79 21.83 16.08 12.80 11.22 9.14 1.08 0.83 0.76 0.55 0.45 0.40 16.77 16.18 12.44 9.40 8.78 10.87 12.53 4.24 6.51 14.73 5.58 16.73. with. 0.6,...,. 1.0. TRR -4.75 -6.02 -6.07 -6.03 -6.00 -6.00 -6.11 -6.00 -6.68 -6.21 -6.15 -6.16 -6.03 -5.80 -6.00 -6.10 -6.04 -6.13 -6.13 -5.60 -5.14 -5.96 -5.56 -4.91. 2-norm. of four. meth-. poisson3Db.. 相 対 残 差 履 歴 を 示 す.Fig.3にTables3‑4よ. り選 択1の. ISOR法. が 有 効 で あ っ た 行 列poisson3Da,poisson3Db,. wang3に. お け る 選 択1のISOR法. 動 の 様 子 を 示 す.ま のISOR法. for. k3plates.. の ωに よ る 反 復 回 数 の 変. た,Fig.4にTables3‑4よ. が ω=1.0で. raefsky3,k3platesに. り選 択1. 最 速 と な っ た 行 列epb3,raefsky2, お け る 選 択1のISOR法. の ωに よ る. 反 復 回 数 の 変 動 の 様 子 を 示 す.Figs.1‑4で. は各 解 法 お よ. び ベ ク トルpの 選 択 の う ち,Tables3‑4で. 最 も優 位 な 収. 束 性 を 示 し た も の を 用 い た.ま 間[0.5,2.0]で0.1刻 Tables3‑5お. た,加. み で 計16通. 速 係 数 ωの 範 囲 は 区. よ びFigs.1‑4の. りを 与 え た. 観 察 か ら,以. 下の知見. を 得 る こ と が で き る. ● 古 典 的SOR法 は 優 れ て い る.. の 収 束 性 に 比 べ て,ISOR法. の収 束 性.

(7) Fig.. 2. History ods. for. of relative matrix. residual. 2-norm. of four. meth-. epb2.. Fig.. 4. 6.ま. Variation of iterations 'yk : 1 when co varies as. of ISOR w = 0 .5,. matrices. raefsky3. epb3,. と. raefsky2,. に 比 べ て,圧. とIGS法. and. for. k3plates.. は,古. 典 的SOR法. と. 倒 的 に 優 位 な 収 束 性 を 示 す こ とが わ. か っ た 。 さ ら に,係tw7kは こ と が わ か っ た.ま. with 1.3. め. 本 研 究 に よ っ て,ISOR法 同IGS法. method 0.6,...,. 選 択1の 方 が 収 束 性 が よ り良 い. た,最. 適 加 速 係 数 ωつ きISOR法. は,. 従 来 の 積 型 反 復 法 と遜 色 の な い 収 束 性 を 示 す こ と もわ か っ た. 参 1)尾 Fig.. 3. Variation of iterations of -yk : 1 when w varies as w matrices. poisson3Da,. ● さ ら に,ISOR法. poisson3Db. method 0.6,..., and. とISOR法. with 2.0. 除 く12. よ り も 高 速 に 収 束 し た.. は,古. 典 的GS法. と 同SOR法. が収束. し な い 行 列 に 対 し て も 収 束 し た. ・ISOR法. に お け る 係 数 伽 の 選 択 で は,行. xenOR1,k3platesを か っ た.一. 列epb2,. 除 く11個 の 行 列 で 選 択1の 方 が 良. 方,IGS法. で は 選 択1と 選 択2の 性 能 は 同. 程 度 で あ っ た7). 。 最 適 ωつ きISOR法. は,従. 来 の積 型 反 復 法 と遜色 の な. い 性 能 が 得 ら れ た. ・Fig.1に ISOR法. 示 し た 残 差 履 歴 か ら,選 の 残 差 はIGS法. 観 察 さ れ た.た. だ し,数. 択2の 係 数7kの. の とき と同様 の単 調 減少 性 が 学 的 に残 差 ノル ム を 最 小 化. し た 訳 で は な い こ とを 付 記 す る. ・ISOR法. 範 囲 で 有 効 な 場 合(Fig.4参 響 解 析 分 野 の 行 列k3platesに. 献. 来 の よ う に[1.0,. 照 〉と,[e.5,Lo1の. 照)と が あ る.ま. た,音. おいては加速係数によ. 究 会報. 告,No.125,pp.13‑18,2008.. 2) Saad, Y., Iterative methods for sparse linear systems 2nd edition, SIAM, Philadelphia, 2003. 3) Sonneveld, P., AGS - IDR - CGS - BiCGSTAB - IDR(s): The circle closed, A case of serendipity, The Proc. of Int. Kyoto Forum 2008 on Krylov subspace methods, pp.1-14, September, 2008. 4) Sonneveld, P., van Gijzen, M.B., IDR(s): a family of simple and fast algorithms for solving large nonsymmetric linear systems, SIAM J. Sci. Comput., Vol. 31, No.2, pp.1035-1062, 2008. 5) University of Florida Sparse Matrix Collection: http://www.cise.ufl.edu/research/sparse/matrices /index.html 6) Wesseling, P., Sonneveld, P., Numerical Experiments with a Multiple Grid- and a Preconditioned Lanczos Type Methods, Lecture Notes in Math., Springer, No.771, pp.543-562, 1980. 7)春. 松 正 敏,日 下 部雄 三,藤 野 清 次,福 重 貴 浩,有 馬 敏 幸,. ペ ー ター ソネ フ ェル ト,"翌DR定 理 に基 づ くGS法 法 の提 案 と収 束 性 評 価",情 報 処 理 学 会HPC研. に お け る 加 速 係 数 ωは,従. 2.0]の 範 囲 で 有 効 な 場 合(Fig.3参. 文. 法 の 収 束性 と有 効 性 の評 価",情 報処 理 学 会HPC研. for. wang3.. は 行 列raef$ky2,raefsky3を. 個 の 行 列 に お い てIGS法 ●IGS法. ISOR 0 .5,. 考. 上 勇介,ペ ー ター 一 ソネ フ ェル ド,藤 野 清次,̀̀IDR‑AGS. とSOR. 究 会 報 告,. 調 布,2009,6. 8)森. 正 武,"数 値解 析",共 立 崖版,東 京,2o92.. 9) Young, D., Iterative methods for solving partial difference equations of elliptic type, Doctoral Thesis, Harvard University, 1950..

(8)

Updating...

参照

Updating...

関連した話題 :

Scan and read on 1LIB APP