markov_modeling.md

Modélisation Markovienne d'un Mélangeur DEM

Description du projet

Ce document explique la construction d'une matrice de transition de Markov à partir de données de simulation DEM (Discrete Element Method).

Objectif

Transformer les trajectoires de particules en une chaîne de Markov discrète où:

• La matrice $P_{ij}$ représente la probabilité qu'une particule passe de l'état $i$ à l'état $j$
• Les états sont définis par la position spatiale discrétisée (grille 5×5×5 = 125 états)

---

1. Fondements Mathématiques

1.1 Chaînes de Markov

Une chaîne de Markov satisfait la propriété de Markov:

$$P(X_{t+1}=j\mathrm{\mid }{X}_t=i,X_{t-1}=i_{t-1},\mathrm{.}\mathrm{.}\mathrm{.})=P(X_{t+1}=j\mathrm{\mid }{X}_t=i)=P_{ij}P(X\_\{t+1\}\; =\; j\; |\; X\_t\; =\; i,\; X\_\{t-1\}\; =\; i\_\{t-1\},\; ...)\; =\; P(X\_\{t+1\}\; =\; j\; |\; X\_t\; =\; i)\; =\; P\_\{ij\}$$

L'état futur ne dépend que de l'état présent, pas de l'historique.

1.2 Matrice de Transition

Propriétés:

• $P_{ij} \geq 0$ (probabilités non-négatives)
• $\sum_{j} P_{ij} = 1$ (somme par ligne = 1) → stochasticité

1.3 Formule d'Estimation de $P_{ij}$

À partir des données, on estime $P_{ij}$ par comptage empirique:

$$P_{ij}=\frac{\text{nombre de transitions }i\to j}{\text{nombre total de particules parties de }i}P\_\{ij\}\; =\; \backslash frac\{\backslash text\{nombre\; de\; transitions\; \}\; i\; \backslash to\; j\}\{\backslash text\{nombre\; total\; de\; particules\; parties\; de\; \}\; i\}$$

Formulation développée:

$$P_{ij}=\frac{1}{N_i}\sum _{t=1}^T\sum _{p=1}^{N_p}{\mathbb{1}}_{s_p(t-1)=i}\cdot {\mathbb{1}}_{s_p(t)=j}P\_\{ij\}\; =\; \backslash frac\{1\}\{N\_i\}\; \backslash sum\_\{t=1\}^\{T\}\; \backslash sum\_\{p=1\}^\{N\_p\}\; \backslash mathbb\{1\}\_\{s\_p(t-1)=i\}\; \backslash cdot\; \backslash mathbb\{1\}\_\{s\_p(t)=j\}$$

où:

• $N_i = \sum_{t} \sum_p \mathbb{1}_{s_p(t-1)=i}$ (nombre de particules dans l'état $i$)
• $s_p(t)$ = état spatial de la particule $p$ au temps $t$
• $\mathbb{1}_{condition}$ = fonction indicatrice (1 si vrai, 0 sinon)

---

2. Importations

import polars as pl           # Lecture efficace des CSV
from huggingface_hub import HfFileSystem  # Accès fichiers distants
import torch                 # Calculs GPU (CUDA)
from tqdm import tqdm        # Barre de progression
import numpy as np            # Tableaux numériques
import matplotlib.pyplot as plt

Bibliothèque	Rôle
polars	Alternative rapide à pandas pour lire les CSV
huggingface_hub	Accès stockage distant via HfFileSystem
torch	Calculs tensoriels sur GPU (CUDA)
tqdm	Barres de progression
numpy	Manipulation de tableaux

---

3. Connexion au Dépôt HuggingFace

fs = HfFileSystem()
folder_path = "hf://buckets/ktongue/DEM_MCM/Output Paraview"
csv_files = sorted(fs.glob(f"{folder_path}/*.csv"))

• HfFileSystem() : Interface style système de fichiers pour HuggingFace
• fs.glob() : Retourne les chemins matching le pattern *.csv
• sorted() : Ordonne lexicographiquement (cohérence temporelle)

---

4. Étape 1: Calcul des Limites Spatiales

Objectif: Déterminer les frontières min/max en x, y, z pour discrétiser l'espace.

# Échantillonnage: 1 fichier sur 100 (limites quasi-constantes)
sample_files = csv_files[::100]

x_vals, y_vals, z_vals = [], [], []

for f in sample_files:
    with fs.open(f, "rb") as file:
        df = pl.read_csv(file)
    x_vals.extend(df["coordinates:0"].to_list())
    y_vals.extend(df["coordinates:1"].to_list())
    z_vals.extend(df["coordinates:2"].to_list())

# Calcul des min/max
xmin, xmax = min(x_vals), max(x_vals)
ymin, ymax = min(y_vals), max(y_vals)
zmin, zmax = min(z_vals), max(z_vals)

# Marge de sécurité (1mm)
margin = 0.001
xmin, xmax = xmin - margin, xmax + margin
ymin, ymax = ymin - margin, ymax + margin
zmin, zmax = zmin - margin, zmax + margin

Échantillonnage csv_files[::100]:

• 6000 fichiers → ~60 fichiers suffisent
• Les limites spatiales ne changent pas significativement

Collecte des coordonnées:

• df["coordinates:0"] : Sélectionne la colonne x
• .to_list() : Convertit en liste Python
• .extend() : Ajoute les éléments (plus efficace que append)

---

5. Étape 2: Discrétisation Spatiale

Objectif: Diviser l'espace 3D en grille régulière de cellules.

nx, ny, nz = 5, 5, 5  # Nombre de divisions par axe
n_states = nx * ny * nz  # Total = 125 états

# Taille de chaque cellule
dx = (xmax - xmin) / nx
dy = (ymax - ymin) / ny
dz = (zmax - zmin) / nz

5.1 Formule de calcul de l'indice de cellule

Pour une coordonnée $x$:

$$i_x=\lfloor \frac{x-x_{min}}{\mathrm{\Delta }x}\rfloor i\_x\; =\; \backslash left\backslash lfloor\; \backslash frac\{x\; -\; x\_\{min\}\}\{\backslash Delta\; x\}\; \backslash right\backslash rfloor$$

Même formule pour $i_y$, $i_z$.

5.2 Fonction compute_states_gpu()

def compute_states_gpu(x, y, z):
    """
    Convertit les coordonnées continues (x,y,z) en indices d'états discrets.
    
    Formule: state = ix + iy * nx + iz * nx * ny
    """
    x_tensor = torch.tensor(x, device="cuda")
    y_tensor = torch.tensor(y, device="cuda")
    z_tensor = torch.tensor(z, device="cuda")
    
    # Calcul des indices avec floor (division puis long())
    ix = ((x_tensor - xmin) / dx).long()
    iy = ((y_tensor - ymin) / dy).long()
    iz = ((z_tensor - zmin) / dz).long()
    
    # Clamp: restreint à [0, max] pour éviter out of bounds
    ix = ix.clamp(0, nx - 1)
    iy = iy.clamp(0, ny - 1)
    iz = iz.clamp(0, nz - 1)
    
    # Index linéaire (row-major order)
    return ix + iy * nx + iz * nx * ny

Détail des opérations:

1. x_tensor - xmin : Translation pour centrer à 0
2. / dx : Normalisation par la taille de cellule
3. .long() : Conversion float → int (équivalent floor)
4. .clamp(0, nx-1) : $$\text{clamp}(ix, 0, n_x-1) = \begin{cases} 0 & \text{si } ix < 0 \ n_x-1 & \text{si } ix \geq n_x \ ix & \text{sinon} \end{cases}$$

Index linéaire:

state = ix + iy * nx + iz * nx * ny

$$state=i_x+i_y\cdot n_x+i_z\cdot n_x\cdot n_{y}state\; =\; i\_x\; +\; i\_y\; \backslash cdot\; n\_x\; +\; i\_z\; \backslash cdot\; n\_x\; \backslash cdot\; n\_y$$

Exemple: Pour nx=5, ny=5, nz=5, cellule (2, 1, 0): $$state=2+1\cdot 5+0\cdot 25=7state\; =\; 2\; +\; 1\; \backslash cdot\; 5\; +\; 0\; \backslash cdot\; 25\; =\; 7$$

---

6. Étape 3: Initialisation des Tenseurs GPU

device = torch.device("cuda" if torch.cuda.is_available() else "cpu")

# transition_counts[i,j] = nombre de transitions i → j
transition_counts = torch.zeros((n_states, n_states), dtype=torch.int64, device=device)

# state_counts[i] = nombre de particules dans l'état i
state_counts = torch.zeros(n_states, dtype=torch.int64, device=device)

Explications:

• torch.zeros(shape) : Crée un tensor de zéros
• dtype=torch.int64 : Entiers 64 bits (évite overflow)
• device=device : Alloue sur GPU ou CPU

Motivation int64: 6000 timesteps × 1030 particules ≈ 6.2M transitions max.

---

7. Étape 4: Calcul des Transitions

n_files = len(csv_files)
df_prev = None
states_prev = None

for i in tqdm(range(1, n_files), desc="Processing"):
    # Lecture du fichier courant
    with fs.open(csv_files[i], "rb") as f:
        df_curr = pl.read_csv(f)
    
    ids_curr = df_curr["Particle_ID"].to_numpy()
    
    # Calcul des états sur GPU
    states_curr = compute_states_gpu(
        df_curr["coordinates:0"].to_numpy(),
        df_curr["coordinates:1"].to_numpy(),
        df_curr["coordinates:2"].to_numpy(),
    )
    
    if df_prev is not None:
        ids_prev = df_prev["Particle_ID"].to_numpy()
        
        # Identification des particules communes
        common_ids = np.intersect1d(ids_prev, ids_curr)
        
        if len(common_ids) > 0:
            # Masques pour particules communes
            prev_idx = np.isin(ids_prev, common_ids)
            curr_idx = np.isin(ids_curr, common_ids)
            
            # États avant/après
            s_prev = states_prev[prev_idx]
            s_curr = states_curr[curr_idx]
            
            # Comptage vectorisé des transitions
            transitions = torch.stack([s_prev, s_curr], dim=1)
            unique_trans, counts = torch.unique(transitions, dim=0, return_counts=True)
            
            # Accumulation des comptages
            for j in range(len(unique_trans)):
                transition_counts[unique_trans[j, 0], unique_trans[j, 1]] += counts[j]
            
            # Comptage par état d'origine
            unique_prev, _ = torch.unique(s_prev, return_counts=True)
            for u in unique_prev:
                mask = s_prev == u
                state_counts[u] += mask.sum().item()
    
    df_prev = df_curr
    states_prev = states_curr

7.1 Identification des particules communes

common_ids = np.intersect1d(ids_prev, ids_curr)

Où: ids commun = intersection(ids precedent, ids courant)

7.2 Masques booléens

prev_idx = np.isin(ids_prev, common_ids)

Retourne True pour chaque élément de ids_prev qui est dans common_ids.

7.3 Comptage vectorisé

transitions = torch.stack([s_prev, s_curr], dim=1)
unique_trans, counts = torch.unique(transitions, dim=0, return_counts=True)

Mathématiquement:

• torch.stack([a, b], dim=1) : Crée matrice [a_i, b_i] par ligne
• torch.unique(..., dim=0) : Trouve les lignes uniques
• return_counts=True : Compte les occurrences

Exemple:

s_prev = [0, 1, 0, 2, 1]
s_curr = [1, 1, 2, 2, 0]

transitions = [[0,1], [1,1], [0,2], [2,2], [1,0]]

unique_trans = [[0,1], [0,2], [1,0], [1,1], [2,2]]
counts =        [1,     1,     1,     1,     1]

7.4 Accumulation

transition_counts[unique_trans[j, 0], unique_trans[j, 1]] += counts[j]

$$C[i,j]\text{count}C[i,\; j]\; \backslash mathrel\{+=\}\; \backslash text\{count\}$$

---

8. Étape 5: Normalisation

P = torch.zeros((n_states, n_states), dtype=torch.float64, device=device)

for i in range(n_states):
    if state_counts[i] > 0:
        P[i] = transition_counts[i].float() / state_counts[i].float()

Formule de normalisation

$$P_{ij}=\frac{C[i,j]}{S[i]}P\_\{ij\}\; =\; \backslash frac\{C[i,j]\}\{S[i]\}$$

où C[i,j] = transition_counts[i,j] et S[i] = state_counts[i]

Preuve de stochasticité:

$$\sum _{j=1}^n{P}_{ij}=\frac{\sum _{j}C[i,j]}{S[i]}=\frac{S[i]}{S[i]}=1\backslash sum\_\{j=1\}^\{n\}\; P\_\{ij\}\; =\; \backslash frac\{\backslash sum\_j\; C[i,j]\}\{S[i]\}\; =\; \backslash frac\{S[i]\}\{S[i]\}\; =\; 1$$

Vérification

row_sums = P.sum(dim=1)
visited = state_counts > 0
print(f"Somme par ligne: {row_sums[visited].min():.6f} / {row_sums[visited].max():.6f}")

---

9. Étape 6: Sauvegarde

P_cpu = P.cpu().numpy()
transition_cpu = transition_counts.cpu().numpy()
state_counts_cpu = state_counts.cpu().numpy()

np.save("transition_matrix.npy", P_cpu)
np.save("transition_counts.npy", transition_cpu)
np.save("state_counts.npy", state_counts_cpu)

• .cpu() : Copie le tensor du GPU vers la mémoire CPU
• .numpy() : Convertit en array NumPy
• Format .npy : Binaire compressé, chargement rapide via np.load()

---

10. Visualisation et Analyse

10.1 Heatmap de la matrice

plt.imshow(P_cpu, cmap='Blues')
plt.colorbar(label='P_ij')
plt.xlabel('État destination (j)')
plt.ylabel('État origine (i)')

Interprétation:

• Diagonale forte : Particules qui restent dans leur cellule (mélange lent)
• Diagonale faible : Mélange rapide
• Structure de blocs : Zones préférentielles

10.2 Distribution des probabilités

P_nonzero = P_cpu[P_cpu > 0]
plt.hist(P_nonzero.flatten(), bins=50)

---

11. Propriétés Mathématiques

11.1 Vérifications

Propriété	Formule	Vérification
Non-négativité	$P_{ij} \geq 0$	np.all(P_cpu >= 0)
Stochasticité	$\sum_j P_{ij} = 1$	np.allclose(row_sums, 1.0)
Rayon spectral	$\rho(P) = 1$	np.linalg.eigvals(P_cpu)

11.2 Distribution Stationnaire

Un vecteur $\pi$ tel que:

$$\pi =\pi P\backslash pi\; =\; \backslash pi\; P$$

où $\pi_i$ = probabilité limite d'être dans l'état $i$.

eigenvalues, eigenvectors = np.linalg.eig(P_cpu.T)
stationary_idx = np.argmin(np.abs(eigenvalues - 1.0))
pi_stationary = np.abs(eigenvectors[:, stationary_idx])
pi_stationary = pi_stationary / pi_stationary.sum()

---

12. Résumé des Formules Clés

Concept	Formule
Indice cellule X	$i_x = \left\lfloor \frac{x - x_{min}}{\Delta x} \right\rfloor$
Index linéaire	$state = i_x + i_y \cdot n_x + i_z \cdot n_x \cdot n_y$
Transition	$P_{ij} = \frac{C[i,j]}{\sum_k C[i,k]}$
Stochasticité	$\sum_j P_{ij} = 1$

---

13. Utilisations Futures

La matrice de transition peut servir à:

1. Simulation: Générer trajectoires avec $X_{t+1} \sim \text{Categorical}(P[X_t,])$
2. Analyse: Calculer temps de mélange, distributions limites
3. Optimisation: Améliorer la conception du mélangeur