Computing the Maximal Eigenpairs of Large Size Tridiagonal Matrices with $\mathcal{O}\left(1 \right)$ Number of Iterations
查看参考文献17篇
|
文摘
|
In a series of papers, Chen [4-6] developed some efficient algorithms for computing the maximal eigenpairs for tridiagonal matrices. The key idea is to explicitly construct effective initials for the maximal eigenpairs and also to employ a self-closed iterative algorithm. In this paper, we extend Chen's algorithm to deal with large scale tridiagonal matrices with super-/sub-diagonal elements. By using appropriate scalings and by optimizing numerical complexity, we make the computational cost for each iteration to be $\mathcal{O}\left(N \right)$. Moreover, to obtain accurate approximations for the maximal eigenpairs, the total number of iterations is found to be independent of the matrix size, i.e., $\mathcal{O}\left(1 \right)$ number of iterations. Consequently, the total cost for computing the maximal eigenpairs is $\mathcal{O}\left(N \right)$The effectiveness of the proposed algorithm is demonstrated by numerical experiments. |
|
来源
|
Numerical Mathematics Theory
, Methods and Applications,2018,11(4):877-894 【核心库】
|
|
DOI
|
10.4208/nmtma.2018.s11
|
|
关键词
|
Maximal eigenpair
;
large size tridiagonal matrix
;
scaling
;
complexity
|
|
地址
|
Department of Mathematics, Southern University of Science and Technology, Shenzhen
|
|
语种
|
英文 |
|
文献类型
|
研究性论文 |
|
ISSN
|
1004-8979 |
|
学科
|
数学 |
|
基金
|
supported by the Special Project on High-Performance Computing of the National Key R&D Program
;
国家自然科学基金
;
the Science Challenge Project
|
|
文献收藏号
|
CSCD:6405414
|
参考文献 共
17
共1页
|
|
1.
Arbenz P.
Lecture notes on solving large scale eigenvalue problems,2016
|
CSCD被引
1
次
|
|
|
|
|
2.
Barth W. Calculation of the eigenvalues of a symmetric tridiagonal matrix by the method of bisection.
Numer. Math,1967,9:386-393
|
CSCD被引
2
次
|
|
|
|
|
3.
Chen M F.
Eigenvalues, Inequalities, and Ergodic Theory,2005
|
CSCD被引
30
次
|
|
|
|
|
4.
Chen M F. Efficient initials for computing maximal eigenpair.
Front. Math. China,2016,11:1397-1418
|
CSCD被引
2
次
|
|
|
|
|
5.
Chen M F. Global algorithms for maximal eigenpair.
Front. Math. China,2017,12(5):1023-1043
|
CSCD被引
8
次
|
|
|
|
|
6.
Chen M F. Trilogy on computing maximal eigenpair.
International Conference on Queueing Theory and Network Applications,2017:312-329
|
CSCD被引
1
次
|
|
|
|
|
7.
Coakley E S. Afost divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices.
Appl. Comput. Harmon. A,2012,34:379-414
|
CSCD被引
3
次
|
|
|
|
|
8.
Dumitriu I. Matrix models for beta ensembles.
J. Math. Phys,2002,43:5830-5847
|
CSCD被引
8
次
|
|
|
|
|
9.
Edelman A.
Numerical methods for eigenvalue distributions of random matrix,2005
|
CSCD被引
1
次
|
|
|
|
|
10.
Edelman A.
Random matrix theory, Acta Numerica,2005:1-65
|
CSCD被引
1
次
|
|
|
|
|
11.
Gill D. An O(N~2) method for computing the eigensystem of N × N symmetric tridiagonal matrices by the divide and conquer approach.
SIAM J. Sci. Stat. Comp,1990,11:161-173
|
CSCD被引
2
次
|
|
|
|
|
12.
Smith G D.
Numerical Solution of Partial Differential Equations, 2nd Ed,1978
|
CSCD被引
1
次
|
|
|
|
|
13.
Golub G H. Calculation of Gauss quadrature rules.
Math. Comp,1969,23:221-239
|
CSCD被引
22
次
|
|
|
|
|
14.
Gu M. A divide-and-conquer algorithm for the symmetric tridiagonal eigen-problem.
SIAM J. Matrix Anal. Appl,1995,16:172-191
|
CSCD被引
7
次
|
|
|
|
|
15.
Ipsen I C F. Solving the symmetric tridiagonal eigenvalue problem on the hypercube.
SIAM J. Sci. Stat. Comput,1990,11(2):203-229
|
CSCD被引
2
次
|
|
|
|
|
16.
Saad Y.
Numerical methods for large eigenvalue problems,2011
|
CSCD被引
5
次
|
|
|
|
|
17.
Szyld D B. Criteria for combining inverse and Rayleigh quotient iteration.
SIAM J. Numer. Anal,1988,25:1369-1375
|
CSCD被引
4
次
|
|
|
|
|
了解气象卫星更多信息，请访问