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

1. Problématique

La théorie de Morse discrète, introduite par Forman, permet de calculer efficacement les groupes d'homologie des complexes simpliciaux en réduisant le nombre de simplexes critiques via un champ de vecteurs gradient. Cependant, le calcul de l'homologie de Morse repose sur l'énumération des trajectoires gradient entre les simplexes critiques.

Le problème central abordé dans cet article est le suivant : lorsqu'on annule une paire de simplexes critiques $(\sigma, \tau)$ pour obtenir un champ de vecteurs gradient plus efficace (avec moins de points critiques), la structure des trajectoires gradient change.

• Défi actuel : Pour calculer les nouveaux opérateurs de bord après annulation, il est traditionnellement nécessaire de réénumérer toutes les nouvelles trajectoires gradient, ce qui est coûteux et complexe.
• Question de recherche : Comment déterminer explicitement les nouveaux opérateurs de bord (et de cobord) du complexe de Morse modifié en fonction des opérateurs originaux, sans avoir à recalculer les trajectoires ?

2. Méthodologie

Les auteurs adoptent une approche purement combinatoire pour résoudre ce problème. Leur méthodologie repose sur les étapes suivantes :

1. Analyse des trajectoires : Ils étudient la relation entre les trajectoires du champ de vecteurs original $V$ et celles du champ modifié $W$ (obtenu par l'annulation d'une paire critique $(\sigma_0^{(k)}, \tau_0^{(k-1)})$).
2. Décomposition des chemins : Ils démontrent que toute nouvelle trajectoire dans $W$ qui implique des simplexes de la trajectoire d'annulation $P_0$ peut être décomposée en une combinaison de trajectoires originales dans $V$ et de la trajectoire inversée $P_0$.
3. Calcul des poids : En utilisant les poids des trajectoires (définis par les nombres d'incidence), ils établissent une correspondance bijective entre les ensembles de trajectoires avant et après annulation.
4. Formulation matricielle : Ils traduisent ces relations combinatoires en opérations algébriques sur les matrices représentant les opérateurs de bord. Ils montrent que la modification des opérateurs correspond à une séquence d'opérations élémentaires sur les lignes (ou colonnes) de la matrice originale.

3. Contributions Clés et Résultats Principaux

Le résultat principal est l'énoncé du Théorème 1.1, qui fournit une formule explicite pour les opérateurs de bord modifiés $\partial^W$ en fonction des opérateurs originaux $\partial^V$.

Soit $V$ un champ de vecteurs gradient sur un complexe $\Delta$, et $(\sigma_0^{(k)}, \tau_0^{(k-1)})$ une paire critique annulable. Soit $W$ le champ résultant.

• Invariance hors de la dimension critique : Pour les dimensions $q > k+1$ ou $q < k-1$, les opérateurs de bord ne changent pas : $\partial^W_q = \partial^V_q$.
• Modification à la dimension $k+1$ : Si un simplexe critique $\beta$ de dimension $k+1$ s'écrit $\partial^V_{k+1}(\beta) = \sum b_j \sigma_j$ (où $\sigma_0$ est le simplexe annulé), alors dans $W$, le terme correspondant à $\sigma_0$ disparaît : $\partial^W_{k+1}(\beta) = \sum_{j=1}^n b_j \sigma_j$.
• Restriction à la dimension $k-1$ : L'opérateur $\partial^W_{k-1}$ est simplement la restriction de $\partial^V_{k-1}$ au sous-groupe engendré par les simplexes critiques restants (excluant $\tau_0$).
• Formule de mise à jour à la dimension $k$ (Résultat Central) :
  Pour les simplexes critiques restants $\sigma_j$ ($j \ge 1$) et $\tau_i$ ($i \ge 1$), si la matrice de bord originale $B$ (représentant $\partial^V_k$) a pour coefficients $a_{ij}$ (où $a_{ij}$ est le coefficient de $\tau_i$ dans $\partial^V_k(\sigma_j)$), alors le nouveau coefficient $a'_{ij}$ est donné par :
  $$a'_{ij} = a_{ij} - a_{00} \cdot a_{0j} \cdot a_{i0}$$
  (Note : $a_{00}$ correspond au poids de la trajectoire unique entre $\sigma_0$ et $\tau_0$, qui est $\pm 1$).

Interprétation Algébrique :
Ce résultat signifie que la matrice $\partial^W_k$ peut être obtenue à partir de $\partial^V_k$ par des opérations élémentaires de lignes (ou de colonnes) :

1. Multiplier la ligne 0 (correspondant à $\tau_0$) par $1/a_{00}$ (puisque $a_{00} = \pm 1$).
2. Soustraire de chaque ligne $i$ ($i \ge 1$) le produit de la ligne 0 par $a_{i0}$.
3. Supprimer la ligne 0 et la colonne 0 (correspondant aux simplexes $\tau_0$ et $\sigma_0$ qui ne sont plus critiques).

Extension aux opérateurs de cobord :
Le Théorème 3.6 établit un résultat analogue pour les opérateurs de cobord $\delta$ dans le complexe co-Morse. Comme la matrice de cobord est la transposée de la matrice de bord, la modification suit la même logique mais appliquée aux colonnes (ou lignes, selon la convention de transposition).

4. Signification et Impact

• Élimination du recalcul des trajectoires : La contribution la plus significative est la suppression de la nécessité d'énumérer les nouvelles trajectoires gradient après une annulation. Cela transforme un problème combinatoire potentiellement complexe en une opération algébrique simple (mise à jour de matrice).
• Efficacité computationnelle : Cette méthode permet d'implémenter des algorithmes d'annulation de paires critiques de manière itérative et efficace pour simplifier les complexes simpliciaux avant le calcul de l'homologie.
• Généralité : Les résultats sont formulés de manière purement combinatoire et s'appliquent aux complexes simpliciaux finis, offrant un cadre rigoureux pour l'optimisation des champs de vecteurs gradient.
• Lien avec l'algèbre linéaire : L'article établit un pont clair entre la géométrie combinatoire de la théorie de Morse discrète et les opérations élémentaires sur les matrices, facilitant l'intégration de ces techniques dans les logiciels de topologie computationnelle.

En résumé, cet article fournit les outils théoriques nécessaires pour mettre à jour dynamiquement la structure algébrique (homologie de Morse) d'un complexe lors de l'optimisation de son champ de vecteurs gradient, sans avoir à repartir de zéro.