Efficient preconditioners for solving dynamical optimal transport via interior point methods
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917570316075008 |
|---|---|
| author | Facca, Enrico Todeschi, Gabriele Natale, Andrea Benzi, Michele |
| author_facet | Facca, Enrico Todeschi, Gabriele Natale, Andrea Benzi, Michele |
| contents | In this paper we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer as $\boldsymbol{B}\boldsymbol{B}$-preconditioner. A series of numerical tests show that the $\boldsymbol{B}\boldsymbol{B}$-preconditioner is the most efficient among those presented, despite a performance deterioration in the last steps of the interior point method. It is in fact the only one having a CPU-time that scales only slightly worse than linearly with respect to the number of unknowns used to discretize the problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_00315 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Efficient preconditioners for solving dynamical optimal transport via interior point methods Facca, Enrico Todeschi, Gabriele Natale, Andrea Benzi, Michele Numerical Analysis Optimization and Control 35Q93, 49M41, 65K10, 65F08, 65F50 In this paper we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer as $\boldsymbol{B}\boldsymbol{B}$-preconditioner. A series of numerical tests show that the $\boldsymbol{B}\boldsymbol{B}$-preconditioner is the most efficient among those presented, despite a performance deterioration in the last steps of the interior point method. It is in fact the only one having a CPU-time that scales only slightly worse than linearly with respect to the number of unknowns used to discretize the problem. |
| title | Efficient preconditioners for solving dynamical optimal transport via interior point methods |
| topic | Numerical Analysis Optimization and Control 35Q93, 49M41, 65K10, 65F08, 65F50 |
| url | https://arxiv.org/abs/2209.00315 |