大型稀疏线性代数方程组的并行非定常迭代方法
|
摘要
充分发挥并行计算机的潜在性能，寻求大型稀疏线性代数方程组的高效并
行解法，是当前大规模科学计算中急待解决的问题，也是研究的热点问题。并
行算法设计与并行程序实现的关键是：依据不同并行计算机的结构特征，减少
整体通讯并尽量使各处理机之间负载平衡。
本文基于这一思路，应用高性能计算机，较系统地研究了求解大型稀疏线
性代数方程组的并行非定常迭代方法，主要的工作分两个部分：
第一部分包括第3、4章。我们针对分布式存储大规模并行处理系统（MPP），
从减少整体通讯和合理分布数据出发，完成了如下工作：
（1）引入多搜索方向，提出了一类新的共轭梯度（CG）方法：多搜索方
向共轭梯度方法，称MSD-CG方法。该方法是基于区域分解方法而提出的，方法
用小线性方程组的求解代替传统的CG方法中整体内积的计算。小方程组的结构
基于区域分解方式和搜索方向的选取，可用直接法或迭代法求解。若用迭代法
近似求解，则得MSD-CG方法一种近似形式，这种近似方法仅需要相邻子区域之
间的通讯，从而完全去掉了整体内积的计算，我们称其为无需整体内积的共轭
梯度（GIPF-CG）方法，它非常适合大规模并行计算，是CG方法在大规模并行
计算机上的有效实施形式。给出了方法相应的预条件形式。
（2）证明了MSD－CG和GIPF-CG方法的收敛性、相容性定理，奠定了
方法的理论基础。特别是给出了MSD-CG方法的基本性质，收敛速度估计，得
到了MSD-CG方法比最速下降法收敛得快的结论。
（3）在曙光3000和自行设计的P-II Cluster上进行了大量的数值试验。
结果表明：虽然GIPF－CG方法的收敛速度比传统的CG方法略慢，但是，有效
的并行使我们的方法整体更为有效。由于小线性方程组中包含了整体信息，我
们的方法在每步都有整体信息的交换，从而克服了加法Schwarz区域分解方法
的随区域个数增大而收敛速度严重下降的问题。预条件方法对GIPF-CG方法有
很大的改善。
MSD-CG和GIPF-CG的算法设计思想很容易推广到非对称问题的求解上，特
别是对CR、CGS、BiCG、BiCGSTAB、CGNR、CGNE、QMR等方法的并行化具有非常
大的指导意义。
中国工程物理研究院博士学位论文
第二部分包括第5、6章。我们设计了具有自然并行性又有良好的负载平衡
性能的松弛型非定常二级多分裂方法。（定常）多分裂和二级多分裂方法的缺陷
是：当处理机台数增加时，其同步性和负载不平衡问题变得越来越严重。我们
通过引入非定常方法，用非定常参数的调整来改善负载不平衡问题；通过引入
异步方法来克服方法的同步性；通过引入松弛和加速因子来对方法进行加速。
该部分的主要工作包括：
（l）提出了两类松弛型非定常二级多分裂迭代法，即外松弛非定常二级
多分裂（ORNSTSM）方法和内松弛非定常二级多分裂（I RNSTSM）方法。这些方法
是基于外推法和AOR方法而提出的。当系数矩阵为H阵时，研究了方法的收
敛性。已有的相应方法都可视为我们的方法的特殊形式。我们给出方法在共享
存储多处理机上的数值试验，结果显示了良好的加速比。可以选择适当的非定
常参数，使非定常方法比最优的定常方法更优，并可达到负载的基本平衡。方
法的整体迭代次数随着非定常参数的增加而减小。
（2）提出了两类异步松弛型非定常二级多分裂迭代法，即AORNSTSM
方法和AIRNSTSM方法。当系数矩阵为H阵时，研究了方法的收敛性。数值
例子显示：异步方法总比其同步形式更优，异步形式的收敛区域比其同步形式
的大，近似最优松弛因子在其收敛区域的上界附近。特别地，用异步形式的非
定常二级多分裂方法，我们可以动态地调整非定常参数来达到动态调整负载平
衡，并得到更优的收敛速度。
At present, a hotspot problem to be solved is to make the best use of the
potential capability of parallel computers and investigate high efficient parallel
methods for solving large sparse linear systems. The key point for designing of
parallel algorithms and implementation of parallel programs is to reduce global
communication and maintain load balance between processors according to
architecture characters of different parallel computers.
In this thesis, based on the above idea, we study systematically parallel
nonstationary iterative methods applied to high performance parallel computers for
solving large sparse linear systems. The main work is divided into two parts.
Chapter 3 and 4 constitute part one. From the point of reduceing global
communication and reasonable distributation of data, we complete the following work
to distributed memory massively parallel processing system:
(1) By introducing multiple search directions, we proposed a new type of
conjugate gradient method, which is called multiple search directions conjugate
gradient method, MSD桟G method in brief. The method is based on domain decomposition
method. In MSD桟G method, we replace the computation of global inner product of
traditional CG method by the solution of smaller linear systems, which can be solved
by direct or iterative methods. The structure of the smaller linear systems is based
on the way of domain decomposition and the choice of multiple search directions.
We obtain an approximate version of MSD桟G method if we solve the smaller systems
approximately by iterative method. This approximate version only requires
communication between neighboring subdomains and eliminate global inner product
entirely. We call it global inner product free conjugate gradient (GIPF桟G) method,
which is therefore well suit for massively parallel computation and is an efficient
implement version of CG method on massively parallel computer. The preconditioned
version of MSD桟G method is also introduced.
(2) We set up the theory of convergence and consistent of MSD桟G and GIPF桟G
method. The basic properties and estimates of convergence rate of MSD桟G method
are obtained. We show that MSD桟G method converges at least faster than the steepest
descent method.
(3) We do lots of numerical experiments on Dawn 3000 and P桰l Cluster designed
by ourselves. The results show that although GIPF桟G converges slightly slower than
that of CG method, but the efficient parallelism of our method makes it higher
efficient globally. Since the global information is contained in the smaller
systems, our method interchanges global information at each step. Therefore our
methods conquer the severely descendant of additive Schwarz domain decomposition
method as the increase of number of subdomains. Our method can also be improved
obviously by preconditioning.
The idea of algorithm designing of MSD桟G and GIPF桟G can be easy generalized
to the case of solving nonsymmetric problems. It is of guiding significance for
the parallelization of many methods, such as CR, CGS, BiCG, BICGSTAB, CGNR, CGNE,
QMR and so on.
Part two consists of Chapter 5 and 6. We design relaxed nonstationary two梥tage
multisplitting methods, which are natural parallel and better load balance. The
limitations of (stationary) multisplitting and two梥tage multisplitting methods
are synchronism and load unbalance becomes severer when the number of processor
increase
行解法，是当前大规模科学计算中急待解决的问题，也是研究的热点问题。并
行算法设计与并行程序实现的关键是：依据不同并行计算机的结构特征，减少
整体通讯并尽量使各处理机之间负载平衡。
本文基于这一思路，应用高性能计算机，较系统地研究了求解大型稀疏线
性代数方程组的并行非定常迭代方法，主要的工作分两个部分：
第一部分包括第3、4章。我们针对分布式存储大规模并行处理系统（MPP），
从减少整体通讯和合理分布数据出发，完成了如下工作：
（1）引入多搜索方向，提出了一类新的共轭梯度（CG）方法：多搜索方
向共轭梯度方法，称MSD-CG方法。该方法是基于区域分解方法而提出的，方法
用小线性方程组的求解代替传统的CG方法中整体内积的计算。小方程组的结构
基于区域分解方式和搜索方向的选取，可用直接法或迭代法求解。若用迭代法
近似求解，则得MSD-CG方法一种近似形式，这种近似方法仅需要相邻子区域之
间的通讯，从而完全去掉了整体内积的计算，我们称其为无需整体内积的共轭
梯度（GIPF-CG）方法，它非常适合大规模并行计算，是CG方法在大规模并行
计算机上的有效实施形式。给出了方法相应的预条件形式。
（2）证明了MSD－CG和GIPF-CG方法的收敛性、相容性定理，奠定了
方法的理论基础。特别是给出了MSD-CG方法的基本性质，收敛速度估计，得
到了MSD-CG方法比最速下降法收敛得快的结论。
（3）在曙光3000和自行设计的P-II Cluster上进行了大量的数值试验。
结果表明：虽然GIPF－CG方法的收敛速度比传统的CG方法略慢，但是，有效
的并行使我们的方法整体更为有效。由于小线性方程组中包含了整体信息，我
们的方法在每步都有整体信息的交换，从而克服了加法Schwarz区域分解方法
的随区域个数增大而收敛速度严重下降的问题。预条件方法对GIPF-CG方法有
很大的改善。
MSD-CG和GIPF-CG的算法设计思想很容易推广到非对称问题的求解上，特
别是对CR、CGS、BiCG、BiCGSTAB、CGNR、CGNE、QMR等方法的并行化具有非常
大的指导意义。
中国工程物理研究院博士学位论文
第二部分包括第5、6章。我们设计了具有自然并行性又有良好的负载平衡
性能的松弛型非定常二级多分裂方法。（定常）多分裂和二级多分裂方法的缺陷
是：当处理机台数增加时，其同步性和负载不平衡问题变得越来越严重。我们
通过引入非定常方法，用非定常参数的调整来改善负载不平衡问题；通过引入
异步方法来克服方法的同步性；通过引入松弛和加速因子来对方法进行加速。
该部分的主要工作包括：
（l）提出了两类松弛型非定常二级多分裂迭代法，即外松弛非定常二级
多分裂（ORNSTSM）方法和内松弛非定常二级多分裂（I RNSTSM）方法。这些方法
是基于外推法和AOR方法而提出的。当系数矩阵为H阵时，研究了方法的收
敛性。已有的相应方法都可视为我们的方法的特殊形式。我们给出方法在共享
存储多处理机上的数值试验，结果显示了良好的加速比。可以选择适当的非定
常参数，使非定常方法比最优的定常方法更优，并可达到负载的基本平衡。方
法的整体迭代次数随着非定常参数的增加而减小。
（2）提出了两类异步松弛型非定常二级多分裂迭代法，即AORNSTSM
方法和AIRNSTSM方法。当系数矩阵为H阵时，研究了方法的收敛性。数值
例子显示：异步方法总比其同步形式更优，异步形式的收敛区域比其同步形式
的大，近似最优松弛因子在其收敛区域的上界附近。特别地，用异步形式的非
定常二级多分裂方法，我们可以动态地调整非定常参数来达到动态调整负载平
衡，并得到更优的收敛速度。
At present, a hotspot problem to be solved is to make the best use of the
potential capability of parallel computers and investigate high efficient parallel
methods for solving large sparse linear systems. The key point for designing of
parallel algorithms and implementation of parallel programs is to reduce global
communication and maintain load balance between processors according to
architecture characters of different parallel computers.
In this thesis, based on the above idea, we study systematically parallel
nonstationary iterative methods applied to high performance parallel computers for
solving large sparse linear systems. The main work is divided into two parts.
Chapter 3 and 4 constitute part one. From the point of reduceing global
communication and reasonable distributation of data, we complete the following work
to distributed memory massively parallel processing system:
(1) By introducing multiple search directions, we proposed a new type of
conjugate gradient method, which is called multiple search directions conjugate
gradient method, MSD桟G method in brief. The method is based on domain decomposition
method. In MSD桟G method, we replace the computation of global inner product of
traditional CG method by the solution of smaller linear systems, which can be solved
by direct or iterative methods. The structure of the smaller linear systems is based
on the way of domain decomposition and the choice of multiple search directions.
We obtain an approximate version of MSD桟G method if we solve the smaller systems
approximately by iterative method. This approximate version only requires
communication between neighboring subdomains and eliminate global inner product
entirely. We call it global inner product free conjugate gradient (GIPF桟G) method,
which is therefore well suit for massively parallel computation and is an efficient
implement version of CG method on massively parallel computer. The preconditioned
version of MSD桟G method is also introduced.
(2) We set up the theory of convergence and consistent of MSD桟G and GIPF桟G
method. The basic properties and estimates of convergence rate of MSD桟G method
are obtained. We show that MSD桟G method converges at least faster than the steepest
descent method.
(3) We do lots of numerical experiments on Dawn 3000 and P桰l Cluster designed
by ourselves. The results show that although GIPF桟G converges slightly slower than
that of CG method, but the efficient parallelism of our method makes it higher
efficient globally. Since the global information is contained in the smaller
systems, our method interchanges global information at each step. Therefore our
methods conquer the severely descendant of additive Schwarz domain decomposition
method as the increase of number of subdomains. Our method can also be improved
obviously by preconditioning.
The idea of algorithm designing of MSD桟G and GIPF桟G can be easy generalized
to the case of solving nonsymmetric problems. It is of guiding significance for
the parallelization of many methods, such as CR, CGS, BiCG, BICGSTAB, CGNR, CGNE,
QMR and so on.
Part two consists of Chapter 5 and 6. We design relaxed nonstationary two梥tage
multisplitting methods, which are natural parallel and better load balance. The
limitations of (stationary) multisplitting and two梥tage multisplitting methods
are synchronism and load unbalance becomes severer when the number of processor
increase
引文
[1] L．M．Adams，E．G．Ong，Additive polynomial preconditioners for parallel computers．Parallel Computing, 9：333-345(1988／1989) ．
[2] P．R．Amestoy，I．S．Duff，Vectorization of a multiprocessor multifrontal code． Int．J，of Suppercomputer Applics．，3：41-59(1989) ．
[3] P．R．Amestoy，I．S．Duff，C．Puglisi，Multifrontal QR factorization in a multiprocessor environment，Numer．Lin．Alg．Appl．，3：275-300(1996) ．
[4] R．S．Anderssen，G．H．Golub，Richardson’s non-stationary matrix iterative procedure，Technical Report STAIN-CS-72-304，Dept．of Computer Science， Stanford University，1972．
[5] S．F．Ashby，T．A．Manteuffel，P．E．Saylor，A taxonomy for conjugate gradient methods，SIAM J． Numer． Anal．，27：1542-1568(1990) ．
[6] O．Axelsson，Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations，Lin．Alg．Appl．，29：1-16(1980) ．
[7] O．Axelsson，G．Lindskog，On the eigenvalue distribution of a class of preconditioning methods，Numer．Math．，48：481-498(1986) ．
[8] O．Axelsson，G．Lindskog，On the rate of convergence of the precondition conjugate gradient method，Numer．Math．，48：499-523(1986) ．
[9] O．Axelsson，A generalized conjugate gradient，least square method，Numer． Math．，51：209-227(1987) ．
[10] O．Axelsson，P．S．Vassilevski，A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning，SIAM j． Matrix Anal．Appl．，12：625-644(1991) ．
[11] O．Axelsson， Iterative Solution Methods，Cambridge University Press， Cambridge，1994．
[12] O．Axelsson， Optimal preconditioners based on rate of convergence estimates for the conjugate gradient method，Technical Report No．9943，University of Nijmegn，Dep．Math．，The Netherlands，1999．
[13] 白中治，王德人，异步并行矩阵多分裂多参数松弛方法，高校计算数学学报， 16(2) ：107-115(1994) ．
[14] Z．Z．Bai，Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations，Numen． Algorithms,15：347-372(1997) ．
[15] Z. Z. Bai, D. R. Wang and D. J. Evans, Models of asynchronous parallel matrix multisplitting relaxed iterations, Parallel Computing, 21:565-582(1995) .
[16] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems, SIAM, Philadephia, 1993．
[17] A. Basermann, Conjugate gradient and Lanczos methods for sparse matrices on distributed memory multiprocessors, J. Parallel & Distributed Computing, 45:46-52(1997) .
[18] A. Basermann, B. Reichel, C. Schelthoff, Preconditioned CG methods for sparse matrices on massively parallel machines, Parallel Computing, 23:381-398 (1997) .
[19] M. Benzi, C. D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17:1135-1149 (1996) .
[20] Ake B jorck, T. Elfving, Z. StrakoS, Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl. , 19:720-736(1998) .
[21] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Science, Third ed. , Academic Press, New York, 1979．
[22] M. Bonnet, G, Meurant, Resolution de systemes d' equations lineaires par la methode du gradient conjugue avec preconditionnement, Rapport CEA/DAM 80069, 1980．
[23] J. H. Bramble, J. E. Pasciak, Junping Wang, Jinchao Xu, Convergence Estimates for product iterative methods with applications to domain decomposition, Math. Comput., 57:1-21(1991) .
[24] J. H. Bramble, J. E. Pasciak, Junping Wang, Jinchao Xu, Convergence Estimates for Multigrid algorithms without regularity assumptions, Math. Comput., 57:23-45(1991) .
[25] A. Brandt, Algebraic multigrid theory: the symmetric case, Appl. Math. Comput., 19:23-56(1986) .
[26] R. Bru, L. Eisner, M. Neumann, Models of parallel chaotic iteration methods, Lin. Alg. Appl., 103:175-192(1988) .
[27] R. Bru, C. Corral, A. Martinez, J. Mas, Multisplitting preconditioners based on incomplete Choleski factorizations, SIAM J. Matrix Anal. Appl., 16:1210-1222(1995) .
[28] R. Bru, V. Migallon, J. Penades and D. B. Szyld, Parallel, synchronous and
asynchronous two-stage multisplitting methods, Electronic Tran. on Numer. Anal., 3:24-38(1995) .
[29] H. M. Bucker, M. Sauren, A parallel version of the unsymmetric Lanczos algorithm and its application to QMR, Technical Report KFA-ZAM-IB-9605, Forschungszen-trum Julich Gmbh, Julich, Germany, 1996．
[30] Zhihao Cao, On convergence of nested stationary iterative methods, Lin. Alg. Appl., 221:159-170(1995) .
[31] T. F. Chan, D. Goovaerts, A note on the efficiency of domain decomposed incomplete factorizations, SAIM J. Sci. Stat. Comput., 11:794-803(1990) .
[32] A. T. Chronopoulos, C. W. Gear, s-Step iterative methods for symmetric linear systems, J. Comp. & Appl. Math., 25:153-168(1989) .
[33] E. Chow, Y. Saad, Approximate inverse techniques for block-partitioned matrices, SIAM J. Sci. Comput., 18:1657-1675(1997) .
[34] A. I. Cohen, Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal., 9:248-259(1972) .
[35] P. Concus, G. H. Golub, D. P. O'Leary, A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, In J. R. Bunch and D. J. Rose, editors, Sparse Matrix Computations, Academic Press, 309-332(1976) .
[36] P. Concus, G.H. Golub, G. Meurant, Block preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6:220-252(1985)
[37] C. Corral, I. Gimenez, J. Marin, J. Mas, Parallel m-step preconditioner for the conjugate gradient method, Parallel Computing, 25:265-281(1999) .
[38] L. Crone, H. A. van der Vorst, Communication aspects of the conjugate gradient method on distributed-memory machines, Supercomputer, X(6) :4-9(1993) .
[39] E. F. D'Azevedo, C. Romine, Reducing communication costs in the conjugate gradient algorithm on distributed memory multiprocessors, Technical reports LAPACK working note 56, Computer Science Department, University of Knoxville, Knoxville, TN, 1993．
[40] J. W. Demmel, M. T. Heath, H. A. van der Vorst, Parallel numerical linear algebra, In Acta Numerica 1993, Cambridge University Press, Cambridge, 1993．
[41] J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, J. W. H. Liu, A Supernodal approach to sparse partial pivoting, Technical Report UCB//CSD95-883, Computer science Division, U. C. Berkeley, Berkeley, California, July 1995．
[42] I.S. Duff, G. A. Meurant, The effect of ordering on preconditioned conjugate
gradient, BIT, 29:635-657(1989) .
[43] S. C. Eisenstat, A Note on the generalized conjugate gradient method, SIAM J. Numer. Anal., 20:358-361(1983) .
[44] J. Erhel, F. Guyomarc'h, An augmented subspace conjugate gradient, Technical Report 1136, Institut de Recherche en Informatique et Systemes Aleatoires, 1997
[45] D. J. Evans, M. M. Martins, M. E. Trigo, On the convergence of some generalized iterative methods with preconditioning, Intern. J. Computer Math. , 44:19-28 (1992) .
[46] V. Faber, T. Manteuffel, Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal., 21:352-362(1984) .
[47] V. Faber, T. Manteuffel, Orthogonal error methods, SIAM J. Numer. Anal., 24: 170-187(1987) .
[48] M. R. Field, Optimizing a parallel conjugate gradient solver, SIAM J. Sci. Comput., 19:27-37(1998) .
[49] R. Fletcher, C. M. Reeves, Function minimization by conjugate gradients, Computer J. , 7 : 149-154 (1964) .
[50] R. Fletcher, Conjugate gradient methods for indefinite systems, In G. A. Watson, editor, Numerical Analysis Dundee 1975 , G. A. Watson ed. , New York, Springer, Lecture Notes in Mathematics, no. 506, 73-89(1976) .
[51] D. R. Fokkema, P. Sleijpen, H. A. Van der Vorst, Generalized conjugate gradient squared, J. Comput. Appl. Math., 71:125-146(1996) .
[52] R. W. Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14:470-482(1993) .
[53] R. W. Freund, N. M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60:315-339(1991) .
[54] A. Frommer, G. Mayer, Convergence of relaxed parallel multisplitting methods, Lin. Alg. Appl., 119:141-152(1989) .
[55] A. Frommer, H. Schwandt, A unified representation and theory of algebraic additive Schwarz and multisplitting methods, SIM J. Matrix Anal. Appl. , 19: 893-912(1997) .
[56] A. Frommer and D. B. Szyld, H-splitting and two-stage iterative methods, Numer. Math., 63(1992) , pp. 345-356．
[57] R. Fuster, V. Migallon and J. Penades, Non-stationary parallel multisplitting AOR methods, Electronic Tran. on Numer. Anal., 4:1-13(1996) .
[58] G．H．Golub，M。L．Overton，The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems，Numer．Math．，53：571-593(1988) ．
[59] G．H．Golub and D．P．O’Leary，Some history of the conjugate gradient and Lanczos algorithms：1948-1976，SIAM Review,31：50-102(1989) ．
[60] G．H．Golub。C．Van Loan，Matrix Computation，second edition，Johns Hopkins University Press，1989．
[61] A．Greenbaum，Congming Li，Zhen Chao，Parallelizing preconditioned conjugate gradient algorithms，Computer Physics Communications,53：295-309(1989) ．
[62] Gu Tongxiang，Liu Xingping，Shen Longjun，Relaxed parallel two-stage multisplitting methods，Intern．J．Computer Math．，75：351-367(2000) ．
[63] 谷同祥，沈隆钧，刘兴平，异步松弛型并行二级多分裂迭代法，高等学校计算数学学 报，即将发表．
[64] 谷同样，刘兴平，并行二级多分裂迭代法，计算数学 20(2) ：153-166(1998) ．
[65] Gu Tongxiang，Wang Nengchao，Safe bounds for the solution of nonlinear problems using a relaxed parallel multisplitting methods，Mathematica Applicata， 8：351-359(1995) ．
[66] Gu Tongxiang，Asynchronous relaxed iterative methods for solving l inear systems of equations，Appl．Math．Mech．，18：801-806(1997) ．
[67] 谷同祥，王能超，并行求解线性方程组的非定常二级多分裂迭代方法，工程数学学报， 14(4) ：25-32(1997) ．
[68] Gu Tongxiang，Discretized Multisplitting AOR Waveform Relaxation Method for Initial Value Problems of Ordinary Difference Equations，数学季刊，14(4) ： 31-42(1997) ．
[69] A． Gupta， V． Kumer，A． Sameh，Performance and scalability of preconditioned conjugate gradient methods on parallel computers，Technical reports,????， University of Minnesota，Dep．Computer Science，1997．
[70] A．Hadjidimos，Accelerated Overrelaxation method，Math．Comp．，32：149-157 (1978) ．
[71] G．Haase，Parallel incomplete Cholesky preconditioners based on the non-over lapping data distribution，Parallel Computing,24：1685-1703(1998) ．
[72] M．R．Hestenes，E．Stiefel，Method of conjugate gradients for solving linear systems，J．Res．Nat．Bur．Stand．，49：409-436(1952) ．
[73] M．T．Jones，P．E．Plassmann，The efficient parallel iterative solution of large sparse linear systems，In A．George，J．R．Gilbert，J．W．H．Liu，editors，Graph Theory and Sparse Matrix Computations,IMA Vol．56，Springer Verlag，Berlin，
1994．
[74] W. D. Joubert, D. M. Young, Necessary and sufficient conditions for the simplification of generalized conjugate gradient algorithms, Lin. Alg. Appl., 88/89:449-485(1987) .
[75] K. Kawamura, R. A. Volz, On the convergence of the conjugate gradient method in Hilbert space, IEEE Trans. on Auto. Control, AC-14:296-297(1969) .
[76] D. S. Kershaw, The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comp. Phys., 26:43-65 (1978) .
[77] L.Yu. Kolotilina, A. Yu. Yeremin, Factorized sparse approximate inverse preconditioning I: Theory, SIAM J. Matrix Anal. Appl., 14:45-58(1993) .
[78] C. Lanczos, An iteration method for the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand, 45:255-282 (1950) .
[79] C. Lanczos, Solution of systems of linear equations by minimized iteration, J. Res. Nat. Bur. Stand., 49:33-53(1952) .
[80] N. K. Lanzkron, D. J. Rose and D. B. Szyld, Convergence of nested classical iterative methods for linear systems, Numer. Math., 58:685-702(1991) .
[81] Guangye Li, A block variant of the GMRES method on massively parallel processors, Parallel Computing, 23:1005-1019(1997) .
[82] X. S. Li, J. W. Demmel, Making sparse Gaussian elimination scalable by static pivoting. In Proceedings of Supercomputing, Orlando, Florida, November 1998．
[83] L. Mansfield, On the conjugate gradient solution of the Schur complement system obtained from domain decomposition, SIAM J. Numer. Math., 27:1612-1620(1990) .
[84] J. Mas, V. Migallon, J. Penades, D. B. Szyld, Nonstationary parallel relaxed multisplitting methods, Lin. Alg. Appl., 241-243:733-747(1996) .
[85] T. P. Mathew, P. L. Polyakov, G. Russo, J. Wang, Domain decomposition operator splittings for the solution of parabolic equations, SIAM J. Sci. Comput., 19:912-932(1998) .
[86] G. Meurant, Computer Solution of Large Linear Systems, Elsvier Science B. V., North Holland, 1999．
[87] G. Meurant, The block preconditioned conjugate gradient method on vector computers, BIT, 24:623-633(1984) .
[88] G. Meurant, Multitasking the conjugate gradient method on the CRAY X-MP/48, Parallel Computing, 5:267-280(1987) .
[89] G. Meurant, Practical use of the conjugate gradient method on parallel supercomputers, Computer Physics Communication, 53:467-477(1989) .
[90] A. Neumann, R. J. Plemmons, Convergence of parallel multisplitting iterative methods for M-matrices, Lin. Alg. Appl., 88/89:559-573(1987) .
[91] N. K. Nichols, On the convergence of two-stage iterative processes for solving linear equations, SIM J. Numer. Anal., 10:460-469(1973) .
[92] R. A. Nicolaides, Deflation of conjugate gradient with applications to boundary value problems, SIM J. Numer. Anal., 24:355-365(1987) .
[93] Y. Notay, On the convergence rate of the conjugate gradients in presence of rounding errors, Numer. Math., 65:301-317(1993) .
[94] D. P. 0' Leary, The block conjugate gradient algorithm and related methods, Lin. Alg. Appl., 29:293-322(1980) .
[95] D. P. 0'Leary, R. E. White, Multi-splittings of matrices and parallel solution of linear systems, SIAM J. Alg. Dis. Meth., 6:630-640(1985) .
[96] J. M. Otrga and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Prentice-hall International, Inc, New Jersey, 1989．
[97] A. Padiy, 0． Axelsson, B. Polman, Generalized augmented matrix preconditioning approach and its application to iterative solution of ill-condition algebraic systems, Technical Report No. 9922, University of Nijmegn, Dep. Math., Netherlands, 1999．
[98] G. Radicati di Brozolo, Y. Robert, Parallel conjugate gradient-like algorithms for solving sparse non-symmetric systems on a vector multiprocessor, Parallel Computing, 11:223-239(1989) .
[99] J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equation. In J. K. Reid, editor, Large Sparse Sets of Linear Equations, Academic Press, 231-254(1971) .
[100] K. J. Ressel, M. H. Gutknecht, QMR smoothing for Lanczos-type product methods based on three-term recurrences, SIAM J. Sci. Comput., 19:55-73(1998) .
[101] Y. Saad, M. H. Schultz, Conjugate gradient-like algorithms for solving nonsymmetric linear systems, Math. Comput., 44:417-424(1985) .
[102] Y. Saad, Krylov subspace methods on supercomputers, SIAM J. Sci. Comput., 10:1200-1232(1989) .
[103] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14:461-469(1993) .
[104] Y. Saad, Iterative methods for sparse linear systems, PWS Publishing Company,
Boston, 1996．
[105] Y. Saad, Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18:435-449(1997) .
[106] Y. Saad, Jun Zhang, BILUTM: A domain-based multi-level block ILUT preconditioner for general sparse matrices, Technical Report UMSI 98/118, Minnesota Supercomputer institute, University of Minnesota, Minneapolis, MN, 1998．
[107] W. Schonauer, Scientific Computing on Vector Computers, North-Holland, NY, 1987．
[108] V. Simoncini, A stabilized QMR version of block BICG, SIAM J. Matrix Anal. Appl., 18:419-434(1997) .
[109] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10(1) : 36-52 (1989) .
[110] E. de Sturler, Nested Krylov methods based on GCR, J. Comput. Appl. Math., 67:15-41(1996) .
[111] E. de Sturler, A performance model for Krylov subspace methods on mesh-based parallel computers, Parallel Computing, 22:57-74(1996) .
[112] K. Sumiyoshin, T. Ebisuzaki, Performance of parallel solution of a block-tridiagnoal linear system on a Fujitsu VPP500． Parallel Computing, 24:287-304 (1998) .
[113] D. B. Szyld, M. T. Jones, Two-stage and multisplitting methods for the parallel solution of linear systems, SIAM J. Matrix Anal. Appl., 13:671-679(1992) .
[114] W. P. Tang, Generalized Schwarz Splittings, SIAM J. Sci. Stat. Comput., 13: 573-595(1992) .
[115] C. H. Tong, A family of quasi-minimal residual methods for nonsymmetric linear systems, SIAM J. Sci. Comput., 15(1) : 89-105 (1994)
[116] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of non-symmetric linear systems, SIAM J. Sci. Stat. Comput., 12:631-644(1992) .
[117] H. A. van der Vorst, C. Vuik, GMRESR: a family of nested GMRES methods, Numer. Lin. Alg. Appl., 1:369-386(1994) .
[118] V.C.N. van Duin, Parallel Sparse Matrix Computations, PhD thesis, Leiden University, Leiden, The Netherlands, 1998．
[119] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall Inc., Englewood Cliffs, NJ, 1962．
[120] P．K．W．Vinsome，ORTHOMIN，an iterative method for solving sparse sets of simultaneous linear equations，in 4th Symposium of Numerical simulation of Reserveir Performance of the Society of Petroleum Engineers of the AIME．Los Angeles，Calif．，1976，Paper SPE 5739．
[121] Wang Deren，On the convergence of parallel multisplitting AOR algorithm，Lin． Alg．Appl．，154／156：473-486(1991) ．
[122] R．Weiss，Convergence behavior of generalized conjugate gradient methods,PhD thesis，University of Karlsrushe，Germany，1990．
[123] R．E．White，Multisplitting with different weighting schemes，SIAM J．Matrix Anal．Appl．，10：481-495(1989) ．
[124] Jinchao Xu，Iterative methods by space decomposition and subspace correction， SIAM Review, 34：581-613(1992) ．
[125] D．M．Young，Iterative solution of large linear systems，Academic Press，NY， 1971．
[126] D．M．Young，K．C．Jea，Generalized conjugate-gradient acceleration of non-symmetrizable iterative methods，Lin．Alg．Appl．，34：159-194(1980) ．
[127] 张宝琳，谷同祥，莫则尧，数值并行计算原理与方法，国防工业出版社，1999．
[128] Jun Zhang，Multigrid Acceleration Techniques and Applications to the Numerical Solution of Partial Differential Equations,PhD thesiS，The George Washington University，U．S．A．，1997．
[129] Shao-Liang Zhang，GPBi-CG：generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems，SIAM J． Sci．Comput．，18：537-551 (1997) ．
[2] P．R．Amestoy，I．S．Duff，Vectorization of a multiprocessor multifrontal code． Int．J，of Suppercomputer Applics．，3：41-59(1989) ．
[3] P．R．Amestoy，I．S．Duff，C．Puglisi，Multifrontal QR factorization in a multiprocessor environment，Numer．Lin．Alg．Appl．，3：275-300(1996) ．
[4] R．S．Anderssen，G．H．Golub，Richardson’s non-stationary matrix iterative procedure，Technical Report STAIN-CS-72-304，Dept．of Computer Science， Stanford University，1972．
[5] S．F．Ashby，T．A．Manteuffel，P．E．Saylor，A taxonomy for conjugate gradient methods，SIAM J． Numer． Anal．，27：1542-1568(1990) ．
[6] O．Axelsson，Conjugate gradient type methods for unsymmetric and inconsistent systems of linear equations，Lin．Alg．Appl．，29：1-16(1980) ．
[7] O．Axelsson，G．Lindskog，On the eigenvalue distribution of a class of preconditioning methods，Numer．Math．，48：481-498(1986) ．
[8] O．Axelsson，G．Lindskog，On the rate of convergence of the precondition conjugate gradient method，Numer．Math．，48：499-523(1986) ．
[9] O．Axelsson，A generalized conjugate gradient，least square method，Numer． Math．，51：209-227(1987) ．
[10] O．Axelsson，P．S．Vassilevski，A black box generalized conjugate gradient solver with inner iterations and variable-step preconditioning，SIAM j． Matrix Anal．Appl．，12：625-644(1991) ．
[11] O．Axelsson， Iterative Solution Methods，Cambridge University Press， Cambridge，1994．
[12] O．Axelsson， Optimal preconditioners based on rate of convergence estimates for the conjugate gradient method，Technical Report No．9943，University of Nijmegn，Dep．Math．，The Netherlands，1999．
[13] 白中治，王德人，异步并行矩阵多分裂多参数松弛方法，高校计算数学学报， 16(2) ：107-115(1994) ．
[14] Z．Z．Bai，Parallel multisplitting two-stage iterative methods for large sparse systems of weakly nonlinear equations，Numen． Algorithms,15：347-372(1997) ．
[15] Z. Z. Bai, D. R. Wang and D. J. Evans, Models of asynchronous parallel matrix multisplitting relaxed iterations, Parallel Computing, 21:565-582(1995) .
[16] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems, SIAM, Philadephia, 1993．
[17] A. Basermann, Conjugate gradient and Lanczos methods for sparse matrices on distributed memory multiprocessors, J. Parallel & Distributed Computing, 45:46-52(1997) .
[18] A. Basermann, B. Reichel, C. Schelthoff, Preconditioned CG methods for sparse matrices on massively parallel machines, Parallel Computing, 23:381-398 (1997) .
[19] M. Benzi, C. D. Meyer, M. Tuma, A sparse approximate inverse preconditioner for the conjugate gradient method, SIAM J. Sci. Comput., 17:1135-1149 (1996) .
[20] Ake B jorck, T. Elfving, Z. StrakoS, Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl. , 19:720-736(1998) .
[21] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Science, Third ed. , Academic Press, New York, 1979．
[22] M. Bonnet, G, Meurant, Resolution de systemes d' equations lineaires par la methode du gradient conjugue avec preconditionnement, Rapport CEA/DAM 80069, 1980．
[23] J. H. Bramble, J. E. Pasciak, Junping Wang, Jinchao Xu, Convergence Estimates for product iterative methods with applications to domain decomposition, Math. Comput., 57:1-21(1991) .
[24] J. H. Bramble, J. E. Pasciak, Junping Wang, Jinchao Xu, Convergence Estimates for Multigrid algorithms without regularity assumptions, Math. Comput., 57:23-45(1991) .
[25] A. Brandt, Algebraic multigrid theory: the symmetric case, Appl. Math. Comput., 19:23-56(1986) .
[26] R. Bru, L. Eisner, M. Neumann, Models of parallel chaotic iteration methods, Lin. Alg. Appl., 103:175-192(1988) .
[27] R. Bru, C. Corral, A. Martinez, J. Mas, Multisplitting preconditioners based on incomplete Choleski factorizations, SIAM J. Matrix Anal. Appl., 16:1210-1222(1995) .
[28] R. Bru, V. Migallon, J. Penades and D. B. Szyld, Parallel, synchronous and
asynchronous two-stage multisplitting methods, Electronic Tran. on Numer. Anal., 3:24-38(1995) .
[29] H. M. Bucker, M. Sauren, A parallel version of the unsymmetric Lanczos algorithm and its application to QMR, Technical Report KFA-ZAM-IB-9605, Forschungszen-trum Julich Gmbh, Julich, Germany, 1996．
[30] Zhihao Cao, On convergence of nested stationary iterative methods, Lin. Alg. Appl., 221:159-170(1995) .
[31] T. F. Chan, D. Goovaerts, A note on the efficiency of domain decomposed incomplete factorizations, SAIM J. Sci. Stat. Comput., 11:794-803(1990) .
[32] A. T. Chronopoulos, C. W. Gear, s-Step iterative methods for symmetric linear systems, J. Comp. & Appl. Math., 25:153-168(1989) .
[33] E. Chow, Y. Saad, Approximate inverse techniques for block-partitioned matrices, SIAM J. Sci. Comput., 18:1657-1675(1997) .
[34] A. I. Cohen, Rate of convergence of several conjugate gradient algorithms, SIAM J. Numer. Anal., 9:248-259(1972) .
[35] P. Concus, G. H. Golub, D. P. O'Leary, A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations, In J. R. Bunch and D. J. Rose, editors, Sparse Matrix Computations, Academic Press, 309-332(1976) .
[36] P. Concus, G.H. Golub, G. Meurant, Block preconditioning for the conjugate gradient method, SIAM J. Sci. Stat. Comput., 6:220-252(1985)
[37] C. Corral, I. Gimenez, J. Marin, J. Mas, Parallel m-step preconditioner for the conjugate gradient method, Parallel Computing, 25:265-281(1999) .
[38] L. Crone, H. A. van der Vorst, Communication aspects of the conjugate gradient method on distributed-memory machines, Supercomputer, X(6) :4-9(1993) .
[39] E. F. D'Azevedo, C. Romine, Reducing communication costs in the conjugate gradient algorithm on distributed memory multiprocessors, Technical reports LAPACK working note 56, Computer Science Department, University of Knoxville, Knoxville, TN, 1993．
[40] J. W. Demmel, M. T. Heath, H. A. van der Vorst, Parallel numerical linear algebra, In Acta Numerica 1993, Cambridge University Press, Cambridge, 1993．
[41] J. W. Demmel, S. C. Eisenstat, J. R. Gilbert, X. S. Li, J. W. H. Liu, A Supernodal approach to sparse partial pivoting, Technical Report UCB//CSD95-883, Computer science Division, U. C. Berkeley, Berkeley, California, July 1995．
[42] I.S. Duff, G. A. Meurant, The effect of ordering on preconditioned conjugate
gradient, BIT, 29:635-657(1989) .
[43] S. C. Eisenstat, A Note on the generalized conjugate gradient method, SIAM J. Numer. Anal., 20:358-361(1983) .
[44] J. Erhel, F. Guyomarc'h, An augmented subspace conjugate gradient, Technical Report 1136, Institut de Recherche en Informatique et Systemes Aleatoires, 1997
[45] D. J. Evans, M. M. Martins, M. E. Trigo, On the convergence of some generalized iterative methods with preconditioning, Intern. J. Computer Math. , 44:19-28 (1992) .
[46] V. Faber, T. Manteuffel, Necessary and sufficient conditions for the existence of a conjugate gradient method, SIAM J. Numer. Anal., 21:352-362(1984) .
[47] V. Faber, T. Manteuffel, Orthogonal error methods, SIAM J. Numer. Anal., 24: 170-187(1987) .
[48] M. R. Field, Optimizing a parallel conjugate gradient solver, SIAM J. Sci. Comput., 19:27-37(1998) .
[49] R. Fletcher, C. M. Reeves, Function minimization by conjugate gradients, Computer J. , 7 : 149-154 (1964) .
[50] R. Fletcher, Conjugate gradient methods for indefinite systems, In G. A. Watson, editor, Numerical Analysis Dundee 1975 , G. A. Watson ed. , New York, Springer, Lecture Notes in Mathematics, no. 506, 73-89(1976) .
[51] D. R. Fokkema, P. Sleijpen, H. A. Van der Vorst, Generalized conjugate gradient squared, J. Comput. Appl. Math., 71:125-146(1996) .
[52] R. W. Freund, A transpose-free quasi-minimal residual algorithm for non-Hermitian linear systems, SIAM J. Sci. Comput., 14:470-482(1993) .
[53] R. W. Freund, N. M. Nachtigal, QMR: a quasi-minimal residual method for non-Hermitian linear systems, Numer. Math., 60:315-339(1991) .
[54] A. Frommer, G. Mayer, Convergence of relaxed parallel multisplitting methods, Lin. Alg. Appl., 119:141-152(1989) .
[55] A. Frommer, H. Schwandt, A unified representation and theory of algebraic additive Schwarz and multisplitting methods, SIM J. Matrix Anal. Appl. , 19: 893-912(1997) .
[56] A. Frommer and D. B. Szyld, H-splitting and two-stage iterative methods, Numer. Math., 63(1992) , pp. 345-356．
[57] R. Fuster, V. Migallon and J. Penades, Non-stationary parallel multisplitting AOR methods, Electronic Tran. on Numer. Anal., 4:1-13(1996) .
[58] G．H．Golub，M。L．Overton，The convergence of inexact Chebyshev and Richardson iterative methods for solving linear systems，Numer．Math．，53：571-593(1988) ．
[59] G．H．Golub and D．P．O’Leary，Some history of the conjugate gradient and Lanczos algorithms：1948-1976，SIAM Review,31：50-102(1989) ．
[60] G．H．Golub。C．Van Loan，Matrix Computation，second edition，Johns Hopkins University Press，1989．
[61] A．Greenbaum，Congming Li，Zhen Chao，Parallelizing preconditioned conjugate gradient algorithms，Computer Physics Communications,53：295-309(1989) ．
[62] Gu Tongxiang，Liu Xingping，Shen Longjun，Relaxed parallel two-stage multisplitting methods，Intern．J．Computer Math．，75：351-367(2000) ．
[63] 谷同祥，沈隆钧，刘兴平，异步松弛型并行二级多分裂迭代法，高等学校计算数学学 报，即将发表．
[64] 谷同样，刘兴平，并行二级多分裂迭代法，计算数学 20(2) ：153-166(1998) ．
[65] Gu Tongxiang，Wang Nengchao，Safe bounds for the solution of nonlinear problems using a relaxed parallel multisplitting methods，Mathematica Applicata， 8：351-359(1995) ．
[66] Gu Tongxiang，Asynchronous relaxed iterative methods for solving l inear systems of equations，Appl．Math．Mech．，18：801-806(1997) ．
[67] 谷同祥，王能超，并行求解线性方程组的非定常二级多分裂迭代方法，工程数学学报， 14(4) ：25-32(1997) ．
[68] Gu Tongxiang，Discretized Multisplitting AOR Waveform Relaxation Method for Initial Value Problems of Ordinary Difference Equations，数学季刊，14(4) ： 31-42(1997) ．
[69] A． Gupta， V． Kumer，A． Sameh，Performance and scalability of preconditioned conjugate gradient methods on parallel computers，Technical reports,????， University of Minnesota，Dep．Computer Science，1997．
[70] A．Hadjidimos，Accelerated Overrelaxation method，Math．Comp．，32：149-157 (1978) ．
[71] G．Haase，Parallel incomplete Cholesky preconditioners based on the non-over lapping data distribution，Parallel Computing,24：1685-1703(1998) ．
[72] M．R．Hestenes，E．Stiefel，Method of conjugate gradients for solving linear systems，J．Res．Nat．Bur．Stand．，49：409-436(1952) ．
[73] M．T．Jones，P．E．Plassmann，The efficient parallel iterative solution of large sparse linear systems，In A．George，J．R．Gilbert，J．W．H．Liu，editors，Graph Theory and Sparse Matrix Computations,IMA Vol．56，Springer Verlag，Berlin，
1994．
[74] W. D. Joubert, D. M. Young, Necessary and sufficient conditions for the simplification of generalized conjugate gradient algorithms, Lin. Alg. Appl., 88/89:449-485(1987) .
[75] K. Kawamura, R. A. Volz, On the convergence of the conjugate gradient method in Hilbert space, IEEE Trans. on Auto. Control, AC-14:296-297(1969) .
[76] D. S. Kershaw, The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations, J. Comp. Phys., 26:43-65 (1978) .
[77] L.Yu. Kolotilina, A. Yu. Yeremin, Factorized sparse approximate inverse preconditioning I: Theory, SIAM J. Matrix Anal. Appl., 14:45-58(1993) .
[78] C. Lanczos, An iteration method for the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand, 45:255-282 (1950) .
[79] C. Lanczos, Solution of systems of linear equations by minimized iteration, J. Res. Nat. Bur. Stand., 49:33-53(1952) .
[80] N. K. Lanzkron, D. J. Rose and D. B. Szyld, Convergence of nested classical iterative methods for linear systems, Numer. Math., 58:685-702(1991) .
[81] Guangye Li, A block variant of the GMRES method on massively parallel processors, Parallel Computing, 23:1005-1019(1997) .
[82] X. S. Li, J. W. Demmel, Making sparse Gaussian elimination scalable by static pivoting. In Proceedings of Supercomputing, Orlando, Florida, November 1998．
[83] L. Mansfield, On the conjugate gradient solution of the Schur complement system obtained from domain decomposition, SIAM J. Numer. Math., 27:1612-1620(1990) .
[84] J. Mas, V. Migallon, J. Penades, D. B. Szyld, Nonstationary parallel relaxed multisplitting methods, Lin. Alg. Appl., 241-243:733-747(1996) .
[85] T. P. Mathew, P. L. Polyakov, G. Russo, J. Wang, Domain decomposition operator splittings for the solution of parabolic equations, SIAM J. Sci. Comput., 19:912-932(1998) .
[86] G. Meurant, Computer Solution of Large Linear Systems, Elsvier Science B. V., North Holland, 1999．
[87] G. Meurant, The block preconditioned conjugate gradient method on vector computers, BIT, 24:623-633(1984) .
[88] G. Meurant, Multitasking the conjugate gradient method on the CRAY X-MP/48, Parallel Computing, 5:267-280(1987) .
[89] G. Meurant, Practical use of the conjugate gradient method on parallel supercomputers, Computer Physics Communication, 53:467-477(1989) .
[90] A. Neumann, R. J. Plemmons, Convergence of parallel multisplitting iterative methods for M-matrices, Lin. Alg. Appl., 88/89:559-573(1987) .
[91] N. K. Nichols, On the convergence of two-stage iterative processes for solving linear equations, SIM J. Numer. Anal., 10:460-469(1973) .
[92] R. A. Nicolaides, Deflation of conjugate gradient with applications to boundary value problems, SIM J. Numer. Anal., 24:355-365(1987) .
[93] Y. Notay, On the convergence rate of the conjugate gradients in presence of rounding errors, Numer. Math., 65:301-317(1993) .
[94] D. P. 0' Leary, The block conjugate gradient algorithm and related methods, Lin. Alg. Appl., 29:293-322(1980) .
[95] D. P. 0'Leary, R. E. White, Multi-splittings of matrices and parallel solution of linear systems, SIAM J. Alg. Dis. Meth., 6:630-640(1985) .
[96] J. M. Otrga and W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Prentice-hall International, Inc, New Jersey, 1989．
[97] A. Padiy, 0． Axelsson, B. Polman, Generalized augmented matrix preconditioning approach and its application to iterative solution of ill-condition algebraic systems, Technical Report No. 9922, University of Nijmegn, Dep. Math., Netherlands, 1999．
[98] G. Radicati di Brozolo, Y. Robert, Parallel conjugate gradient-like algorithms for solving sparse non-symmetric systems on a vector multiprocessor, Parallel Computing, 11:223-239(1989) .
[99] J. K. Reid, On the method of conjugate gradients for the solution of large sparse systems of linear equation. In J. K. Reid, editor, Large Sparse Sets of Linear Equations, Academic Press, 231-254(1971) .
[100] K. J. Ressel, M. H. Gutknecht, QMR smoothing for Lanczos-type product methods based on three-term recurrences, SIAM J. Sci. Comput., 19:55-73(1998) .
[101] Y. Saad, M. H. Schultz, Conjugate gradient-like algorithms for solving nonsymmetric linear systems, Math. Comput., 44:417-424(1985) .
[102] Y. Saad, Krylov subspace methods on supercomputers, SIAM J. Sci. Comput., 10:1200-1232(1989) .
[103] Y. Saad, A flexible inner-outer preconditioned GMRES algorithm, SIAM J. Sci. Comput., 14:461-469(1993) .
[104] Y. Saad, Iterative methods for sparse linear systems, PWS Publishing Company,
Boston, 1996．
[105] Y. Saad, Analysis of augmented Krylov subspace methods, SIAM J. Matrix Anal. Appl., 18:435-449(1997) .
[106] Y. Saad, Jun Zhang, BILUTM: A domain-based multi-level block ILUT preconditioner for general sparse matrices, Technical Report UMSI 98/118, Minnesota Supercomputer institute, University of Minnesota, Minneapolis, MN, 1998．
[107] W. Schonauer, Scientific Computing on Vector Computers, North-Holland, NY, 1987．
[108] V. Simoncini, A stabilized QMR version of block BICG, SIAM J. Matrix Anal. Appl., 18:419-434(1997) .
[109] P. Sonneveld, CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10(1) : 36-52 (1989) .
[110] E. de Sturler, Nested Krylov methods based on GCR, J. Comput. Appl. Math., 67:15-41(1996) .
[111] E. de Sturler, A performance model for Krylov subspace methods on mesh-based parallel computers, Parallel Computing, 22:57-74(1996) .
[112] K. Sumiyoshin, T. Ebisuzaki, Performance of parallel solution of a block-tridiagnoal linear system on a Fujitsu VPP500． Parallel Computing, 24:287-304 (1998) .
[113] D. B. Szyld, M. T. Jones, Two-stage and multisplitting methods for the parallel solution of linear systems, SIAM J. Matrix Anal. Appl., 13:671-679(1992) .
[114] W. P. Tang, Generalized Schwarz Splittings, SIAM J. Sci. Stat. Comput., 13: 573-595(1992) .
[115] C. H. Tong, A family of quasi-minimal residual methods for nonsymmetric linear systems, SIAM J. Sci. Comput., 15(1) : 89-105 (1994)
[116] H. A. van der Vorst, Bi-CGSTAB: A fast and smoothly converging variant of Bi-CG for the solution of non-symmetric linear systems, SIAM J. Sci. Stat. Comput., 12:631-644(1992) .
[117] H. A. van der Vorst, C. Vuik, GMRESR: a family of nested GMRES methods, Numer. Lin. Alg. Appl., 1:369-386(1994) .
[118] V.C.N. van Duin, Parallel Sparse Matrix Computations, PhD thesis, Leiden University, Leiden, The Netherlands, 1998．
[119] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall Inc., Englewood Cliffs, NJ, 1962．
[120] P．K．W．Vinsome，ORTHOMIN，an iterative method for solving sparse sets of simultaneous linear equations，in 4th Symposium of Numerical simulation of Reserveir Performance of the Society of Petroleum Engineers of the AIME．Los Angeles，Calif．，1976，Paper SPE 5739．
[121] Wang Deren，On the convergence of parallel multisplitting AOR algorithm，Lin． Alg．Appl．，154／156：473-486(1991) ．
[122] R．Weiss，Convergence behavior of generalized conjugate gradient methods,PhD thesis，University of Karlsrushe，Germany，1990．
[123] R．E．White，Multisplitting with different weighting schemes，SIAM J．Matrix Anal．Appl．，10：481-495(1989) ．
[124] Jinchao Xu，Iterative methods by space decomposition and subspace correction， SIAM Review, 34：581-613(1992) ．
[125] D．M．Young，Iterative solution of large linear systems，Academic Press，NY， 1971．
[126] D．M．Young，K．C．Jea，Generalized conjugate-gradient acceleration of non-symmetrizable iterative methods，Lin．Alg．Appl．，34：159-194(1980) ．
[127] 张宝琳，谷同祥，莫则尧，数值并行计算原理与方法，国防工业出版社，1999．
[128] Jun Zhang，Multigrid Acceleration Techniques and Applications to the Numerical Solution of Partial Differential Equations,PhD thesiS，The George Washington University，U．S．A．，1997．
[129] Shao-Liang Zhang，GPBi-CG：generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems，SIAM J． Sci．Comput．，18：537-551 (1997) ．