摘要
矩阵广义特征值问题是当前迅速发展的计算机科学和数值代数中的一个非常活跃的研究课题。它在很多应用中扮演非常重要的角色,从数学角度来看,矩阵特征值问题的应用大多来自数学物理方程、差分方程、Markov过程等。目的是为了计算固体、流体、电磁、微观粒子、系统控制等重大问题。在实际的科学研究与工程应用中,比如在建筑工程、航空航天研究、生物科学、计算物理以及石油勘探中,都要涉及到大规模矩阵广义特征值问题的计算。
大规模并行处理系统(MPP)和PC机群为并行求解矩阵广义特征值问题提供了分布式存储环境。本文从理论和实验两方面深入研究了分布式环境下实矩阵广义特征值问题Ax=λBx的并行计算,提出了一些新的算法。本文的主要研究成果概括如下:
(1)关于实对称定三对角矩阵广义特征值问题
ⅰ) 提出了一种基于等规模矩阵划分策略的分治算法,子问题的规模之和等于原问题的规模。该算法利用割线法迭代计算广义特征值,具有计算量少,计算速度快的优点,并且算法具有内在并行性。理论分析和数值实验均证明该算法比K.Y.Li算法快,在矩阵规模较大时,计算时间约可以减少10%-20%。当n→∞时,加速比S_p→p,在分布式环境下可以获得很好的线性加速比和稳定的效率。
ⅱ) 提出了一种具有全新矩阵划分策略的分治算法。在这个划分策略中,子问题的规模之和等于原问题的规模减1,文中给出了特征值分割定理及其证明。该算法所提供的特征区间要优于第一种算法,因而在采用相同的迭代方式时,算法具有计算量少、计算时间短的优点。在矩阵规模较大时,计算时间约可以减少30%甚至更多。同时,算法也具有良好的内在并行性,当n→∞时,加速比S_p→p,在分布式环境下可以获得很好的线性加速比和稳定的效率。
(2)关于实对称带状矩阵广义特征值问题
ⅰ) 提出了一种结合多分法的并行分治算法,给出了特征值分割定理及其证明。在该算法中,子问题的规模之和等于原问题的规模。算法利用二分法结合广义Rayleigh商迭代,计算包含在特征区间内的每个特征对。在计算全部特征值和特征向量的情况下,算法的计算复杂性为O(n~2r~2),当r<<n时,优于
坛一一一~一续攀遨粼望廷二生掣夔
LApACK的计算复杂性O(n’)。在并行实现时,算法结合并行性好的多分法,
在分布式环境下获得了很高的并行加速比和效率。
ii)提出了另一种结合多分法的并行分治算法,给出了特征值分割定理及其证明。
在该算法中,子问题的规模之和等于原问题的规模减;,其中;为半带宽。在
计算全部特征值和特征向量的情况下,算法的计算复杂性为。(。’:’),并且该
算法的计算时间绝大多数情况都少于前一种分治算法。结合多分法,算法具
有很好的并行性,在分布式环境下,获得了很高的并行加速比和效率。
iii)提出了一种基于分治策略的并行同伦连续方法。通过限制步长、抛弃特征值
束的方法,提高算法效率。在矩阵规模较大时、算法的计算时间明显比
LAPACK少。在算法的并行实现时,充分利用计算与通信的重叠,在分布式
环境下获得了很高的并行加速比和稳定的效率。
(3)提出了一种计算实对称定矩阵广义特征值问题的并行分治算法。该算法是在计
算矩阵B的谱分解和MDR约化的基础上,将问题转化为对称三对角一正定对角
矩阵广义特征值问题,然后利用分治算法结合割线法迭代进行计算。根据扰动
理论,给出了每个特征值的包含区间。数值实验表明,在分布式环境下,该算
法可以获得很高的并行加速比和效率。
(4)提出了一种计算非对称矩阵广义特征值问题的分治算法。该算法在分治策略的
基础上,利用Laguerre迭代计算广义特征值,并采用各种方法尽可能减少特征
值的遗漏。采用收缩方法计算遗漏的特征值。数值实验表明,该算法计算速度
快,并行效果好。
(5)在分布式环境下实现了本文提出的所有算法,并形成了一个符合规范的软件包。
Generalized eigenvalue problem of matrix pair is an active research task. It plays a very important role in many application, according to the point of mathematics point, its mostly application originate from equations of mathematical physics, difference equations, Markov process, and so on, its purpose is to solve the problems of solid, fluid, electromagnetic, microscopic particles, system control, and etc. In practical science research and engineer applications, such as, architecture project, research of aeronautics and astronautics, bioscience, computing physics and oil reconnoiter, many large scale generalized eigenvalue problems need to be solved.
Massively Parallel Processing system (MPP) and PC cluster provide distributed-memory environments for parallel solving the generalized eigenvalue problem. This thesis investigates parallel solving the generalized eigenvalue problem Ax- Bx deeply, and proposes some new algorithms. The main productions are summarized as follows:
(1) The symmetric-definite tridiagonal generalized eigenvalue problems
i) A divide-and-conquer algorithm is proposed. The original problem is divided into two subproblems, and the sum of the subproblem's scales is equal to the original problem's scale. The generalized eigenvalues are computed by secant iteration. The advantage of this algorithm is that its computing quantity and computing time are less than the divide-and-conquer algorithm of K.Y. Li. With good parallelism in nature, it is quite suitable for parallel processing. Theoretical analysis and numerical experiments show that this algorithm is faster than the divide-and-conquer of K.Y. Li. About 10%-20% computing time is lessen when the problem's scale is large enough. The speedup satisfy: Sp - p as n - .
Good linear speedup and stable efficiency can be achieved under distributed-memory environments.
ii) A divide-and-conquer algorithm /with new dividing strategy is proposed. In this new dividing strategy, the sum of the subproblem's scales is equal to the original problem's scale minus 1. An eigenvalue interlacing theorem is given and proved. The interval including every eigenvalue provided by this dividing strategy is better than that provided by the first dividing strategy, with same iterative method, this algorithm has the advantage of less computing quantity and time. About 30% or more computing time is lessen when the problem's scale is large enough. This
algorithm has good parallelism in nature, the speedup satisfy: Sp - p as n - .
Good linear speedup and stable efficiency can be achieved under distributed-memory environments. (2) The symmetric-definite band generalized eigenvalue problems
i) A parallel divide-and-conquer algorithm combined with multisection method is proposed, the sum of the subproblem's scales is equal to the original problem's scale. An eigenvalue interlacing theorem is given and proved. Each eigenpair is computed by bisection and generalized Rayleigh quotient iteration. For computing all eigenvalues and eigenvectors is O(n2r2), it is less than O(n3), which is the computational complexity of LAPACK, when r n. This divide-and-conquer algorithm is combined with multisection method when it's implemented under distributed environment, high speedup and efficiency can be achieved, ii) A parallel divide-and-conquer algorithm combined with multisection method is proposed, the sum of the subproblem's scales is equal to the original problem's scale minus r, where r is semi-bandwidth. For computing all eigenvalues and eigenvectors is O(玍2). The computing time of this algorithm mostly is less than that of the former algorithm. Combined with multisection method, this divide-and-conquer algorithm has high parallelism, and high speedup and efficiency can be achieved under distributed environments.
iii) A parallel homotopy continuation algorithm based on divide-and-conquer is proposed. Efficiency of algorithm is improved by restricting step size and giving up eigenvalue's clusters, the computing ti
引文
[1] 李晓梅,蒋增荣等著,并行算法,长沙:湖南科学技术出版社,1992
[2] 李晓梅等著,面向结构的并行算法-设计与分析,长沙:国防科技大学出版社,1996
[3] 邓健新,矩阵本征值并行计算与工程计算的核心问题,计算机世界报,1996年第16期专题版
[4] 蒋伯诚,张锁春,高科技研究中的数值计算,长沙:国防科技大学出版社,1995
[5] 王勖成,邵敏,有限单元法基本原理与数值方法,北京:清华大学出版社,1988
[6] 邹鹏成,量子力学,北京:高等教育出版社,1989
[7] Schiff L.I.著,李淑娴,陈崇光译,量子力学,北京:人民教育出版社,1981
[8] 陈强顺,分析力学导论,上海:同济大学出版社,1997
[9] Wilkinson J. H., The Algebraic Eigenvalue Problem, (Oxford University Press, New York, 1965)
[10] Parlett B. N., The Symmetric Eigenvalue Problem, Prentice-Hall, Englewood Cliffs, NJ, 1980
[11] Golub G. H. and Van Loan C. F., Matrix Computations, The Johns Hopkins University Press, MD 21211, third edition, 1996
[12] http://www.netlib.org/lapack/lapack.tgz
[13] http://www.netlib.org/scalapack/scalapack.tgz
[14] http://www.netlib.org/eispack
[15] Collatz L., Numerical Treatment of Differential Equations (Springer, Berlin, 1960)
[16] Grieves B. and Dunn D., Symmetric matrix methods for Schrdinger eigenvectors, J. Phys. A: Math. Gen., 1990, 23:5479~5491
[17] Strang G. and Fix G., An Analysis of the Finite Element Method (Prentice-Hall, Englewood Cliffs, NJ, 1973)
[18] Bauska I. and Osborn J., Eigenvlaue Problems, in Handbook of Numerical Analysis, North-Holland Press, Amsterdam, 1991
[19] Arbenz P., Divide and conquer algorithms for the bandsymmetric eigenvalue problem, parallel computing, 1992, 18:1105~1128
[20] Li K. Y. and Li T. Y., An algorithm for symmetric tridiagonal eigenproblems: divide
and conquer with homotopy continuation, SIAM J. Sci. Comput., 1993, 14(3) :735-751
[21] Arbenz P., Computing eigenvalues of banded symmetric Toeplitz matrices, SIAM J. Sci. Stat. Comput., 1991, 12(4) :734-754
[22] Cuppen J. J. M., A divide and conquer method for the symmetric tridiagonal eigenproblem, Numer. Math., 1981, 36:177-195
[23] Zhijing G. Mou and Paul Hudak, An algebraic model for divide-and-conquer and its parallelism, The Journal of Supercomputing, 1988, 2(3) :257-278
[24] Schwarz H. R., Tridiagonalization of a symmetric band matrix, Numer. Math., 1968, 12:231-241
[25] Lang B., A parallel algorithm for reducing symmetric banded matrices to tridiagonal form, SIAM J. Sci. Comput, 1993,14(6) :1320-1338
[26] 罗晓广,李晓梅,解对称带状矩阵特征值问题的二分法及其改进,计算物理, 1997, 14(4-5) , 450-452
[27] Li T. Y. and Zeng Z. G, The Laguerre iteration in solving the symmetric tridiagonal eigenproblem, revisited, SIAM J. Sci. Comput., 1994, 15(5) : 1145-1173
[28] Li T. Y. and Rhee N. H., Homotopy algorithm for symmetric eigenvalue problems, Numer. Math., 1989, 55:265-280
[29] Lo S., Phillipe B. and Sameh A., A multiprocessor algorithm for the symmetric tridiagonal eigenvalue problems, SIAM J. Sci. Stat. Comp., 1987, 8(2) :155-165
[30] Li T. Y, Zeng Z. G. and Cong L., Solving eigenvalue problems of real nonsymmetric matrices with real homotopies, SIAM J. Numer. Anal., 1992, 29(1) :229-248
[31] Lui S. H., Keller H. B. and Kwok T. W. C., Homotopy method for the large, sparse, real nonsymmetric eigenvalue problem, SIAM J. Matrix Anal. AppL, 1997, 18(2) :312-333
[32] Dongarra J. J. and Sorensen D. C., A fully parallel algorithm for the symmetric eigenvalue problem, SIAM J. Sci. Stat. Comput., 1990, 11:203-229
[33] Deng J. X., On parallel fast Jacobi algorithm for the eigenproblem of real symmetric matrices, J. Comp. Math., 1989, 7:412-417
[34] Sleijpen G. L. G. and Van der Vorst H. A., A Jacobi-Davidson iteration method for linear eigenvalue problems, SIAM J. Matrix Anal. AppL, 1996, 17(2) :401-425
[35] Duff I. S. and Scott J. A., Computing selected eigenvalues of large sparse symmetric matrices using subspace iteration, ACM Trans. Math. Software, 1993, 19(2) : 137-159
[36] 孙家昶,邓健新,曹建文,解高阶Hermit矩阵特征值问题的并行块消去迭代法,数
值计算与计算机应用,1997,18(2):125~134
[37] 罗晓广,分布式存储环境下矩阵特征值问题的并行计算,长沙:国防科技大学研究生院博士论文,1998
[38] 邓健新,解实对称矩阵特征值问题的并行算法,数值计算与计算机应用,1997,18(4):246~258
[39] Nikolajsen J. L., An improved Laguerre eigensolver for unsymmetric matrices, SIAM J. Sci. Comput., 2000, 22(3):822~834
[40] 莫则尧,分布式环境下并行多重网格计算,长沙:国防科技大学研究生院博士论文,1997
[41] Fox G., Williams R. and Messina P., Parallel computing works! Morgan Kaufmann Publishers, Inc., SanFrancisco, California, 1994
[42] 孙家昶,迟学斌,汪道柳,网络并行计算与分布式编程环境,北京:科学出版社,1996
[43] Van der Vorst H. A., Golub G. H., 150 Years old and still alive: eigenproblems, http://www.math.uu.nl/people/vorst/Stateig.ps.gz
[44] Carlos F. Borgers and William B. Gragg, A parallel divide and conquer algorithm for the generalized real symmetric definite tridiagonal eigenproblem, Numerical Linear Algebra, 1995, 2:11~30
[45] Ribbens C. J. and Beattie C., Parallel solution of generalized symmetric tridiagonal eigenvalue problem on shared memory multiprocessors, Technical Report TR 92-47, Department of Computer Science, Virginia Polytechnic Institute and State University (1992)
[46] Li K. Y., Li T. Y. and Zeng Z. G., An algorithm for the generalized symmetric tridiagonal eigenvalue problem, Numerical Algorithms, 1994, 8(2-4):269~291
[47] Moler C. B. and Stewart G. W., An algorithm for generalized matrix eigenvalue problems, SIAM J. Numer. Anal., 1973, 10:241~256
[48] Kaufman L., An algorithm for the banded symmetric generalized matrix eigenvalue problem, SIAM J. Matrix Anal. Appl., 1993, 14(2):372~389
[49] Zhang Hong, William F. Moss, Using parallel banded linear system solvers in generalized eigenvalue problems, Parallel Comput., 1994, 20(8): 1089~1105
[50] Zhang T., Law K. H. and Gloub G. H., On the homotopy method for perturbed symmetric generalized eigenvalue problems, SIAM J. Sci. Comput., 1998, 19(5):1625~1645
[51] Li K. Y., Zhao S. B., A parallel method for the real symmetric generalized band eigenproblem, Proceedings of 1997 International Workshop on Computational Science and Engineering (IWCSE'97), Hefei, P. R. China, 1997, 29~33
[52] 迟学斌,特征值问题的算法、复杂性及并行实现,数值计算与计算机应用,1998,19(1):28~34
[53] 周树荃,薛长峰,非对称矩阵广义特征值问题的并行QZ算法,中国工业与应用数学学会第四次大会论文集,复旦大学出版社,1996,497~498
[54] Li T. Y. and Zeng Z. G., Homotopy-determinant algorithm for solving nonsymmetric eigenvalue problems, Math. Comput., 1992, 59(200):483~502
[55] Ribbens C. J. and Beattie C., Parallel solution of a generalized symmetric eigenvalue problem, Proc. Fifth SIAM Conf. On Parallel Processing for Scientific Computing, 1991, 16~21
[56] Li K. Y. and Li T. Y., A homotopy algorithm for a symmetric generalized eigenproblem, Numer. Algorithms, 1993, 4:167~195
[57] Li T. Y. and Sauer T., Homotopy method for generalized eigenvalue problems Aχ=λBχ, Linear Algebra Appl., 1987, 91:65~74
[58] Bernard Philippe and Brigitte Vital, Parallel implementations for solving generalized eigenvalue problems with symmetric sparse matrices, Applied Numerical Mathematics, 1993, 12:391~402
[59] Grimes R. G., Lewis J. G., and Simon H. D., A shifted block Lanczos algorithm for solving sparse symmetric generalized eigenproblems, SIAM J. Matrix Anal. Appl., 1994, 15(1):228~272
[60] Kothe Kai, Voss Heinrich, A full parallel condensation method for generalized eigenvalue problems on distributed memory computers, Parallel Comput., 1995, 21:907~921
[61] Knyazev A. V., Skordhodov A. L., Preconditioned gradient-type iterative methods in a subspace for parallel generalized symmetric eigenvalue problem, SIAM J. Numer Anal., 1994, 31(4):1226~1239
[62] Dzeng D. C. and Lin W. W., Homotopy continuation method for the numerical solutions of generalized symmetric eigenvalue problems, J. Austral. Math. Soc. Ser. B., 1991, 32:437~456
[63] Ruhe A., Rational Krylov algorithms for nonsymmetric eigenvalue problems. Linear Algebra Appl., 1994, 197&198:283~295
[64] Lang B., Parallel Reduktion Symmetrischer Bandmatrizen auf Tridiagonalgestalt,
PH.D. thesis,University of Korlsruhe(TH), Karlsruhe, Germany, 1991
[65] Fokkema D. R., Sleijpen G. L. G. and Van der Vorst H. A., Jacobi-Davidson style QR and QZ algorithm for the reduction of matrix pencils, SIAM J. Sci. Comput., 1998, 20(1) :94-125
[66] Chandrasekaran S., An efficient and stable algorithm for the symmetric-definite generalized eigenvalue problem, SIAM J. Matrix Anal. Appl., 2000, 21(4) : 1202-1228
[67] Li C. K. and Mathias R., Generalized eigenvalues of a definite Hermitian matrix pair, Linear Algebra Appl., 1998, 271:309-321
[68] Nool M. and Van der Ploeg A., A parallel Jacobi-Davidson-type method for solving large generalized eigenvalue problems in magnetohydrodynamics, SIAM J. Sci. Comput., 2000, 22(1) :95-112
[69] 薛长峰,周树荃,非对称广义特征值问题的并行同伦-行列式算法,数值计算与 计算机应用,1999, 20(3) :161-166
[70] Wu K. and Simon H., A parallel Lanczos method for symmetric generalized eigenvalue problems, http://www.nersc.gov/-kewu/ps/planso.ps
[71] 孙家昶,邓健新,曹建文,广义本征值并行计算在晶体能带中的应用,科学通报, 1997, 42(8) :818-821
[72] Van der Vorst H. A. and Sleijpen G. L. G, A parallelizable and fast algorithm for very large generalized eigenproblems, Applied Parallel Computing, Industrial Computation and Optimization, Third International Workshop, PARA 96, Lyngby, Denmark, August 18-21, 1996, Proceedings, 686-696
[73] Booten J. G. L., Van der Vorst H. A., Meijer P. M., and te Riele H. J. J., A preconditioned Jacobi-Davidson method for solving large generalized eigenvalue problems, http://citeseer.nj.nec.com/booten94preconditioned.html
[74] Hyman M., Eigenvalues and eigenvectors of general matrices, in: Proc. Of 12th National Metting of the Associate for Computing Machinery, Houseton, Texas, 1957
[75] Dongarra J. J. and Sidani M., A parallel algorithm for the nonsymmetric eigenvalue problem, SIAM J. Sci. Comput., 1993,14(3) :542-569
[76] Jenning A. and Osborne M. R., Generalized eigenvalue problems for certain unsymmetric band matrices, Linear Algebra Appl., 1977, 29:139-150
[77] Rodingue G, A gradient method for the matrix eigenvalue problem Ax-rBx, Numer. Math., 1973,22:1-16
[78] Crawford C. R., Reduction of a band symmetric generalized eigenvalue problem,
Comm. Assoc. Comp. Mach., 1973, 16:41~44
[79] Crawford C. R., A stable generalized eigenvalue problem, SIAM J. Num. Anal., 1976, 13:854~860
[80] Fix G. and Heiberger R., An algorithm for the ill-conditioned generalized eigenvalue problem, SIAM J. Num. Anal., 1972, 9:78~88
[81] Charlier J. P., Dooren P. V., A Jacobi-like algorithm for computing the generalized schur form of a regular pencil, J. Comput Appl. Math., 1989, 27:17~36
[82] Peters G. and Wilkinson J. H., Eigenvalues of Aχ=λBχ with band symmetric A and B, Comp. J., 1969, 12:398~404
[83] Stewart G. W., Perturbation bounds for the definite generalized eigenvalue problem, Linear Algebra Appl., 1979, 23:69~86
[84] 周树荃,曾岚,求解广义特征值问题的并行保域行列式查找法,南京航空航天大学学报,1995,27(2):147~155
[85] 周树荃,戴华,求解对称带状矩阵广义特征值问题的保域行列式查找法,南京航空学院学报,1985,17(4):23~30
[86] Chu M. T., A note on homotopy method for linear algebraic eigenvalue problems, Linear Algebra Appl., 1988, 105:225~236
[87] Costiner S. and Ta'asan S., Adaptive multigrid techniques for large-scale eigenvalue problems: solutions of the Schrodinger problem in two and three dimension, Phys. Rev. E, 1995, 51:3704~3717
[88] Saad Y., Numerical methods for large eigenvalue problems, Manchester University Press, Manchester, 1992
[89] Pantazis R. D., Regions of convergence of the Rayleigh quotient iteration method, Numer. Linear Algebra Appl., 1995, 2(3):251~269
[90] Rellich F., Perturbation theory of eigenvalue problems, Gordon and Breach, New York, 1969
[91] Stewart G. W. and Sun J. G., Matrix perturbation theory, Academic Press, Boston, 1990
[92] Vandergraft J., Generalized Rayleigh methods with applications to finding eigenvalues of large matrices, Linear Algebra Appl., 1971, 4:353~368
[93] Peters G. and Wilkinson J. H., Aχ=λBχ and the generalized eigenproblem, SIAM J. Numer. Anal., 1970, 7:479~492
[94] Smith et al. B. T., Matrix eigensystem Routines-EISPACK guide, 2nd ed. (Springer,
New York, 1976)
[95] Stewart G W., Gershgorin theory for the generalized eigenvalue problem Ax=γBx, Math. Comp., 1975, 29:600-606
[96] Kaufman L., The LZ-algorithm to solve the generalized eigenvalue problem, SIAM J. Numer. Anal., 1974, 11:997-1024
[97] Ericsson T. and Ruhe A., The spectral transformation Lanczos method for the numerical solution of large sparse generalized symmetric eigenvalue problems, Math. Comp., 1980, 35:1251-1268
[98] Ruhe A., The rational Krylov algorithm for generalized eigenvalue problems, in 92 Shanghai International Numerical Algebra and its Applications Conference, Fudan University, Shanghai, October 26-30, 1992
[99] Martin R. S. and Wilkinson J. H., Reduction of the symmetric eigenproblem Ax=γBx and related problems to standard form, Numer. Math., 1968, 11:99-110
[100] Chu M. T., Li T. Y. and Sauer T., Homotopy method for general r-matrix problems, SIAM J. Matrix Anal. Appl., 1988, 9:528-53
[101] Bunse-Gerstner A., An algorithm for the symmetric generalized eigenvalue problem, Linear Algebra Appl., 1984, 58:43-68
[102] 陈军,分布式存储环境下并行计算可扩展性的研究与应用,长沙:国防科技大学 研究生院博士论文, 2000
[103] Cullum J., Kerner W. and Willoughby R., A generalized nonsymmetric Lanczos procedure, Comput. Phys. Commun., 1989, 53:19-48
[104] Jones M. T. and Patrick M. L., The use of Lanczos' method to solve the large generalized symmetric eigenvalue problem in parallel, ICASE Report No. 90-48, Hampton, VA( 1990)
[105] Pantakis R. D. and Szyld D. B., A multiprocessor method for the solution of the generalized eigenvalue problem in an interval, in: J. Dongarra, P. Messina, D.C. Sorensen and R.G. Voigt, eds., Parallel Processing for Scientific Computing (SIAM, Philadelphia, PA, 1990)
[106] Zhang T., Golub G.H. and Law K.H., Subspace iterative method for eigenvalue problems, Linear Algebra Appl., 1999, 294:239-258
[107] Wang S. and Zhao S., An algorithm for Ax=γBx with symmetric and positive definite A and B, SIAM J. Matrix Anal. Appl., 1991, 12:654-660
[108] 夏又生,解广义特征值问题的半分法,南京邮电学院学报,1991, 11(4) :84-92
[109] 莫则尧,大型科学与工程应用程序并行化关键技术及其应用研究,北京:北京应用物理与计算数学研究所[博士后研究工作报告],1999
[110] Li T. Y. and Zou X. L., Implementing the parallel quasi-Laguerre's algorithm for symmetric tridiagonal eigenproblems, SIAM J. Sci. Comput., 1999, 20(6): 1954~1963
[111] Knyanzev A. V. and Skorokhodov A. L., Iterative method of gradient type in a subspace for a partial symmetric generalized eigenvalue problem, Russian Acad. Sci. Dokl. Math., 1993, 45:474~478
[112] Simon H D., The Lanczos algorithm for solving symmetric linear systems, PhD thesis, University of California, Berkeley, 1982
[113] Berger A. E., Solomon J. M. and Ciment M., Higher order accurate tridiagonal difference methods for diffusion convection equations, in: Advances in Computer Methods for Partial Differential Equations Ⅲ, eds. R. Vichnevetsky and R.S. Stepleman (IMACS, 1978), 322~330
[114] Boisvert R. F., Families of higher order accurate discretizations of some elliptic problems, SIAM J. Sci. Stat. Comp., 1981, 2:268~284
[115] 徐树方,矩阵计算的理论与方法,北京:北京大学出版社,1995
[116] 刘长学,超大规模稀疏矩阵计算方法,上海:上海科学技术出版社,1991
[117] 关治,陈景良,数值计算方法,北京:清华大学出版社,1990