鞍点问题和马尔科夫链问题的高性能算法研究
|
摘要
科学与工程的很多重要领域如通讯网络和输送现象的模拟、经济管理和市场预测、高阶微分方程求解、流体力学、计算电磁学、油藏模拟和最优化问题等都离不开线性代数系统的求解.随着科学技术的迅猛发展,人们对线性代数系统的求解在计算速度和计算精度方面的要求变得越来越高.因此,线性代数系统的求解方法研究一直都是科学与工程计算的核心之一,具有十分重要的理论意义和实际应用价值.本文针对鞍点问题和马尔科夫链问题产生的线性代数系统,深入研究了直接法,矩阵分裂迭代法, Krylov子空间方法和预处理技术等在求解相应线性代数系统中的应用,并构造出了一些新的有效算法.全文共六章,分为四个部分:
研究了鞍点问题迭代求解预处理技术.首先提出了修正的对称超松弛类(MSSOR-like)迭代法求解经典鞍点问题,讨论了该迭代法的收敛性,给出了最优参数的选取范围,数值实验验证了其有效性.其次,针对具有2×2块结构的奇异对称鞍点问题,通过改变系数矩阵中(2,2)块矩阵的值,构造了修正的SSOR(MSSOR)预处理子,研究了MSSOR预处理矩阵的谱性质及其收敛性,数值实验说明了MSSOR预处理子能有效加快迭代法的收敛速度.最后,针对对称广义鞍点问题产生的不定线性代数系统,借用交替迭代法的思想,结合现有的块对角预处理子和约束预处理子,建立了乘积预处理子,分析了该预处理矩阵的特征值分布情况,对应特征向量的具体形式和最小多项式的最大次数,数值实验显示该乘积预处理子在减少所需计算时间和迭代步数方面有着明显的效果.
研究了矩阵分裂迭代法在求解马尔科夫链问题中的应用.由于马尔科夫链问题产生的线性代数系统通常是奇异的,以致适用于求解非奇异线性代数系统的很多计算方法不能直接应用于该问题的求解.为了克服这一难点,本文首先给出一个定理说明存在一个非负数使得马尔科夫链问题产生的线性方程组经过修正之后具有正定性.然后基于矩阵分裂迭代法的思想,构造了对称与反对称矩阵分裂(SSS)迭代法和三角与反对称矩阵分裂(TSS)迭代法.这类迭代法包含两个子系统,本文从理论上详细讨论了SSS和TSS迭代法的收敛性及其最优参数选取情况.在实际计算中,如果利用直接法精确求解SSS和TSS迭代法中的两个子系统,则每个子系统的计算量与求解原系统相当,以致这里的两步迭代失去了意义.为了加快两个子系统的求解速度,本文发展了非精确的SSS和TSS迭代法,记为ISSS和ITSS迭代法.数值实验说明了这些方法的有效性.
研究了求解马尔科夫链问题的向量外推加速多级聚合算法.首先介绍了多级聚合算法和向量外推方法的相关原理,说明多级聚合算法的核心部分在于如何有效地构造限制和延伸算子.然后指出该算法在求解马尔科夫链问题时存在的主要缺陷,即各层之间相互转化所需要的限制和延伸算子依赖于最新近似解,使得每步迭代中都需要重新计算限制和延伸算子,从而耗费大量的计算时间,令人无法接受.因此,本文结合向量外推方法计算量小,所需输入量少等优点,构造了新的向量外推加速多级聚合算法,数值实验说明了该新算法在减少计算时间和迭代步数方面所取得的进步.
研究了求解非奇异线性方程组的两个共轭方向方法, Bi-CR和Bi-CG方法,发现它们具有短项循环公式和双共轭性等特点.故试图将Bi-CR和Bi-CG方法推广到求解马尔科夫链问题产生的奇异线性代数系统,使之成为获得平稳状态概率分布向量的有效计算工具.数值实验说明了Bi-CR和Bi-CG方法求解马尔科夫链问题的有效性和稳定性.
Solutions of large-scale sparse linear algebraic systems are deeply involved in vari-ous scientific and engineering fields, such as simulations of communication network andtransport phenomena, economic management and market forecasting, numerical solu-tions of high-order differential equations, fluid mechanics, computational electromagnet-ics, reservoir modeling and optimization problems. With the rapid development of sci-ence and technology, the requirements to the speed and accuracy of solving large-scalesparse linear algebraic systems become more and more. Therefore, research of methodsfor solving large-scale sparse linear algebraic systems is still one of the key issues oflarge-scale scientific and engineering computing and such research has important theo-retic significance and practical applications. This doctoral dissertation deeply studies thedirect methods, matrix splitting methods, Krylov subspace methods and preconditioningtechniques for solving large-scale sparse linear algebraic systems which arise from saddlepoint problems and Markov chain problems. The dissertation consists of four parts withsix chapters:
Part one contributes to preconditioning techniques for iteration solutions of sad-dle point problems. A modified symmetric successive overrelaxation-like (MSSOR-like)method is firstly proposed for solving saddle point problems. Its convergence conditionsare discussed, and the optimal domain of iteration parameter is given. Numerical ex-periments verify the effectiveness of the MSSOR-like method. Next, a modified SSORpreconditioner is established for solving singular symmetric saddle point problems bychanging the values of the (2,2) block matrix. The convergence conditions and spectralproperties of the MSSOR preconditioned matrix are studied comprehensively. The ef-ficiency and stability of the proposed preconditioner are shown through the numericalresults. At last, a product preconditioner is constructed for solving the symmetric in-definite saddle point matrices as the product of two fairly simple preconditiners. One isthe popular constraint preconditioner, and another is the famous block Jacobi precondi-tioner. Results concerning the eigenvalue distributions and form of the eigenvectors ofthe product preconditioned matrix and its minimal polynomial are analyzed. Numericalexperiments show the efficiency of the proposed product preconditioner in reducing the computational time and iteration counts.
Part two is to study matrix splitting methods with applications to Markov chain prob-lems. A large amount of computational methods for nonsingular large-scale sparse linearsystems is not able to be directly applied to solve the Markov chain problems since theircoefficient matrices are often irreducible and singular. For overcoming this difficulty, atheorem is firstly presented to indicate that there exists a nonnegative constant suchthat the shifted linear system is positive-definite. Then two iteration methods are devel-oped to compute the stationary probability distribution vector of Markov chains basedon matrix splitting methods. One is the symmetric and skew-symmetric splitting (SSS)iteration method, and another is the triangular and skew-symmetric splitting (TSS) it-eration method. Both of the SSS and TSS iteration methods include two subsystems.Convergence properties and optimal parameter selections of these methods are studied.In practical computation, if these subsystems are solved exactly with direct methods, thenthe SSS and TSS iteration methods are meaningless, because the cost for solving thesesubsystems is equal to that for solving the original system by direct solvers. Consequently,for improving their convergence, we solve them inexactly by Krylov subspace methodsand develop ISSS and ITSS methods. Numerical results illustrate the effectiveness of theproposed methods.
Part three proposes an accelerated multilevel aggregation algorithm for Markovchains by combining with vector extrapolation methods. The dissertation briefly intro-duces the background of the multilevel aggregation algorithm and vector extrapolationmethods at first. Then the main drawback of the multilevel aggregation algorithm forMarkov chains is presented. That is, the construction of the restriction and prolonga-tion operators depends on the update of the stationary probability distribution vector ateach iteration step, and thus the computational time is unacceptable. Therefore, takingadvantages of the merit of the vector extrapolation methods, the accelerated multilevelaggregation algorithm is established for Markov chain problems. Numerical experimentson several representative Markov chain examples are used to illustrate the effectivenessof the proposed algorithm.
Part four studies two conjugate direction methods (Bi-CR and Bi-CG) for comput-ing the stationary probability distribution vector of Markov chains. Motivated by thecelebrated applications of the two conjugate direction methods to nonsingular linear sys- tems, this dissertation attempts to extend the Bi-CR and Bi-CG methods to singular linearsystems which arise from Markov chain problems, as one of the possible computationaltools. Numerical experiments examine the Bi-CR and Bi-CG methods and illustrate bothof them work well for Markov chain problems.
研究了鞍点问题迭代求解预处理技术.首先提出了修正的对称超松弛类(MSSOR-like)迭代法求解经典鞍点问题,讨论了该迭代法的收敛性,给出了最优参数的选取范围,数值实验验证了其有效性.其次,针对具有2×2块结构的奇异对称鞍点问题,通过改变系数矩阵中(2,2)块矩阵的值,构造了修正的SSOR(MSSOR)预处理子,研究了MSSOR预处理矩阵的谱性质及其收敛性,数值实验说明了MSSOR预处理子能有效加快迭代法的收敛速度.最后,针对对称广义鞍点问题产生的不定线性代数系统,借用交替迭代法的思想,结合现有的块对角预处理子和约束预处理子,建立了乘积预处理子,分析了该预处理矩阵的特征值分布情况,对应特征向量的具体形式和最小多项式的最大次数,数值实验显示该乘积预处理子在减少所需计算时间和迭代步数方面有着明显的效果.
研究了矩阵分裂迭代法在求解马尔科夫链问题中的应用.由于马尔科夫链问题产生的线性代数系统通常是奇异的,以致适用于求解非奇异线性代数系统的很多计算方法不能直接应用于该问题的求解.为了克服这一难点,本文首先给出一个定理说明存在一个非负数使得马尔科夫链问题产生的线性方程组经过修正之后具有正定性.然后基于矩阵分裂迭代法的思想,构造了对称与反对称矩阵分裂(SSS)迭代法和三角与反对称矩阵分裂(TSS)迭代法.这类迭代法包含两个子系统,本文从理论上详细讨论了SSS和TSS迭代法的收敛性及其最优参数选取情况.在实际计算中,如果利用直接法精确求解SSS和TSS迭代法中的两个子系统,则每个子系统的计算量与求解原系统相当,以致这里的两步迭代失去了意义.为了加快两个子系统的求解速度,本文发展了非精确的SSS和TSS迭代法,记为ISSS和ITSS迭代法.数值实验说明了这些方法的有效性.
研究了求解马尔科夫链问题的向量外推加速多级聚合算法.首先介绍了多级聚合算法和向量外推方法的相关原理,说明多级聚合算法的核心部分在于如何有效地构造限制和延伸算子.然后指出该算法在求解马尔科夫链问题时存在的主要缺陷,即各层之间相互转化所需要的限制和延伸算子依赖于最新近似解,使得每步迭代中都需要重新计算限制和延伸算子,从而耗费大量的计算时间,令人无法接受.因此,本文结合向量外推方法计算量小,所需输入量少等优点,构造了新的向量外推加速多级聚合算法,数值实验说明了该新算法在减少计算时间和迭代步数方面所取得的进步.
研究了求解非奇异线性方程组的两个共轭方向方法, Bi-CR和Bi-CG方法,发现它们具有短项循环公式和双共轭性等特点.故试图将Bi-CR和Bi-CG方法推广到求解马尔科夫链问题产生的奇异线性代数系统,使之成为获得平稳状态概率分布向量的有效计算工具.数值实验说明了Bi-CR和Bi-CG方法求解马尔科夫链问题的有效性和稳定性.
Solutions of large-scale sparse linear algebraic systems are deeply involved in vari-ous scientific and engineering fields, such as simulations of communication network andtransport phenomena, economic management and market forecasting, numerical solu-tions of high-order differential equations, fluid mechanics, computational electromagnet-ics, reservoir modeling and optimization problems. With the rapid development of sci-ence and technology, the requirements to the speed and accuracy of solving large-scalesparse linear algebraic systems become more and more. Therefore, research of methodsfor solving large-scale sparse linear algebraic systems is still one of the key issues oflarge-scale scientific and engineering computing and such research has important theo-retic significance and practical applications. This doctoral dissertation deeply studies thedirect methods, matrix splitting methods, Krylov subspace methods and preconditioningtechniques for solving large-scale sparse linear algebraic systems which arise from saddlepoint problems and Markov chain problems. The dissertation consists of four parts withsix chapters:
Part one contributes to preconditioning techniques for iteration solutions of sad-dle point problems. A modified symmetric successive overrelaxation-like (MSSOR-like)method is firstly proposed for solving saddle point problems. Its convergence conditionsare discussed, and the optimal domain of iteration parameter is given. Numerical ex-periments verify the effectiveness of the MSSOR-like method. Next, a modified SSORpreconditioner is established for solving singular symmetric saddle point problems bychanging the values of the (2,2) block matrix. The convergence conditions and spectralproperties of the MSSOR preconditioned matrix are studied comprehensively. The ef-ficiency and stability of the proposed preconditioner are shown through the numericalresults. At last, a product preconditioner is constructed for solving the symmetric in-definite saddle point matrices as the product of two fairly simple preconditiners. One isthe popular constraint preconditioner, and another is the famous block Jacobi precondi-tioner. Results concerning the eigenvalue distributions and form of the eigenvectors ofthe product preconditioned matrix and its minimal polynomial are analyzed. Numericalexperiments show the efficiency of the proposed product preconditioner in reducing the computational time and iteration counts.
Part two is to study matrix splitting methods with applications to Markov chain prob-lems. A large amount of computational methods for nonsingular large-scale sparse linearsystems is not able to be directly applied to solve the Markov chain problems since theircoefficient matrices are often irreducible and singular. For overcoming this difficulty, atheorem is firstly presented to indicate that there exists a nonnegative constant suchthat the shifted linear system is positive-definite. Then two iteration methods are devel-oped to compute the stationary probability distribution vector of Markov chains basedon matrix splitting methods. One is the symmetric and skew-symmetric splitting (SSS)iteration method, and another is the triangular and skew-symmetric splitting (TSS) it-eration method. Both of the SSS and TSS iteration methods include two subsystems.Convergence properties and optimal parameter selections of these methods are studied.In practical computation, if these subsystems are solved exactly with direct methods, thenthe SSS and TSS iteration methods are meaningless, because the cost for solving thesesubsystems is equal to that for solving the original system by direct solvers. Consequently,for improving their convergence, we solve them inexactly by Krylov subspace methodsand develop ISSS and ITSS methods. Numerical results illustrate the effectiveness of theproposed methods.
Part three proposes an accelerated multilevel aggregation algorithm for Markovchains by combining with vector extrapolation methods. The dissertation briefly intro-duces the background of the multilevel aggregation algorithm and vector extrapolationmethods at first. Then the main drawback of the multilevel aggregation algorithm forMarkov chains is presented. That is, the construction of the restriction and prolonga-tion operators depends on the update of the stationary probability distribution vector ateach iteration step, and thus the computational time is unacceptable. Therefore, takingadvantages of the merit of the vector extrapolation methods, the accelerated multilevelaggregation algorithm is established for Markov chain problems. Numerical experimentson several representative Markov chain examples are used to illustrate the effectivenessof the proposed algorithm.
Part four studies two conjugate direction methods (Bi-CR and Bi-CG) for comput-ing the stationary probability distribution vector of Markov chains. Motivated by thecelebrated applications of the two conjugate direction methods to nonsingular linear sys- tems, this dissertation attempts to extend the Bi-CR and Bi-CG methods to singular linearsystems which arise from Markov chain problems, as one of the possible computationaltools. Numerical experiments examine the Bi-CR and Bi-CG methods and illustrate bothof them work well for Markov chain problems.
引文
[1] K. Abe, H. Ogata, M. Sugihara, et al.. Convergence theory of the CR method for linear singularsystems. Transactions of the Japan Society for Industrial and Applied Mathematics,1999,9:1-13
[2] W.E. Arnoldi. The principle of minimized iteration in the solution of the matrix eigenvalue prob-lem. Quart. Appl. Math.,1951,9:17-29
[3] K. Arrow, L. Hurwica, H. Uzawa. Studies in Nonlinear Programming. Stanford University Press,Stanford, CA,1958
[4] O. Axelsson. A class of iterative methods for finite element equations. Comm. Meth. Appl.,1976,9:123-137
[5] O. Axelsson. Iterative Solution Methods. Cambridge University Press, New York,1994
[6] Z.-Z. Bai. Structured preconditioners for nonsingular matrices of block two-by-two structures.Math. Comp.,2006,75:791-815
[7] Z.-Z. Bai, G.H. Golub, L.-Z. Lu, et al.. Block triangular and skew-Hermitian splitting methodsfor positive-definite linear systems. SIAM J. Sci. Comput.,2005,20:844-863
[8] Z.-Z. Bai, G.H. Golub, J.Y. Pan. Preconditioned Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive semidefinite linear systems. Numer. Math.,2004,98:1-32
[10] Z.-Z. Bai, G.H. Golub, M.K. Ng. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl.,2003,24:603-626
[10] Z.-Z. Bai, G.H. Golub, M.K. Ng. On successive-overrelaxation acceleration of the Hermitianand skew-Hermitian splitting iterations. Numerical Linear Algebra with Applications,2007,14:319-335
[11] Z.-Z. Bai, M.K. Ng, Z.-Q. Wang. Constraint preconditioners for symmetric indefinite matrices.SIAM J. Matrix Anal. Appl.,2009,31:410-433
[12] G. Bao, W.-W. Sun. A fast algorithm for the electromagnetic scattering from a large cavity. SIAMJ. Sci. Comput.,2005,27:553-574
[13] G. Barker, R.J. Plemmons. Convergent iterations for computing stationary distributions ofMarkov chains. SIAM J. Alg. Disc. Meth.,1986,7:390-398
[14] R. Barrett. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.Society for Industrial Mathematics,1994
[15] M. Benzi. A generalization of the Hermitian and skew-Hermitian splitting iteration. SIAM J.Matrix Anal. Appl.,2009,31:360-374
[16] M. Benzi. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys.,2002,182:418-477
[17] M. Benzi, G.H. Golub. A preconditioner for generalized saddle point problems. SIAM J. MatrixAnal. Appl.,2004,26:20-41
[18] M. Benzi, G.H. Golub and J. Liesen. Numerical solution of saddle point problems. Acta numer-ica.2005,14:1-137
[19] M. Benzi, V. Kuhlemann. Restricted additive methods for Markov chains. Numer. Linear AlgebraAppl.,2011,18:1011-1029
[20] M. Benzi, C.D. Meyer, M. Tuma. A sparse approximate inverse preconditioner for the conjugategradient method. SIAM J. Sci. Comput.,1996,17:1135-1149
[21] M. Benzi, D.B. Szyld. Existence and uniqueness of splittings for stationary iterative methodswith applications to alternating methods. Numer. Math.,1997,76:309-321
[22] M. Benzi, B. Uc ar. Block triangular preconditioners for M-matrices and Markov chains. ETNA,2007,26:209-227
[23] M. Benzi, B. Uc ar. Product preconditioning for Markov chain problems. in Proceedings of the2006Markov Anniversary Meeting, A. N. Langville and W. J. Stewart, eds., Raleigh, NC,2006,(Charleston, SC), Boson Books,239-256
[24] A. Berman, R.J. Plemmons. Nonnegative Matrices in the Mathematical Sciences. AcademicPress, New York,1979
[25] D.A. Bini, G. Latouche, B. Meini. Numerical Methods for Structured Markov Chains. OxfordUniversity Press, London,2005
[26] A. Bjorck. Numerical stability of methods for solving augmented systems. In Proceedings fromRecent Developments in Optimization Theory and Nonlinear Analysis, Jerusalem,1995, Y. Cen-sor and S. Reich, eds., Contemp. Math.,204, Amer. Math. Soc., Providence, RI,1997,51-60
[27] S. Borovac. A graph based approach to the convergence of one level schwarz iterations for sin-gular M-matrices and Markov chains. SIAM J. Matrix Anal. Appl.,2008,30:1371-1391
[28] J.H. Bramble, J.E. Pasciak. A preconditioning technique for indefinite systems resulting frommixed approximations of elliptic problems. Math. Comput.,1988,50:1-17
[29] J.H. Bramble, J.E. Pasciak. Iterative technique for time dependent Stokes problems. Comput.Math. Appl.,1997,33:13-30
[30] J. Bramble, J. Pasciak, A. Vassilev. Analysis of the inexact Uzawa algorithm for saddle pointproblems. SIAM J. Numer. Anal.,1997,34:1072-1092
[31] J. Bramble, J. Pasciak, A. Vassilev. Uzawa type algorithms for nonsymmetric saddle point prob-lems. Math. Comput.,2000,69:667-689
[32] A. Brandt, S. McCormick and J. Ruge. Algebraic Multigrid (AMG) for Sparse Matrix Equations.D.J Evans (Ed.), Sparsity and its Applications,1984
[33] M. Brezina, R. Falgout, S. Maclachlan, et al.. Adaptive algebraic multigrid. SIAM J. Sci. Com-put.,2006,27:1261-1286
[34] M. Brezina, R. Falgout, S. Maclachlan, et al.. Adaptive smoothed aggregation (αSA) multigrid.SIAM Rev.,2005,47:317-346
[35] C. Brezinski. Ge′ne′ralisations de la transformation de Shanks. de la table de Pade′, et de1’-algorithme, Calcolo,1975,11:317-360
[36] C. Brezinski, M. Redivo Zaglia. The PageRank vector: properties, computation, approximation,and acceleration. SIAM J. Matrix Anal. Appl.,2006,28:551-575
[37] C. Brezinski, M. Redivo Zaglia. Rational extrapolation for the PageRank vector. Math. Comp.,2008,77:1585-1598
[38] W.L. Briggs, V.E. Henson, S.F. McCormick. A Multigrid Tutorial. SIAM, Philadelphia,2000
[39] A.Z. Broder, R. Lempel, F. Maghoul, et al.. Efficient PageRank approximation via graph aggre-gation. Inf Retrieval,2006,9:123-138
[40] P. Brown, H.F. Walker. GMRES on (nearly) singular systems. SIAM J. Matrix Anal. Appl.,1997,18:37-51
[41] C.G. Broyden. A comparison of three basic conjugate direction methods. Numer. Linear AlgebraAppl.,1996,3:473-489
[42] R. Bru, R. Canto′, J.J. Climent. On M-multisplittings of singular M-matrices and Markov chains.Numerical Lin. Alg. Appl.,1998,5:299-311
[43] R. Bru, F. Pedroche, D.B. Szyld. Additive Schwarz iterations for Markov chains. SIAM J. MatrixAnal. Appl.,2005,27:445-458
[44] P. Buchholz. A class of hierarchical queueing networks and their analysis. Queueing Systems,1994,15:59-80
[45] P. Buchholz. Multilevel solutions for structured Markov chains. SIAM J. Matrix Anal. Appl.,2000,22:342-357
[46] P. Buchholz, T. Dayar. On the convergence of a class of multilevel methods for large sparseMarkov chains. SIAM J. Matrix Anal. Appl.,2007,29:1025-1049
[47] J. Buzacott, J. Shanthikumar. Stochastic Models of Manufacturing Systems. Prentice-Hall Inter-national Editions, New Jersey,1993
[48] S. Cabay, L.W. Jackson. A polynomial extrapolation method for finding limits and antilimits ofvector sequences. SIAM J. Numer. Anal.,1976,13:734-752
[49] D. Calvetti, B. Lewis, L. Reichel. GMRES-type methods for inconsistent systems. Linear Alge-bra Appl.,2000,316:157-169
[50] Z.-H. Cao. A class of constraint preconditioners for nonsymmetric saddle point matrices. Numer.Math.,2006,103:47-61
[51] Z.-H. Cao. A note on costraint preconditioning for nonsymmetric indefinite matrices. SIAM J.Matrix Anal. Appl.,2002,24:121-125
[52] Z.-H. Cao. Constraint Schur complement preconditioners for nonsymmetric saddle point prob-lems, Appl. Numer. Math.,2009,59:151-169
[53] Z.H. Cao. Fast iterative solution of stabilized Navier-Stokes systems. Appl. Math. Comput.,2004,157:219-241
[54] Z.-H. Cao. Fast Uzawa algorithms for generalized saddle point problems. Appl. Numer. Math.,2003,46:157-171
[55] Z.H. Cao. Positive stable block triangular preconditioners for symmetric saddle point problems,Appl. Math. Comput.,2007,57:899-910
[56] R. Chan, W.K. Ching. Circulant preconditioners for stochastic automata networks. Numer.Math.,2000,87:35-57
[57] T.F. Chan, E. Gallopoulos, V. Simoncini, et al.. A quasi-minimal residual variant of theBiCGSTAB algorithm for nonsymmetric systems. SIAM J. Sci. Comput.,1994,15:338-347
[58] L.C. Chan, M.K. Ng, N.K. Tsing. Spectral analysis for HSS preconditioners. Numer. Math.Theor. Meth. Appl.,2008,1:57-77
[59] X. Chen. Global and superlinear convergence of inexact Uzawa methods for saddle point prob-lems with nondifferential mappings. SIAM J. Numer. Anal.,1998,35:1130-1148
[60] X. Chen. On preconditioned Uzawa methods and SOR methods for saddle point problems. J.Comput. Appl. Math.,1998,100:207-224
[61] W.K. Ching. Circulant preconditioners for failure prone manufacturing systems. Lin. Alg. Appl.,1997,266:161-180
[62] W.K. Ching. Iterative methods for queueing systems with batch arrivals and negative customers.BIT,2003,43:285-296
[63] W.K. Ching, R.H. Chan, X.Y. Zhou. Circulant preconditioners for Markov-Modulated poissonprocesses and their applications to manufacturing systems. SIAM J. Matrix Anal. Appl.,1997,18:464-491
[64] B.A. Copra. The best of the20th century: editors name top10algorithms. From SIAM News,2000,33:1-2
[65] V. Conrad, Y. Wallach. Alternating methods for sets of linear equations. Numerische Mathe-matik,1979,32:105-108
[66] E.J. Craig. The N-step iteration procedures. J. Math. Phys.,1955,34:64-73
[67] M.-R. Cui. A sufficient condition for the convergence of the inexact Uzawa algorithm for saddlepoint problems. J. Comput. Appl. Math.,2002,139:189-196
[68] M.-R. Cui. On the iterative algorithm for saddle point problems. Appl. Math. Comput.,2008,204:10-13
[69] M. T. Darvishi, P. Hessari. Symmetric SOR method for augmented systems. Appl. Math. Comp.,2006,183:409-415
[70] J.W. Demmel. Applied Numerical Linear Algebra. SIAM, Philadelphia,1997
[71] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Smoothed aggregation multigrid forMarkov chains. SIAM J. Sci. Comput.,2010,32:40-61
[72] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Algebraic multigrid for Markov chains.SIAM J. Sci. Comput.,2010,32:566-562
[73] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Multilevel adaptive aggregation forMarkov chains, with applications to web ranking. SIAM J. Sci. Comput.,2008,30:2235-2262
[74] H. De Sterck, K. Miller, T. Manteuffel et al.. Top-level acceleration of adaptive algebraic mul-tilevel methods for steady-state solution to Markov chains. Advances in Computational Mathe-matics,2011,35:375-403
[75] H. De Sterck, K. Miller, G. Sanders et al.. Recursively accelerated multilevel aggregation forMarkov chains. SIAM J. Sci. Comput.,2010,32:1652-1671
[76] H.S. Dollar. Constraint-style preconditioners for regularized saddle point problems. SIAM J.Matrix Anal. Appl.,2007,29:672-684
[77] H.S. Dollar. Extending constraint preconditioners for saddle point problems. Tech. Report. NA-05/02, Oxford University Computing Laboratory,2005
[78] H.S. Dollar, A. Wathen. Approximate factorization constraint preconditioners for saddle pointmatrices. SIAM J. Sci. Comput.,2006,27:1555-1572
[79] H.S. Dollar, A. Wathen. Incomplete factorization constraint preconditioners for saddle point ma-trices. Tech. Report. NA-04/01, Oxford University Computing Laboratory, Numerical AnalysisGroup,2004
[80] J. Dongarra and F. Sullivan. The top10algorithms in the20th century (guest editors’ introduc-tion). Comp. Sci. Eng.,2000,2:22-23
[81] J. Douglas. Jr., H.H. Rachford. Jr.. Alternating direction methods for three space variables. Nu-mer. Math.,1956,4:41-63
[82] X. Du, D.B. Szyld. Inexact GMRES for singular linear systems, BIT Numerical Mathematics,2008,48:511-531
[83] I.S. Duff, A.M. Erisman and J.K. Reid. Direct Methods for Sparse Matrices. Oxford UniversityPress, Oxford,1986
[84] P.R. Eddy. Extrapolating to the limit of a vector sequence. in: P. C. C. Wang (Ed.), InformationLinkage Between Applied Mathematics and Industry, Academic Press, New York,1979, pp.387-396
[85] S.C. Eisenstat. A note on the generalized conjugate gradient method. SIAM J. Number Anal.,1983,20:358-361
[86] S.C. Eisenstat, H.C. Elman and M.H. Schultz. Variational iterative methods for nonsymmetricsystems of linear equations. SIAM J. Numer. Anal.,1983,20:345-357
[87] H.C. Elman. Multigrid and Krylov subspace methods for the discrete Stokes equations. I. J.Numer. Methods Fluids,1996,227:1645-1661
[88] H.C. Elman. Preconditioning for the steady-state Navier-Stokes equations with low viscosity.SIAM J. Sci. Comput.,1999,20:1299-1316
[89] H.C. Elman, G.H. Golub. Inexact and preconditioned Uzawa algorithms for saddle point prob-lems. SIAM J. Numer. Anal.,1994,31:1645-1661
[90] H.C. Elman, D. Silvester. Fast nonsymmetric iterations and preconditioning for Navier-Stokesequations. SIAM J. Sci. Comput.,1996,17:33-46
[91] H.C. Elman, D. Silvester, A. Wathen. Iterative methods for problems in computational fluiddynamics, in Iterative Methods in Scientific Computing. R. Chan, T.F. Chan, G.H. Golub, eds.,Springer-Verlag, Singapore,1997,271-327
[92] D.J. Evans. Direct methods of solution of partial differential equations with periodic boundaryconditions. Math. Comput. Simulation,1979,21:270-275
[93] B. Fischer, A. Ramage, D. Silvester, et al.. Minimum residual methods for augmented systems.BIT,1998,38:527-543
[94] R. Fletcher. Conjugate gradient methods for indefinite systems, in: Numerical Analysis Dundee1975, ed. G. Watson, Lecture Notes in Mathematics506, Springer-Verlag, Berlin,1976, pp.73-89
[95] D.R. Fokkema, P. Sleijpen, H.A. van der Vorst. Generalized conjugate gradient squared. J. Com-put. App1. Math.,1996,71:125-146
[96] S. Frankel. Convergence rates of iterative treatments of partial differential equations. MTAC.1950,4:65-75
[97] R.W. Freund. A transpose-free quasi-minimal residual algorithm for non-Hermitian linear sys-tems. SIAM J. Sci. Comput.,1993,14:470-482
[98] R.W. Freund, M. Hochbruck. On the use of two QMR algorithms for solving singular systemsand applications in Markov chain modeling. Numerical Linear Algebraic Applications,1994,1:403-420
[99] R.W. Freund, N.M. Nachtigal. An implementation of the QMR method based on coupled two-term recurrences. SIAM J. Sci. Comput.,1994,15:313-337
[100] R.W. Freund, N.M. Nachtigal. QMR: a quasi-minimal residual method for non-Hermitian linearsystems. Numer. Math.,1991,60:315-339
[101] E. Gelenbe. Product-form queueing networks with negative and positive cunstomers. J. Appl.Probab.,1991,28:656-663
[102] P.E. Gill, W. Murray and M.H. Wright. Practical Optimization. Academic Press, London, UK,1981
[103] G.H. Golub, C. Greif. An Arnoldi-Type algorithm for computing PageRank. BIT,2006,46:759-771
[104] G.H. Golub, C. Greif, J.M. Varah. An algebraic analysis of a block diagonal preconditioner forsaddle point systems. SIAM J. Matrix Anal. Appl.,2006,27:779-792
[105] G.H. Golub, D. Vanderstraeten. On the preconditioning of matrices with a domain skew-symmetric component. Numer. Algorithm,2000,25:223-239
[106] G. H. Golub and C. F. Van Loan. Matrix Computations.3rd ed., Johns Hopkins UniversityPress, Baltimore, MD,1996
[107] G.H. Golub, A.J. Wathen. An iteration for indefinite systems and its application to the Navier-Stokes equations. SIAM J. Sci. Comput.,1998,19:530-539
[108] G.H. Golub, X. Wu, J.Y. Yuan. SOR-like methods for augmented systems. BIT,2001,41:71-85
[109] M.H. Gutknecht. Variants of BiCGSTAB for matrices with complex spectrum. SIAM J. Sci.Comput.,1993,14:1020-1033
[110] M. Haviv. Aggregation/Disaggregation methods for computing the stationary distribution of aMarkov chain. SIAM J. Numer. Anal.,1987,24:952-966
[111] K. Hayami. On the behaviour of the conjugate residual method for singular systems. In Pro-ceedings of Fifth China-Japan Seminar on Numerical Mathematics, Shanghai,2000. Shi Z-C,Kawarada H (eds). Science Press: Beijing/New York,2002, pp.117-126
[112] K. Hayami, M. Sugihara. A geometric view of Krylov subspace methods on singular systems,Numer. Linear Algebra Appl.,2011,18:449-469
[113] K. Hayami, M. Sugihara. On the convergence of the GCR(k) method for singular systems, NIITechnical Reports, NII-2004-009E, National Institute of Informatics, Tokyo,2004,1-24
[114] H. Heffes, D. Lucantoni. A Markov modulated characterization of packetized voice and datatraffic and related statistical multiplexer performance. IEEE J. Select. Areas Commun.,1986,4:856-868
[115] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Res.Natl. Bur. Standards Section B,1952,49:409-436
[116] R.A. Horn, C.R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge,1985
[117]胡家赣.线性代数方程组迭代解法.北京:科学出版社,1997
[118]黄廷祝,杨传胜.特殊矩阵分析及应用.北京:科学出版社,2007
[119]黄廷祝,钟守铭,李正良.矩阵理论.北京:高等教育出版社,2003
[120] I.C.F. Ipsen. A note on preconditioning nonsymmetric matrices. SIAM J. Sci. Comput.,2001,23:1050-1051
[121] I.C.F. Ipsen, C.D. Meyer. The idea behind Krylov methods. American Mathematical Monthly,1998,105:889-899
[122] C. Isensee, G. Horton. A multi-level method for the steady state solution of Markov chains. In:Simulation and Visualization2004, Magdeburg, Germany,2004
[123] C. Isensee, G. Horton. A multi-level method for the steady state solution of discrete-timeMarkov chains. In Proceedings of the2nd Balkan conference in informatics, pp.413-420, Ohrid,Macedonia, November2005
[124] K.C. Jea, D.M. Young. Generalized conjugate gradient acceleration of nonsymmetrizable itera-tive methods. Linear Algebra and its Applications,1980,34:159-194
[125] Y.-F. Jing, T.-Z. Huang, Y. Zhang, et al.. Lanczos-type variants of COCR method for complexnonsymmetric linear systems. J. Comput. Phys.,2009,228:6376-6394
[126] E.F. Kaasschieter. Preconditioned conjugate gradients for solving singular systems. J. Comput.Appl. Math.,1998,24:265-275
[127] W.J. Kammerer, M.Z. Nashed. On the convergence of the conjugate gradient method for singu-lar linear operator equations. SIAM J. Numer. Anal.,1972,9:165-181
[128] S.D. Kamvar, T.H. Haveliwala, G.H. Golub. Adaptive methods for the computation of PageR-ank. Stanford University Technical Report,2003
[129] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, et al.. Exploiting the block structure of the webfor computing PageRank. Stanford University Technical Report,1999
[130] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, et al.. Extrapolation methods for acceleratingPageRank computations. In Proceedings of the Twelfth International World Wide Web Confer-ence,2003
[131] L. Kaufman. Matrix methods for queueing problems. SIAM J. Sci. Stat. Comput.,1982,4:525-552
[132] D. Kay, D. Loghin, A. Wathen. A preconditioner for the steady-state Navier-Stokes equations.SIAM J. Sci. Comput.,2002,24:237-256
[133] C. Keller, N.I.M. Gould, A. Wathen. Constraint preconditioning for indefinite linear systems.SIAM J. Matrix Anal. Appl.,2000,21:1300-1317
[134] A. Klawonn. Block-triangular preconditioners for saddle point problems with a penalty term.SIAM J. Sci. Comput.,1998,19:172-184
[135] U.R. Krieger. On a two-level multigrid solution method for finite Markov chains. Linear Alge-bra Appl.,1995,223:415-438
[136] L.A. Krukier, L.G. Chikina, T.V. Belokon. Triangular skew-symmetric iterative solvers forstrongly nonsymmetric positive real linear system of equations. Applied Numerical Mathemat-ics,2002,41:89-105
[137] L.A. Krukier, T.S. Martynova, Z.-Z. Bai. Product-type skew-Hermitian triangular splitting iter-ation methods for strongly non-Hermitian positive definite linear systems. Journal of Computa-tional and Applied Mathematics,2009,232:3-16
[138] C. Lanczos. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur.Standards,1952,49:33-53
[139] A.N. Langville, C.D. Meyer. A survey of eigenvector methods for web information retrieval.SIAM Review,2005,47:135-161
[140] G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling.ASA-SIAM series on statistics and applied probability,1999
[141] J. Li, X. Kong. Optimum parameters of GSOR-like methods for solving the augmented linearsystems. Appl. Math. Comp.,2008,204:150-161
[142] C. Li, B. Li, D.J. Evans. A generalized successive overrelaxation method for least squaresproblems. BIT,1998,38:347-356
[143] Z. Li, C.J. Li, D.J. Evans. Chebyshev acceleration for the SOR-like method. Int. J. Comput.Math.,2005,82:583-593
[144] Z. Li, C.J. Li, D.J. Evans, et al.. Two-parameter GSOR method for the augmented system. Int.J. Comput. Math.,2005,82:1033-1042
[145] C. Li, Z. Li, X.H. Shao, et al.. Optimum parameter for the SOR-like method for augmentedsystems. Int. J. Comput. Math.,2004,81:749-763
[146] Y.Q. Lin, Y.M. Wei. A note on constraint preconditioners for nonsymmetric saddle point prob-lems. Numer. Linear Algebra Appl.,2000,14:659-664
[147] X.-F. Ling, X.-Z. Hu. On the iterative algorithm for large sparse saddle point problems. Appl.Math. Comput.,2006,178:372-379
[148]刘次华.随机过程及其应用.北京:高等教育出版社,2004
[149] D. Loghin, A. Wathen. Analysis of preconditioners for saddle point problems. SIAM J. Sci.Comput.,2004,25:2029-2049
[150] J.-F. Lu. A note on the iterative algorithm for large sparse saddle point problems. Appl. Math.Comput.,2007,188:189-193
[151] I. Marek, P. Mayer. Convergence theory of some classes of iterative aggregation/disaggregationmethods for computing stationary probability vector of stochastic matrices. Lin. Alg. Appl.,2003,363:177-200
[152] I. Marek, D.B. Szyld. Algebraic schwarz methods for the numerical solution of Markov chains.Linar Algebraic and its Applications,2004,386:67-81
[153] K. Meier-Hellstern. The analysis of a queue arising in overflow models. IEEE Trans. Commun.,1989,37:367-372
[154] M. Mesˇina. Convergence acceleration for the iterative solution of the equations X=AX+f.Comput. Methods Appl. Mech. Engrg.,1977,10:165-173
[155] G. Meurant. Computer Solution of Large Linear Systems. Elsevier, Amsterdam,1999
[156] H. Minc. Nonnegative Matrices. New York, John Wiley&Sons,1988
[157] A.C. Muresan, Y. Notay. Analysis of aggregation-based multigrid. SIAM J. Sci. Comput.,2008,30:1082-1103
[158] M.F. Murphy, G.H. Golub, A. Wathen. A note on preconditioning for indefinite linear systems.SIAM J. Sci. Comput.,2000,21:1969-1972
[159] M.F. Murphy, G.H. Golub, A. Wathen. A note on preconditioning for indefinite linear systems.Tech. Report, SCCM-99-03, Stanford University,1999
[160] S.G. Nash, A. Sofer. Preconditioned reduced matrices. SIAM J. Matrix Anal. Appl.,1996,17:47-68
[161] N.K. Nichols. On the convergence of two-stage iterative processes for solving linear equations.SIAM J. Numer. Anal.,1973,10:460-469
[162] M. Nikolova, M.K. Ng, S. Zhang, et al.. Efficient reconstruction of piecewise constant imagesusing nonsmooth nonconvex minimization. SIAM J. Img. Sci.,2008,1:2-25
[163] Y. Notay. Aggregation-based algebraic multilevel preconditioning. SIAM J. Matrix Anal. Appl.,2006,27:998-1018
[164] Y. Notay, P.S. Vassilevski. Recursive Krylov-based multigrid cycles. Numer. Linear AlgebraAppl.,2008,15:473-487
[165] L. Page, S. Brin, R. Motwani, et al.. The PageRank citation ranking: Bringing order to the web.Technical Report1999-0120, Computer Science Department, Stanford,1999
[166] C.C. Paige and M.A. Saunders. Solution of sparse indefinite systems of linear equations. SIAMJ. Numer. Anal.,1975,12:617-629
[167] A. Papoulis and S.U. Pillai. Probability, Random Variables and Stochastic Processes with ErrataSheet. McGraw Hill Higher Education,2002
[168] L.F. Pavarino. Preconditioned mixed spectral element methods for elasticity and Stokes prob-lems. SIAM J. Sci. Comput.,1998,19:1941-1957
[169] J. Peters, V. Reichelt, A. Reusken. Fast iterative solvers for discrete stokes equations. SIAM J.Sci. Comput.,2005,27:646-666
[170] B. Philippe, Y. Saad, W.J. Stewart. Numerical methods in Markov chain modeling. OperationsResearch,1992,40:1156-1179
[171] B. Plateau, K. Atif. Stochastic automata network for modelling parallell systems. IEEE Trans.software Eng.,1991,17:1093-1108
[172] L. Reichel, Q. Ye. Breakdown-free GMRES for singular systems. SIAM J. Matrix Anal. Appl.,2005,26:1001-1021
[173] S.M. Ross. Stochastic Processes. John Wiley&Sons New York,1983
[174] T. Rusten, R. Winther. A preconditioned iterative method for saddle point problems. SIAM J.Matrix Anal. Appl.,1992,13:887-904
[175] Y. Saad. Analysis of augmented krylov subspace techniques:[Technical Report UMSI-95/175]. Minnesota Supercomputing Institute,1995
[176] Y. Saad. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl.,1994,1:387-402
[177] Y. Saad. Iterative Methods for Sparse Linear Systems. Second ed., SIAM, Philadelphia, PA,2003
[178] Y. Saad. Krylov subspace methods for solving large unsymmetric linear systems. Math. Com-put.,1981,37:105-126
[179] Y. Saad. Preconditioned Krylov subspace methods for the numerical solution of Markov chains.In W. J. Stewart, editor, Computations with Markov chains, pp.49-64, Kluwer academic pub-lishers,1995
[180] Y. Saad, M.H. Schultz. GMRES: a generalized minimal residual algorithm for solving a non-symmetric linear system. SIAM J. Sci. Statist. Comput.,1986,7:856-869
[181] Y. Saad and H. A. van der Vorst. Iterative solution of linear systems in the20th century. J.Comput. Appl. Math.,2000,123:1-33
[182] Y. Saad, K. Wu. DQGMRES: A direct quasi-minima l residual algorithm based on incompleteorthogonalization:[Technical Report UMSI-93/131]. Minnesota Supercomputing Institute, Min-neapolis, MN,1993
[183] G.H. Santos, B.P.B. Silva, J.Y. Yuan. Block SOR methods for rank deficient least squares prob-lems. J. Comput. Appl. Math.,1998,100:1-9
[184] G.H. Santos, J.Y. Yuan. Preconditioned conjugate gradient methods for rank deficient leastsquares problems. Int. J. Comput. Math.,1999,75:509-518
[185] O. Schneider. Krylov subspace methods and their generalizations for solving singular operatorequations with applications to continuous time Markov chains. Doctoral Dissertation, Fakulta¨tfu¨r Mathematik und Informatik, der Technischen Universita¨t Bergakademie Freiberg, November2005
[186] W. Schonauer. Scientific Computing on Vector Computers. North-Holland. NY,1987
[187] P. J. Schweitzer, K. W. Kindle. An iterative aggregation-disaggregation algorithm for solvinglinear equations. Appl. Math. Comput.,1986,18:313-354
[188] E. Seneta. Non-negative Matrices and Markov Chains. Springer Verlag,2006
[189] X.H. Shao, Z. Li, C.J. Li. Modified SOR-like method for the augmented system. Int. J. Comput.Math.,2007,84:1653-1662
[190] A. Sidi. DGMRES: a GMRES-type algorithm for Drazin-inverse solution of singular nonsym-metric linear systems. Linear Algebra Appl.,2001,335:189-204
[191] A. Sidi. Efficient implementation of minimal polynomial and reduced rank extrapolation meth-ods. J. Comput. Appl. Math.,1991,36:305-337
[192] A. Sidi. Vector extrapolation methods with applications to solution of large systems of equationsand to PageRank computations. Computers and Math. Appl.,2008,56:1-24
[193] C. Siefert, E.D. Sturler. Preconditioners for generalized saddle point problems. SIAM J. Numer.Anal.,2006,44:1275-1296
[194] V. Simoncini. Block triangular preconditioners for symmetric saddle point problems. Appl.Numer. Math.,2004,49:63-80
[195] V. Simoncini, M. Benzi. Spectral properties of the Hermitian and skew-Hermitian splitting pre-conditioner for saddle point problmes. SIAM J. Matrix Anal. Appl.,2004,26:377-389
[196] G.L.G. Sleijpen and D.R. Fokkema. BiCGSTAB(l) for linear equations involving unsymmetricmatrices with complex spectrum. Electronic Trans. Numer. Analysis,1993,1:11-32
[197] D.A. Smith, W.F. Ford, A. Sidi. Extrapolation methods for vector sequence. SIAM Review,1987,29:199-233
[198] L. Smoch. Some results about GMRES in the singular case. Numer. Algo.,199922:193-212
[199] T. Sogabe. Extensions of the conjugate residual method:[Ph.D. Thesis], Tokyo: University ofTokyo,2006
[200] T. Sogabe, M. Sugihara, S.-L. Zhang. An extension of the conjugate residual method to non-symmetric linear systems. J. Comput. Appl. Math.,2009,266:103-113
[201] P. Sonneveld. CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci.Statist. Comput.,1989,10:36-52
[202] W.J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton UniversityPress NJ,1994
[203] W.J. Stewart. Probability, Markov Chains, Queues, and Simulation. Princeton Univ Pr,2009
[204] W.J. Stewart, K. Atif, B. Plateau. The numerical solution of stochastic automata networks. Euro.J. Operat. Res.,1995,86:503-525
[205] W. J. Stewart, W. L. Cao. Iterative aggregation/disaggregation techniques for nearly uncoupledMarkov chains. J. ACM.,1985,32:702-719
[206] E. Stiefel. Relaxationsmethoden bester Strategie zur Lo¨ung linearer Gleichungssysteme. Com-ment. Math. Helv.,1955,29:157-179
[207] K. Stuben. A review of algebraic multigrid. J. Comput. Appl. Math.,2001,124:281-309
[208] E. Sturler. Nested krylov methods based on GCR. J. of computional and applied mathematics,1996
[209] E.D. Sturler, J. Liesen. Block-diagonal and constraint preconditioners for nonsymmetric indef-inite linear systems. Part I: theory. SIAM J. Sci. Comput.,2005,26:1598-1619
[210] D.B. Szyld. Equivalence of convergence conditions for itrative methods for singular quations.Numer. Linear Algebra Appl.,1994,1:151-154
[211] K. Tanabe. The conjugate gradient method for computing all the extremal stationary probabilityvectors of a stochastic matrix. Annals of the Institute of Statistical Mathematics Part B,1985,37:173-187
[212] W.F. Tinney, J.W. Walker. Direct solution of sparse network equations by optimally orderedtriangular factorization. Proc. of IEEE,1967,55:1801-1809
[213] H.A. van der Vorst. BiCGSTAB: a fast and smoothly converging variant of BiCG for the solutionof nonsymmetric linear systems. SIAM J. Sci. Statist. Comput.,1992,13:631-644
[214] R.S. Varga. Matrix Iterative Analysis. Springer Verlag,2000
[215] P. Vaneˇk, J. Mandel and M. Brezina. Algebraic multigrid by smoothed aggregation for secondand fourth order elliptic problems. Computing,1996,56:179-196
[216] P. Vaneˇk, J. Mandel and M. Brezina. Algebraic multigrid on unstructured meshes. Technical,Report X, Center for Computational Mathematics, Mathematics Department,1994
[217] E. Virnik. An algebraic multigrid preconditioner for a class of singular M-matrices. SIAM J.Sci. Comput.,2007,29:1982-1991
[218] L. Wang, Z.-Z. Bai. Skew-Hermitian triangular splitting iteration methods for non-Hermitianpositive definite linear systems of strong skew-Hermitian parts. BIT Numerical Mathematics,2004,44:363-386
[219] A. Wathen and D. Silvester. Fast iterative solution of stabilized stokes systems part I: Usingsimple diagonal preconditioners. SIAM J. Numer. Anal.,1993,30:630-649
[220] A. Wathen and D. Silvester. Fast iterative solution of stabilized stokes systems Part II: Usinggeneral block diagonal preconditioners. SIAM J. Numer. Anal.,1994,31:1352-1367
[221] Y. Wei, H. Wu. Convergence properties of Krylov subspace methods for singular linear systemswith arbitrary index. J. Comput. Appl. Math.,2000,114:305-318
[222] C. Wen, T.-Z. Huang, C. Wang. Triangular and skew-symmetric splitting methods for numericalsolutions of Markov chains. Computers and Mathematics with Applications,2011,62:4039-4048
[223] C. Wen, T.-Z. Huang, D.-A. Wu, et al.. The finest level acceleration of multilevel aggregationfor Markov chains. INT J. Numer. Anal. Mod. Series B,2011,2:27-41
[224] O.B. Widlund. A Lanczos method for a class of nonsymmetric systems of linear equations.SIAM J. Numer. Anal.,1978,15:801-812
[225] G. Wittum. Multigrid methods for Stokes and Navier-Stokes equations. Transformingsmoothers: Algorithms and numerical results, Numer. Math.,1989,54:543-563
[226] S. Wright. Stability of augmented system factorizations in interior-point methods. SIAM J.Matrix Anal. Appl.,1997,18:191-222
[227]吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算.湖南:湖南科学技术出版社,2004
[228] S.-L. Wu, T.-Z. Huang, X.-L. Zhao. A modified SSOR iterative method for augmented systems.J. Comp. Appl. Math.,2009,228:424-433
[229] G. Wu, Y. Wei. An Arnoldi-Extrapolation algorithm for computing PageRank. J. Comput. Appl.Math.,2010,234:3196-3212
[230] P. Wynn. Accelerated techniques for iterated vector and matrix problems. Math. Comp.,1962,16:301-322
[231] P. Wynn. On a device for computing em(Sn) transformation. Math. Tab. Other Aids Comput.,1956,10:91-96
[232]徐树方.矩阵计算的理论与方法.北京:北京大学出版社,1995
[233] D.M. Young. Iterative methods for solving partial differential equations of elliptic type:[Ph.D.Thesis], Cambridge, MA, USA: Harvard University,1950
[234] D.M. Young. Iterative Solution of Large Linear Systems. Academic Press, New York,1971
[235] H. Young, B. Byung, K. Chong. Performance analysis of leaky-bucket bandwidth enforcementstrategy for bursty traffics in an ATM network. Comput. Net. ISDN Syst.,1992,25:295-303
[236] J.Y. Yuan. Iterative methods for generalized least squares problems. Ph.D. Thesis, IMPA, Riode Janeiro, Brazil,1993
[237] J.Y. Yuan. Numerical methods for generalized least squares problems. J. Comput. Appl. Math.,1996,66:571-584
[238] J.Y. Yuan, A.N. Iusem. Preconditioned conjugate gradient methods for generalized least squaresproblems. J. Comput. Appl. Math.,1996,71:287-297
[239] W.-O. Yuen, W.K. Ching, M.K. Ng. A hybrid algorithm for queueing systems. Calcolo,2004,41:139-151
[240] S.-Z. Zhang. GPBiCG: generalized product-type methods based on BiCG for solving nonsym-metric linear systems. SIAM J. Sci. Comput.,1997,18:537-551
[241] G.F. Zhang, Q.H. Lu. On generalized symmetric SOR method for augmented systems. J. Comp.Appl. Math.,2008,219:51-58
[242] S.-L. Zhang, Y. Oyanagi, M. Sugihara. Necessary and sufficient conditions for the convergenceof Orthomin(k) on inconsistent linear systems. Numer. Math.,2000,87:391-405
[243] B. Zheng, K. Wang, Y.J. Wu. SSOR-like methods for saddle point problems. Int. J. ComputerMath.,2009,86:1405-1423
[2] W.E. Arnoldi. The principle of minimized iteration in the solution of the matrix eigenvalue prob-lem. Quart. Appl. Math.,1951,9:17-29
[3] K. Arrow, L. Hurwica, H. Uzawa. Studies in Nonlinear Programming. Stanford University Press,Stanford, CA,1958
[4] O. Axelsson. A class of iterative methods for finite element equations. Comm. Meth. Appl.,1976,9:123-137
[5] O. Axelsson. Iterative Solution Methods. Cambridge University Press, New York,1994
[6] Z.-Z. Bai. Structured preconditioners for nonsingular matrices of block two-by-two structures.Math. Comp.,2006,75:791-815
[7] Z.-Z. Bai, G.H. Golub, L.-Z. Lu, et al.. Block triangular and skew-Hermitian splitting methodsfor positive-definite linear systems. SIAM J. Sci. Comput.,2005,20:844-863
[8] Z.-Z. Bai, G.H. Golub, J.Y. Pan. Preconditioned Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive semidefinite linear systems. Numer. Math.,2004,98:1-32
[10] Z.-Z. Bai, G.H. Golub, M.K. Ng. Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix Anal. Appl.,2003,24:603-626
[10] Z.-Z. Bai, G.H. Golub, M.K. Ng. On successive-overrelaxation acceleration of the Hermitianand skew-Hermitian splitting iterations. Numerical Linear Algebra with Applications,2007,14:319-335
[11] Z.-Z. Bai, M.K. Ng, Z.-Q. Wang. Constraint preconditioners for symmetric indefinite matrices.SIAM J. Matrix Anal. Appl.,2009,31:410-433
[12] G. Bao, W.-W. Sun. A fast algorithm for the electromagnetic scattering from a large cavity. SIAMJ. Sci. Comput.,2005,27:553-574
[13] G. Barker, R.J. Plemmons. Convergent iterations for computing stationary distributions ofMarkov chains. SIAM J. Alg. Disc. Meth.,1986,7:390-398
[14] R. Barrett. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods.Society for Industrial Mathematics,1994
[15] M. Benzi. A generalization of the Hermitian and skew-Hermitian splitting iteration. SIAM J.Matrix Anal. Appl.,2009,31:360-374
[16] M. Benzi. Preconditioning techniques for large linear systems: a survey. J. Comput. Phys.,2002,182:418-477
[17] M. Benzi, G.H. Golub. A preconditioner for generalized saddle point problems. SIAM J. MatrixAnal. Appl.,2004,26:20-41
[18] M. Benzi, G.H. Golub and J. Liesen. Numerical solution of saddle point problems. Acta numer-ica.2005,14:1-137
[19] M. Benzi, V. Kuhlemann. Restricted additive methods for Markov chains. Numer. Linear AlgebraAppl.,2011,18:1011-1029
[20] M. Benzi, C.D. Meyer, M. Tuma. A sparse approximate inverse preconditioner for the conjugategradient method. SIAM J. Sci. Comput.,1996,17:1135-1149
[21] M. Benzi, D.B. Szyld. Existence and uniqueness of splittings for stationary iterative methodswith applications to alternating methods. Numer. Math.,1997,76:309-321
[22] M. Benzi, B. Uc ar. Block triangular preconditioners for M-matrices and Markov chains. ETNA,2007,26:209-227
[23] M. Benzi, B. Uc ar. Product preconditioning for Markov chain problems. in Proceedings of the2006Markov Anniversary Meeting, A. N. Langville and W. J. Stewart, eds., Raleigh, NC,2006,(Charleston, SC), Boson Books,239-256
[24] A. Berman, R.J. Plemmons. Nonnegative Matrices in the Mathematical Sciences. AcademicPress, New York,1979
[25] D.A. Bini, G. Latouche, B. Meini. Numerical Methods for Structured Markov Chains. OxfordUniversity Press, London,2005
[26] A. Bjorck. Numerical stability of methods for solving augmented systems. In Proceedings fromRecent Developments in Optimization Theory and Nonlinear Analysis, Jerusalem,1995, Y. Cen-sor and S. Reich, eds., Contemp. Math.,204, Amer. Math. Soc., Providence, RI,1997,51-60
[27] S. Borovac. A graph based approach to the convergence of one level schwarz iterations for sin-gular M-matrices and Markov chains. SIAM J. Matrix Anal. Appl.,2008,30:1371-1391
[28] J.H. Bramble, J.E. Pasciak. A preconditioning technique for indefinite systems resulting frommixed approximations of elliptic problems. Math. Comput.,1988,50:1-17
[29] J.H. Bramble, J.E. Pasciak. Iterative technique for time dependent Stokes problems. Comput.Math. Appl.,1997,33:13-30
[30] J. Bramble, J. Pasciak, A. Vassilev. Analysis of the inexact Uzawa algorithm for saddle pointproblems. SIAM J. Numer. Anal.,1997,34:1072-1092
[31] J. Bramble, J. Pasciak, A. Vassilev. Uzawa type algorithms for nonsymmetric saddle point prob-lems. Math. Comput.,2000,69:667-689
[32] A. Brandt, S. McCormick and J. Ruge. Algebraic Multigrid (AMG) for Sparse Matrix Equations.D.J Evans (Ed.), Sparsity and its Applications,1984
[33] M. Brezina, R. Falgout, S. Maclachlan, et al.. Adaptive algebraic multigrid. SIAM J. Sci. Com-put.,2006,27:1261-1286
[34] M. Brezina, R. Falgout, S. Maclachlan, et al.. Adaptive smoothed aggregation (αSA) multigrid.SIAM Rev.,2005,47:317-346
[35] C. Brezinski. Ge′ne′ralisations de la transformation de Shanks. de la table de Pade′, et de1’-algorithme, Calcolo,1975,11:317-360
[36] C. Brezinski, M. Redivo Zaglia. The PageRank vector: properties, computation, approximation,and acceleration. SIAM J. Matrix Anal. Appl.,2006,28:551-575
[37] C. Brezinski, M. Redivo Zaglia. Rational extrapolation for the PageRank vector. Math. Comp.,2008,77:1585-1598
[38] W.L. Briggs, V.E. Henson, S.F. McCormick. A Multigrid Tutorial. SIAM, Philadelphia,2000
[39] A.Z. Broder, R. Lempel, F. Maghoul, et al.. Efficient PageRank approximation via graph aggre-gation. Inf Retrieval,2006,9:123-138
[40] P. Brown, H.F. Walker. GMRES on (nearly) singular systems. SIAM J. Matrix Anal. Appl.,1997,18:37-51
[41] C.G. Broyden. A comparison of three basic conjugate direction methods. Numer. Linear AlgebraAppl.,1996,3:473-489
[42] R. Bru, R. Canto′, J.J. Climent. On M-multisplittings of singular M-matrices and Markov chains.Numerical Lin. Alg. Appl.,1998,5:299-311
[43] R. Bru, F. Pedroche, D.B. Szyld. Additive Schwarz iterations for Markov chains. SIAM J. MatrixAnal. Appl.,2005,27:445-458
[44] P. Buchholz. A class of hierarchical queueing networks and their analysis. Queueing Systems,1994,15:59-80
[45] P. Buchholz. Multilevel solutions for structured Markov chains. SIAM J. Matrix Anal. Appl.,2000,22:342-357
[46] P. Buchholz, T. Dayar. On the convergence of a class of multilevel methods for large sparseMarkov chains. SIAM J. Matrix Anal. Appl.,2007,29:1025-1049
[47] J. Buzacott, J. Shanthikumar. Stochastic Models of Manufacturing Systems. Prentice-Hall Inter-national Editions, New Jersey,1993
[48] S. Cabay, L.W. Jackson. A polynomial extrapolation method for finding limits and antilimits ofvector sequences. SIAM J. Numer. Anal.,1976,13:734-752
[49] D. Calvetti, B. Lewis, L. Reichel. GMRES-type methods for inconsistent systems. Linear Alge-bra Appl.,2000,316:157-169
[50] Z.-H. Cao. A class of constraint preconditioners for nonsymmetric saddle point matrices. Numer.Math.,2006,103:47-61
[51] Z.-H. Cao. A note on costraint preconditioning for nonsymmetric indefinite matrices. SIAM J.Matrix Anal. Appl.,2002,24:121-125
[52] Z.-H. Cao. Constraint Schur complement preconditioners for nonsymmetric saddle point prob-lems, Appl. Numer. Math.,2009,59:151-169
[53] Z.H. Cao. Fast iterative solution of stabilized Navier-Stokes systems. Appl. Math. Comput.,2004,157:219-241
[54] Z.-H. Cao. Fast Uzawa algorithms for generalized saddle point problems. Appl. Numer. Math.,2003,46:157-171
[55] Z.H. Cao. Positive stable block triangular preconditioners for symmetric saddle point problems,Appl. Math. Comput.,2007,57:899-910
[56] R. Chan, W.K. Ching. Circulant preconditioners for stochastic automata networks. Numer.Math.,2000,87:35-57
[57] T.F. Chan, E. Gallopoulos, V. Simoncini, et al.. A quasi-minimal residual variant of theBiCGSTAB algorithm for nonsymmetric systems. SIAM J. Sci. Comput.,1994,15:338-347
[58] L.C. Chan, M.K. Ng, N.K. Tsing. Spectral analysis for HSS preconditioners. Numer. Math.Theor. Meth. Appl.,2008,1:57-77
[59] X. Chen. Global and superlinear convergence of inexact Uzawa methods for saddle point prob-lems with nondifferential mappings. SIAM J. Numer. Anal.,1998,35:1130-1148
[60] X. Chen. On preconditioned Uzawa methods and SOR methods for saddle point problems. J.Comput. Appl. Math.,1998,100:207-224
[61] W.K. Ching. Circulant preconditioners for failure prone manufacturing systems. Lin. Alg. Appl.,1997,266:161-180
[62] W.K. Ching. Iterative methods for queueing systems with batch arrivals and negative customers.BIT,2003,43:285-296
[63] W.K. Ching, R.H. Chan, X.Y. Zhou. Circulant preconditioners for Markov-Modulated poissonprocesses and their applications to manufacturing systems. SIAM J. Matrix Anal. Appl.,1997,18:464-491
[64] B.A. Copra. The best of the20th century: editors name top10algorithms. From SIAM News,2000,33:1-2
[65] V. Conrad, Y. Wallach. Alternating methods for sets of linear equations. Numerische Mathe-matik,1979,32:105-108
[66] E.J. Craig. The N-step iteration procedures. J. Math. Phys.,1955,34:64-73
[67] M.-R. Cui. A sufficient condition for the convergence of the inexact Uzawa algorithm for saddlepoint problems. J. Comput. Appl. Math.,2002,139:189-196
[68] M.-R. Cui. On the iterative algorithm for saddle point problems. Appl. Math. Comput.,2008,204:10-13
[69] M. T. Darvishi, P. Hessari. Symmetric SOR method for augmented systems. Appl. Math. Comp.,2006,183:409-415
[70] J.W. Demmel. Applied Numerical Linear Algebra. SIAM, Philadelphia,1997
[71] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Smoothed aggregation multigrid forMarkov chains. SIAM J. Sci. Comput.,2010,32:40-61
[72] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Algebraic multigrid for Markov chains.SIAM J. Sci. Comput.,2010,32:566-562
[73] H. De Sterck, T.A. Manteuffel, S.F. McCormick, et al.. Multilevel adaptive aggregation forMarkov chains, with applications to web ranking. SIAM J. Sci. Comput.,2008,30:2235-2262
[74] H. De Sterck, K. Miller, T. Manteuffel et al.. Top-level acceleration of adaptive algebraic mul-tilevel methods for steady-state solution to Markov chains. Advances in Computational Mathe-matics,2011,35:375-403
[75] H. De Sterck, K. Miller, G. Sanders et al.. Recursively accelerated multilevel aggregation forMarkov chains. SIAM J. Sci. Comput.,2010,32:1652-1671
[76] H.S. Dollar. Constraint-style preconditioners for regularized saddle point problems. SIAM J.Matrix Anal. Appl.,2007,29:672-684
[77] H.S. Dollar. Extending constraint preconditioners for saddle point problems. Tech. Report. NA-05/02, Oxford University Computing Laboratory,2005
[78] H.S. Dollar, A. Wathen. Approximate factorization constraint preconditioners for saddle pointmatrices. SIAM J. Sci. Comput.,2006,27:1555-1572
[79] H.S. Dollar, A. Wathen. Incomplete factorization constraint preconditioners for saddle point ma-trices. Tech. Report. NA-04/01, Oxford University Computing Laboratory, Numerical AnalysisGroup,2004
[80] J. Dongarra and F. Sullivan. The top10algorithms in the20th century (guest editors’ introduc-tion). Comp. Sci. Eng.,2000,2:22-23
[81] J. Douglas. Jr., H.H. Rachford. Jr.. Alternating direction methods for three space variables. Nu-mer. Math.,1956,4:41-63
[82] X. Du, D.B. Szyld. Inexact GMRES for singular linear systems, BIT Numerical Mathematics,2008,48:511-531
[83] I.S. Duff, A.M. Erisman and J.K. Reid. Direct Methods for Sparse Matrices. Oxford UniversityPress, Oxford,1986
[84] P.R. Eddy. Extrapolating to the limit of a vector sequence. in: P. C. C. Wang (Ed.), InformationLinkage Between Applied Mathematics and Industry, Academic Press, New York,1979, pp.387-396
[85] S.C. Eisenstat. A note on the generalized conjugate gradient method. SIAM J. Number Anal.,1983,20:358-361
[86] S.C. Eisenstat, H.C. Elman and M.H. Schultz. Variational iterative methods for nonsymmetricsystems of linear equations. SIAM J. Numer. Anal.,1983,20:345-357
[87] H.C. Elman. Multigrid and Krylov subspace methods for the discrete Stokes equations. I. J.Numer. Methods Fluids,1996,227:1645-1661
[88] H.C. Elman. Preconditioning for the steady-state Navier-Stokes equations with low viscosity.SIAM J. Sci. Comput.,1999,20:1299-1316
[89] H.C. Elman, G.H. Golub. Inexact and preconditioned Uzawa algorithms for saddle point prob-lems. SIAM J. Numer. Anal.,1994,31:1645-1661
[90] H.C. Elman, D. Silvester. Fast nonsymmetric iterations and preconditioning for Navier-Stokesequations. SIAM J. Sci. Comput.,1996,17:33-46
[91] H.C. Elman, D. Silvester, A. Wathen. Iterative methods for problems in computational fluiddynamics, in Iterative Methods in Scientific Computing. R. Chan, T.F. Chan, G.H. Golub, eds.,Springer-Verlag, Singapore,1997,271-327
[92] D.J. Evans. Direct methods of solution of partial differential equations with periodic boundaryconditions. Math. Comput. Simulation,1979,21:270-275
[93] B. Fischer, A. Ramage, D. Silvester, et al.. Minimum residual methods for augmented systems.BIT,1998,38:527-543
[94] R. Fletcher. Conjugate gradient methods for indefinite systems, in: Numerical Analysis Dundee1975, ed. G. Watson, Lecture Notes in Mathematics506, Springer-Verlag, Berlin,1976, pp.73-89
[95] D.R. Fokkema, P. Sleijpen, H.A. van der Vorst. Generalized conjugate gradient squared. J. Com-put. App1. Math.,1996,71:125-146
[96] S. Frankel. Convergence rates of iterative treatments of partial differential equations. MTAC.1950,4:65-75
[97] R.W. Freund. A transpose-free quasi-minimal residual algorithm for non-Hermitian linear sys-tems. SIAM J. Sci. Comput.,1993,14:470-482
[98] R.W. Freund, M. Hochbruck. On the use of two QMR algorithms for solving singular systemsand applications in Markov chain modeling. Numerical Linear Algebraic Applications,1994,1:403-420
[99] R.W. Freund, N.M. Nachtigal. An implementation of the QMR method based on coupled two-term recurrences. SIAM J. Sci. Comput.,1994,15:313-337
[100] R.W. Freund, N.M. Nachtigal. QMR: a quasi-minimal residual method for non-Hermitian linearsystems. Numer. Math.,1991,60:315-339
[101] E. Gelenbe. Product-form queueing networks with negative and positive cunstomers. J. Appl.Probab.,1991,28:656-663
[102] P.E. Gill, W. Murray and M.H. Wright. Practical Optimization. Academic Press, London, UK,1981
[103] G.H. Golub, C. Greif. An Arnoldi-Type algorithm for computing PageRank. BIT,2006,46:759-771
[104] G.H. Golub, C. Greif, J.M. Varah. An algebraic analysis of a block diagonal preconditioner forsaddle point systems. SIAM J. Matrix Anal. Appl.,2006,27:779-792
[105] G.H. Golub, D. Vanderstraeten. On the preconditioning of matrices with a domain skew-symmetric component. Numer. Algorithm,2000,25:223-239
[106] G. H. Golub and C. F. Van Loan. Matrix Computations.3rd ed., Johns Hopkins UniversityPress, Baltimore, MD,1996
[107] G.H. Golub, A.J. Wathen. An iteration for indefinite systems and its application to the Navier-Stokes equations. SIAM J. Sci. Comput.,1998,19:530-539
[108] G.H. Golub, X. Wu, J.Y. Yuan. SOR-like methods for augmented systems. BIT,2001,41:71-85
[109] M.H. Gutknecht. Variants of BiCGSTAB for matrices with complex spectrum. SIAM J. Sci.Comput.,1993,14:1020-1033
[110] M. Haviv. Aggregation/Disaggregation methods for computing the stationary distribution of aMarkov chain. SIAM J. Numer. Anal.,1987,24:952-966
[111] K. Hayami. On the behaviour of the conjugate residual method for singular systems. In Pro-ceedings of Fifth China-Japan Seminar on Numerical Mathematics, Shanghai,2000. Shi Z-C,Kawarada H (eds). Science Press: Beijing/New York,2002, pp.117-126
[112] K. Hayami, M. Sugihara. A geometric view of Krylov subspace methods on singular systems,Numer. Linear Algebra Appl.,2011,18:449-469
[113] K. Hayami, M. Sugihara. On the convergence of the GCR(k) method for singular systems, NIITechnical Reports, NII-2004-009E, National Institute of Informatics, Tokyo,2004,1-24
[114] H. Heffes, D. Lucantoni. A Markov modulated characterization of packetized voice and datatraffic and related statistical multiplexer performance. IEEE J. Select. Areas Commun.,1986,4:856-868
[115] M.R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. J. Res.Natl. Bur. Standards Section B,1952,49:409-436
[116] R.A. Horn, C.R. Johnson. Matrix Analysis. Cambridge University Press, Cambridge,1985
[117]胡家赣.线性代数方程组迭代解法.北京:科学出版社,1997
[118]黄廷祝,杨传胜.特殊矩阵分析及应用.北京:科学出版社,2007
[119]黄廷祝,钟守铭,李正良.矩阵理论.北京:高等教育出版社,2003
[120] I.C.F. Ipsen. A note on preconditioning nonsymmetric matrices. SIAM J. Sci. Comput.,2001,23:1050-1051
[121] I.C.F. Ipsen, C.D. Meyer. The idea behind Krylov methods. American Mathematical Monthly,1998,105:889-899
[122] C. Isensee, G. Horton. A multi-level method for the steady state solution of Markov chains. In:Simulation and Visualization2004, Magdeburg, Germany,2004
[123] C. Isensee, G. Horton. A multi-level method for the steady state solution of discrete-timeMarkov chains. In Proceedings of the2nd Balkan conference in informatics, pp.413-420, Ohrid,Macedonia, November2005
[124] K.C. Jea, D.M. Young. Generalized conjugate gradient acceleration of nonsymmetrizable itera-tive methods. Linear Algebra and its Applications,1980,34:159-194
[125] Y.-F. Jing, T.-Z. Huang, Y. Zhang, et al.. Lanczos-type variants of COCR method for complexnonsymmetric linear systems. J. Comput. Phys.,2009,228:6376-6394
[126] E.F. Kaasschieter. Preconditioned conjugate gradients for solving singular systems. J. Comput.Appl. Math.,1998,24:265-275
[127] W.J. Kammerer, M.Z. Nashed. On the convergence of the conjugate gradient method for singu-lar linear operator equations. SIAM J. Numer. Anal.,1972,9:165-181
[128] S.D. Kamvar, T.H. Haveliwala, G.H. Golub. Adaptive methods for the computation of PageR-ank. Stanford University Technical Report,2003
[129] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, et al.. Exploiting the block structure of the webfor computing PageRank. Stanford University Technical Report,1999
[130] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, et al.. Extrapolation methods for acceleratingPageRank computations. In Proceedings of the Twelfth International World Wide Web Confer-ence,2003
[131] L. Kaufman. Matrix methods for queueing problems. SIAM J. Sci. Stat. Comput.,1982,4:525-552
[132] D. Kay, D. Loghin, A. Wathen. A preconditioner for the steady-state Navier-Stokes equations.SIAM J. Sci. Comput.,2002,24:237-256
[133] C. Keller, N.I.M. Gould, A. Wathen. Constraint preconditioning for indefinite linear systems.SIAM J. Matrix Anal. Appl.,2000,21:1300-1317
[134] A. Klawonn. Block-triangular preconditioners for saddle point problems with a penalty term.SIAM J. Sci. Comput.,1998,19:172-184
[135] U.R. Krieger. On a two-level multigrid solution method for finite Markov chains. Linear Alge-bra Appl.,1995,223:415-438
[136] L.A. Krukier, L.G. Chikina, T.V. Belokon. Triangular skew-symmetric iterative solvers forstrongly nonsymmetric positive real linear system of equations. Applied Numerical Mathemat-ics,2002,41:89-105
[137] L.A. Krukier, T.S. Martynova, Z.-Z. Bai. Product-type skew-Hermitian triangular splitting iter-ation methods for strongly non-Hermitian positive definite linear systems. Journal of Computa-tional and Applied Mathematics,2009,232:3-16
[138] C. Lanczos. Solution of systems of linear equations by minimized iterations. J. Res. Nat. Bur.Standards,1952,49:33-53
[139] A.N. Langville, C.D. Meyer. A survey of eigenvector methods for web information retrieval.SIAM Review,2005,47:135-161
[140] G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling.ASA-SIAM series on statistics and applied probability,1999
[141] J. Li, X. Kong. Optimum parameters of GSOR-like methods for solving the augmented linearsystems. Appl. Math. Comp.,2008,204:150-161
[142] C. Li, B. Li, D.J. Evans. A generalized successive overrelaxation method for least squaresproblems. BIT,1998,38:347-356
[143] Z. Li, C.J. Li, D.J. Evans. Chebyshev acceleration for the SOR-like method. Int. J. Comput.Math.,2005,82:583-593
[144] Z. Li, C.J. Li, D.J. Evans, et al.. Two-parameter GSOR method for the augmented system. Int.J. Comput. Math.,2005,82:1033-1042
[145] C. Li, Z. Li, X.H. Shao, et al.. Optimum parameter for the SOR-like method for augmentedsystems. Int. J. Comput. Math.,2004,81:749-763
[146] Y.Q. Lin, Y.M. Wei. A note on constraint preconditioners for nonsymmetric saddle point prob-lems. Numer. Linear Algebra Appl.,2000,14:659-664
[147] X.-F. Ling, X.-Z. Hu. On the iterative algorithm for large sparse saddle point problems. Appl.Math. Comput.,2006,178:372-379
[148]刘次华.随机过程及其应用.北京:高等教育出版社,2004
[149] D. Loghin, A. Wathen. Analysis of preconditioners for saddle point problems. SIAM J. Sci.Comput.,2004,25:2029-2049
[150] J.-F. Lu. A note on the iterative algorithm for large sparse saddle point problems. Appl. Math.Comput.,2007,188:189-193
[151] I. Marek, P. Mayer. Convergence theory of some classes of iterative aggregation/disaggregationmethods for computing stationary probability vector of stochastic matrices. Lin. Alg. Appl.,2003,363:177-200
[152] I. Marek, D.B. Szyld. Algebraic schwarz methods for the numerical solution of Markov chains.Linar Algebraic and its Applications,2004,386:67-81
[153] K. Meier-Hellstern. The analysis of a queue arising in overflow models. IEEE Trans. Commun.,1989,37:367-372
[154] M. Mesˇina. Convergence acceleration for the iterative solution of the equations X=AX+f.Comput. Methods Appl. Mech. Engrg.,1977,10:165-173
[155] G. Meurant. Computer Solution of Large Linear Systems. Elsevier, Amsterdam,1999
[156] H. Minc. Nonnegative Matrices. New York, John Wiley&Sons,1988
[157] A.C. Muresan, Y. Notay. Analysis of aggregation-based multigrid. SIAM J. Sci. Comput.,2008,30:1082-1103
[158] M.F. Murphy, G.H. Golub, A. Wathen. A note on preconditioning for indefinite linear systems.SIAM J. Sci. Comput.,2000,21:1969-1972
[159] M.F. Murphy, G.H. Golub, A. Wathen. A note on preconditioning for indefinite linear systems.Tech. Report, SCCM-99-03, Stanford University,1999
[160] S.G. Nash, A. Sofer. Preconditioned reduced matrices. SIAM J. Matrix Anal. Appl.,1996,17:47-68
[161] N.K. Nichols. On the convergence of two-stage iterative processes for solving linear equations.SIAM J. Numer. Anal.,1973,10:460-469
[162] M. Nikolova, M.K. Ng, S. Zhang, et al.. Efficient reconstruction of piecewise constant imagesusing nonsmooth nonconvex minimization. SIAM J. Img. Sci.,2008,1:2-25
[163] Y. Notay. Aggregation-based algebraic multilevel preconditioning. SIAM J. Matrix Anal. Appl.,2006,27:998-1018
[164] Y. Notay, P.S. Vassilevski. Recursive Krylov-based multigrid cycles. Numer. Linear AlgebraAppl.,2008,15:473-487
[165] L. Page, S. Brin, R. Motwani, et al.. The PageRank citation ranking: Bringing order to the web.Technical Report1999-0120, Computer Science Department, Stanford,1999
[166] C.C. Paige and M.A. Saunders. Solution of sparse indefinite systems of linear equations. SIAMJ. Numer. Anal.,1975,12:617-629
[167] A. Papoulis and S.U. Pillai. Probability, Random Variables and Stochastic Processes with ErrataSheet. McGraw Hill Higher Education,2002
[168] L.F. Pavarino. Preconditioned mixed spectral element methods for elasticity and Stokes prob-lems. SIAM J. Sci. Comput.,1998,19:1941-1957
[169] J. Peters, V. Reichelt, A. Reusken. Fast iterative solvers for discrete stokes equations. SIAM J.Sci. Comput.,2005,27:646-666
[170] B. Philippe, Y. Saad, W.J. Stewart. Numerical methods in Markov chain modeling. OperationsResearch,1992,40:1156-1179
[171] B. Plateau, K. Atif. Stochastic automata network for modelling parallell systems. IEEE Trans.software Eng.,1991,17:1093-1108
[172] L. Reichel, Q. Ye. Breakdown-free GMRES for singular systems. SIAM J. Matrix Anal. Appl.,2005,26:1001-1021
[173] S.M. Ross. Stochastic Processes. John Wiley&Sons New York,1983
[174] T. Rusten, R. Winther. A preconditioned iterative method for saddle point problems. SIAM J.Matrix Anal. Appl.,1992,13:887-904
[175] Y. Saad. Analysis of augmented krylov subspace techniques:[Technical Report UMSI-95/175]. Minnesota Supercomputing Institute,1995
[176] Y. Saad. ILUT: A dual threshold incomplete LU factorization. Numer. Linear Algebra Appl.,1994,1:387-402
[177] Y. Saad. Iterative Methods for Sparse Linear Systems. Second ed., SIAM, Philadelphia, PA,2003
[178] Y. Saad. Krylov subspace methods for solving large unsymmetric linear systems. Math. Com-put.,1981,37:105-126
[179] Y. Saad. Preconditioned Krylov subspace methods for the numerical solution of Markov chains.In W. J. Stewart, editor, Computations with Markov chains, pp.49-64, Kluwer academic pub-lishers,1995
[180] Y. Saad, M.H. Schultz. GMRES: a generalized minimal residual algorithm for solving a non-symmetric linear system. SIAM J. Sci. Statist. Comput.,1986,7:856-869
[181] Y. Saad and H. A. van der Vorst. Iterative solution of linear systems in the20th century. J.Comput. Appl. Math.,2000,123:1-33
[182] Y. Saad, K. Wu. DQGMRES: A direct quasi-minima l residual algorithm based on incompleteorthogonalization:[Technical Report UMSI-93/131]. Minnesota Supercomputing Institute, Min-neapolis, MN,1993
[183] G.H. Santos, B.P.B. Silva, J.Y. Yuan. Block SOR methods for rank deficient least squares prob-lems. J. Comput. Appl. Math.,1998,100:1-9
[184] G.H. Santos, J.Y. Yuan. Preconditioned conjugate gradient methods for rank deficient leastsquares problems. Int. J. Comput. Math.,1999,75:509-518
[185] O. Schneider. Krylov subspace methods and their generalizations for solving singular operatorequations with applications to continuous time Markov chains. Doctoral Dissertation, Fakulta¨tfu¨r Mathematik und Informatik, der Technischen Universita¨t Bergakademie Freiberg, November2005
[186] W. Schonauer. Scientific Computing on Vector Computers. North-Holland. NY,1987
[187] P. J. Schweitzer, K. W. Kindle. An iterative aggregation-disaggregation algorithm for solvinglinear equations. Appl. Math. Comput.,1986,18:313-354
[188] E. Seneta. Non-negative Matrices and Markov Chains. Springer Verlag,2006
[189] X.H. Shao, Z. Li, C.J. Li. Modified SOR-like method for the augmented system. Int. J. Comput.Math.,2007,84:1653-1662
[190] A. Sidi. DGMRES: a GMRES-type algorithm for Drazin-inverse solution of singular nonsym-metric linear systems. Linear Algebra Appl.,2001,335:189-204
[191] A. Sidi. Efficient implementation of minimal polynomial and reduced rank extrapolation meth-ods. J. Comput. Appl. Math.,1991,36:305-337
[192] A. Sidi. Vector extrapolation methods with applications to solution of large systems of equationsand to PageRank computations. Computers and Math. Appl.,2008,56:1-24
[193] C. Siefert, E.D. Sturler. Preconditioners for generalized saddle point problems. SIAM J. Numer.Anal.,2006,44:1275-1296
[194] V. Simoncini. Block triangular preconditioners for symmetric saddle point problems. Appl.Numer. Math.,2004,49:63-80
[195] V. Simoncini, M. Benzi. Spectral properties of the Hermitian and skew-Hermitian splitting pre-conditioner for saddle point problmes. SIAM J. Matrix Anal. Appl.,2004,26:377-389
[196] G.L.G. Sleijpen and D.R. Fokkema. BiCGSTAB(l) for linear equations involving unsymmetricmatrices with complex spectrum. Electronic Trans. Numer. Analysis,1993,1:11-32
[197] D.A. Smith, W.F. Ford, A. Sidi. Extrapolation methods for vector sequence. SIAM Review,1987,29:199-233
[198] L. Smoch. Some results about GMRES in the singular case. Numer. Algo.,199922:193-212
[199] T. Sogabe. Extensions of the conjugate residual method:[Ph.D. Thesis], Tokyo: University ofTokyo,2006
[200] T. Sogabe, M. Sugihara, S.-L. Zhang. An extension of the conjugate residual method to non-symmetric linear systems. J. Comput. Appl. Math.,2009,266:103-113
[201] P. Sonneveld. CGS: a fast Lanczos-type solver for nonsymmetric linear systems. SIAM J. Sci.Statist. Comput.,1989,10:36-52
[202] W.J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton UniversityPress NJ,1994
[203] W.J. Stewart. Probability, Markov Chains, Queues, and Simulation. Princeton Univ Pr,2009
[204] W.J. Stewart, K. Atif, B. Plateau. The numerical solution of stochastic automata networks. Euro.J. Operat. Res.,1995,86:503-525
[205] W. J. Stewart, W. L. Cao. Iterative aggregation/disaggregation techniques for nearly uncoupledMarkov chains. J. ACM.,1985,32:702-719
[206] E. Stiefel. Relaxationsmethoden bester Strategie zur Lo¨ung linearer Gleichungssysteme. Com-ment. Math. Helv.,1955,29:157-179
[207] K. Stuben. A review of algebraic multigrid. J. Comput. Appl. Math.,2001,124:281-309
[208] E. Sturler. Nested krylov methods based on GCR. J. of computional and applied mathematics,1996
[209] E.D. Sturler, J. Liesen. Block-diagonal and constraint preconditioners for nonsymmetric indef-inite linear systems. Part I: theory. SIAM J. Sci. Comput.,2005,26:1598-1619
[210] D.B. Szyld. Equivalence of convergence conditions for itrative methods for singular quations.Numer. Linear Algebra Appl.,1994,1:151-154
[211] K. Tanabe. The conjugate gradient method for computing all the extremal stationary probabilityvectors of a stochastic matrix. Annals of the Institute of Statistical Mathematics Part B,1985,37:173-187
[212] W.F. Tinney, J.W. Walker. Direct solution of sparse network equations by optimally orderedtriangular factorization. Proc. of IEEE,1967,55:1801-1809
[213] H.A. van der Vorst. BiCGSTAB: a fast and smoothly converging variant of BiCG for the solutionof nonsymmetric linear systems. SIAM J. Sci. Statist. Comput.,1992,13:631-644
[214] R.S. Varga. Matrix Iterative Analysis. Springer Verlag,2000
[215] P. Vaneˇk, J. Mandel and M. Brezina. Algebraic multigrid by smoothed aggregation for secondand fourth order elliptic problems. Computing,1996,56:179-196
[216] P. Vaneˇk, J. Mandel and M. Brezina. Algebraic multigrid on unstructured meshes. Technical,Report X, Center for Computational Mathematics, Mathematics Department,1994
[217] E. Virnik. An algebraic multigrid preconditioner for a class of singular M-matrices. SIAM J.Sci. Comput.,2007,29:1982-1991
[218] L. Wang, Z.-Z. Bai. Skew-Hermitian triangular splitting iteration methods for non-Hermitianpositive definite linear systems of strong skew-Hermitian parts. BIT Numerical Mathematics,2004,44:363-386
[219] A. Wathen and D. Silvester. Fast iterative solution of stabilized stokes systems part I: Usingsimple diagonal preconditioners. SIAM J. Numer. Anal.,1993,30:630-649
[220] A. Wathen and D. Silvester. Fast iterative solution of stabilized stokes systems Part II: Usinggeneral block diagonal preconditioners. SIAM J. Numer. Anal.,1994,31:1352-1367
[221] Y. Wei, H. Wu. Convergence properties of Krylov subspace methods for singular linear systemswith arbitrary index. J. Comput. Appl. Math.,2000,114:305-318
[222] C. Wen, T.-Z. Huang, C. Wang. Triangular and skew-symmetric splitting methods for numericalsolutions of Markov chains. Computers and Mathematics with Applications,2011,62:4039-4048
[223] C. Wen, T.-Z. Huang, D.-A. Wu, et al.. The finest level acceleration of multilevel aggregationfor Markov chains. INT J. Numer. Anal. Mod. Series B,2011,2:27-41
[224] O.B. Widlund. A Lanczos method for a class of nonsymmetric systems of linear equations.SIAM J. Numer. Anal.,1978,15:801-812
[225] G. Wittum. Multigrid methods for Stokes and Navier-Stokes equations. Transformingsmoothers: Algorithms and numerical results, Numer. Math.,1989,54:543-563
[226] S. Wright. Stability of augmented system factorizations in interior-point methods. SIAM J.Matrix Anal. Appl.,1997,18:191-222
[227]吴建平,王正华,李晓梅.稀疏线性方程组的高效求解与并行计算.湖南:湖南科学技术出版社,2004
[228] S.-L. Wu, T.-Z. Huang, X.-L. Zhao. A modified SSOR iterative method for augmented systems.J. Comp. Appl. Math.,2009,228:424-433
[229] G. Wu, Y. Wei. An Arnoldi-Extrapolation algorithm for computing PageRank. J. Comput. Appl.Math.,2010,234:3196-3212
[230] P. Wynn. Accelerated techniques for iterated vector and matrix problems. Math. Comp.,1962,16:301-322
[231] P. Wynn. On a device for computing em(Sn) transformation. Math. Tab. Other Aids Comput.,1956,10:91-96
[232]徐树方.矩阵计算的理论与方法.北京:北京大学出版社,1995
[233] D.M. Young. Iterative methods for solving partial differential equations of elliptic type:[Ph.D.Thesis], Cambridge, MA, USA: Harvard University,1950
[234] D.M. Young. Iterative Solution of Large Linear Systems. Academic Press, New York,1971
[235] H. Young, B. Byung, K. Chong. Performance analysis of leaky-bucket bandwidth enforcementstrategy for bursty traffics in an ATM network. Comput. Net. ISDN Syst.,1992,25:295-303
[236] J.Y. Yuan. Iterative methods for generalized least squares problems. Ph.D. Thesis, IMPA, Riode Janeiro, Brazil,1993
[237] J.Y. Yuan. Numerical methods for generalized least squares problems. J. Comput. Appl. Math.,1996,66:571-584
[238] J.Y. Yuan, A.N. Iusem. Preconditioned conjugate gradient methods for generalized least squaresproblems. J. Comput. Appl. Math.,1996,71:287-297
[239] W.-O. Yuen, W.K. Ching, M.K. Ng. A hybrid algorithm for queueing systems. Calcolo,2004,41:139-151
[240] S.-Z. Zhang. GPBiCG: generalized product-type methods based on BiCG for solving nonsym-metric linear systems. SIAM J. Sci. Comput.,1997,18:537-551
[241] G.F. Zhang, Q.H. Lu. On generalized symmetric SOR method for augmented systems. J. Comp.Appl. Math.,2008,219:51-58
[242] S.-L. Zhang, Y. Oyanagi, M. Sugihara. Necessary and sufficient conditions for the convergenceof Orthomin(k) on inconsistent linear systems. Numer. Math.,2000,87:391-405
[243] B. Zheng, K. Wang, Y.J. Wu. SSOR-like methods for saddle point problems. Int. J. ComputerMath.,2009,86:1405-1423