\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram} \setcounter{tocdepth}{1} \usepackage{../xups24} \graphicspath{{xups24-03_figures}} \usepackage[french,onelanguage,ruled,shortend,algosection,norelsize]{algorithm2e} \SetAlTitleFnt{textsc} \SetKwSty{texttt} \SetAlgoLined \let\code\textsf \hyphenation{topo-lo-gi-que appli-ca-tion appli-ca-tions inter-nes défi-ni-tion direc-te autre-ment modu-les dimen-sion inter-val-le degré} %\XUPScorrections \begin{document} \frontmatter \title{Théorie de la persistance (1/2): structure} \author{\firstname{Steve} \lastname{Oudot}} \address{Inria Saclay - Ile-de-France \& École polytechnique, Bât. Alan Turing, 1 rue Honoré d'Estienne d'Orves, 91120 Palaiseau} \email{steve.oudot@inria.fr} \urladdr{https://geometrica.saclay.inria.fr/team/Steve.Oudot/} %\thanks{Journées X-UPS 2024. Introduction à l'analyse de données. Éditions de l'École polytechnique, 2024} \begin{abstract} Dans ce texte nous utilisons l’homologie pour introduire formellement la théorie de la persistance, notamment dans ses \hbox{aspects} algébriques. Nous présentons ses principaux objets d’étude, appelés modules de persistance, et nous étudions leurs propriétés de décomposition. Ces décompositions forment la base des descripteurs utilisés en analyse topologique de données, appelés codes-barres ou diagrammes de persistance.\end{abstract} \maketitle \tableofcontents \mainmatter La théorie de la persistance s'applique à deux niveaux en parallèle: au niveau topologique, sur des filtrations d'espaces topologiques; au~niveau algébrique, sur les modules induits en homologie, appelés \emph{modules de persistance}. Le c\oe ur de la théorie se situe au niveau algébrique et les modules de persistance sont son principal objet d'étude. Dans ce texte on s'attachera essentiellement à leurs propriétés de décomposition et au calcul des \emph{codes-barres} induits, tandis que dans le texte suivant on regardera leurs propriétés de stabilité. Dans ce texte on fixe un corps~$\field$ et un ensemble totalement ordonné~$(T, \leq)$. \section{Filtrations d'espaces topologiques} Rappelons d'abord le concept classique de filtration d'espaces topologiques et donnons quelques exemples clés pour l'analyse topologique de données. \begin{definition}\label{def:filt} Une \emph{filtration} d'espaces topologiques indexée par~$T$ est une famille $(X_t)_{t\in T}$ d'espaces topologiques imbriqués au sens que $X_t\subseteq X_{t'}$ pour tous $t\leq t'\in T$. \end{definition} \begin{exemple}\label{ex:filt-sublevel} Étant donné un espace topologique~$X$ et une fonction $f\colon X\to\R$, tous deux quelconques, la famille des \emph{sous-niveaux} $F_t=f^{-1}\left( ]-\infty, t]\right)$ forme une filtration indexée par~$T=\R$ muni de l'ordre usuel sur les réels. De manière duale, comme vu dans le texte~\cite{chap-intro}, la famille des \emph{sur-niveaux} $F^t=f^{-1}\left([t, +\infty[\right)$ forme une filtration indexée par $T=\R$ muni de l'ordre opposé. \end{exemple} \begin{definition}\label{def:filt_simp} Une filtration $(X_t)_{t\in T}$ est dite \emph{simpliciale} si chaque espace $X_t$ est un complexe simplicial et un sous-complexe de $X_{t'}$ pour tout $t'\geq t$ dans l'ensemble~$T$. \end{definition} \begin{figure}[t] \centering \includegraphics[width=\textwidth]{filt_simp} \caption{En haut: une fonction réelle $f$ sur un complexe simplicial~$X$. En bas: la filtration (simpliciale) des sous-niveaux de~$f$, restreinte aux indices $\{1, 2, 3, 4, 5\}$.} \label{fig:filt_simp} \end{figure} \begin{exemple} Étant donné un complexe simplicial~$X$ et une fonction $f\colon X\to\R$ qui associe un réel à chaque simplexe de~$X$, la filtration des sous-niveaux de~$f$ est simpliciale. Voir la figure~\ref{fig:filt_simp} pour une illustration. \end{exemple} \section{Modules de persistance} Comme dit en introduction de ce texte, les modules de persistance sont le principal objet d'étude de la théorie de la persistance. \begin{definition}\label{def:module_pers} Un \emph{$\field$-module de persistance indexé par~$T$}, ou simplement \emph{module de persistance} lorsque le corps~$\field$ et l'ensemble d'indexation~$T$ sont clairs dans le contexte, est une famille $(M_t)_{t\in T}$ de $\field$\nobreakdash-espa\-ces vectoriels reliés par des applications $\field$-linéaires $m_{t,t'}\colon M_t\to\nobreak M_{t'}$ pour tous $t\leq t'\in T$ telles que: \[ \begin{cases} m_{t,t}= \id_{M_t} & \forall t\in T,\\ m_{t,t''}= m_{t',t''} \circ m_{t,t'} & \forall t\leq t'\leq t'' \in T. \end{cases} \] Les espaces $M_t$ et les applications $m_{t,t'}$ sont appelés respectivement \emph{espaces internes} et \emph{applications internes} au module~$M$. \end{definition} Le cas d'usage typique des modules de persistance en analyse topologique de données est le suivant: \begin{lemme}\label{lem:filt-homology} Pour toute filtration $(X_t)_{t\in T}$ et tout degré~$k$ en homologie, la famille des groupes d'homologie $(H_k^{\mathrm{sing}}(X_t))_{t\in T}$, reliés par les applications linéaires $(\iota_{t,t'})_*$ induites par les inclusions $\iota_{t,t'}\colon X_t\hookrightarrow X_{t'}$, forme un module de persistance indexé par~$T$. Celui-ci est appelé le \emph{module de persistance induit} par $(X_t)_{t\in T}$ en homologie de degré~$k$. \end{lemme} \begin{proof} Découle directement de la fonctorialité de l'homologie. \end{proof} \begin{exemple}\label{ex:mod_pers} Le module de persistance induit en homologie de degré~$1$ par la filtration simpliciale de la figure~\ref{fig:filt_simp} restreinte aux indices $\{1, 2, 3, 4, 5\}$ est le suivant: \[ \xymatrix@C=1.2cm{ \field\ar[r]^-{\left(\begin{smallmatrix}1\\0\end{smallmatrix}\right)} & \field^2 \ar[r]^-{\left(\begin{smallmatrix}0&1\end{smallmatrix}\right)} & \field \ar[r]^-{\left(\begin{smallmatrix}0\\1\end{smallmatrix}\right)} & \field^2 \ar[r]^-{\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right)} & \field^2 } \] Notons que seules les applications internes reliant deux espaces internes successifs sont explicitées ici, les autres se déduisent par composition. La représentation matricielle des applications internes dépend du choix des bases pour les groupes d'homologie: ici on a pris les cycles minimaux entourant chaque ``trou'' dans le complexe simplicial pour former les bases. \end{exemple} \begin{definition}\label{def:submodule} Un module de persistance~$N$ est un \emph{sous-module} d'un autre module de persistance~$M$, noté $N\subseteq M$, si $N_t$ est un sous-espace vectoriel de~$M_t$ pour tout~$t\in T$, et si $n_{t,t'}$ est la restriction de~$m_{t,t'}$ à~${N_t}$ pour tous $t\leq t' \in T$. \end{definition} \begin{definition}\label{def:module_morph} Un \emph{morphisme de $\field$-modules de persistance} \hbox{$\phi\colon M\to N$} est une famille d'applications $\field$-linéaires $\left(\phi_t\colon M_t \to N_t\right)_{t\in T}$ telles que le diagramme suivant commute pour tous $t\leq t'\in T$: \[ \xymatrix@C=1.2cm{ M_t \ar^-{m_{t,t'}}[r]\ar_-{\phi_t}[d] & M_{t'} \ar^-{\phi_{t'}}[d] \\ N_t \ar_-{n_{t,t'}}[r] & N_{t'} } \] \end{definition} On a en particulier un \emph{morphisme identité} pour chaque module de persistance~$M$, noté $\id_M$ et défini point à point par $(\id_M)_t =\id_{M_t}$. On a également un \emph{morphisme nul} $M\stackrel{0}{\longrightarrow} N$ entre toute paire de modules de persistance~$M,N$, défini point à point par l'application linéaire nulle. La composition des morphismes de modules de persistance, quant à elle, est définie point à point par la composition des applications linéaires: \begin{definition}\label{def:module_comp} Pour tous morphismes de modules de persistance $L \stackrel{\phi}{\longrightarrow} M \stackrel{\psi}{\longrightarrow} N$ indexés par~$T$, la \emph{composée} $\psi \circ \phi$ est définie par: \[ (\psi\circ \phi)_t \ = \ \psi_t\circ \phi_t \quad \forall t\in T. \] \end{definition} La composition est donc associative, du fait de l'associativité de la composition des applications linéaires. De plus, pour tout morphisme $\phi\colon M\to N$ on a $\phi\circ\id_M = \id_N\circ \phi= \phi$, ainsi les morphismes identités associés aux modules de persistance forment l'identité pour la composition. \section{Le point de vue de la théorie des catégories} \label{sec:cat} Les définitions ci-dessus peuvent être reformulées de manière très succincte en utilisant le langage de la théorie des catégories. On peut en effet voir l'ensemble totalement ordonné~$T$ comme une catégorie (notée~$\sfT$), avec un objet par élément $t\in T$ et un unique morphisme par paire d'éléments comparables $t\leq t' \in T$. La définition~\ref{def:module_pers} revient alors à dire que les modules de persistance sont des foncteurs de~$\sfT$ dans la catégorie des $\field$-espaces vectoriels, notés $\sfT\to \Vect_{\field}$, tandis que la définition~\ref{def:module_morph} revient à dire que les morphismes entre modules de persistance sont les transformations naturelles entre foncteurs $\sfT\to \Vect_{\field}$, dont la composition se fait point à point comme rappelé dans la définition~\ref{def:module_comp}. Ensemble, ces éléments nous disent que les modules de persistance forment une catégorie de foncteurs. Au-delà de ce langage, la théorie des catégories fournit un ensemble d'outils et de résultats fondamentaux sur lesquels nous pouvons nous appuyer pour justifier les diverses propriétés des modules de persistance. En premier lieu, il est bien connu que les foncteurs à valeurs dans une catégorie abélienne comme~$\Vect_{\field}$ forment eux-mêmes une catégorie abélienne, avec les implications suivantes dans notre cas: \begin{itemize} \item pour tous modules de persistance $M,N$, l'ensemble des morphismes $M\to N$ forme un groupe abélien; de plus, la composition des morphismes de modules de persistance est bilinéaire; \item il existe un (unique) module de persistance, appelé \emph{zéro-module de persistance} et noté~$0$, qui a la propriété que tout morphisme $M\to 0$ ou $0\to N$ est nul, et qui se définit comme ayant tous ses espaces internes et toutes ses applications internes nuls; \item le produit et la somme directe de modules de persistance existent et sont définis point à point comme dans la définition~\ref{def:direct-sum} ci-dessous; \item tout morphisme de modules de persistance admet un noyau et un conoyau, définis point à point comme dans la définition~\ref{def:kernel_image_cokernel} ci-dessous; de plus, un morphisme~$\phi$ est simplifiable à gauche pour la composition ($\phi\circ \psi = \phi \circ\psi' \Rightarrow \psi=\psi'$) si et seulement si son noyau est nul; de manière similaire, $\phi$ est simplifiable à droite si et seulement si son conoyau est nul. \end{itemize} Ainsi, on peut manipuler les modules de persistance et les morphismes qui les relient un peu à la manière des espaces vectoriels et des applications linéaires. D'ailleurs, la théorie de la persistance contient celle des espaces vectoriels puisque la catégorie des modules de persistance indexés par un ensemble singleton (par exemple $T=\{1\}$) est équivalente à celle des espaces vectoriels, chaque module dans ce cas étant formé d'un unique espace interne et chaque morphisme entre modules étant formé d'une unique application linéaire. \begin{definition}\label{def:direct-sum} Étant donnés deux modules de persistance~$M,N$, leur \emph{somme directe} $M\oplus N$ est définie point à point, c'est-à-dire que $(M \oplus\nobreak N)_t = M_t \oplus N_t$ pour tout $t\in T$, et $mn_{t,t'} = m_{t,t'} \oplus n_{t,t'}$ pour tous $t\leq t'\in T$, où $(mn_t)_{t\in T}$ désigne la famille d'applications internes au module $M\oplus N$. \end{definition} \begin{definition}\label{def:kernel_image_cokernel} Pour tout morphisme de modules de persistance $\phi\colon M\to N$, le noyau~$\ker\phi$, l'image~$\im \phi$ et le conoyau~$\coker \phi$ sont tous trois définis point à point de la manière suivante (décrite pour le noyau et analogue pour l'image et le conoyau): \begin{itemize} \item pour tout $t\in T$, l'espace $(\ker \phi)_t$ est défini comme étant $\ker \phi_t$; \item pour tous $t\leq t' \in T$, l'application interne $(\ker \phi)_t \to (\ker \phi)_{t'}$ est définie comme étant la restriction de $m_{t,t'}$ à $\ker \phi_t$. \end{itemize} \end{definition} Un morphisme $\phi\colon M\to N$ est appelé \emph{monomorphisme} lorsqu'il est simplifiable à gauche pour la composition, ce qui, comme on l'a vu plus haut, revient à dire que $\ker \phi=0$ (\ie $\ker \phi_t=0$ pour tout $t\in T$). De manière similaire, $\phi$ est appelé \emph{épimorphisme} lorsqu'il est simplifiable à droite, ce qui revient à dire que $\coker \phi=0$ (\ie $\coker \phi_t=0$ pour tout $t\in T$). Enfin, $\phi$ est appelé \emph{isomorphisme} lorsque $\ker \phi = 0 = \coker \phi$, et dans ce cas les modules $M$ et $N$ sont dits \emph{isomorphes}, noté $M\cong N$. \section{Le point de vue de l'algèbre commutative} \label{sec:alg_comm} Nous allons maintenant justifier l'usage du terme \emph{module} dans la dénomination des modules de persistance. Il s'avère en effet que, sous certaines conditions, les modules de persistance peuvent être vus comme des modules sur des algèbres. Cela provient de résultats plus généraux de plongement des catégories abéliennes dans des catégories de modules. Pour simplifier l'exposé nous allons nous concentrer sur le cas particulier où l'ensemble totalement ordonné~$T$ est fini: dans ce cas, les modules de persistance peuvent être vus comme des modules sur l'algèbre des polynômes à une variable à coefficients dans~$\field$. Supposons donc que $T$ est fini, et même, sans perte de généralité, que $T = \{0, 1,\dots, \ell\}\subset\N$. Soit $M$ un module de persistance indexé par~$T$. On l'étend d'abord en un module de persistance~$M'$ indexé par~$\N$ en posant \[ \begin{cases} M'_t = M_{\min\{t,\ell\}} & \forall t\in\N, \\ m'_{t,t'} = m_{\min\{t,\ell\}, \min\{t',\ell\}} & \forall t\leq t' \in\N. \end{cases} \] On vérifie aisément que $M'$ est bien un module de persistance. On~considère ensuite le $\field$-espace vectoriel \[ \bar M = \bigoplus_{t=0}^\infty M'_t \] que l'on munit d'une structure de module à gauche sur $\field[x]$ en posant \[ x\cdot (\alpha_0,\, \alpha_1,\, \alpha_2,\, \cdots)\quad =\quad (0,\, m'_{0,1}(\alpha_0),\, m'_{1,2}(\alpha_1),\, \cdots) \] pour tout élément $(\alpha_0,\, \alpha_1,\, \alpha_2,\, \cdots)$ de $\bar M$. La structure de module est complétée par composition et linéarité, et l'on observe que c'est en fait une structure de module $\N$-gradué sur l'algèbre $\field[x]$ (elle-même $\N$-graduée) dont la composante de degré~$t$ est~$M'_t$. Ainsi on envoie les modules de persistance indexés par~$T$ dans les modules $\N$-gradués sur $\field[x]$. On peut montrer que cette opération induit un plongement de catégorie abélienne, ce qui en pratique signifie que l'on peut sans problème traiter les modules de persistance comme des modules sur l'algèbre des polynômes et utiliser des outils de l'algèbre commutative pour les étudier. On en verra un exemple dans la prochaine section. \section{Décomposition des modules de persistance} \label{sec:decomp} L'une des questions fondamentales qui se posent à nous est celle de la classification des modules de persistance à isomorphisme près. Pour y répondre nous allons énoncer un théorème de structure (théorème~\ref{thm:decomp}) qui décompose les modules de persistance en somme directe de modules structurellement très simples, les \emph{modules intervalles} (définition~\ref{def:interval_module}). C'est de ces décompositions que seront issus nos codes-barres (définition~\ref{def:decomp_barcode}), qui, du fait de ce résultat structurel, forment un invariant complet des modules de persistance. \begin{definition}\label{def:decomp} Si un module de persistance~$M$ se décompose (à isomorphisme près) en une somme directe $M\cong L \oplus N$ dont les deux termes sont non nuls, alors on dit que $M$ est \emph{décomposable} et les termes $L, N$ sont appelés des \emph{facteurs de~$M$}. Si au contraire il n'existe pas de décomposition de~$M$ de ce type, alors on dit que $M$ est \emph{indécomposable}. \end{definition} Comme on l'a vu à la section~\ref{sec:cat}, les modules de persistance sont équivalents aux espaces vectoriels lorsque l'ensemble d'indexation~$T$ est un singleton, donc leur décomposition dans ce cas très particulier est facile. Dans le cas général en revanche, la question est beaucoup plus complexe, et pour s'en convaincre il suffit de savoir que les modules de persistance ne sont alors généralement plus semi-simples, c'est-à-dire que tous leurs sous-modules ne sont pas des facteurs (autrement dit, il n'y a pas d'analogue du théorème de la base incomplète). Voici un exemple. \begin{exemple}\label{ex:not_semi-simple} Prenons le module de persistance $\field \stackrel{\hspace{-3pt}\id_\field}{\longrightarrow} \field$ indexé sur l'ensemble~$T=\{1,2\}$. Ce module admet $0 \longrightarrow \field$ comme sous-module mais pas comme facteur. En effet, si c'était un facteur alors, par additivité de la dimension, tout supplémentaire devrait avoir dimension~$1$ à l'indice~$1$ et dimension~$0$ à l'indice~$2$ et serait donc isomorphe à $\field\to 0$. Or, ce dernier ne peut être un sous-module de~$M$ car $\id_{\field}$ envoie $\field$ sur $\field$ et non pas sur~$0$. \end{exemple} Le bon côté des choses est que, sous certaines hypothèses, les modules de persistance indécomposables sont structurellement très simples. On les appelle des \emph{modules intervalles}. \begin{definition}\label{def:interval_module} Un \emph{intervalle} est un sous-ensemble~$I$ de~$T$ qui est convexe pour l'ordre, c'est-à-dire que pour tous $t\leq t' \leq t''\in T$ tels que $t,t''\in I$ on a $t'\in I$. Le \emph{module intervalle}~$\field_I$ associé à~$I$ est défini point à point par\vspace*{-3pt}\enlargethispage{\baselineskip} \[ (\field_I)_t = \begin{cases} \field & \text{si}\ t\in I, \\ 0 & \text{sinon,} \end{cases} \] avec pour application interne $(\field_I)_t\to (\field_I)_{t'}$ l'identité de $\field$ si $t,t' \in I$ et l'application nulle sinon. $I$ est appelé le \emph{support} de~$\field_I$. \end{definition} Par exemple, les modules de persistance impliqués dans l'exem\-ple~\ref{ex:not_semi-simple} sont tous des modules intervalles. \begin{exercice} Montrer que les modules intervalles sont indécomposables. \end{exercice} Il existe tout un éventail de résultats de décomposition en somme directe des modules de persistance. Le résultat ci-dessous est le plus couramment employé. Il fait l'hypothèse que le module de persistance considéré est pdf: \begin{definition}\label{def:pfd} Un module de persistance~$M$ est \emph{point à point de dimension finie} (pdf) si $\dim M_t<+\infty$ pour tout indice $t\in T$. \end{definition} \begin{theoreme}[décomposition]\label{thm:decomp} Tout module de persistance pdf~$M$ indexé par un ensemble totalement ordonné~$T$ se décompose en une somme directe (potentiellement avec un nombre infini de termes au total, mais point à point finie) dont chaque terme est un module intervalle. Cette décomposition est unique à isomorphisme et réordonnancement près des termes. \end{theoreme} \begin{exemple} Le module de persistance~$M$ de l'exemple~\ref{ex:mod_pers}, indexé par $T=\{1, 2, 3, 4, 5\}$, se décompose comme suit:\vspace*{-3pt} \[ M \cong \field_{\{1,2\}} \oplus \field_{\{2, 3, 4, 5\}} \oplus \field_{\{4,5\}} \] Dans ce cas particulier la décomposition se lit directement dans les matrices des applications internes de~$M$, qui sont diagonales. Dans le cas général toutefois, les matrices n'ont pas de raison d'être diagonales mais le théorème de décomposition dit en substance qu'il existe une famille de bases pour les espaces internes de~$M$ qui sont compatibles entre elles au sens qu'elles rendent les matrices diagonales. \end{exemple} \begin{remarque}\label{rem:int_general} Lorsque $T=\R$, les intervalles supports des facteurs dans la décomposition peuvent être ouverts, semi-ouverts, ou fermés. Ceci contraste avec les intervalles du texte~\cite{chap-intro}, que l'on avait forcés à être semi-ouverts à gauche par convention. \end{remarque} L'unicité de la décomposition dans le théorème~\ref{thm:decomp} implique en particulier celle des intervalles supports des facteurs, avec lesquels on peut ainsi former le \emph{code-barres} du module. \begin{definition}\label{def:decomp_barcode} Pour un module de persistance pdf~$M$, le \emph{code-barres} de~$M$, noté $\barcode(M)$, est le multi-ensemble des intervalles supports des facteurs dans la décomposition de~$M$. Lorsque $T=\R$ muni de l'ordre usuel, le \emph{diagramme de persistance}, noté~$D(M)$, est le multi-ensemble de points $(a,b)$ dans le plan étendu $\R\times ]-\infty, +\infty]$ correspondant aux intervalles $[a,b]$, $]a,b]$, $]a,b[$ ou $]a,b[$ de~$\barcode(M)$. \end{definition} Le théorème de décomposition implique que le code-barres est un invariant complet pour les modules de persistance pdf indexés par~$T\subseteq\R$. La nature purement géométrique du code-barres en fait un outil idéal pour, d'une part, l'interprétation visuelle de la structure du module, et d'autre part, la comparaison de cette structure avec celles d'autres modules. On verra en effet dans le texte~\cite{sec-stabilite} que l'on peut définir une distance naturelle entre modules de persistance, que les codes-barres permettent de calculer exactement. \begin{remarque} Ici on ne définit le diagramme de persistance que dans le cas où~$T=\R$ car dans le cas général les extrémités (ouvertes ou fermées) des intervalles ne sont pas toujours définies de manière unique. Notons par ailleurs suite à la remarque~\ref{rem:int_general} que, dans le cas où $T=\R$, le diagramme de persistance n'est plus équivalent au code-barres car il perd l'information sur le caractère ouvert, semi-ouvert ou fermé des intervalles. En particulier, le diagramme de persistance n'est pas un invariant complet des modules de persistance pdf. \end{remarque} \begin{remarque}\label{rem:pers_bonne-approche} Dans le contexte de l'exemple~\ref{ex:filt-sublevel}, le lemme~\ref{lem:filt-homology} nous fournit un module de persistance par degré en homologie pour la filtration des sur-niveaux d'une fonction $f\colon X\to\R$ quelconque. Le~théorème~\ref{thm:decomp} assure alors que ce module de persistance a un code-barres bien défini, à la seule condition que les groupes d'homologie des sur-niveaux de~$f$ soient de dimension finie. Dans le cas particulier de l'homologie de degré~$0$, cette hypothèse revient à dire que les sur-niveaux de~$f$ ont chacun un nombre fini de composantes connexes par arc. Cette condition est beaucoup moins restrictive que celles que nous avons dû énoncer dans le texte~\cite{chap-intro}. En particulier, à~présent le code-barres encode les intervalles de persistance de toutes les composantes connexes par arc dans les sur-niveaux de~$f$, et non plus seulement de celles engendrées par les pics de la fonction.\vspace*{-.5\baselineskip} \end{remarque} \enlargethispage{2\baselineskip}% \subsection*{Origine du théorème de décomposition dans le cas où $T$ est fini} Supposons que $T$ est fini, égal à $\{0, 1,\dots, \ell\}$ sans perte de généralité. Comme nous l'avons vu dans la section~\ref{sec:alg_comm}, on peut envoyer tout module de persistance~$M$ sur un module $\N$-gradué~$\bar M$ sur l'algèbre graduée des polynômes~$\field[x]$, et cette opération définit un plongement de catégorie abélienne. Cela implique que l'on peut décomposer~$\bar M$ en tant que module $\N$-gradué sur $\field[x]$ puis en déduire une décomposition de~$M$ en tant que module de persistance. C'est ce que nous allons faire maintenant. Soit donc un module de persistance~$M$ pdf indexé par~$T$. Dans la construction du module de persistance~$M'$ indexé par~$\N$ donnée à la section~\ref{sec:alg_comm}, remarquons que les applications internes deviennent des isomorphismes au-delà de l'indice~$\ell$. En conséquence, les morphismes de transition entre les degrés au-delà du degré~$\ell$ dans~$\bar M$ sont des isomorphismes, ce qui implique que $\bar M$ est de type fini en tant que module gradué sur l'anneau $\field[x]$. Ce dernier étant euclidien, on peut décomposer~$\bar M$ en utilisant le théorème des facteurs invariants, ou~plutôt sa version graduée\footnote{Une preuve constructive classique du théorème des facteurs invariants dans le cas d'un anneau euclidien repose sur la réduction en forme de Smith de la matrice d'une présentation finie du module. Dans le cas gradué, la preuve est identique une fois que l'on a observé que les idéaux impliqués sont tous homogènes.}, qui nous donne la décomposition suivante:\vspace*{-3pt} \[ \bar M \quad \cong \quad \bigoplus_{j\in \mathcal{J}_{\mathrm{libre}}} x^{a_j}\cdot \field[x] \quad \oplus \quad \bigoplus_{j\in \mathcal{J}_{\mathrm{torsion}}} x^{a_j}\cdot \bigl(\field[x]\ /\ x^{d_j}\cdot \field[x]\bigr). \] La première somme directe dans la décomposition est la partie libre de~$\bar M$, qui engendre les intervalles s'étendant à droite indéfiniment dans la décomposition du module de persistance~$M$, de la forme $[a_j, +\infty[{}\cap T = \{a_j,\dots, \ell\}$ avec $0\leq a_j\leq \ell$. La deuxième somme directe dans la décomposition ci-dessus est la torsion du module~$\bar M$, qui engendre le reste des intervalles dans la décomposition de~$M$, de la forme $[a_j, a_j+d_j[{} = \{a_j,\dots, a_j+d_j-1\}$ avec $0\leq a_j < a_j+d_j\leq \ell$ -- cette dernière inégalité provient du fait que les morphismes de transition au-delà du degré~$\ell$ dans~$\bar M$ sont des isomorphismes. Ainsi, le théorème~\ref{thm:decomp} dans le cas particulier où $T$ est fini découle directement du théorème des facteurs invariants. Dans le cas général, le résultat est beaucoup plus subtile et se prouve avec des outils de théorie des représentations d'algèbres développés dans les années~1970 -- voir par exemple la preuve de~\cite{crawley2015decomposition}. \section{Calcul des codes-barres} Pour faire des calculs on se place dans le cadre simplicial, avec en entrée une filtration simpliciale de longueur finie dont on suppose que chaque complexe simplicial a un nombre fini de simplexes: \[ \emptyset = X_0 \subseteq X_1\subseteq \cdots \subseteq X_\ell = X \] Sans perte de généralité, on suppose de plus que chaque inclusion $X_{i-1}\subseteq X_i$ dans la séquence correspond à l'ajout d'un unique simplexe~$\sigma_i$ dans le complexe. Notons que, du fait que les~$X_i$ sont d'honnêtes complexes simpliciaux, $\sigma_i$ n'apparaît dans la filtration qu'une fois que toutes ses faces sont apparues. Ceci ne veut toutefois pas dire que tous les sommets apparaissent en premier, puis toutes les arêtes, et ainsi de suite. Sur cette entrée nous allons calculer les code-barres des modules de persistance induits en homologie simpliciale par la filtration pour tous les degrés d'homologie à la fois. La méthode est en fait la même que celle du calcul de l'homologie simpliciale usuelle (voir la remarque~1.13 du texte~\cite{chap-homologie}), au détail important près que l'\emph{on ne peut modifier l'ordre sur les simplexes imposé par la filtration} lors de l'exécution du pivot de Gauss pour réduire les matrices des opérateurs de bord. Voici les étapes, illustrées sur un exemple dans la figure~\ref{fig:algo_pers}: \begin{figure}[t] \centering \includegraphics[width=\textwidth]{algo_pers} \caption{En haut: une fonction réelle~$f$ sur un complexe simplicial~$X$. En bas: la matrice des opérateurs de bord de tous les degrés de~$X$ (gauche), ordonnée selon les valeurs de~$f$, et sa version réduite par le pivot de Gauss (droite).} \label{fig:algo_pers} \end{figure} \begin{enumerate} \item On construit tout d'abord la matrice $D$ contenant les matrices des opérateurs de bord de tous les degrés du complexe simplicial total~$X$. Chaque simplexe $\sigma_i$ donne lieu à exactement une ligne et une colonne dans~$D$, et ces dernières sont ordonnées par indices croissants dans la filtration. En notant $d_i$ la dimension du simplexe~$\sigma_i$, l'entrée $D_{i,j}$ de la matrice est nulle si $d_i\neq d_j-1$, sinon elle est égale à la coordonnée du vecteur~$\partial_{d_j}(\sigma_j)$ le long de l'axe~$\sigma_i$ dans l'espace des chaînes~$C_{d_i}(X)$. Quand $\field=\Z/{2\Z}$, cela revient à dire que $D_{i,j}$ vaut~$1$ si~$\sigma_i$ est une face de $\sigma_j$ et $0$ sinon. \item On réduit la matrice~$D$ à une forme échelonnée en colonnes, sans changer l'ordre des lignes et des colonnes. Le \emph{pivot} d'une colonne non nulle est son entrée non nulle la plus basse (c'est-à-dire située sur la ligne d'indice le plus élevé), et la forme échelonnée a la propriété que les pivots se situent tous sur des lignes distinctes. Pour atteindre cet état, on applique une version restreinte du pivot de Gauss décrite dans l'algorithme~\ref{alg:pivot}, où $D_{\cdot, i}$ désigne la colonne de~$D$ d'indice~$i$, la~fonction $\code{pivligne}(i)$ renvoie l'indice de la ligne sur laquelle se trouve le pivot de $D_{\cdot, i}$ lorsqu'il existe et zéro sinon, enfin la fonction $\code{piv(i)}$ renvoie la valeur du pivot de $D_{\cdot, i}$ (qui existe lorsque cette fonction est appelée). \item Une fois la matrice~$D$ réduite en forme échelonnée, ses pivots définissent un appariement partiel des simplexes de~$X$, à partir duquel le code-barres de la filtration peut être déduit. Plus précisément, à tout pivot situé à l'intersection d'une ligne~$i$ et d'une colonne~$j$ correspond la paire de simplexes $(\sigma_i, \sigma_j)$, qui engendre l'intervalle $[i,j)$ en degré $d_i$ dans le code-barres. Les simplexes impliqués dans aucune paire, quant à eux, engendrent les intervalles infinis du code-barres; plus précisément, le simplexe~$\sigma_k$ engendre l'intervalle $[k,+\infty)$ en degré~$d_k$. \end{enumerate} \bgroup\smaller \begin{algorithm}[t] \KwIn{matrice $D$ de taille $\ell\times \ell$ à coefficients dans $\field$} \For{$j$ allant de $1$ à $\ell$}{ \While{$\exists i