Cancellation of a critical pair in discrete Morse theory and its effect on (co)boundary operators

Titel: Annulering van een kritiek paar in discrete Morse-theorie en het effect op (co)randoperatoren

1. Probleemstelling

Discrete Morse-theorie is een krachtig combinatorisch hulpmiddel om de homologiegroepen van simpliciale complexen efficiënt te berekenen. De kern van deze theorie ligt in het definiëren van een "goed" gradiëntvectorveld dat het aantal kritieke simplices minimaliseert. Dit reduceert de berekening van homologie tot het analyseren van een eenvoudigere ketencomplex (het Morse-complex).

Echter, het vinden van een optimaal gradiëntvectorveld (met het absolute minimum aan kritieke simplices) is een NP-moeilijk probleem. Een veelgebruikte strategie is het annuleren van paren kritieke simplices om een bestaand vectorveld te verbeteren. Hoewel deze techniek het aantal kritieke simplices verlaagt, heeft het een ingrijpend effect op de structuur van het vectorveld:

• Het verandert de verzameling van kritieke simplices.
• Het perturbeert (verandert) de bestaande gradiënttrajecten.

Het centrale probleem dat dit artikel aanpakt, is dat na het annuleren van een kritiek paar, de gebruiker traditioneel gedwongen is om alle nieuwe gradiënttrajecten opnieuw te tellen om de nieuwe randoperatoren (boundary operators) van het Morse-complex te berekenen. Dit opnieuw tellen is computatie-intensief en ondermijnt de efficiëntie van de methode. De auteurs stellen de vraag: Is er een directe, combinatorische manier om de nieuwe randoperatoren te berekenen op basis van de oude, zonder de nieuwe trajecten expliciet te hoeven enumereren?

2. Methodologie

De auteurs hanteren een puur combinatorische aanpak binnen de raamwerken van discrete Morse-theorie en algebraïsche topologie.

• Definities en Kader: Ze werken met een $d$-dimensionaal simpliciaal complex $\Delta$ en een toegewezen gradiëntvectorveld $V$. Ze definiëren kritieke simplices, gradiënttrajecten (V-trajecten) en hun gewichten (op basis van incidentiegetallen).
• Annuleringsproces: Ze beschouwen een annuleerbaar kritiek paar $(\sigma_0^{(k)}, \tau_0^{(k-1)})$, waarbij er een uniek traject $P_0$ bestaat van $\sigma_0$ naar $\tau_0$. Door dit paar te annuleren, ontstaat een nieuw vectorveld $W$.
• Analyse van Trajecten: In plaats van het nieuwe veld $W$ te simuleren, analyseren de auteurs de relatie tussen de trajecten in $V$ en die in $W$. Ze tonen aan dat elke $W$-traject die betrokken simplices bevat uit het geannuleerde traject $P_0$, kan worden ontbonden in combinaties van $V$-trajecten en het omgekeerde traject $P_0$.
• Lineaire Algebra: Ze vertalen de sommatie van gewichten van trajecten naar matrixoperaties. De randoperatoren worden voorgesteld als matrices waarbij de rijen en kolommen corresponderen met kritieke simplices.

3. Belangrijkste Bijdragen en Resultaten

Het hoofddoel van het artikel is het afleiden van een expliciete formule voor de gewijzigde randoperatoren ($\partial^W$) na annulering, uitgedrukt in termen van de oorspronkelijke operatoren ($\partial^V$).

Hoofdstelling (Theorema 1.1):
Laat $\partial^V_q$ en $\partial^W_q$ de $q$-de randafbeeldingen zijn voor respectievelijk de vectorvelden $V$ en $W$ (na annulering van het paar $(\sigma_0, \tau_0)$). Dan geldt:

1. Onveranderde dimensies: Voor $q > k+1$ of $q < k-1$ blijft de operator onveranderd: $\partial^W_q = \partial^V_q$.
2. Dimensie $k+1$: De operator $\partial^W_{k+1}$ is gelijk aan $\partial^V_{k+1}$, maar met de kolom die correspondeert met het geannuleerde simplex $\sigma_0$ verwijderd.
3. Dimensie $k-1$: De operator $\partial^W_{k-1}$ is de restrictie van $\partial^V_{k-1}$ tot de subgroep die de overgebleven kritieke simplices omvat (met $\tau_0$ verwijderd).
4. Dimensie $k$ (De kern van de bijdrage): Voor de operator op dimensie $k$, die de relatie legt tussen de overgebleven $k$-simplices en $(k-1)$-simplices, geldt een specifieke transformatie.
   • Laat $B$ de matrix zijn van $\partial^V_k$, met rijen geïndexeerd door $\tau_0, \dots, \tau_m$ en kolommen door $\sigma_0, \dots, \sigma_n$.
   • De nieuwe matrix $B'$ (voor $\partial^W_k$) wordt verkregen door een reeks elementaire rijoperaties op $B$ uit te voeren:
     • Eerst wordt de eerste rij (voor $\tau_0$) genormaliseerd (aangezien $a_{00} = \pm 1$).
     • Vervolgens wordt voor elke andere rij $i \geq 1$ de volgende operatie uitgevoerd: $R_i \leftarrow R_i - a_{i0} \cdot a_{00} \cdot R_0$.
   • De uiteindelijke matrix voor $\partial^W_k$ is de submatrix van $B'$ waarbij de 0-de rij en de 0-de kolom zijn verwijderd.

Formule:
Als $\partial^V_k(\sigma_j) = \sum_{i=0}^m a_{ij} \tau_i$, dan is voor $j \geq 1$:
$$\partial^W_k(\sigma_j) = \sum_{i=1}^m (a_{ij} - a_{00}a_{0j}a_{i0}) \cdot \tau_i$$

Co-randoperatoren (Theorema 3.6):
De auteurs tonen aan dat een analoog resultaat geldt voor de co-randoperatoren ($\delta$) in het co-Morse-complex. Omdat de matrix van de co-randoperator de getransponeerde is van de randoperator, kunnen dezelfde rijoperaties (of kolomoperaties, afhankelijk van de representatie) worden toegepast.

4. Significatie en Impact

De resultaten van dit artikel hebben aanzienlijke theoretische en praktische implicaties:

• Eliminatie van Traject-Enumeratie: De belangrijkste bijdrage is dat het niet langer nodig is om alle nieuwe gradiënttrajecten te tellen na een annulering. Dit was een grote bottleneck in eerdere implementaties.
• Efficiëntie: De berekening van de nieuwe homologiegroepen na een annulering wordt gereduceerd tot een reeks elementaire rijoperaties op de bestaande matrix. Dit is een computatie-efficiëntere operatie ($O(n^3)$ of beter) vergeleken met het opnieuw doorlopen van het complex om trajecten te vinden.
• Combinatorische Inzicht: Het artikel biedt een diep inzicht in hoe de algebraïsche structuur van het Morse-complex reageert op topologische wijzigingen (annulering). Het verbindt de geometrische veranderingen in het vectorveld direct met lineaire algebra.
• Toepasbaarheid: Deze methode maakt het mogelijk om iteratieve algoritmen voor het vinden van optimale gradiëntvectorvelden (zoals heuristieken die paren annuleren) veel sneller uit te voeren, omdat de update van de homologie-informaten lokaal en algebraïsch kan gebeuren.

Samenvattend biedt dit werk een wiskundig rigoureuze en computatie-efficiënte oplossing voor het probleem van het bijwerken van Morse-homologie na het annuleren van kritieke paren, door de brug te slaan tussen de combinatoriek van trajecten en de lineaire algebra van randoperatoren.