Polynomial and Parallelizable Preconditioning for Block Tridiagonal Positive Definite Matrices
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910956623233024 |
|---|---|
| author | Yang, Shaohui Ohtsuka, Toshiyuki Plancher, Brian Jones, Colin N. |
| author_facet | Yang, Shaohui Ohtsuka, Toshiyuki Plancher, Brian Jones, Colin N. |
| contents | The efficient solution of moderately large-scale linear systems arising from the KKT conditions in optimal control problems (OCPs) is a critical challenge in robotics. With the stagnation of Moore's law, there is growing interest in leveraging GPU-accelerated iterative methods, and corresponding parallel preconditioners, to overcome these computational challenges. To improve the performance of such solvers, we introduce a parallel-friendly, parametrized multi-splitting polynomial preconditioner framework. We first construct and prove the optimal parametrization theoretically in terms of the least amount of distinct eigenvalues and the narrowest spectrum range. We then compare the theoretical time complexity of solving the linear system directly or iteratively. We finally show through numerical experiments how much the preconditioning improves the convergence of OCP linear systems solves. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_15269 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial and Parallelizable Preconditioning for Block Tridiagonal Positive Definite Matrices Yang, Shaohui Ohtsuka, Toshiyuki Plancher, Brian Jones, Colin N. Optimization and Control Systems and Control The efficient solution of moderately large-scale linear systems arising from the KKT conditions in optimal control problems (OCPs) is a critical challenge in robotics. With the stagnation of Moore's law, there is growing interest in leveraging GPU-accelerated iterative methods, and corresponding parallel preconditioners, to overcome these computational challenges. To improve the performance of such solvers, we introduce a parallel-friendly, parametrized multi-splitting polynomial preconditioner framework. We first construct and prove the optimal parametrization theoretically in terms of the least amount of distinct eigenvalues and the narrowest spectrum range. We then compare the theoretical time complexity of solving the linear system directly or iteratively. We finally show through numerical experiments how much the preconditioning improves the convergence of OCP linear systems solves. |
| title | Polynomial and Parallelizable Preconditioning for Block Tridiagonal Positive Definite Matrices |
| topic | Optimization and Control Systems and Control |
| url | https://arxiv.org/abs/2503.15269 |