Computing Accurate Eigenvalues using a Mixed-Precision Jacobi Algorithm.
Saved in:
| Title: | Computing Accurate Eigenvalues using a Mixed-Precision Jacobi Algorithm. |
|---|---|
| Authors: | Higham, Nicholas J.1 (AUTHOR) highamnj@gmail.com, Tisseur, Françoise2 (AUTHOR) Francoise.Tisseur@manchester.ac.uk, Webb, Marcus2 (AUTHOR) marcus.webb@manchester.ac.uk, Zhou, Zhengbo3 (AUTHOR) zhengbo.zhou@postgrad.manchester.ac.uk |
| Source: | SIAM Journal on Matrix Analysis & Applications. 2025, Vol. 46 Issue 4, p2423-2448. 26p. |
| Subjects: | Eigenvalues, Jacobi method, Empirical research, Matrix multiplications, Algorithms, Numerical analysis, Approximation error |
| Abstract: | We provide a rounding error analysis of a mixed-precision preconditioned Jacobi algorithm, which uses low precision to compute the preconditioner, applies it at high precision (amounting to two matrix-matrix multiplications), and solves the eigenproblem using the Jacobi algorithm at working precision. Our analysis yields meaningfully smaller relative forward error bounds for the computed eigenvalues compared with those of the Jacobi algorithm. We further prove that, after preconditioning, if the off-diagonal entries of the preconditioned matrix are sufficiently small relative to its smallest diagonal entry, the relative forward error bound is independent of the condition number of the original matrix. We present two constructions for the preconditioner that exploit low precision, along with their error analyses. Our numerical experiments confirm our theoretical results and compare the relative forward error of the proposed algorithm with the Jacobi algorithm, a preconditioned Jacobi algorithm, and MATLAB's eig function. Timings using Julia suggest that the dominant cost of obtaining this level of accuracy comes from the high precision matrix-matrix multiplies; if support in software or hardware for this were improved, then this would become a negligible cost. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 189326379 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Computing Accurate Eigenvalues using a Mixed-Precision Jacobi Algorithm. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Higham%2C+Nicholas+J%2E%22">Higham, Nicholas J.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> highamnj@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Tisseur%2C+Françoise%22">Tisseur, Françoise</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> Francoise.Tisseur@manchester.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Webb%2C+Marcus%22">Webb, Marcus</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> marcus.webb@manchester.ac.uk</i><br /><searchLink fieldCode="AR" term="%22Zhou%2C+Zhengbo%22">Zhou, Zhengbo</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> zhengbo.zhou@postgrad.manchester.ac.uk</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Matrix+Analysis+%26+Applications%22">SIAM Journal on Matrix Analysis & Applications</searchLink>. 2025, Vol. 46 Issue 4, p2423-2448. 26p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Eigenvalues%22">Eigenvalues</searchLink><br /><searchLink fieldCode="DE" term="%22Jacobi+method%22">Jacobi method</searchLink><br /><searchLink fieldCode="DE" term="%22Empirical+research%22">Empirical research</searchLink><br /><searchLink fieldCode="DE" term="%22Matrix+multiplications%22">Matrix multiplications</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Numerical+analysis%22">Numerical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Approximation+error%22">Approximation error</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: We provide a rounding error analysis of a mixed-precision preconditioned Jacobi algorithm, which uses low precision to compute the preconditioner, applies it at high precision (amounting to two matrix-matrix multiplications), and solves the eigenproblem using the Jacobi algorithm at working precision. Our analysis yields meaningfully smaller relative forward error bounds for the computed eigenvalues compared with those of the Jacobi algorithm. We further prove that, after preconditioning, if the off-diagonal entries of the preconditioned matrix are sufficiently small relative to its smallest diagonal entry, the relative forward error bound is independent of the condition number of the original matrix. We present two constructions for the preconditioner that exploit low precision, along with their error analyses. Our numerical experiments confirm our theoretical results and compare the relative forward error of the proposed algorithm with the Jacobi algorithm, a preconditioned Jacobi algorithm, and MATLAB's eig function. Timings using Julia suggest that the dominant cost of obtaining this level of accuracy comes from the high precision matrix-matrix multiplies; if support in software or hardware for this were improved, then this would become a negligible cost. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Matrix Analysis & Applications is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=189326379 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/25M1723748 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 26 StartPage: 2423 Subjects: – SubjectFull: Eigenvalues Type: general – SubjectFull: Jacobi method Type: general – SubjectFull: Empirical research Type: general – SubjectFull: Matrix multiplications Type: general – SubjectFull: Algorithms Type: general – SubjectFull: Numerical analysis Type: general – SubjectFull: Approximation error Type: general Titles: – TitleFull: Computing Accurate Eigenvalues using a Mixed-Precision Jacobi Algorithm. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Higham, Nicholas J. – PersonEntity: Name: NameFull: Tisseur, Françoise – PersonEntity: Name: NameFull: Webb, Marcus – PersonEntity: Name: NameFull: Zhou, Zhengbo IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 10 Text: 2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 08954798 Numbering: – Type: volume Value: 46 – Type: issue Value: 4 Titles: – TitleFull: SIAM Journal on Matrix Analysis & Applications Type: main |
| ResultId | 1 |
