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 条
  • [1] Accelerating the SVD two stage bidiagonal reduction and divide and conquer using GPUs
    Gates, Mark
    Tomov, Stanimire
    Dongarra, Jack
    PARALLEL COMPUTING, 2018, 74 : 3 - 18
  • [2] A Divide-and-Conquer Algorithm for Computing Voronoi Diagrams
    Smith, Elijah
    Trefftz, Christian
    DeVries, Byron
    2020 IEEE INTERNATIONAL CONFERENCE ON ELECTRO INFORMATION TECHNOLOGY (EIT), 2020, : 495 - 499
  • [3] A DIVIDE-AND-CONQUER ALGORITHM FOR THE SYMMETRICAL TRIDIAGONAL EIGENPROBLEM
    GU, M
    EISENSTAT, SC
    SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1995, 16 (01) : 172 - 191
  • [4] 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
  • [5] DIVIDE-AND-CONQUER NEURAL NETWORKS
    ROMANIUK, SG
    HALL, LO
    NEURAL NETWORKS, 1993, 6 (08) : 1105 - 1116
  • [6] A Divide-and-Conquer Genetic Programming Algorithm With Ensembles for Image Classification
    Bi, Ying
    Xue, Bing
    Zhang, Mengjie
    IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 2021, 25 (06) : 1148 - 1162
  • [7] An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths
    Liao, Xiangke
    Li, Shengguo
    Cheng, Lizhi
    Gu, Ming
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2016, 71 (10) : 1933 - 1943
  • [8] A DIVIDE-AND-CONQUER DICTIONARY LEARNING ALGORITHM AND ITS PERFORMANCE ANALYSIS
    Mukherjee, Subhadip
    Seelamantula, Chandra Sekhar
    2016 IEEE INTERNATIONAL CONFERENCE ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING PROCEEDINGS, 2016, : 4712 - 4716
  • [9] A functional language to implement the divide-and-conquer Delaunay triangulation algorithm
    Moura, AL
    Camacho, JR
    Guimaraes, SC
    Salerno, CH
    APPLIED MATHEMATICS AND COMPUTATION, 2005, 168 (01) : 178 - 191
  • [10] An Efficient Parallel Divide-and-Conquer Algorithm for Generalized Matrix Multiplication
    Eagan, John
    Herdman, Marc
    Vaughn, Christian
    Bean, Nathaniel
    Kern, Sarah
    Pirouz, Matin
    2023 IEEE 13TH ANNUAL COMPUTING AND COMMUNICATION WORKSHOP AND CONFERENCE, CCWC, 2023, : 442 - 449
12345