Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization
We address the basic question in discrete Morse theory of combining discrete gradient fields that are partially defined on subsets of the given complex. This is a well-posed question when the discrete gradient field <i>V</i> is generated using a fixed algorithm which has a local nature....
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-12-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/14/12/360 |
| _version_ | 1827674465235894272 |
|---|---|
| author | Douglas Lenseth Boris Goldfarb |
| author_facet | Douglas Lenseth Boris Goldfarb |
| author_sort | Douglas Lenseth |
| collection | DOAJ |
| description | We address the basic question in discrete Morse theory of combining discrete gradient fields that are partially defined on subsets of the given complex. This is a well-posed question when the discrete gradient field <i>V</i> is generated using a fixed algorithm which has a local nature. One example is ProcessLowerStars, a widely used algorithm for computing persistent homology associated to a grey-scale image in 2D or 3D. While the algorithm for <i>V</i> may be inherently local, being computed within stars of vertices and so embarrassingly parallelizable, in practical use, it is natural to want to distribute the computation over patches <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>i</mi></msub></semantics></math></inline-formula>, apply the chosen algorithm to compute the fields <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>V</mi><mi>i</mi></msub></semantics></math></inline-formula> associated to each patch, and then assemble the ambient field <i>V</i> from these. Simply merging the fields from the patches, even when that makes sense, gives a wrong answer. We develop both very general merging procedures and leaner versions designed for specific, easy-to-arrange covering patterns. |
| first_indexed | 2024-03-10T04:40:45Z |
| format | Article |
| id | doaj.art-a03c03ae430b4535ad7982140ed2e1d7 |
| institution | Directory Open Access Journal |
| issn | 1999-4893 |
| language | English |
| last_indexed | 2024-03-10T04:40:45Z |
| publishDate | 2021-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj.art-a03c03ae430b4535ad7982140ed2e1d72023-11-23T03:24:58ZengMDPI AGAlgorithms1999-48932021-12-01141236010.3390/a14120360Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric ParallelizationDouglas Lenseth0Boris Goldfarb1Department of Mathematics and Statistics, State University of New York, Albany, NY 12222, USADepartment of Mathematics and Statistics, State University of New York, Albany, NY 12222, USAWe address the basic question in discrete Morse theory of combining discrete gradient fields that are partially defined on subsets of the given complex. This is a well-posed question when the discrete gradient field <i>V</i> is generated using a fixed algorithm which has a local nature. One example is ProcessLowerStars, a widely used algorithm for computing persistent homology associated to a grey-scale image in 2D or 3D. While the algorithm for <i>V</i> may be inherently local, being computed within stars of vertices and so embarrassingly parallelizable, in practical use, it is natural to want to distribute the computation over patches <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>P</mi><mi>i</mi></msub></semantics></math></inline-formula>, apply the chosen algorithm to compute the fields <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>V</mi><mi>i</mi></msub></semantics></math></inline-formula> associated to each patch, and then assemble the ambient field <i>V</i> from these. Simply merging the fields from the patches, even when that makes sense, gives a wrong answer. We develop both very general merging procedures and leaner versions designed for specific, easy-to-arrange covering patterns.https://www.mdpi.com/1999-4893/14/12/360discrete Morse theorygradient vector fielddistributed computation |
| spellingShingle | Douglas Lenseth Boris Goldfarb Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization Algorithms discrete Morse theory gradient vector field distributed computation |
| title | Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization |
| title_full | Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization |
| title_fullStr | Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization |
| title_full_unstemmed | Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization |
| title_short | Merging Discrete Morse Vector Fields: A Case of Stubborn Geometric Parallelization |
| title_sort | merging discrete morse vector fields a case of stubborn geometric parallelization |
| topic | discrete Morse theory gradient vector field distributed computation |
| url | https://www.mdpi.com/1999-4893/14/12/360 |
| work_keys_str_mv | AT douglaslenseth mergingdiscretemorsevectorfieldsacaseofstubborngeometricparallelization AT borisgoldfarb mergingdiscretemorsevectorfieldsacaseofstubborngeometricparallelization |