Bonjour à tous,
 
Voila je vais présenter mon probleme.
J'ai une matrice a inverser, pour résoudre un systeme linéaire, AX=B
 
X etant un vecteur de taille N, typiquement N est autour de 200
A est une matrice qui est tridiagonale
Ce calcul a l'air des plus simples, mais ce n'est qu'une illusion, à savoir que j'ai en fait jusqu'a plusieurs milliers de systemes comme celui la a resoudre à chaque iteration, et que le calcul du B est assez long on va dire.  
 
Actuellement je suis en version monoproc.
Donc pour résoudre mon systeme j'utilise les algo du Numerical, algo qui dans ce cas sont de complexité O(N)
 
Le "souci" est que maintenant je veux passer en version parallelle.
Actuellement j'ai "découpé" mon vecteur X en plusieurs sous vecteurs, Xi et
Chaque CPU ayant un domaine Xi. Derniere précision, chaque sous vecteur Xi à des points communs avec ses voisins.
Exemple :
X={X0,X1,X2,X3,X4,X5,X6}
CPU 0 : X={X0,X1,X2,X3}
CPU 1 : X={X3,X4,X5,X6}
J'ai deja les algo pour calculer les Bi en consequences, calculs reduisants au maximum les communications (j'ai juste besoin de transmettre les frontieres)
 
Je me demandais donc si une personne ici aurait un algo permettant d'eviter les communications interproc pour cette inversion.
La raison étant que le calcul de B est extrement long et que j'ai deja parallélisé ce calcul de maniere  
Voir meme, soyons fou, un algo de complexité equivalente a mon algo actuel.
D'ailleur je me demandais ce qui etait le plus rentable entre, un algo de complexité superieure mais ayant un coup de communication nul et un algo plus rapide mais entrainant des communications inter proc. J'aurai tendance à dire, ca depends
 
Actuellement je m'oriente vers une méthode  "barbare" a savoir que chaque CPU renvoie au CPU0 sa partie du domaine, CPU0 qui resoud le systeme et renvoie l'info ensuite...
 
Voila, toute piste est la bienvenue, merci  

y a t il VRAIMENT besoin de paralleliser ça sur plusieurs CPU ? La version LAPACK de cet algo doit deja avoir un temps de calcul plus que raisonnable.

Sur le fond NON, je suis d'accord que la version actuelle et encore plus la version LAPACK doit avoir un temps de calcul tout a fait raisonnable.
 
Le "hic" c'est que, étant donné que ce calcul n'est pas parallelle, cela entraine un surcout en communications, à coté. Et j'ai quelques Mo à transferer à chaque iterations (typiquement Niteration >100 000), ce que je voudrais éviter au max...
 

la question ets : as tu besoin de faire ces communications ...
 
Pour AX=B avec |X| = 200 ... je vois pas l'interet d'utiliser plusieurs CPU.
Donc est-ce purement scolaire ? ou y a t il une raison de distribuer ce calcul ?

+1
 
Si tu parallélises, tu comptes faire tourner ça sur combien de processeurs ? Avec un problème aussi "petit", ton efficacité risque de chuter très vite quand le nombre de processeurs augmentera, donc c'est surement pas rentable.

Ok je vais etre plus précis,  
 
En fait j'ai un joli petit systèmes d'eq diff à résoudre, 3 champs (Y1,Y2,Y3) et géométrie 3D.
dY1/dt = Lineaire1(Y1,Y2,Y3)+ NonLineaire1(Y1,Y2,Y3)
dY2/dt = Lineaire2(Y1,Y2,Y3)+ NonLineaire2(Y1,Y2,Y3)
d laplacien(Y3)/dt = Lineaire3(Y1,Y2,Y3)+ NonLineaire3(Y1,Y2,Y3)
 
La géométrie que j'utilise fait que mes champs suivant les directions y et z sont représentés sous forme spectrale.
 
Ainsi, si on prend la derniere équation, l'obtention de Y3 à partir de son laplacien equivaut à la résolution d'un système
AnmY3nm=Bnm.
J'ai donc NxM matrices à inverser pour connaitre Y3.
 
Ma représentation semispectrale a plusieurs avantages dans mon cas mais entraine aussi une contrainte à savoir que une decomposition de domaine ne peut etre performante que si elle est effectuée suivant la troisieme direction, à savoir X
 
Je ne vais pas rentrer dans le detail du pourquoi ni des differents termes lineaires et non lineaires, ce n'est pas utile
 
Actuellement pour Y1 et Y2 comme je l'ai dis j'ai mon domaine décomposé et les communications sont réduites au minimum. Ainsi chaque CPU à une matrice de taille NxMxX1 avec X1=2+X/Nombre_CPU
Le souci concerne Y3, à chaque itération, je dois inverser ma matrice et renvoyer le résultat à chaque CPU.
J'ai donc un "gros"  
Gather Y3
Calcul Inverse Y3
Scatter Y3
 
Hors si j'arrivais à inverser "juste" sur chaque sous domaine, je n'aurai pas besoin de faire ces Gathers/Scatters
Voila une présentation plus détaillée du probleme...
 
Edit : Pour Francesco, le nombre de CPU va etre de 12 voir 16 dans un premier temps.

Je suis pas sûr d'avoir compris tous les détails de ton problème : en particulier, que représente exactement ton équation "AnmY3nm=Bnm" ?
Quand tu parlais de 200, c'est la taille de quoi ? (c'est la taille d'une matrice Anm, ou bien le nombre de matrices à inverser ?)
 
En tous cas, ton problème n'a pas l'air simple du tout... Par curiosité, c'est quel domaine d'application ?

Donc 200 c'est la troisieme dimension des matrices, les matrices sont de tailles NxMx200 en gros. 200 c'est la taille de mon vecteur  que je veux inverser. Le nombre de matrices à inverser est NxM
Et pour l'equation,
Anm = operateur du laplacien + un terme sur la diagonale
Bnm = Lineaire3(Y1,Y2,Y3)+ NonLineaire3(Y1,Y2,Y3) donc en fait Bnm est aussi une matrice B[n][m][x]
Y3nm = vecteur Y3[n][m]
 
 
Concernant le domaine, simulation numériques de plasmas magnétisés voila ^^

N et M valent combien ?

en gros N=30 et M=180