多重分割疊代法的實行

Abstract

通常解一個大型線性系統Ax=b都是利用疊代法。首先將A 分解成 A＝M －N ，經過適 當轉換得到演算法x(m+1)=x(m)+M (m)（１），因為M 通常是個下三角矩陣，所以演 算法（１）是一個不利於平行計算的演算法。懷特為了解決這個問題，發展出多重分 割疊代法。假如A=B -C ,K=1, ...，K 代入Ax=b得到x=B C =B b 。找適當的對角 線矩陣{D D .....D }滿足D +D + ...+D =1 代入得到演算法x(m+1)=x(m)+Gx(m) （ ２）。經過適當選擇G=ΣD B 將可使演算法（２）利於平行演算。懷特在他的論文（ ８９）中介紹演算法（２）的收斂定理及應用。在我的論文中，主要討論假如有K 個 平行演算器，演算法（２）執行一次疊代的時間比演算法（１）節省(K－１) T 時間 ，T 表示矩陣乘向 量所花時間。