A DIVIDE-AND-CONQUER ALGORITHM FOR THE BIDIAGONAL SVD

被引：86
|
作者：
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期
关键词：
SINGULAR VALUE DECOMPOSITION; DIVIDE-AND-CONQUER; BIDIAGONAL MATRIX;
D O I：
10.1137/S0895479892242232
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The authors present a stable and efficient divide-and-conquer algorithm for computing the singular value decomposition (SVD) of a lower bidiagonal matrix. Previous divide-and-conquer algorithms all suffer from a potential loss of orthogonality among the computed singular vectors unless extended precision arithmetic is used. A generalization that computes the SVD of a lower banded matrix is also presented.
引用
收藏
页码：79 / 92
页数：14
相关论文
共 50 条
  • [31] A DIVIDE-AND-CONQUER ALGORITHM FOR COMPUTING SINGULAR-VALUES
    CHANDRASEKARAN, S
    IPSEN, ICF
    ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK, 1994, 74 (06): : T532 - T534
  • [32] Divide-and-Conquer Learning with Nystrom: Optimal Rate and Algorithm
    Yin, Rong
    Liu, Yong
    Lu, Lijing
    Wang, Weiping
    Meng, Dan
    THIRTY-FOURTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THE THIRTY-SECOND INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE AND THE TENTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2020, 34 : 6696 - 6703
  • [33] A DIVIDE-AND-CONQUER ALGORITHM FOR CONSTRUCTING RELATIVE NEIGHBORHOOD GRAPH
    HUANG, NF
    BIT, 1990, 30 (02): : 196 - 206
  • [34] ON A PROPOSED DIVIDE-AND-CONQUER MINIMAL SPANNING TREE ALGORITHM
    STOJMENOVIC, I
    LANGSTON, MA
    BIT, 1988, 28 (04): : 785 - 791
  • [35] A Divide-and-Conquer Algorithm for Irregular Redistribution in Parallelizing Compilers
    Hui Wang
    Minyi Guo
    Daming Wei
    The Journal of Supercomputing, 2004, 29 : 157 - 170
  • [36] Divide-and-conquer algorithm for computing set containment joins
    Melnik, S
    Garcia-Molina, H
    ADVANCES IN DATABASE TECHNOLOGY - EDBT 2002, 2002, 2287 : 427 - 444
  • [37] A PRACTICAL DIVIDE-AND-CONQUER ALGORITHM FOR THE RECTANGLE INTERSECTION PROBLEM
    GUTING, RH
    SCHILLING, W
    INFORMATION SCIENCES, 1987, 42 (02) : 95 - 112
  • [38] Divide-and-conquer algorithm for creating neighborhood graph for clustering
    Virmajoki, O
    Fränti, P
    PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION, VOL 1, 2004, : 264 - 267
  • [39] Kart: a divide-and-conquer algorithm for NGS read alignment
    Lin, Hsin-Nan
    Hsu, Wen-Lian
    BIOINFORMATICS, 2017, 33 (15) : 2281 - 2287
  • [40] A Divide-and-Conquer Algorithm for All Spanning Tree Generation
    Chakraborty, Maumita
    Mehera, Ranjan
    Pal, Rajat Kumar
    ADVANCED COMPUTING AND SYSTEMS FOR SECURITY, VOL 3, 2017, 567 : 19 - 36
12345