A DIVIDE-AND-CONQUER ALGORITHM FOR THE SYMMETRICAL TRIDIAGONAL EIGENPROBLEM

被引：147
|
作者：
GU, M
EISENSTAT, SC
机构：
[1] UNIV CALIF BERKELEY,LAWRENCE BERKELEY LAB,BERKELEY,CA 94720
[2] YALE UNIV,DEPT COMP SCI,NEW HAVEN,CT 06520
来源：
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS | 1995年 / 16卷 / 01期
关键词：
SYMMETRICAL TRIDIAGONAL EIGENPROBLEM; DIVIDE-AND-CONQUER; ARROWHEAD MATRIX;
D O I：
10.1137/S0895479892241287
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The authors present a stable and efficient divide-and-conquer algorithm for computing the spectral decomposition of an N x N symmetric tridiagonal matrix. The key elements are a new, stable method for finding the spectral decomposition of a symmetric arrowhead matrix and a new implementation of deflation. Numerical results show that this algorithm is competitive with bisection with inverse iteration, Cuppen's divide-and-conquer algorithm, and the QR algorithm for solving the symmetric tridiagonal eigenproblem.
引用
收藏
页码：172 / 191
页数：20
相关论文
共 50 条
  • [1] AN ALGORITHM FOR SYMMETRICAL TRIDIAGONAL EIGENPROBLEMS - DIVIDE-AND-CONQUER WITH HOMOTOPY CONTINUATION
    LI, KY
    LI, TY
    SIAM JOURNAL ON SCIENTIFIC COMPUTING, 1993, 14 (03): : 735 - 751
  • [2] AN IMPLEMENTATION OF A DIVIDE-AND-CONQUER ALGORITHM FOR THE UNITARY EIGENPROBLEM
    AMMAR, GS
    REICHEL, L
    SORENSEN, DC
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 1992, 18 (03): : 292 - 307
  • [3] Exploiting the parallel divide-and-conquer method to solve the symmetric tridiagonal eigenproblem
    Badia, JM
    Vidal, AM
    PROCEEDINGS OF THE SIXTH EUROMICRO WORKSHOP ON PARALLEL AND DISTRIBUTED PROCESSING - PDP '98, 1998, : 13 - 19
  • [4] EIGENVALUES OF A SYMMETRICAL TRIDIAGONAL MATRIX - A DIVIDE-AND-CONQUER APPROACH
    KRISHNAKUMAR, AS
    MORF, M
    NUMERISCHE MATHEMATIK, 1986, 48 (03) : 349 - 368
  • [5] A NOTE ON DIVIDE-AND-CONQUER ALGORITHMS FOR THE SYMMETRICAL TRIDIAGONAL EIGENVALUE PROBLEM
    ARBENZ, P
    GATES, K
    ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1994, 74 (06): : T529 - T531
  • [6] A DIVIDE AND CONQUER METHOD FOR THE SYMMETRIC TRIDIAGONAL EIGENPROBLEM
    CUPPEN, JJM
    NUMERISCHE MATHEMATIK, 1981, 36 (02) : 177 - 195
  • [7] A parallel symmetric block-tridiagonal divide-and-conquer algorithm
    Bai, Yihua
    Ward, Robert C.
    ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE, 2007, 33 (04):
  • [8] A Parallel Structured Divide-and-Conquer Algorithm for Symmetric Tridiagonal Eigenvalue Problems
    Liao, Xia
    Li, Shengguo
    Lu, Yutong
    Roman, Jose E.
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2021, 32 (02) : 367 - 378
  • [9] DIVIDE-AND-CONQUER METHODS FOR BLOCK TRIDIAGONAL SYSTEMS
    MEHRMANN, V
    PARALLEL COMPUTING, 1993, 19 (03) : 257 - 279
  • [10] An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
    Li, Shengguo
    Rouet, Francois-Henry
    Liu, Jie
    Huang, Chun
    Gao, Xingyu
    Chi, Xuebin
    JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS, 2018, 344 : 512 - 520
12345