{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:29:59Z","timestamp":1772119799664,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T00:00:00Z","timestamp":1689724800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T00:00:00Z","timestamp":1689724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Numer Algor"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We propose fast numerical algorithms to improve the accuracy of singular vectors for a real matrix. Recently, Ogita and Aishima proposed an iterative refinement algorithm for singular value decomposition that is constructed with highly accurate matrix multiplications carried out six times per iteration. The algorithm runs for the problem that has no multiple and clustered singular values. In this study, we show that the same algorithm can be run with highly accurate matrix multiplications carried out five times. Also, we proposed four algorithms constructed with highly accurate matrix multiplications, two algorithms with the multiplications carried out four times, and the other two with the multiplications carried out five times. These algorithms adopt the idea of a mixed-precision iterative refinement method for linear systems. Numerical experiments demonstrate speed-up and quadratic convergence of the proposed algorithms. As a result, the fastest algorithm is 1.7 and 1.4 times faster than the Ogita-Aishima algorithm per iteration on a CPU and GPU, respectively.<\/jats:p>","DOI":"10.1007\/s11075-023-01596-9","type":"journal-article","created":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T07:02:51Z","timestamp":1689750171000},"page":"979-1009","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Acceleration of iterative refinement for singular value decomposition"],"prefix":"10.1007","volume":"95","author":[{"given":"Yuki","family":"Uchino","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Terao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katsuhisa","family":"Ozaki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,7,19]]},"reference":[{"key":"1596_CR1","unstructured":"LAPACK (Linear Algebra PACKage) (2022). http:\/\/www.netlib.org\/lapack\/"},{"issue":"1","key":"1596_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF01932678","volume":"12","author":"P\u00c5 Wedin","year":"1972","unstructured":"Wedin, P.\u00c5.: Perturbation bounds in connection with singular value decomposition. BIT Numerical Mathematics 12(1), 99\u2013111 (1972)","journal-title":"BIT Numerical Mathematics"},{"issue":"1","key":"1596_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/0707001","volume":"7","author":"C Davis","year":"1970","unstructured":"Davis, C., Kahan, W.M.: The rotation of eigenvectors by a perturbation. III. SIAM J. Numer. Anal. 7(1), 1\u201346 (1970)","journal-title":"III. SIAM J. Numer. Anal."},{"key":"1596_CR4","doi-asserted-by":"crossref","unstructured":"Wedin, P.\u00c5.: On angles between subspaces of a finite dimensional inner product space. In: Matrix Pencils, pp. 263\u2013285. Springer, Berlin, Heidelberg (1983)","DOI":"10.1007\/BFb0062107"},{"issue":"2","key":"1596_CR5","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1023\/A:1022303426500","volume":"40","author":"FM Dopico","year":"2000","unstructured":"Dopico, F.M.: A note on sin $$\\Theta $$ theorems for singular subspace variations. BIT Numerical Mathematics 40(2), 395\u2013403 (2000)","journal-title":"BIT Numerical Mathematics"},{"issue":"1","key":"1596_CR6","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.cam.2003.12.039","volume":"170","author":"PI Davies","year":"2004","unstructured":"Davies, P.I., Smith, M.I.: Updating the singular value decomposition. J. Comput. Appl. Math. 170(1), 145\u2013167 (2004)","journal-title":"J. Comput. Appl. Math."},{"key":"1596_CR7","doi-asserted-by":"publisher","first-page":"112512","DOI":"10.1016\/j.cam.2019.112512","volume":"369","author":"T Ogita","year":"2020","unstructured":"Ogita, T., Aishima, K.: Iterative refinement for singular value decomposition based on matrix multiplication. J. Comput. Appl. Math 369, 112512 (2020)","journal-title":"J. Comput. Appl. Math"},{"key":"1596_CR8","unstructured":"Hida, Y., Li, X.S., Bailey, D.H.: Quad-double arithmetic: Algorithms, implementation, and application. In: 15th IEEE Symposium on Computer Arithmetic, pp. 155\u2013162 (2000). Citeseer"},{"key":"1596_CR9","doi-asserted-by":"crossref","unstructured":"Hida, Y., Li, X.S., Bailey, D.H.: Algorithms for quad-double precision floating point arithmetic. In: Proceedings 15th IEEE Symposium on Computer Arithmetic. ARITH-15 2001, pp. 155\u2013162 (2001). IEEE","DOI":"10.1109\/ARITH.2001.930115"},{"key":"1596_CR10","unstructured":"Advanpix LLC.: Multiprecision Computing Toolbox for MATLAB. (2023). http:\/\/www.advanpix.com\/"},{"key":"1596_CR11","doi-asserted-by":"crossref","unstructured":"Wilkinson, J.H.: Rounding errors in algebraic processes. Soc. Ind. Appl. Math. (2023)","DOI":"10.1137\/1.9781611977523"},{"issue":"2","key":"1596_CR12","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1145\/321386.321394","volume":"14","author":"CB Moler","year":"1967","unstructured":"Moler, C.B.: Iterative refinement in floating point. J. ACM (JACM) 14(2), 316\u2013321 (1967)","journal-title":"J. ACM (JACM)"},{"key":"1596_CR13","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/BF01932150","volume":"17","author":"M Jankowski","year":"1977","unstructured":"Jankowski, M., Wo\u017aniakowski, H.: Iterative refinement implies numerical stability. BIT Numer. Math. 17, 303\u2013311 (1977)","journal-title":"BIT Numer. Math."},{"issue":"151","key":"1596_CR14","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1090\/S0025-5718-1980-0572859-4","volume":"35","author":"RD Skeel","year":"1980","unstructured":"Skeel, R.D.: Iterative refinement implies numerical stability for Gaussian elimination. Math. Comput. 35(151), 817\u2013832 (1980)","journal-title":"Math. Comput."},{"key":"1596_CR15","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/BF01933262","volume":"31","author":"NJ Higham","year":"1991","unstructured":"Higham, N.J.: Iterative refinement enhances the stability of QR factorization methods for solving linear equations. BIT Numer. Math. 31, 447\u2013468 (1991)","journal-title":"BIT Numer. Math."},{"issue":"4","key":"1596_CR16","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1093\/imanum\/17.4.495","volume":"17","author":"NJ Higham","year":"1997","unstructured":"Higham, N.J.: Iterative refinement for linear systems and LAPACK. IMA J. Numer. Anal. 17(4), 495\u2013509 (1997)","journal-title":"IMA J. Numer. Anal."},{"key":"1596_CR17","doi-asserted-by":"crossref","unstructured":"Higham, N.J.: Accuracy and stability of numerical algorithms. Soc. Ind. Appl. Math. (2002)","DOI":"10.1137\/1.9780898718027"},{"key":"1596_CR18","doi-asserted-by":"crossref","unstructured":"Langou, J., Langou, J., Luszczek, P., Kurzak, J. Buttari, A., Dongarra, J.: Exploiting the performance of 32 bit floating point arithmetic in obtaining 64 bit accuracy (revisiting iterative refinement for linear systems). In: Proceedings of the 2006 ACM\/IEEE Conference on Supercomputing (2006)","DOI":"10.1109\/SC.2006.30"},{"issue":"6","key":"1596_CR19","doi-asserted-by":"publisher","first-page":"A2834","DOI":"10.1137\/17M1122918","volume":"39","author":"E Carson","year":"2017","unstructured":"Carson, E., Higham, N.J.: A new analysis of iterative refinement and its application to accurate solution of ill-conditioned sparse linear systems. SIAM J. Sci. Comput. 39(6), A2834\u2013A2856 (2017)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"1596_CR20","doi-asserted-by":"publisher","first-page":"817","DOI":"10.1137\/17M1140819","volume":"40","author":"E Carson","year":"2018","unstructured":"Carson, E., Higham, N.J.: Accelerating the solution of linear systems by iterative refinement in three precisions. SIAM J. Sci. Comput. 40(2), 817\u2013847 (2018)","journal-title":"SIAM J. Sci. Comput."},{"key":"1596_CR21","unstructured":"Higham, N.J.: Error analysis for standard and GMRES-based iterative refinement in two and three-precisions (2019)"},{"issue":"2243","key":"1596_CR22","doi-asserted-by":"publisher","first-page":"20200110","DOI":"10.1098\/rspa.2020.0110","volume":"476","author":"A Haidar","year":"2020","unstructured":"Haidar, A., Bayraktar, H., Tomov, S., Dongarra, J., Higham, N.J.: Mixed-precision iterative refinement using tensor cores on GPUs to accelerate solution of linear systems. Proceedings of the Royal Society A. 476(2243), 20200110 (2020)","journal-title":"Proceedings of the Royal Society A."},{"issue":"3","key":"1596_CR23","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1007\/s13160-018-0310-3","volume":"35","author":"T Ogita","year":"2018","unstructured":"Ogita, T., Aishima, K.: Iterative refinement for symmetric eigenvalue decomposition. Japan Journal of Industrial and Applied Mathematics. 35(3), 1007\u20131035 (2018)","journal-title":"Japan Journal of Industrial and Applied Mathematics."},{"issue":"1","key":"1596_CR24","first-page":"1","volume":"15","author":"Y Uchino","year":"2022","unstructured":"Uchino, Y., Ozaki, K., Ogita, T.: Acceleration of iterative refinement for symmetric eigenvalue decomposition (in Japanese). IPSJ Transactions on Advanced Computing System, in press 15(1), 1\u201312 (2022)","journal-title":"IPSJ Transactions on Advanced Computing System, in press"},{"issue":"1","key":"1596_CR25","first-page":"78","volume":"29","author":"K Shiroma","year":"2019","unstructured":"Shiroma, K., Kudo, S., Yamamoto, Y.: An eigendecomposition tracking method for real symmetric matrices based on Ogita-Aishima\u2019s eigenvector refinement algorithm (in Japanese). Trans. JSIAM 29(1), 78\u2013120 (2019)","journal-title":"Trans. JSIAM"},{"issue":"1","key":"1596_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s11075-011-9478-1","volume":"59","author":"K Ozaki","year":"2012","unstructured":"Ozaki, K., Ogita, T., Oishi, S., Rump, S.M.: Error-free transformations of matrix multiplication by using fast routines of matrix multiplication and its applications. Numerical Algorithms 59(1), 95\u2013118 (2012)","journal-title":"Numerical Algorithms"},{"key":"1596_CR27","unstructured":"Nakata, M.: MPLAPACK version 1.0.0 user manual (2021)"},{"issue":"2","key":"1596_CR28","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1145\/567806.567808","volume":"28","author":"XS Li","year":"2002","unstructured":"Li, X.S., Demmel, J.W., Bailey, D.H., Henry, G., Hida, Y., Iskandar, J., Kahan, W., Kang, S.Y., Kapur, A., Martin, M.C., et al.: Design, implementation and testing of extended and mixed precision BLAS. ACM Transactions on Mathematical Software 28(2), 152\u2013205 (2002)","journal-title":"ACM Transactions on Mathematical Software"},{"key":"1596_CR29","first-page":"1","volume":"754\u20132008","author":"IEEE standard for floating-point arithmetic","year":"2008","unstructured":"IEEE standard for floating-point arithmetic: IEEE Std 754\u20132008, 1\u201370 (2008)","journal-title":"IEEE Std"},{"issue":"2","key":"1596_CR30","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1137\/0702016","volume":"2","author":"GH Golub","year":"1965","unstructured":"Golub, G.H., Kahan, W.M.: Calculating the singular values and pseudo-inverse of a matrix. Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis 2(2), 205\u2013224 (1965)","journal-title":"Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis"},{"key":"1596_CR31","doi-asserted-by":"crossref","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. JHU press, Baltimore (2013)","DOI":"10.56021\/9781421407944"}],"container-title":["Numerical Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-023-01596-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11075-023-01596-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11075-023-01596-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,24]],"date-time":"2024-10-24T09:17:51Z","timestamp":1729761471000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11075-023-01596-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,19]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1596"],"URL":"https:\/\/doi.org\/10.1007\/s11075-023-01596-9","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-1931986\/v1","asserted-by":"object"}]},"ISSN":["1017-1398","1572-9265"],"issn-type":[{"value":"1017-1398","type":"print"},{"value":"1572-9265","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,7,19]]},"assertion":[{"value":"5 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 June 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 July 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval and consent to participate"}},{"value":"Not applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Human and animal ethics"}},{"value":"The authors declare no competing interests.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}