Movatterモバイル変換


[0]ホーム

URL:


Skip to main content

Advertisement

Springer Nature Link
Log in

Computing the Bidiagonal SVD Through an Associated Tridiagonal Eigenproblem

  • Conference paper
  • First Online:

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

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. 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)

    MATH  Google Scholar 

  2. Marques, O., Demmel, J., Voemel, C., Parlett, B.N.: A testing infrastructure for symmetric tridiagonal eigensolvers. ACM TOMS35, 1–13 (2008)

    Article  Google Scholar 

  3. 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)

    Article MathSciNet MATH  Google Scholar 

  4. Dhillon, I.S., Parlett, B.N.: Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. Linear Algebra Appl.387, 1–28 (2004)

    Article MathSciNet MATH  Google Scholar 

  5. Dhillon, I.S., Parlett, B.N., Voemel, C.: The design and implementation of the MRRR algorithm. ACM TOMS32, 533–560 (2006)

    Article MathSciNet MATH  Google Scholar 

  6. Willems, P., Lang, B.: A framework for the MR\(^3\) algorithm: theory and implementation. SIAM J. Sci. Comput.35, 740–766 (2013)

    Article MathSciNet  Google Scholar 

  7. Demmel, J., Kahan, W.: Accurate singular values of bidiagonal matrices. SIAM J. Sci. Stat. Comput.11, 873–912 (1990)

    Article MathSciNet MATH  Google Scholar 

  8. Willems, P., Lang, B., Voemel, C.: Computing the bidiagonal SVD using multiple relatively robust representations. SIAM. J. Matrix Anal. Appl.28, 907–926 (2006)

    Article MathSciNet MATH  Google Scholar 

  9. Willems, P.: On MR\(^3\)-type algorithms for the tridiagonal symmetric eigenproblem and the bidiagonal SVD, PhD dissertation, University of Wuppertal (2010)

    Google Scholar 

  10. Voemel, C.: ScaLAPACK’s MRRR algorithm. ACM TOMS37, 1–35 (2010)

    Article MathSciNet MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Lawrence Berkeley National Laboratory, Berkeley, USA

    Osni Marques

  2. Faculdade de Economia and CMUP, Universidade Do Porto, Porto, Portugal

    Paulo B. Vasconcelos

Authors
  1. Osni Marques

    You can also search for this author inPubMed Google Scholar

  2. 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

  1. University of Porto, Porto, Portugal

    Inês Dutra

  2. University of Porto, Porto, Portugal

    Rui Camacho

  3. University of Porto, Porto, Portugal

    Jorge Barbosa

  4. 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

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only


[8]ページ先頭

©2009-2025 Movatter.jp