Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 10150))
Included in the following conference series:
478Accesses
Abstract
In this paper, we present an algorithm for the singular value decomposition (SVD) of a bidiagonal matrix by means of the eigenpairs of an associated symmetric tridiagonal matrix. The algorithm is particularly suited for the computation of a subset of singular values and corresponding vectors. We focus on a sequential implementation of the algorithm, discuss special cases and other issues. We use a large set of bidiagonal matrices to assess the accuracy of the implementation and to identify potential shortcomings. We show that the algorithm can be up to three orders of magnitude faster than existing algorithms, which are limited to the computation of a full SVD.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 5719
- Price includes VAT (Japan)
- Softcover Book
- JPY 7149
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bai, Z., Demmel, J., Dongarra, J., Ruhe, A., van der Vorst, H. (eds.): Templates for the solution of Algebraic Eigenvalue Problems: A Practical Guide. SIAM, Philadelphia (2000)
Marques, O., Demmel, J., Voemel, C., Parlett, B.N.: A testing infrastructure for symmetric tridiagonal eigensolvers. ACM TOMS35, 1–13 (2008)
Demmel, J., Marques, O., Voemel, C., Parlett, B.N.: Performance and accuracy of LAPACK’s symmetric tridiagonal eigensolvers. SIAM J. Sci. Comput.30, 1508–1526 (2008)
Dhillon, I.S., Parlett, B.N.: Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra Appl.387, 1–28 (2004)
Dhillon, I.S., Parlett, B.N., Voemel, C.: The design and implementation of the MRRR algorithm. ACM TOMS32, 533–560 (2006)
Willems, P., Lang, B.: A framework for the MR\(^3\) algorithm: theory and implementation. SIAM J. Sci. Comput.35, 740–766 (2013)
Demmel, J., Kahan, W.: Accurate singular values of bidiagonal matrices. SIAM J. Sci. Stat. Comput.11, 873–912 (1990)
Willems, P., Lang, B., Voemel, C.: Computing the bidiagonal SVD using multiple relatively robust representations. SIAM. J. Matrix Anal. Appl.28, 907–926 (2006)
Willems, P.: On MR\(^3\)-type algorithms for the tridiagonal symmetric eigenproblem and the bidiagonal SVD, PhD dissertation, University of Wuppertal (2010)
Voemel, C.: ScaLAPACK’s MRRR algorithm. ACM TOMS37, 1–35 (2010)
Author information
Authors and Affiliations
Lawrence Berkeley National Laboratory, Berkeley, USA
Osni Marques
Faculdade de Economia and CMUP, Universidade Do Porto, Porto, Portugal
Paulo B. Vasconcelos
- Osni Marques
You can also search for this author inPubMed Google Scholar
- Paulo B. Vasconcelos
You can also search for this author inPubMed Google Scholar
Corresponding authors
Correspondence toOsni Marques orPaulo B. Vasconcelos.
Editor information
Editors and Affiliations
University of Porto, Porto, Portugal
Inês Dutra
University of Porto, Porto, Portugal
Rui Camacho
University of Porto, Porto, Portugal
Jorge Barbosa
Lawrence Berkeley National Laboratory, Berkeley, California, USA
Osni Marques
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Marques, O., Vasconcelos, P.B. (2017). Computing the Bidiagonal SVD Through an Associated Tridiagonal Eigenproblem. In: Dutra, I., Camacho, R., Barbosa, J., Marques, O. (eds) High Performance Computing for Computational Science – VECPAR 2016. VECPAR 2016. Lecture Notes in Computer Science(), vol 10150. Springer, Cham. https://doi.org/10.1007/978-3-319-61982-8_8
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-319-61981-1
Online ISBN:978-3-319-61982-8
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative