Nesterov's Accelerated Jacobi-Type Methods for Large-Scale Symmetric Positive Semidefinite Linear Systems.
Saved in:
| Title: | Nesterov's Accelerated Jacobi-Type Methods for Large-Scale Symmetric Positive Semidefinite Linear Systems. |
|---|---|
| Authors: | Liang, Ling1 (AUTHOR) liang.ling@u.nus.edu, Pang, Qiyuan2 (AUTHOR) qpang413@gmail.com, Toh, Kim-Chuan3 (AUTHOR) mattohkc@nus.edu.sg, Yang, Haizhao4 (AUTHOR) hzyang@umd.edu |
| Source: | SIAM Journal on Scientific Computing. 2025, Vol. 47 Issue 6, pA3494-A3515. 22p. |
| Subjects: | Jacobi method, Linear systems, Convex programming, Numerical analysis, Iterative methods (Mathematics), Parallel processing |
| Abstract: | Solving symmetric positive semidefinite linear systems is an essential task in many scientific computing problems. While Jacobi-type methods, including the classical Jacobi method and the weighted Jacobi method, exhibit simplicity in their forms and friendliness to parallelization, they are not attractive either because of the potential convergence failure or their slow convergence rate. This paper aims to showcase the possibility of improving classical Jacobi-type methods by employing Nesterov's acceleration technique that results in an accelerated Jacobi-type method with improved convergence properties. Simultaneously, it preserves the appealing features for parallel implementation. In particular, we show that the proposed method has an \(O\left (t^{-2}\right)\) convergence rate in terms of objective function values of the associated convex quadratic optimization problem, where \(t\geq 1\) denotes the iteration counter. To further improve the practical performance of the proposed method, we also develop and analyze a restarted variant of the method, which is shown to have an \(O\left ((\log_2(t))^2t^{-2}\right)\) convergence rate when the coefficient matrix is positive definite. Furthermore, we conduct appropriate numerical experiments to evaluate the efficiency of the proposed method. Our numerical results demonstrate that the proposed method outperforms the classical Jacobi-type methods and the conjugate gradient method, and shows a comparable performance as the preconditioned conjugate gradient method with a diagonal preconditioner. Finally, we develop a parallel implementation and conduct speed-up tests on some large-scale systems. Our results indicate that the proposed framework is highly scalable. [ABSTRACT FROM AUTHOR] |
| Copyright of SIAM Journal on Scientific Computing 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: 191459263 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Nesterov's Accelerated Jacobi-Type Methods for Large-Scale Symmetric Positive Semidefinite Linear Systems. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Liang%2C+Ling%22">Liang, Ling</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> liang.ling@u.nus.edu</i><br /><searchLink fieldCode="AR" term="%22Pang%2C+Qiyuan%22">Pang, Qiyuan</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> qpang413@gmail.com</i><br /><searchLink fieldCode="AR" term="%22Toh%2C+Kim-Chuan%22">Toh, Kim-Chuan</searchLink><relatesTo>3</relatesTo> (AUTHOR)<i> mattohkc@nus.edu.sg</i><br /><searchLink fieldCode="AR" term="%22Yang%2C+Haizhao%22">Yang, Haizhao</searchLink><relatesTo>4</relatesTo> (AUTHOR)<i> hzyang@umd.edu</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22SIAM+Journal+on+Scientific+Computing%22">SIAM Journal on Scientific Computing</searchLink>. 2025, Vol. 47 Issue 6, pA3494-A3515. 22p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Jacobi+method%22">Jacobi method</searchLink><br /><searchLink fieldCode="DE" term="%22Linear+systems%22">Linear systems</searchLink><br /><searchLink fieldCode="DE" term="%22Convex+programming%22">Convex programming</searchLink><br /><searchLink fieldCode="DE" term="%22Numerical+analysis%22">Numerical analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Iterative+methods+%28Mathematics%29%22">Iterative methods (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+processing%22">Parallel processing</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Solving symmetric positive semidefinite linear systems is an essential task in many scientific computing problems. While Jacobi-type methods, including the classical Jacobi method and the weighted Jacobi method, exhibit simplicity in their forms and friendliness to parallelization, they are not attractive either because of the potential convergence failure or their slow convergence rate. This paper aims to showcase the possibility of improving classical Jacobi-type methods by employing Nesterov's acceleration technique that results in an accelerated Jacobi-type method with improved convergence properties. Simultaneously, it preserves the appealing features for parallel implementation. In particular, we show that the proposed method has an \(O\left (t^{-2}\right)\) convergence rate in terms of objective function values of the associated convex quadratic optimization problem, where \(t\geq 1\) denotes the iteration counter. To further improve the practical performance of the proposed method, we also develop and analyze a restarted variant of the method, which is shown to have an \(O\left ((\log_2(t))^2t^{-2}\right)\) convergence rate when the coefficient matrix is positive definite. Furthermore, we conduct appropriate numerical experiments to evaluate the efficiency of the proposed method. Our numerical results demonstrate that the proposed method outperforms the classical Jacobi-type methods and the conjugate gradient method, and shows a comparable performance as the preconditioned conjugate gradient method with a diagonal preconditioner. Finally, we develop a parallel implementation and conduct speed-up tests on some large-scale systems. Our results indicate that the proposed framework is highly scalable. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of SIAM Journal on Scientific Computing 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=191459263 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1137/24M1673899 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 22 StartPage: A3494 Subjects: – SubjectFull: Jacobi method Type: general – SubjectFull: Linear systems Type: general – SubjectFull: Convex programming Type: general – SubjectFull: Numerical analysis Type: general – SubjectFull: Iterative methods (Mathematics) Type: general – SubjectFull: Parallel processing Type: general Titles: – TitleFull: Nesterov's Accelerated Jacobi-Type Methods for Large-Scale Symmetric Positive Semidefinite Linear Systems. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Liang, Ling – PersonEntity: Name: NameFull: Pang, Qiyuan – PersonEntity: Name: NameFull: Toh, Kim-Chuan – PersonEntity: Name: NameFull: Yang, Haizhao IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 11 Text: 2025 Type: published Y: 2025 Identifiers: – Type: issn-print Value: 10648275 Numbering: – Type: volume Value: 47 – Type: issue Value: 6 Titles: – TitleFull: SIAM Journal on Scientific Computing Type: main |
| ResultId | 1 |
