{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,3]],"date-time":"2024-08-03T15:01:32Z","timestamp":1722697292759},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T00:00:00Z","timestamp":1589846400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1339676"]},{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia (FCT) through the sabbatical fellowship","award":["SFRH\/BSAB\/142986\/2018"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"The Singular Value Decomposition (SVD) is widely used in numerical analysis and scientific computing applications, including dimensionality reduction, data compression and clustering, and computation of pseudo-inverses. In many cases, a crucial part of the SVD of a general matrix is to find the SVD of an associated bidiagonal matrix. This article discusses an algorithm to compute the SVD of a bidiagonal matrix through the eigenpairs of an associated symmetric tridiagonal matrix. The algorithm enables the computation of only a subset of singular values and corresponding vectors, with potential performance gains. The article focuses on a sequential version of the algorithm, and discusses special cases and implementation details. The implementation, called BDSVDX, has been included in the LAPACK library. We use a large set of bidiagonal matrices to assess the accuracy of the implementation, both in single and double precision, as well as to identify potential shortcomings. The results show that BDSVDX can be up to three orders of magnitude faster than existing algorithms, which are limited to the computation of a full SVD. We also show comparisons of an implementation that uses BDSVDX as a building block for the computation of the SVD of general matrices.<\/jats:p>","DOI":"10.1145\/3361746","type":"journal-article","created":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T23:58:23Z","timestamp":1590191903000},"page":"1-25","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Bidiagonal SVD Computation via an Associated Tridiagonal Eigenproblem"],"prefix":"10.1145","volume":"46","author":[{"given":"Osni","family":"Marques","sequence":"first","affiliation":[{"name":"Lawrence Berkeley National Laboratory, Berkeley, California, USA"}]},{"given":"James","family":"Demmel","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley CA, USA"}]},{"given":"Paulo B.","family":"Vasconcelos","sequence":"additional","affiliation":[{"name":"Centro de Matem\u00e1tica 8 Faculdade Economia, University of Porto, Porto, Portugal"}]}],"member":"320","published-online":{"date-parts":[[2020,5,19]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"With Formulas, Graphs, and Mathematical Tables","author":"Abramowitz M.","unstructured":"M. Abramowitz . 1974. Handbook of Mathematical Functions , With Formulas, Graphs, and Mathematical Tables . Dover Publications, Inc. , New York, NY . M. Abramowitz. 1974. Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables. Dover Publications, Inc., New York, NY."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof L. S. Blackford J. Demmel J. J. Dongarra J. Du Croz S. Hammarling A. Greenbaum A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide (3rd ed.). Society for Industrial and Applied Mathematics Philadelphia PA. E. Anderson Z. Bai C. Bischof L. S. Blackford J. Demmel J. J. Dongarra J. Du Croz S. Hammarling A. Greenbaum A. McKenney and D. Sorensen. 1999. LAPACK Users\u2019 Guide (3rd ed.). Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2011.05.002"},{"key":"e_1_2_1_4_1","volume-title":"Numerical Methods for Least Squares Problems","unstructured":"\u00c5. Bj\u00f6rck. 1996. Numerical Methods for Least Squares Problems . Society for Industrial and Applied Mathematics , Philadelphia, PA . \u00c5. Bj\u00f6rck. 1996. Numerical Methods for Least Squares Problems. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"L. S. Blackford J. Choi A. Cleary E. D\u2019Azevedo J. Demmel I. Dhillon J. Dongarra S. Hammarling G. Henry A. Petitet K. Stanley D. Walker and R. C. Whaley. 1997. ScaLAPACK Users\u2019 Guide. Society for Industrial and Applied Mathematics Philadelphia PA. L. S. Blackford J. Choi A. Cleary E. D\u2019Azevedo J. Demmel I. Dhillon J. Dongarra S. Hammarling G. Henry A. Petitet K. Stanley D. Walker and R. C. Whaley. 1997. ScaLAPACK Users\u2019 Guide. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898719642"},{"key":"e_1_2_1_6_1","volume-title":"Applied Numerical Linear Algebra","author":"Demmel J.","unstructured":"J. Demmel . 1997. Applied Numerical Linear Algebra . Vol. 56 . Society for Industrial and Applied Mathematics , Philadelphia, PA . J. Demmel. 1997. Applied Numerical Linear Algebra. Vol. 56. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_2_1_7_1","volume-title":"Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide","author":"Demmel J.","unstructured":"J. Demmel , J. Dongarra , A. Ruhe , and H. van der Vorst . 2000. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide . Society for Industrial and Applied Mathematics, Philadelphia, PA. Bai, Zhaojun (Ed .). J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst. 2000. Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide. Society for Industrial and Applied Mathematics, Philadelphia, PA. Bai, Zhaojun (Ed.)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/3214393.3214403"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070688778"},{"key":"e_1_2_1_10_1","volume-title":"University of California","author":"Dhillon I.","unstructured":"I. Dhillon . 1997. A New O(N2) Algorithm for the Symmetric Tridiagonal Eigenvalue\/ Eigenvector Problem . Ph.D. Dissertation . University of California , Berkeley . I. Dhillon. 1997. A New O(N2) Algorithm for the Symmetric Tridiagonal Eigenvalue\/Eigenvector Problem. Ph.D. Dissertation. University of California, Berkeley."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. SIAM","author":"Dhillon I.","unstructured":"I. Dhillon , G. Fann , and B. Parlett . 1997. Application of a new algorithm for the symmetric eigenproblem to computational quantum chemistry . In Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. SIAM , Philadelphia. http:\/\/www.cs.utexas.edu\/ inderjit\/public_papers\/fannchem1.ps. I. Dhillon, G. Fann, and B. Parlett. 1997. Application of a new algorithm for the symmetric eigenproblem to computational quantum chemistry. In Proceedings of the 8th SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Philadelphia. http:\/\/www.cs.utexas.edu\/ inderjit\/public_papers\/fannchem1.ps."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2003.12.028"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186785.1186788"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117732"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1955-0067841-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/0702016"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(01)00398-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479801394829"},{"key":"e_1_2_1_19_1","volume-title":"Higham and Pythagoras Papadimitriou","author":"Nicholas","year":"1993","unstructured":"Nicholas J. Higham and Pythagoras Papadimitriou . 1993 . Parallel Singular Value Decomposition via the Polar Decomposition. University of Manchester, Department of Mathematics . Nicholas J. Higham and Pythagoras Papadimitriou. 1993. Parallel Singular Value Decomposition via the Polar Decomposition. University of Manchester, Department of Mathematics."},{"key":"e_1_2_1_20_1","unstructured":"Intel. 2017a. Intel(R) Fortran Compiler 2018 Update 1 for Linux. Intel. 2017a. Intel(R) Fortran Compiler 2018 Update 1 for Linux."},{"key":"e_1_2_1_21_1","unstructured":"Intel. 2017b. Intel(R) Math Kernel Library 2018 Update 1 for Linux. Intel. 2017b. Intel(R) Math Kernel Library 2018 Update 1 for Linux."},{"key":"e_1_2_1_22_1","unstructured":"LAPACK. 2018. LAPACK\u2014Linear Algebra PACKage. https:\/\/github.com\/Reference-LAPACK. LAPACK. 2018. LAPACK\u2014Linear Algebra PACKage. https:\/\/github.com\/Reference-LAPACK."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/130945995"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1377603.1377611"},{"key":"e_1_2_1_25_1","volume-title":"12th International Conference on High Performance Computing for Computational Science (VECPAR 2016)","author":"Marques O.","year":"2016","unstructured":"O. Marques and P. B. Vasconcelos . 2016. Computing the bidiagonal SVD through an associated tridiagonal eigenproblem . In 12th International Conference on High Performance Computing for Computational Science (VECPAR 2016) Porto, Portugal , June 28-30, 2016 , Revised Selected Papers. Springer, Heildeberg, Germany, 64--74. O. Marques and P. B. Vasconcelos. 2016. Computing the bidiagonal SVD through an associated tridiagonal eigenproblem. In 12th International Conference on High Performance Computing for Computational Science (VECPAR 2016) Porto, Portugal, June 28-30, 2016, Revised Selected Papers. Springer, Heildeberg, Germany, 64--74."},{"key":"e_1_2_1_26_1","unstructured":"MatrixMarket. 2018. Matrix Market. Retrieved from http:\/\/math.nist.gov\/MatrixMarket. MatrixMarket. 2018. Matrix Market. Retrieved from http:\/\/math.nist.gov\/MatrixMarket."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1090567.1642747"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090774999"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/120876605"},{"key":"e_1_2_1_30_1","unstructured":"F. Olver D. Lozier R. Boisvert and C. Clark. 2010. NIST Handbook of Mathematical Functions Hardback and CD-ROM. Cambridge University Press New York. F. Olver D. Lozier R. Boisvert and C. Clark. 2010. NIST Handbook of Mathematical Functions Hardback and CD-ROM. Cambridge University Press New York."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0962492900002580"},{"key":"e_1_2_1_32_1","volume-title":"The Symmetric Eigenvalue Problem","author":"Parlett B.","unstructured":"B. Parlett . 1998. The Symmetric Eigenvalue Problem . Vol. 20 . Society for Industrial and Applied Mathematics, Philadelphia , PA. B. Parlett. 1998. The Symmetric Eigenvalue Problem. Vol. 20. Society for Industrial and Applied Mathematics, Philadelphia, PA."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687062"},{"key":"e_1_2_1_34_1","unstructured":"ScaLAPACK. 2012. ScaLAPACK version 2.0.2. Retrieved from http:\/\/www.netlib.org\/scalapack. ScaLAPACK. 2012. ScaLAPACK version 2.0.2. Retrieved from http:\/\/www.netlib.org\/scalapack."},{"key":"e_1_2_1_35_1","unstructured":"TAU. 2018. TAU Performance System. Retrieved from https:\/\/www.cs.uoregon.edu\/research\/tau. TAU. 2018. TAU Performance System. Retrieved from https:\/\/www.cs.uoregon.edu\/research\/tau."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644001.1644002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1018812"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/110834020"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/050628301"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3361746","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3361746","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T07:49:01Z","timestamp":1672559341000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3361746"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,19]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3361746"],"URL":"http:\/\/dx.doi.org\/10.1145\/3361746","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,19]]},"assertion":[{"value":"2018-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}