Engineering a Combinatorial Laplacian Solver: Lessons Learned
Linear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a t...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2016-10-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1999-4893/9/4/72 |
| _version_ | 1818025339720302592 |
|---|---|
| author | Daniel Hoske Dimitar Lukarski Henning Meyerhenke Michael Wegner |
| author_facet | Daniel Hoske Dimitar Lukarski Henning Meyerhenke Michael Wegner |
| author_sort | Daniel Hoske |
| collection | DOAJ |
| description | Linear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a theoretical perspective, but their practical performance was unclear. Here, we address this gap. We provide the first implementation of the combinatorial solver by Kelner et al. (STOC 2013), which is appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix (which is SDD) corresponds to a graph; solving symmetric Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our experiments are ambivalent. While they confirm the predicted nearly-linear running time, the constant factors make the solver much slower for reasonable inputs than basic methods with higher asymptotic complexity. We were also not able to use the solver effectively as a smoother or preconditioner. Moreover, while spanning trees with lower stretch indeed reduce the solver’s running time, we experience again a discrepancy in practice: in our experiments, simple spanning tree algorithms perform better than those with a guaranteed low stretch. We expect that our results provide insights for future improvements of combinatorial linear solvers. |
| first_indexed | 2024-12-10T04:14:33Z |
| format | Article |
| id | doaj.art-ddaac81d1abd4edf8b285ab0100f7e18 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-12-10T04:14:33Z |
| publishDate | 2016-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-ddaac81d1abd4edf8b285ab0100f7e182022-12-22T02:02:38ZengMDPI AGAlgorithms1999-48932016-10-01947210.3390/a9040072a9040072Engineering a Combinatorial Laplacian Solver: Lessons LearnedDaniel Hoske0Dimitar Lukarski1Henning Meyerhenke2Michael Wegner3Institute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, GermanyParalution Labs UG & Co. KG, D-76571 Gaggenau, GermanyInstitute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, GermanyInstitute of Theoretical Informatics, Karlsruhe Institute of Technology (KIT), Am Fasanengarten 5, D-76131 Karlsruhe, GermanyLinear system solving is a main workhorse in applied mathematics. Recently, theoretical computer scientists contributed sophisticated algorithms for solving linear systems with symmetric diagonally-dominant (SDD) matrices in provably nearly-linear time. These algorithms are very interesting from a theoretical perspective, but their practical performance was unclear. Here, we address this gap. We provide the first implementation of the combinatorial solver by Kelner et al. (STOC 2013), which is appealing for implementation due to its conceptual simplicity. The algorithm exploits that a Laplacian matrix (which is SDD) corresponds to a graph; solving symmetric Laplacian linear systems amounts to finding an electrical flow in this graph with the help of cycles induced by a spanning tree with the low-stretch property. The results of our experiments are ambivalent. While they confirm the predicted nearly-linear running time, the constant factors make the solver much slower for reasonable inputs than basic methods with higher asymptotic complexity. We were also not able to use the solver effectively as a smoother or preconditioner. Moreover, while spanning trees with lower stretch indeed reduce the solver’s running time, we experience again a discrepancy in practice: in our experiments, simple spanning tree algorithms perform better than those with a guaranteed low stretch. We expect that our results provide insights for future improvements of combinatorial linear solvers.http://www.mdpi.com/1999-4893/9/4/72Laplacian linear systemsgraph algorithmslow-stretch spanning treeselectrical graph flowsalgorithm engineering |
| spellingShingle | Daniel Hoske Dimitar Lukarski Henning Meyerhenke Michael Wegner Engineering a Combinatorial Laplacian Solver: Lessons Learned Algorithms Laplacian linear systems graph algorithms low-stretch spanning trees electrical graph flows algorithm engineering |
| title | Engineering a Combinatorial Laplacian Solver: Lessons Learned |
| title_full | Engineering a Combinatorial Laplacian Solver: Lessons Learned |
| title_fullStr | Engineering a Combinatorial Laplacian Solver: Lessons Learned |
| title_full_unstemmed | Engineering a Combinatorial Laplacian Solver: Lessons Learned |
| title_short | Engineering a Combinatorial Laplacian Solver: Lessons Learned |
| title_sort | engineering a combinatorial laplacian solver lessons learned |
| topic | Laplacian linear systems graph algorithms low-stretch spanning trees electrical graph flows algorithm engineering |
| url | http://www.mdpi.com/1999-4893/9/4/72 |
| work_keys_str_mv | AT danielhoske engineeringacombinatoriallaplaciansolverlessonslearned AT dimitarlukarski engineeringacombinatoriallaplaciansolverlessonslearned AT henningmeyerhenke engineeringacombinatoriallaplaciansolverlessonslearned AT michaelwegner engineeringacombinatoriallaplaciansolverlessonslearned |