research-article

Augmented Implicitly Restarted Lanczos Bidiagonalization Methods

Authors:

Lothar ReichelAuthors Info & Claims

SIAM Journal on Scientific Computing, Volume 27, Issue 1

Pages 19 - 42

https://doi.org/10.1137/04060593X

Published: 01 January 2005 Publication History

Abstract

New restarted Lanczos bidiagonalization methods for the computation of a few of the largest or smallest singular values of a large matrix are presented. Restarting is carried out by augmentation of Krylov subspaces that arise naturally in the standard Lanczos bidiagonalization method. The augmenting vectors are associated with certain Ritz or harmonic Ritz vectors. Computed examples show the new methods to be competitive with available schemes.

References

[1]

J. Baglama, D. Calvetti, L. Reichel, Iterative methods for the computation of a few eigenvalues of a large symmetric matrix, BIT, 36 (1996), 400–421, International Linear Algebra Year (Toulouse, 1995)

Digital Library

[2]

J. Baglama, D. Calvetti, L. Reichel, IRBL: an implicitly restarted block‐Lanczos method for large‐scale Hermitian eigenproblems, SIAM J. Sci. Comput., 24 (2003), 1650–1677

Digital Library

[3]

J. Baglama, D. Calvetti, L. Reichel, Algorithm 827: irbleigs: a MATLAB program for computing a few eigenpairs of a large sparse Hermitian matrix, ACM Trans. Math. Software, 29 (2003), 337–348

Digital Library

[4]

Åke Björck, Numerical methods for least squares problems, Society for Industrial and Applied Mathematics (SIAM), 1996xviii+408

[5]

Åke Björck, Eric Grimme, Paul Van Dooren, An implicit shift bidiagonalization algorithmfor ill‐posed systems, BIT, 34 (1994), 510–534

Digital Library

[6]

James Bunch, Christopher Nielsen, Updating the singular value decomposition, Numer. Math., 31 (1978/79), 111–129

Digital Library

[7]

D. Calvetti, L. Reichel, D. Sorensen, An implicitly restarted Lanczos method for large symmetric eigenvalue problems, Electron. Trans. Numer. Anal., 2 (1994), 1–21

[8]

P. Comon and G. H. Golub, Tracking a few extreme singular values and vectors in signal processing, Proc. IEEE, 78 (1990), pp. 1327–1343.

[9]

I. S. Duff, R. G. Grimes, and J. G. Lewis, User’s Guide for the Harwell‐Boeing Sparse Matrix Collection (Release I), Technical report TR/PA/92/86, CERFACS, Toulouse, France, 1992.

The matrices are available at http://math.nist.gov/MatrixMarket/.

[10]

G. Golub, W. Kahan, Calculating the singular values and pseudo‐inverse of a matrix, J. Soc. Indust. Appl. Math. Ser. B Numer. Anal., 2 (1965), 205–224

[11]

Gene Golub, Charles Van Loan, Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, 1996xxx+698

[12]

M. Gu and S. C. Eisenstat, A Stable and Fast Algorithm for Updating the Singular Value Decomposition, Technical report YALEU/DCS/RR‐966, Department of Computer Science, Yale University, New Haven, CT, 1993.

[13]

Michiel Hochstenbach, A Jacobi‐Davidson type SVD method, SIAM J. Sci. Comput., 23 (2001), 606–628, Copper Mountain Conference (2000)

Digital Library

[14]

M. E. Hochstenbach, Harmonic and refined extraction methods for the singular value problem, with applications to least‐squares problems, BIT, to appear.

[15]

Suely Oliveira, A convergence proof of an iterative subspace method for eigenvalues problems, Springer, Berlin, 1997, 316–325

[16]

Zhongxiao Jia, Datian Niu, An implicitly restarted refined bidiagonalization Lanczos method for computing a partial singular value decomposition, SIAM J. Matrix Anal. Appl., 25 (2003), 246–265

Digital Library

[17]

E. Kokiopoulou, C. Bekas, E. Gallopoulos, Computing smallest singular triplets with implicitly restarted Lanczos bidiagonalization, Appl. Numer. Math., 49 (2004), 39–61

Digital Library

[18]

R. M. Larsen, Lanczos bidiagonalization with partial reorthogonalization, Chapter of Ph.D. thesis, Department of Computer Science, University of Aarhus, Aarhus, Denmark, 1998; also available online from http://soi.stanford.edu/∼rmunk/.

[19]

Peter Läuchli, Jordan‐Elimination und Ausgleichung nach kleinsten Quadraten, Numer. Math., 3 (1961), 226–240

Digital Library

[20]

R. Lehoucq, Implicitly restarted Arnoldi methods and subspace iteration, SIAM J. Matrix Anal. Appl., 23 (2001), 551–562

Digital Library

[21]

R. Lehoucq, D. Sorensen, Deflation techniques for an implicitly restarted Arnoldi iteration, SIAM J. Matrix Anal. Appl., 17 (1996), 789–821

Digital Library

[22]

R. B. Lehoucq, D. C. Sorensen, and C. Yang, ARPACK Users’ Guide: Solution of Large‐Scale Eigenvalue Problems with Implicitly Restarted Arnoldi Methods, Software Environ. Tools 6, SIAM, Philadelphia, 1998.

[23]

The MathWorks, Inc., MATLAB, Version 6.5

R13,

Natick, MA, 2002.

[24]

Ronald Morgan, Computing interior eigenvalues of large matrices, Linear Algebra Appl., 154/156 (1991), 289–309

[25]

Ronald Morgan, On restarting the Arnoldi method for large nonsymmetric eigenvalue problems, Math. Comp., 65 (1996), 1213–1230

Digital Library

[26]

R. B. Morgan and M. Zeng, Harmonic Restarted Arnoldi Algorithm for Calculating Eigenvalues and Determining Multiplicity, preprint, 2003.

[27]

Chris Paige, Beresford Parlett, Henk van der Vorst, Approximate solutions and eigenvalue bounds from Krylov subspaces, Numer. Linear Algebra Appl., 2 (1995), 115–133

[28]

Horst Simon, Hongyuan Zha, Low‐rank matrix approximation using the Lanczos bidiagonalization process with applications, SIAM J. Sci. Comput., 21 (2000), 2257–2274

Digital Library

[29]

D. Sorensen, Implicit application of polynomial filters in a

k

‐step Arnoldi method, SIAM J. Matrix Anal. Appl., 13 (1992), 357–385

Digital Library

[30]

D. C. Sorensen, Numerical methods for large eigenvalue problems, Acta Numer., 11 (2002), pp. 519–584.

[31]

Andreas Stathopoulos, Yousef Saad, Restarting techniques for the (Jacobi‐)Davidson symmetric eigenvalue methods, Electron. Trans. Numer. Anal., 7 (1998), 163–181, Large scale eigenvalue problems (Argonne, IL, 1997)

[32]

Andreas Stathopoulos, Yousef Saad, Kesheng Wu, Dynamic thick restarting of the Davidson, and the implicitly restarted Arnoldi methods, SIAM J. Sci. Comput., 19 (1998), 227–245, Special issue on iterative methods (Copper Mountain, CO, 1996)

Digital Library

[33]

Kesheng Wu, Horst Simon, Thick‐restart Lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Anal. Appl., 22 (2000), 602–616

Digital Library

Cited By

Feng XYu WXie YTang J(2024)Algorithm 1043: Faster Randomized SVD with Dynamic ShiftsACM Transactions on Mathematical Software10.1145/366062950:2(1-27)Online publication date: 23-Apr-2024
https://dl.acm.org/doi/10.1145/3660629
Zhu YWang CZhang QXiong HHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Graph Signal Diffusion Model for Collaborative FilteringProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657759(1380-1390)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657759
Lazzaro DMorigi SZuzolo P(2024)Learning intrinsic shape representations via spectral mesh convolutionsNeurocomputing10.1016/j.neucom.2024.128152598:COnline publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1016/j.neucom.2024.128152
Show More Cited By

Index Terms

Augmented Implicitly Restarted Lanczos Bidiagonalization Methods
1. Computing methodologies

Index terms have been assigned to the content through auto-classification.

Recommendations

An augmented LSQR method

The LSQR iterative method for solving least-squares problems may require many iterations to determine an approximate solution with desired accuracy. This often depends on the fact that singular vector components of the solution associated with small ...
An implicitly restarted block Lanczos bidiagonalization method using Leja shifts
Abstract
In this paper, we propose an implicitly restarted block Lanczos bidiagonalization (IRBLB) method for computing a few extreme or interior singular values and associated right and left singular vectors of a large matrix A. Our method combines the ...
Hybrid iterative refined restarted Lanczos bidiagonalization methods
Abstract
Presented are new hybrid restarted Lanczos bidiagonalization methods for the computation of a few of the extreme singular triplets of very large matrices. Restarting is carried out either by a thick-restarted scheme with Ritz vectors or explicitly ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing Volume 27, Issue 1

2005

367 pages

ISSN:1064-8275

Issue’s Table of Contents

Copyright © 2005 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2005

Author Tags

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

41
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng XYu WXie YTang J(2024)Algorithm 1043: Faster Randomized SVD with Dynamic ShiftsACM Transactions on Mathematical Software10.1145/366062950:2(1-27)Online publication date: 23-Apr-2024
https://dl.acm.org/doi/10.1145/3660629
Zhu YWang CZhang QXiong HHui Yang GWang HHan SHauff CZuccon GZhang Y(2024)Graph Signal Diffusion Model for Collaborative FilteringProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3626772.3657759(1380-1390)Online publication date: 10-Jul-2024
https://dl.acm.org/doi/10.1145/3626772.3657759
Lazzaro DMorigi SZuzolo P(2024)Learning intrinsic shape representations via spectral mesh convolutionsNeurocomputing10.1016/j.neucom.2024.128152598:COnline publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1016/j.neucom.2024.128152
El Hachimi AJbilou KHached MRatnani A(2024)Tensor Golub–Kahan method based on Einstein productJournal of Computational and Applied Mathematics10.1016/j.cam.2024.116048451:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.cam.2024.116048
Alvarruiz FCampos CRoman J(2024)Thick-restarted joint Lanczos bidiagonalization for the GSVDJournal of Computational and Applied Mathematics10.1016/j.cam.2023.115506440:COnline publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1016/j.cam.2023.115506
Modell AGallagher ICeccherini EWhiteley NRubin-Delanchy POh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Intensity profile projectionProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667131(23259-23296)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667131
Jang JKang U(2023)Static and Streaming Tucker Decomposition for Dense TensorsACM Transactions on Knowledge Discovery from Data10.1145/356868217:5(1-34)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1145/3568682
Wei TMa JChow T(2023)Fine-tuning Partition-aware Item Similarities for Efficient and Scalable RecommendationProceedings of the ACM Web Conference 202310.1145/3543507.3583240(823-832)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583240
Merchant AMathioudakis MWang YChua TLauw HSi LTerzi ETsaparas P(2023)Graph Summarization via Node Grouping: A Spectral AlgorithmProceedings of the Sixteenth ACM International Conference on Web Search and Data Mining10.1145/3539597.3570441(742-750)Online publication date: 27-Feb-2023
https://dl.acm.org/doi/10.1145/3539597.3570441
De Pascuale SAllen KGreen DLore J(2023)Compression of tokamak boundary plasma simulation data using a maximum volume algorithm for matrix skeleton decompositionJournal of Computational Physics10.1016/j.jcp.2023.112089484:COnline publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1016/j.jcp.2023.112089
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents