Acceleration of Iterative Refinement for Singular Value Decomposition

Acceleration of Iterative Refinement for Singular Value Decomposition | Research Square window.SnipcartSettings = { analytics: { enabled: false } }; (function() { var accessVector = localStorage.getItem('access_vector') || ''; window.dataLayer = window.dataLayer || []; if (accessVector) { window.dataLayer.push({ user: { profile: { profileInfo: { snid: accessVector } } } }); } })(); (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-K279D39R'); Browse Preprints In Review Journals COVID-19 Preprints AJE Video Bytes Research Tools Research Promotion AJE Professional Editing AJE Rubriq About Preprint Platform In Review Editorial Policies Our Team Advisory Board Help Center Sign In Submit a Preprint Cite Share Download PDF Research Article Acceleration of Iterative Refinement for Singular Value Decomposition Yuki Uchino, Takeshi Terao, Katsuhisa Ozaki This is a preprint; it has not been peer reviewed by a journal. https://doi.org/ 10.21203/rs.3.rs-1931986/v1 This work is licensed under a CC BY 4.0 License Status: Published Journal Publication published 19 Jul, 2023 Read the published version in Numerical Algorithms → Version 1 posted 7 You are reading this latest preprint version Abstract 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. Singular value decomposition Iterative refinement Mixed-precision computation Accurate numerical computation Full Text Additional Declarations No competing interests reported. Cite Share Download PDF Status: Published Journal Publication published 19 Jul, 2023 Read the published version in Numerical Algorithms → Version 1 posted Editorial decision: Major revision 25 Nov, 2022 Reviews received at journal 15 Nov, 2022 Reviewers agreed at journal 25 Oct, 2022 Reviewers invited by journal 25 Oct, 2022 Submission checks completed at journal 09 Aug, 2022 Editor assigned by journal 09 Aug, 2022 First submitted to journal 05 Aug, 2022 You are reading this latest preprint version Research Square lets you share your work early, gain feedback from the community, and start making changes to your manuscript prior to peer review in a journal. As a division of Research Square Company, we’re committed to making research communication faster, fairer, and more useful. We do this by developing innovative software and high quality services for the global research community. Our growing team is made up of researchers and industry professionals working together to solve the most critical problems facing scientific publishing. Also discoverable on Platform About Our Team In Review Editorial Policies Advisory Board Help Center Resources Author Services Accessibility API Access RSS feed Manage Cookie Preferences © Research Square 2026 | ISSN 2693-5015 (online) Privacy Policy Terms of Service Do Not Sell My Personal Information {"props":{"pageProps":{"initialData":{"identity":"rs-1931986","acceptedTermsAndConditions":true,"allowDirectSubmit":false,"archivedVersions":[],"articleType":"Research Article","associatedPublications":[],"authors":[{"id":127637709,"identity":"587c2c4b-08e8-41f0-a273-2d3fd9812aec","order_by":0,"name":"Yuki Uchino","email":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAZAAAAAyAQMAAABI0h/eAAAABlBMVEX///8AAABVwtN+AAAACXBIWXMAAA7EAAAOxAGVKw4bAAABFklEQVRIie2QMWvCQBTHXzjQpeJ6ojRf4YJQEWz7Vd4RaCanQnFwOBCeS0tXoYV+hXyDXghkks6BhpIsTu7VwdLTLhYSxa2U+y0PHvzu/38HYLH8RTiLchRf58Ad+tmwX6NMqfkiH+nunsKOKWcXrXyupeJQg2Pv7+i1leCSsuDlaUL5mj5cqDc1rMZQ71Uo/WeNQtJiGGbR1HugW0+ZYs59AqyvyhWRokZJbBiaLN4gdF5jU6yhgAldpUiljRK4M0mtDeH1LmVzUPEdhfMYIZXUNilyq7CDKVnCAEc3XpjKabfzhr5RRNxJePUt74+f65UYuO4sWBTLO7xUzagoluOBX/Vj5ZhK3BcnKVuuTlcsFovln/IN30JcZt/KOC8AAAAASUVORK5CYII=","orcid":"","institution":"Shibaura Institute of Technology","correspondingAuthor":true,"prefix":"","firstName":"Yuki","middleName":"","lastName":"Uchino","suffix":""},{"id":127637710,"identity":"a6a4bec2-bec5-46b8-a835-35d5ebe23ac3","order_by":1,"name":"Takeshi Terao","email":"","orcid":"","institution":"RIKEN Center for Computational Science","correspondingAuthor":false,"prefix":"","firstName":"Takeshi","middleName":"","lastName":"Terao","suffix":""},{"id":127637711,"identity":"503fc5d3-90f0-4bd8-a6d6-ed89e4bb302f","order_by":2,"name":"Katsuhisa Ozaki","email":"","orcid":"","institution":"Shibaura Institute of Technology","correspondingAuthor":false,"prefix":"","firstName":"Katsuhisa","middleName":"","lastName":"Ozaki","suffix":""}],"badges":[],"createdAt":"2022-08-05 07:44:15","currentVersionCode":1,"declarations":"","doi":"10.21203/rs.3.rs-1931986/v1","doiUrl":"https://doi.org/10.21203/rs.3.rs-1931986/v1","draftVersion":[],"editorialEvents":[{"content":"https://doi.org/10.1007/s11075-023-01596-9","type":"published","date":"2023-07-19T21:42:22+00:00"}],"editorialNote":"","failedWorkflow":false,"files":[{"id":25100257,"identity":"85b92217-647a-4710-b85d-17c263f52c2d","added_by":"auto","created_at":"2022-08-11 17:08:43","extension":"pdf","order_by":0,"title":"","display":"","copyAsset":false,"role":"manuscript-pdf","size":7857712,"visible":true,"origin":"","legend":"","description":"","filename":"Iterativerefinementforsingularvaluedecomposition1.pdf","url":"https://assets-eu.researchsquare.com/files/rs-1931986/v1_covered.pdf"}],"financialInterests":"No competing interests reported.","formattedTitle":"Acceleration of Iterative Refinement for Singular Value Decomposition","fulltext":[{"header":"Full Text","content":"This preprint is available for \u003ca href='/article/rs-1931986/latest.pdf' target='_blank'\u003edownload as a PDF\u003c/a\u003e."}],"fulltextSource":"","fullText":"","funders":[],"hasAdminPriorityOnWorkflow":false,"hasManuscriptDocX":false,"hasOptedInToPreprint":true,"hasPassedJournalQc":"","hasAnyPriority":false,"hideJournal":false,"highlight":"","institution":"","isAcceptedByJournal":true,"isAuthorSuppliedPdf":true,"isDeskRejected":"","isHiddenFromSearch":false,"isInQc":false,"isInWorkflow":false,"isPdf":false,"isPdfUpToDate":true,"isWithdrawnOrRetracted":false,"journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false},"keywords":"Singular value decomposition, Iterative refinement, Mixed-precision computation, Accurate numerical computation","lastPublishedDoi":"10.21203/rs.3.rs-1931986/v1","lastPublishedDoiUrl":"https://doi.org/10.21203/rs.3.rs-1931986/v1","license":{"name":"CC BY 4.0","url":"https://creativecommons.org/licenses/by/4.0/"},"manuscriptAbstract":"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.","manuscriptTitle":"Acceleration of Iterative Refinement for Singular Value Decomposition","msid":"","msnumber":"","nonDraftVersions":[{"code":1,"date":"2022-08-11 17:08:35","doi":"10.21203/rs.3.rs-1931986/v1","editorialEvents":[{"type":"communityComments","content":0},{"type":"decision","content":"Major revision","date":"2022-11-25T11:10:08+00:00","index":"","fulltext":""},{"type":"editorInvitedReview","content":"","date":"2022-11-15T14:44:55+00:00","index":"hide","fulltext":""},{"type":"reviewerAgreed","content":"a88d57ad-a765-4a2a-a958-1132ff71aaa1","date":"2022-10-25T12:07:51+00:00","index":"hide","fulltext":""},{"type":"reviewersInvited","content":"","date":"2022-10-25T08:49:00+00:00","index":"","fulltext":""},{"type":"checksComplete","content":"","date":"2022-08-09T12:02:01+00:00","index":"","fulltext":""},{"type":"editorAssigned","content":"","date":"2022-08-09T12:02:01+00:00","index":"","fulltext":""},{"type":"submitted","content":"Numerical Algorithms","date":"2022-08-05T07:34:56+00:00","index":"","fulltext":""}],"status":"published","journal":{"display":true,"email":"[email protected]","identity":"numerical-algorithms","isNatureJournal":false,"hasQc":true,"allowDirectSubmit":false,"externalIdentity":"numa","sideBox":"Learn more about [Numerical Algorithms](http://link.springer.com/journal/11075)","snPcode":"11075","submissionUrl":"https://submission.nature.com/new-submission/11075/3","title":"Numerical Algorithms","twitterHandle":"","acdcEnabled":true,"dfaEnabled":true,"editorialSystem":"em","reportingPortfolio":"Springer Hybrid","inReviewEnabled":true,"inReviewRevisionsEnabled":false}}],"origin":"","ownerIdentity":"4dec923f-3cf9-4836-93c4-f6875a6992d4","owner":[],"postedDate":"August 11th, 2022","published":true,"recentEditorialEvents":[],"rejectedJournal":[],"revision":"","amendment":"","status":"published-in-journal","subjectAreas":[],"tags":[],"updatedAt":"2023-10-16T22:09:45+00:00","versionOfRecord":{"articleIdentity":"rs-1931986","link":"https://doi.org/10.1007/s11075-023-01596-9","journal":{"identity":"numerical-algorithms","isVorOnly":false,"title":"Numerical Algorithms"},"publishedOn":"2023-07-19 21:42:22","publishedOnDateReadable":"July 19th, 2023"},"versionCreatedAt":"2022-08-11 17:08:35","video":"","vorDoi":"10.1007/s11075-023-01596-9","vorDoiUrl":"https://doi.org/10.1007/s11075-023-01596-9","workflowStages":[]},"version":"v1","identity":"rs-1931986","journalConfig":"researchsquare"},"__N_SSP":true},"page":"/article/[identity]/[[...version]]","query":{"redirect":"/article/rs-1931986","identity":"rs-1931986","version":["v1"]},"buildId":"J0_U0BvcaRcwD8yVFaRlm","isFallback":false,"isExperimentalCompile":false,"dynamicIds":[84888],"gssp":true,"scriptLoader":[]}