趙 靜

(安徽科技學院 數(shù)學系，安徽 鳳陽 233100)

一個新型自適應預條件的總體CGS算法

趙 靜

(安徽科技學院 數(shù)學系，安徽 鳳陽 233100)

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

矩陣Krylov子空間方法；多右端項；總體CGS算法；總體GMRES算法

0 引言

在頻域電磁波散射計算等問題中，人們常常需要計算如下具有多個右端項大型稀疏非對稱線性方程組的解

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

近年來求解方程組(1)的一些塊Krylov子空間方法得到了迅猛發(fā)展.基于塊Arnoldi過程，Vital[1]提出了塊GMRES (Bl-GMRES)方法，之后很多學者[2-5]對其進行了深入研究和改進.基于塊 Lanczos過程，產(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].當方程組(1)的右端項不能同時獲知時，種子投影法是十分有效的；詳見文獻[2,10-11].

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

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

1 自適應預處理的Gl-CGS算法

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

算法1一般預處理的Gl-CGS 算法

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

11) 結束.

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

1) 預條件后的方程應該容易求解；

2) 預條件子應該較容易構造且應用預條件子的代價不能太高.

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

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

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

2 數(shù)值例子

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

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

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

由表 1可以看出，同其他 3種算法比較，PGl-CGS算法收斂速度快且求解精度好.對矩陣 RDB200L而言，Gl-BiCGSTAB算法在200步內(nèi)不收斂；對矩陣ORSREG1而言，Gl-CGS和Gl-BiCGSTAB算法的求解精度分別僅僅達到?5.260 4和?4.716 7.在圖 1中，橫坐標表示迭代次數(shù)，縱坐標表示殘量 F-范數(shù)的常用對數(shù).從圖 1可以看出，Gl-CGS算法的殘量震蕩激烈呈現(xiàn)不規(guī)則收斂行為而 PGl-CGS算法的殘量收斂比較光滑.PGl-CGS算法的迭代步數(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] 張建華,戴華.求解具有多個右端項線性方程組的總體CGS算法[J]. 高等學校計算數(shù)學學報, 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

安徽省教育廳自然科學一般項目(KJ2009B122Z)

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

(責任編校：李建明英文校對：李玉玲)