Inversion d'une transformation

[Jekub]

Bonjour,

Je bloque actuellement sur un problème de maths qui à pour origine un programme sur lequel je bosse actuellement. Je travail sur des «matrices triangulaires» que je stocke de manière linéaire.

Lorsque l'on veut stocker une matrice triangulaire, une manière simple et efficace consiste à utiliser un simple tableau et de linéariser la matrice:
- Soit mat[N][N] notre matrice telle que mat[i][j] ;) 0 uniquement si i ;) j.
- On calcul l'index par la formule : idx(i, j) = (j*(j+1))/2 + i
Avec cette méthode, la matrice suivante:
1 0 0
2 3 0
4 5 6
Sera stocker sou la forme du tableau suivant:
1 2 3 4 5 6

On peut généraliser cette méthode de stockage au cas à 3 dimensions facilement :
- Soit mat[N][N][N] notre matrice telle que mat[i][j][k] ;) 0 uniquement si i ;) j ;) k.
- On calcul l'index par la formule : idx(i, j, k) = (k*(k+1)*(k+2))/6 + (j*(j+1))/2 + i

Jusque là, aucun problème et tout marche très bien. Mon soucis est comment faire pour inverser cette transformation ?

Je dispose de l'index, je connais le nombre de dimensions (2 ou 3 uniquement dans mon cas) et je sais que les valeurs que je dois trouver sont des entiers tels que 0 ;) i ;) j ;) N ou 0 ;) i ;) j ;) k ;) N suivant les cas. Je sais aussi que la solution existe et quelle est unique mais comment la retrouver ?

Je bloque sur ce problème. Je précise que je cherche la solution sous forme de formule pour i, j et k. J'ai une solution qui utilise des boucle pour retrouver les trois valeurs mais elle n'est pas efficace et surtout peu satisfaisante.

Merci d'avance pour l'aide ou les informations que vous pourrez m'apporter.

Jekub

[fatal_error]

salut,

en 2D
on indexe à partir de i=0 ,j=1.
Les coeff sur la diagonales sont donnés en fonction de la ligne par

genre u_0 = 1
u_1 = 3
etc...
si on connait l'index que je note z, on cherche le couple (n,j) tel que l'index associé soit z.
on cherche donc n, entier, avec
cad

on vérifie que pour z de la diago (1,3,6,10) on retrouve bien les lignes (ou colonne c pareil vu qu'on est sur la diago) (0,1,2,3)
La fonction u_n est croissante, donc ya juste à chopper

ou ceil(x) désigne la partie entiere supérieure x (genre E(2)=2, E(2,35)=3)
on déduit trivialement i de


par exemple given z=8, on trouve

i = 8 - (2(2+1))/2 = 2
cad (3+1eme ligne, 2eme colonne)

[Dlzlogic]

C'est une découverte, il existe donc des matrices à 3 dimensions.

[st00pid_n00b]

Bonjour,

J'ai essayé de mon côté et je suis arrivé à un résultat similaire à fatal_error (et au fond la démarche est la même).

Un détail d'importance: j'ai supposé qu'en bon informaticien tu as indexé ton tableau à partir de 0, et fatal_error en bon mathématicien l'a indexé à partir de 1.

Soit n l'index dans le tableau. On sait que:


j est le plus grand entier vérifiant l'inégalité de gauche, et le plus petit vérifiant celle de droite.
En partant de l'inégalité de gauche:


Ce qui donne:


Puisqu'on veut le plus grand entier vérifiant ça on prend:


Puis

A 3 dimensions, ça va se compliquer, mais déjà faudrait tester si c'est vraiment plus efficace (parce qu'entre un calcul de racine carrée, et une boucle qui se contente d'ajouter des entiers...)

[Jekub]

Merci beaucoup pour vos réponses. Je vois comment faire grâce à vous.

@Dlzlogic:
J'assume parfaitement l'abus de langage qui consiste à utiliser le terme matrice même à 3-dimensions. J'avoue, j'aurais pus rester sur le terme tableau à n-dimensions ou parler de tenseurs.

Je suis désolé pour les puristes.

@st00pid_n00b:

Pour ce qui est des performances: Les tableaux en question sont particulièrement grand, j'ai N=2048 ce qui donne des tableaux d'environ 10Go. Cette représentation n'a pas été choisie par hasard, grâce à elle, pour une grosse partie des calculs j'ai juste à les parcourir dans l'ordre des index ce qui est parfaitement efficace.
Par contre, pour les quelques moments ou je dois retrouver les coordonnées à partir de l'index, vu la dimension, une boucle est loin d'être si efficace. Je viens de tester pour le cas à deux dimensions et en moyenne le calcul direct est plus rapide que la boucle.

[st00pid_n00b]

Je suis content de voir que ça améliore tes perfs. Alors en 3D, tu l'as peut être résolu mais ça donne ça:



k est le plus grand entier vérifiant l'inégalité de gauche, qui donne:


En utilisant les formules de Cardan (je te passe les détails, j'ai suivi la méthode donnée par Wikipedia) on trouve:


Cas particulier: Pour n=0, , et i=j=k=0.

Pour n>0: On pose et on a:



Ensuite, et la méthode précédente donne i et j.

C'est encore plus lourd en calculs de racines, donc à voir. Un autre problème potentiel est que lorsque i=j=k on s'approche dangereusement de l'entier supérieur avant de prendre la partie entière. Je me demande si les erreurs d'arrondi peuvent faire foirer le calcul lorsque n est grand.

[fatal_error]

j'ai pour ma part qq questions...
si j'ai bien compris tu représentes ta matrice sous forme de liste.

Mais qu'est-ce qui t'empêche de prendre une autre bijection et de numéroter différemment?
par exemple, tu prends la classique
f(i,j) = i*n + j, n la dimension de la matrice
et simplement tu concat dans ta liste les elem de la partie inférieure de la matrice
tu retrouves facilement
j = f(i,j)%n
i = (f(i,j) - j ) /n
pas de racines carrées...
le seul truc c'est qu'il faut garder trace de la dimension de la matrice, mais bon, c'est pas si vilain...

idem le cas 3d
f(i,j,k) = i*n^2+j*n+k
et
k = f(i,j,k)%n
j = (f(i,j,k)-k )%n^2
i = (f(i,j,k) - jn - k)/n^2

[Dlzlogic]

Bonjour,
Un tableau, en mémoire est toujours rangé sous forme fe liste, c'est à dire les éléments les unes à la suite des autres.
L'intérêt du tableau, c'est à dire de sa représentation, est la facilité d'adressage pour l'individu.
Si j'ai bien compris le but de la question est de faire un stockage et un adressage tel que le valeurs toujours nulles n'occupe pas une place inutile.
Si j'avais à faire ça, j'utiliserais la fonction malloc().

[st00pid_n00b]

Une autre manière de trouver k serait de stocker les valeurs de k(k+1)(k+2)/6 dans un tableau de taille N, puis de chercher par dichotomie entre quelles valeurs se trouve l'index n.

Pour N=2048 ça doit faire une dizaine de comparaisons. C'est du O(log(N)) plutôt qu'en "temps constant" mais ça devrait être plus rapide.

[Jekub]

Voila les réponses en vrac pour tout le monde :

@st00pid_n00b:

J'ai fini par arriver au même calcul que toi. Ton premier message m'ayant mis sur la piste. Les perf reste bonne et je n'ai pas de problèmes numérique grâce à une petite astuce: j'approxime la racine cubique, et j'ai préparé mon approximation pour qu'elle soit toujours légèrement inférieure à la valeur exacte. L'erreur moyenne est plus grande mais dans ce cas ça marche bien mieux.

La différence de performance face à une boucle est moins nette mais vu que le code est sans branchement cela reste plus rapide et surtout je peux le faire pour plusieurs valeur en parallèle via les instruction sse2.

@fatal_error:

La bijection est étudiée pour ne stocker explicitement que les valeurs telles (i ;) j ;) k). Les autres sont fixées à zéro et n'on pas besoin d'apparaitre explicitement.

Si tu prend le cas d'une matrice triangulaire, il y a en gros la moitié de la matrice que tu n'a pas à stocker et donc tu peux travailler sur des matrices en gros deux fois plus grandes. (pas tout à fais la moitié à cause de la diagonale)
Ici c'est pareil mais en 3 dimensions donc avec encore plus de gain à la clé.

Par contre, retrouver la valeur correspondant à (i, j, k) est simple, mais retrouver à quelle case de la matrice correspond la valeur d'indice (n) dans le tableaux est plus compliqué...

@st00pid_n00b:

L'idée est bonne et je l'ai déjà essayée mais le gros problème de cette solution est la taille de la liste. En nombre d'instructions à exécuter c'est légèrement intéressant mais ça pourri le cache des processeur et donc ce n'est pas plus rapide.

Sur un des algos que j'utilise, ça interagit même très mal avec les accès mémoire de l'algo et donne des performances dramatiques.

@tout le monde:

Merci pour votre aide et j'espère que ces quelques explication supplémentaire répondent aussi à vos questions.

[st00pid_n00b]

Salut,

Merci pour tes reponses. Ca change de resoudre un probleme qui sert a quelque chose dautre que d´avoir une bonne note au DM... Je serais curieux de savoir comment tu approximes la racine cubique, puisque lorsque i=j=0 ca doit tomber juste et il ne faut pas arrondir en dessous. (Dsl pas d´accents je suis a l´etranger)