Une structure de données pour maillages cartésiens creux
application à l'adaptation dynamique de maillage par multirésolution
La multirésolution
Idée générale
- s'apparente à de la compression d'image
- représentation multiéchelle d'une solution
- indicateurs pour mesurer la régularité
- multirésolution (MR)
- par valeurs moyennes
- par valeurs ponctuelles
Exemple
Prenons un domaine $\Omega \in [0, 1] \times [0, 1]$.
Pour un niveau $l$ donné, une cellule $C^l_{i,j}$ est donnée par $[2^{-l}i,2^{-l}(i+1)] \times [2^{-l}j,2^{-l}(j+1)]$ pour $i, j=0, \cdots, 2^j-1$.Exemple
On définit les détails
$$
d_{i,j}^l = u_{i,j}^l - \hat{u}_{i, j}^l
$$
L'ensemble des indices et des niveaux appartenant au maillage compressé
$$
\Lambda_{\epsilon_l} = \left\{ (i, j, l) \; \text{tel que} \; |d_{i,j}^l| \geq \epsilon_l
\right\}
$$
avec
$$
\epsilon_l = 2^{N_{dim}(l-l_{max})}\epsilon.
$$
taux de compression de 80%
Exemple
Calcul de la valeur prédite $\hat{u}_{i, j}^l$
- un opérateur de projection ($\mathbf{P}_{l+1\rightarrow l}$)
- un opérateur de prédiction ($\mathbf{P}_{l\rightarrow l+1}$)
moyenne
opérateur local à la cellule avec un stencil
Contrainte
$$ \mathbf{P}_{l+1\rightarrow l}\circ \mathbf{P}_{l\rightarrow l+1} = \mathit{Id} $$La structure de données
Crée le lien entre la méthode numérique,
l'algorithme
et la machine
Structure de données naïve
Courbe de Lebesgue
Les intervalles
Première construction
level: 0
y: 0
x: [0, 4[
y: 1
x: [0, 1[, [3, 4[
y: 2
x: [0, 1[, [3, 4[
y: 3
x: [0, 4[
level: 1
y: 2
x: [2, 6[
y: 3
x: [2, 6[
y: 4
x: [2, 6[
y: 5
x: [2, 6[
Passage à un stockage compressé
level: 0
x: [0, 4[ , [0, 1[ , [3, 4[ ,
[0, 1[ , [3, 4[ , [0, 4[
y: [0, 4[
offset: [0, 1, 3, 5, 6]
level: 1
x: [2, 6[ , [2, 6[ , [2, 6[ ,
[2, 6[
y: [2, 6[@0
offset: [0, 1, 2, 3, 4]
Passage à un stockage compressé
level: 0
x: [0, 4[@0, [0, 1[@4, [3, 4[@2,
[0, 1[@6, [3, 4[@4, [0, 4[@8
y: [0, 4[@0
offset: [0, 1, 3, 5, 6]
level: 1
x: [2, 6[@10, [2, 6[@14, [2, 6[@18,
[2, 6[@22
y: [2, 6[@0
offset: [0, 1, 2, 3, 4]
Passage à un stockage compressé
Les cellules utiles
Les cellules utiles
Les cellules utiles
Les cellules utiles
Opérateurs sur des ensembles
Intersection
Union
Différence
Projection
Translation
...
Opérateurs sur des ensembles
Opérateurs sur des ensembles
Opérateurs sur des ensembles
Opérateurs sur des ensembles
Opérateurs sur des ensembles
Opérateurs sur des ensembles
MuRe
MuRe
- écrit en C++
- implémente
- les intervalles
- les operateurs sur ces espaces
- flexible
- interface simple
- utilise xtensor et sa philosophie
Exemple d'utilisation pour la projection
auto expr = intersection(mesh[all_cells][level],
mesh[proj_cells][level - 1])
.on(level - 1);
expr.apply_op(projection(field));
class projection_op: ...
{
public:
template< class T >
void operator()(Dim<1>, T &field) const
{
field(level, i) =
.5 * (field(level + 1, 2 * i) + field(level + 1, 2 * i + 1));
}
template< class T >
void operator()(Dim<2>, T &field) const
{
field(level, i, j) = .25 * (field(level + 1, 2 * i, 2 * j) +
field(level + 1, 2 * i, 2 * j + 1) +
field(level + 1, 2 * i + 1, 2 * j) +
field(level + 1, 2 * i + 1, 2 * j + 1));
}
...
};
L'écriture du schéma volume fini
u = u - dt * upwind(a, u);
L'écriture du schéma volume fini
u = u - dt * upwind(a, u);
