一個(gè)新型自適應(yīng)預(yù)條件的總體CGS算法

趙 靜

(安徽科技學(xué)院 數(shù)學(xué)系，安徽 鳳陽(yáng) 233100)

一個(gè)新型自適應(yīng)預(yù)條件的總體CGS算法

趙 靜

(安徽科技學(xué)院 數(shù)學(xué)系，安徽 鳳陽(yáng) 233100)

總體 CGS算法(Gl-CGS)是求解具有多個(gè)右端項(xiàng)大型稀疏非對(duì)稱(chēng)線性方程組的一個(gè)有效矩陣 Krylov子空間方法.然而，在一些實(shí)際問(wèn)題中Gl-CGS算法常常收斂得很慢甚至停滯.針對(duì)此問(wèn)題，將總體CGS算法嵌入總體GMRES迭代過(guò)程，構(gòu)造了一個(gè)新型自適應(yīng)預(yù)條件子.最后，數(shù)值試驗(yàn)表明此預(yù)條件子的有效性.

矩陣Krylov子空間方法；多右端項(xiàng)；總體CGS算法；總體GMRES算法

0 引言

在頻域電磁波散射計(jì)算等問(wèn)題中，人們常常需要計(jì)算如下具有多個(gè)右端項(xiàng)大型稀疏非對(duì)稱(chēng)線性方程組的解

其中A為N×N階實(shí)矩陣，X=[x(1),x(2),…,x(s)],B=[b(1),b(2),… ,b(s)]為N×s陣且s＜＜N.

近年來(lái)求解方程組(1)的一些塊Krylov子空間方法得到了迅猛發(fā)展.基于塊Arnoldi過(guò)程，Vital[1]提出了塊GMRES (Bl-GMRES)方法，之后很多學(xué)者[2-5]對(duì)其進(jìn)行了深入研究和改進(jìn).基于塊 Lanczos過(guò)程，產(chǎn)生了一些經(jīng)典有效的塊Krylov子空間方法，如塊CG方法(Bl-CG)[6]295、塊BiCG方法(Bl-BiCG)[6]296、塊BiCGSTAB方法(Bl-BiCGSTAB)[7]、新型塊Lanczos型方法[8]及塊QMR方法(Bl-QMR)[9].當(dāng)方程組(1)的右端項(xiàng)不能同時(shí)獲知時(shí)，種子投影法是十分有效的；詳見(jiàn)文獻(xiàn)[2,10-11].

最近產(chǎn)生第三種求解方程組(1)的熱門(mén)方法即總體Krylov子空間方法，其主要思想是在矩陣Krylov子空間上采用正交投影或斜投影技術(shù).Jbilou等[12]49、Heyouni等[14]317分別提出了求解方程組(1)的總體 GMRES方法(Gl-GMRES)[12]55，總體BiCG類(lèi)方法[13]119，總體CMRH方法(Gl-CMRH)[14]323和加權(quán)總體CMRH方法[15].林依勤[16]提出了隱式再開(kāi)始的Gl-GMRES方法.當(dāng)系數(shù)陣為對(duì)角陣時(shí)，Bellalij等人[17]分析了Gl-GMRES方法的收斂性.基于總體Lanczos過(guò)程，一些學(xué)者提出了一類(lèi)總體Lanczos型方法；詳見(jiàn)文獻(xiàn)[18-19].

為避免矩陣轉(zhuǎn)置乘積，張建華和戴華[19]390給出了總體 CGS算法(Gl-CGS)，數(shù)值實(shí)驗(yàn)表明此方法的收斂速度為Gl-BiCG算法的將近一倍.然而在某些復(fù)雜的實(shí)際問(wèn)題中，Gl-CGS算法的殘量范數(shù)常呈現(xiàn)不規(guī)則行為或收斂速度很慢.借鑒文獻(xiàn)[20-21]的思想，本文構(gòu)造一個(gè)新型自適應(yīng)預(yù)條件子.該預(yù)條件子實(shí)際是一個(gè)多項(xiàng)式預(yù)條件子，它由Gl-CGS算法嵌入總體GMRES過(guò)程隱式構(gòu)造而成.新方法能減少迭代步數(shù)，伴隨迭代步數(shù)的減少，存貯量會(huì)降低，運(yùn)算量也會(huì)下降.

1 自適應(yīng)預(yù)處理的Gl-CGS算法

數(shù)值實(shí)驗(yàn)表明Gl-CGS 算法收斂速度比Gl-BiCG算法快，然而在一些實(shí)際問(wèn)題中，Gl-CGS 算法收斂得很慢甚至停滯.因此，如何選擇恰當(dāng)?shù)念A(yù)條件子成為Gl-CGS 算法高效求解的關(guān)鍵.下面給出預(yù)條件子的構(gòu)造過(guò)程.借鑒文獻(xiàn)[23]的思想，把Gl-CGS 算法應(yīng)用到預(yù)處理方程組

算法1一般預(yù)處理的Gl-CGS 算法

選擇初始估計(jì)矩陣X0，計(jì)算R0=B-AX0，選擇矩陣

11) 結(jié)束.

算法1的每一步迭代都需要計(jì)算K?1Rj和K?1Vj.一個(gè)好的預(yù)條件子需滿(mǎn)足如下性質(zhì)：

1) 預(yù)條件后的方程應(yīng)該容易求解；

2) 預(yù)條件子應(yīng)該較容易構(gòu)造且應(yīng)用預(yù)條件子的代價(jià)不能太高.

下面給出一個(gè)新型預(yù)條件子K的隱式構(gòu)造過(guò)程.即對(duì)?F∈RN×s，當(dāng)計(jì)算K-1 F時(shí)，都轉(zhuǎn)化為求解方程組AW=F,然后使用Gl-GMRES(m)方法迭代k步，得Wk來(lái)逼近K?1F，其中k常取2或3，m的值由實(shí)際問(wèn)題而定，W0取為零矩陣.

算法2 新型自適應(yīng)預(yù)處理的Gl-CGS算法 (PGl-CGS)

當(dāng)s= 1時(shí)，PGl-CGS算法轉(zhuǎn)化為曹海燕等人提出的CGS/GMRES(m)算法[21]147.該預(yù)條件也可應(yīng)用到GliCG和Gl-BiCGSTAB等算法中，我們將在另文中研究此問(wèn)題.

2 數(shù)值例子

本節(jié)通過(guò)一個(gè)數(shù)值例子說(shuō)明PGl-CGS算法的有效性.數(shù)值實(shí)驗(yàn)在Matlab環(huán)境下運(yùn)行，初始估計(jì)值取為零矩陣.右端項(xiàng)B=rand(N,s)，其中rand產(chǎn)生一個(gè)系數(shù)分布在區(qū)間[0,1]上的一個(gè)N×s隨機(jī)矩陣.實(shí)驗(yàn)終止條件為.Its,Times和TRR分別表示迭代步數(shù)，計(jì)算時(shí)間和相對(duì)殘量F范數(shù)的常用對(duì)數(shù)值.

在本例中，比較PGl-CGS算法與Gl-CGS，WGl-GMRES[15]149和Gl-BiCGSTAB[13]131算法求解方程組(1)的有效性.實(shí)驗(yàn)所用矩陣分別來(lái)于流體動(dòng)力學(xué)(CDDE2,CDDE4)，石油存貯模擬(ORSREG1)，偏微分方程(PDE900)和反應(yīng)擴(kuò)散 brusselator模型(RDB200L).置R~0=R0,s=5,m=20,k=3.所有算法迭代步數(shù)不超過(guò)200.當(dāng)用Gl-GMRES(m)算法構(gòu)造預(yù)條件子時(shí)，初始矩陣都取為零矩陣.

表1 矩陣及Gl-CGS, WGl-GMRES, PGl-CGS, Gl-BiCGSTAB算法的數(shù)值結(jié)果

由表 1可以看出，同其他 3種算法比較，PGl-CGS算法收斂速度快且求解精度好.對(duì)矩陣 RDB200L而言，Gl-BiCGSTAB算法在200步內(nèi)不收斂；對(duì)矩陣ORSREG1而言，Gl-CGS和Gl-BiCGSTAB算法的求解精度分別僅僅達(dá)到?5.260 4和?4.716 7.在圖 1中，橫坐標(biāo)表示迭代次數(shù)，縱坐標(biāo)表示殘量 F-范數(shù)的常用對(duì)數(shù).從圖 1可以看出，Gl-CGS算法的殘量震蕩激烈呈現(xiàn)不規(guī)則收斂行為而 PGl-CGS算法的殘量收斂比較光滑.PGl-CGS算法的迭代步數(shù)、計(jì)算時(shí)間和存貯量都比WGl-GMRES少.

圖1 矩陣CDDE2(左)和矩陣PDE900(右)的收斂行為

[1] VITAL B. Etude de quelques methodes de resolution de problemes linearies de grade taide sur multiprocesseur [D]. Universite de Rennes, Rennes, France, 1990.

[2] SIMONCINI V, GALLOPOULOS E. An iterative method for nonsymmetric systems with multiple right-hand sides[J]. SIAM J. Sci. Comput, 1995, 16:917-933.

[3] SIMONCINI V, GALLOPOULOS E. Convergence properties of block GMRES and matrix polynomials[J]. Linear Algebra Appl, 1996, 247:97-119.

[4] GU G D, CAO Z H. A block GMRES method augmented with eigenvectors[J]. Appl. Math. Comput, 2001, 121:271-289.

[5] MORGAN R B. Restarted block-GMRES with deflation of eignvalues[J]. Appl. Numer. Math, 2005, 54:222-236.

[6] O’LEARY D P. The block conjugate gradient algorithm and related methods[J]. Linear Algebra Appl, 1980, 29:293-322.

[7] GUENNOUNI A E, JBILOU K, SADOK H. A block version of BICGSTAB for linear systems with multiple right-hand sides[J]. Elec. Trans. Numer. Anal, 2003, 16:129-142.

[8] GUENNOUNI A E, JBILOU K, SADOK H. The block Lanczos method for linear systems with multiple right-hand sides[J]. Appl. Numer. Math, 2004, 51:243-256.

[9] FREUND R, MALHOTRA M. A block QMR algorithm for non-Hermitian linear systems with multiple right-hand sides[J]. Linear Algebra Appl, 1997, 254:119-157.

[10] CHAN T, WANG W. Analysis of projection methods for solving linear systems with multiple right-hand sides[J]. SIAM J. Sci. Comput, 1997, 18:1689-1721.

[11] SAAD Y. On the Lanczos method for solving symmetric linear systems with several right-hand sides[J]. Math. Comp, 1987, 48:651-662.

[12] JBILOU K, MESSAOUDI A, SADOK H. Global FOM and GMRES algorithms for matrix equation[J]. Appl. Numer. Math, 1999, 31:49-63.

[13] JBILOU K, SADOK H, TINZEFTE A. Oblique projection methods for linear systems with multiple right-hand sides[J]. Elec. Trans. Numer. Anal, 2005, 20:119-138.

[14] HEYOUNI M. The global Hessenberg and CMRH methods for linear systems with multiple right-hand sides[J]. Numer. Algorithms, 2001, 26:317-332.

[15] HEYOUNI M, ESSAI A. Matrix Krylov subspace methods for linear systems with multiple right-hand sides[J]. Numer. Algorithms, 2005, 40:137-156.

[16] LIN Y Q. Implicitly restarted global FOM and GMRES for nonsymmetric matrix equations and Sylvester equations[J]. Appl. Math. Comput, 2005, 167:1004-1025.

[17] BELLALIJ M, JBILOU K, SADOK H. New convergence results on the global GMRES method for diagonalizable matrices[J]. J. Comput. Appl. Math, 2008, 219:350-358.

[18] SALKUYEH D K. CG-type algorithms to solve symmetric matrix equations[J]. Appl. Math. Comput, 2006, 172:985-999.

[19] 張建華,戴華.求解具有多個(gè)右端項(xiàng)線性方程組的總體CGS算法[J]. 高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào), 2008, 30:390-399.

[20] SAAD Y. A flexible inner-outer preconditioned GMRES algorithm[J]. SIAM J. Sci. Stat. Comput, 1993, 14:461-469.

[21] CAO H Y, LI X W. CGS/GMRES(k): An adaptive preconditioned CGS algorithm for nonsymmetric linear systems[J]. Numer. Math. J. Chinese Univ. (English Ser.), 1998, 7:145-158.

[22] SONNEVELD P. CGS: a fast Lanczos-type solver for nonsymmetric linear systems[J]. SIAM J. Sci. Statist. Comput,1989, 10:36-52.

[23] VAN DER VORST H A. “BiCGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems,”[J]. SIAM J. Sci. Statist. Comput, 1992,13:631-644.

A New Adaptive Preconditioned Global CGS Algorithm

ZHAO Jing
(Department of mathematics, Anhui Science and Technology University, Fengyang, Anhui 233100, China)

Global CGS algorithm (Gl-CGS) is popular matrix Krylov subspace method for large, sparse and nonsymmetric linear systems with multiple right-hand sides. However, the Gl-CGS may suffer from slow convergence or be stationary in some applications. In order to remedy this, we present a new adaptive preconditioner, which is constructed in the iteration. step of Gl-CGS, by several steps of global GMRES (m). Finally, numerical experiments show the effectiveness of the new preconditioner.

matrix Krylov subspace; multiple right-hand sides; Gl-CGS; Gl-GMRES

O241.6

A

1673-2065(2011)04-0022-04

2011-02-11

安徽省教育廳自然科學(xué)一般項(xiàng)目(KJ2009B122Z)

趙 靜(1982-),女,山東泰安人,安徽科技學(xué)院數(shù)學(xué)系教師,理學(xué)碩士.

(責(zé)任編校：李建明英文校對(duì)：李玉玲)