Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913213011984384 |
|---|---|
| author | Savostianov, Anton Tudisco, Francesco Guglielmi, Nicola |
| author_facet | Savostianov, Anton Tudisco, Francesco Guglielmi, Nicola |
| contents | Techniques based on $k$-th order Hodge Laplacian operators $L_k$ are widely used to describe the topology as well as the governing dynamics of high-order systems modeled as simplicial complexes. In all of them, it is required to solve a number of least square problems with $L_k$ as coefficient matrix, for example in order to compute some portions of the spectrum or integrate the dynamical system. In this work, we introduce the notion of optimal collapsible subcomplex and we present a fast combinatorial algorithm for the computation of a sparse Cholesky-like preconditioner for $L_k$ that exploits the topological structure of the simplicial complex. The performance of the preconditioner is tested for conjugate gradient method for least square problems (CGLS) on a variety of simplicial complexes with different dimensions and edge densities. We show that, for sparse simplicial complexes, the new preconditioner reduces significantly the condition number of $L_k$ and performs better than the standard incomplete Cholesky factorization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_15492 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex Savostianov, Anton Tudisco, Francesco Guglielmi, Nicola Numerical Analysis Social and Information Networks 65F08, 05C50, 57M15, 62R40 Techniques based on $k$-th order Hodge Laplacian operators $L_k$ are widely used to describe the topology as well as the governing dynamics of high-order systems modeled as simplicial complexes. In all of them, it is required to solve a number of least square problems with $L_k$ as coefficient matrix, for example in order to compute some portions of the spectrum or integrate the dynamical system. In this work, we introduce the notion of optimal collapsible subcomplex and we present a fast combinatorial algorithm for the computation of a sparse Cholesky-like preconditioner for $L_k$ that exploits the topological structure of the simplicial complex. The performance of the preconditioner is tested for conjugate gradient method for least square problems (CGLS) on a variety of simplicial complexes with different dimensions and edge densities. We show that, for sparse simplicial complexes, the new preconditioner reduces significantly the condition number of $L_k$ and performs better than the standard incomplete Cholesky factorization. |
| title | Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex |
| topic | Numerical Analysis Social and Information Networks 65F08, 05C50, 57M15, 62R40 |
| url | https://arxiv.org/abs/2401.15492 |