Optimtool et parallelisme

Bonjour,
j'ai plusieurs problèmes en matlab.
J'ai 3 optimisations à faire, une en résolvant un système linéaire (j'inverse donc une matrice, il y'a 2 méthodes que je connaisse, soit 1\A soit 1/A), une autre en résolvant un programme linéaire, mais que je peux transformer un peu en une optimisation avec contraintes et un programme quadratique.

Je connais les fonctions pour chacune de ces optimisation, cependant j'ai vu qu'il était possible de combiner parallelisme et optimisation, or je ne sais pas comment faire.

J'aimerais bien connaitre la marche à suivre pour combiner les 2. Si une âme charitable pouvait m'aider, je lui en serais reconnaissant.

Merci,
Otto

Salut,
bienvenu sur le forum.

Pour moi, optimisation et parallélisme sont 2 notions indépendantes... On parallélise un algorithme (d'optimisation, de résolution d'EDP ou autre). Donc quel est ton algo ? Essaye de voir ce qui peut être fait en parallèle et ce qui doit être fait en séquentiel.

Peux-tu nous donner un peu plus d'infos ? Est-ce que tes 3 optimisations sont indépendantes l'une de l'autre ou bien est-ce que la sortie d'une optimisation (donc les paramètres ajustés) te servent de condition initiale pour la 2e optimisation ? Idem pour la 3e ?

Bonjour,
pour fixer un peu plus les idées, je travaille sur 3 algorithmes complétements indépendants en pratique (même si je peux faire des simplifications de calcul en les faisant tourner en série).

En gros, voici ce que je fais:
1- je calcule des "grosses" matrices (peu importe comment) symétriques, A,B,C.

2-i) J'inverse A et B (algo 1) (soit avec inv(A) soit avec 1/A je ne sais pas ce qui est plus performant).
ii) Je résouds un programme linéaire pour trouver le minimax de x'Ay et x'By (algo 2) (j'utilise la commande linprog).
iii) Je résouds un programme quadratique pour C puisque je cherche à minimiser x'Cx sous contrainte. (avec quadprog)

Chacune des parties i,ii,iii sont complétement indépendantes et dans ces parties je ne fais qu'appeler les fonctions inv,linprog,quadprog respectivement.

J'ai vu sur le site de matlab que l'on pouvait associer parallelisme aux outils d'optimisation. Je ne sais pas ce qu'ils entendent réellement par là, mais ce que j'aimerais faire si c'est possible (parce que je dois avouer que je ne suis pas un expert en informatique ni en programmation et je ne sais pas vraiment ce qui se fait ou non) serait de résoudre mon programme linéaire sur plusieurs cpu en même temps pour diminuer le temps de calcul. Idem pour le système linéaire, idem pour la programmation quadratique.

Il me semble avoir compris que cela se faisait avec d'autres logiciels de calcul comme Maple par exemple.

J'écris présentement plusieurs articles scientifiques et j'ai besoin d'avoir une grande rapidité de calcul, voila pourquoi je me suis tourné vers la programmation en parallele que je n'ai découverte qu'hier... J'ai à ma disposition 8CPU.

Merci pour votre aide.
Otto

Salut!

Citation:

---

en résolvant un système linéaire (j'inverse donc une matrice

---

C'est exactement ce qu'il ne faut pas faire. Quand on écrit x=A^(-1)*b, c'est une convention d'écriture qui signifie que x est la solution du système linéaire A*x=b, mais cela ne veut pas dire qu'il faut effectivement inverser A. Pour t'en rendre compte, tu peux construire une grosse matrice et un vecteur et chronométrer une fois x=A\b et une fois x=inv(A)*b. Tu verras que la première méthode est sensiblement plus rapide.
D'autre part, si la vitesse d'exécution est vraiment essentielle, MatLab n'est peut-être pas l'outil optimal: tu devrais t'orienter vers des bibliothèques écrites en Fortran ou en C (LinPack ou LAPack).
Jean-Marc Blanc

Bonjour,
j'avais remarqué cela, merci pour ta réponse.
Le coeur du probleme n'est pas la cependant, je me demande si on peut partager ce calcul sur plusieurs machines ainsi que ceux du programme linéaire et quadratique.

Merci.

Salut, ton code se parallélise super facilement. Voici l'algo

1) sur 3 processeurs, calculer A, B et C (1 processeur par matrice)
2) sur 3 processeurs, tant qu'à faire, les mêmes résoudre x'Ay, x'By et x'Cx

que sont x et y ?

Point, c'est fini.

Maintenant, si tu es un champion de la programmation et de l'algèbre linaire, tu peux pour résoudre x'Ay (par exemple) le faire sur plusieurs processeurs (et non sur 1 seul comme je l'ai dit à l'étape 2)). Renseigne toi sur les matrices par bloc etc...

avoir 8 CPU c'est bien. Mais dans le calcul parallèle, il faut aussi prendre en compte le temps de connexion et de transfert des données (bref les communications entre les processus...). C'est tout un métier (si si je t'assure)

Relis bien ce qu'à dit Jean-Marc Blanc. S'il ne t'avais pas fait cette remarque, je te l'aurais faite. Voici ma position sur Matlab : Matlab c'est très bien si tu veux un résultat rapide "presque sans rien faire" (car tout est déjà codé). Maintenant si tu veux t'intéresser de près au temps de calcul, la réponse est ultra simple : oublie les langages interprétés (Matlab) et passe aux langages compilés (C, C++, Fortran). Il te faudra réécrire le code mais tu gagnes plein de temps.

En C, pour la parallélisation, je peux te donner des infos sur la programmation multi-threads (mutex etc...) et sur la programmation avec MPI.

A mon boulot, j'ai réécrit un programme Matlab en C. De 3 minutes (en Matlab) je suis passé à 0.25 secondes en C. Je pense que cela doit te convaincre.

Tu as parlé de Maple. Ce logiciel est très bien pour faire du calcul symbolique. A chaque outil sa fonction.

Relis bien la réponse de Jean-Marc Blanc. Et retiens bien qu'il ne faut JAMAIS inverser une matrice. Beaucoup trop long en terme de temps de calcul.

Bonne soirée

Salut,
merci de ta réponse.

Je fais déjà ce que tu proposes pour gagner du temps en pratique mais comme mes algorithmes sont indépendants, ce temps de calcul gagné n'est pas le plus intéressant.

Je m'intéresse surtout à ce que tu dis sur le parallelisme pour résoudre des sytèemes linéaires et il se trouve que j'ai justement vu un post en parler sur ce même forum pas plus tard que cet après midi. Je vais lire aussi un peu ce qui s'est raconté.

En réalité, j'aimerais que mon algorithme aille le plus vite possible évidemment ... mais je préfère dans un premier temps rester sur un langage interpreté. Je travaille avec d'autres personnes (entre autre mon directeur de thèse) qui lui programme en C++ et je sais qu'il utilise linpack et lapack (je ne sais pas ce que c'est cela dit ...).

Je n'ai que peu de connaissances en programmation et c'est la raison pour laquelle je suis sous matlab (plus facile à programmer) et pour l'instant je n'essaie pas encore de pousser. Cela dit la question que j'ai posée m'intéresse au dela du langage que j'utilise. Tu m'apportes déjà un élément de réponse en me parlant de matrices par blocs, j'avoue que je peux éventuellement regarder de ce coté-ci.

Quant à la résolution du système linéaire, je n'avais pas compris avant de poster sur ce forum que l'inversion d'une matrice était plus lente que la résolution d'un système linéaire. En tant que mathématicien, je ne voyais pas de différence.

Merci encore :)
Otto

Citation:

---

Envoyé par salseropom

Salut, ton code se parallélise super facilement. Voici l'algo

1) sur 3 processeurs, calculer A, B et C (1 processeur par matrice)
2) sur 3 processeurs, tant qu'à faire, les mêmes résoudre x'Ay, x'By et x'Cx

que sont x et y ?

Point, c'est fini.

Maintenant, si tu es un champion de la programmation et de l'algèbre linaire, tu peux pour résoudre x'Ay (par exemple) le faire sur plusieurs processeurs (et non sur 1 seul comme je l'ai dit à l'étape 2)). Renseigne toi sur les matrices par bloc etc...

---

Juste pour compléter mon dernier message,

x et y sont des vecteurs dont la somme des composantes est 1 et à composantes positives. Je crois que l'on appelle ça un simplexe mais je ne suis pas familier avec ce langage.

Pour ce qui est de résoudre x'Ay sur plusieurs processeurs (en réalité je cherche à minimiser cette quantité pour mon 2e algorithme, mais peu importe) c'est vraiment l'objet de ma question sur ce forum. :)

J'espère avoir été plus clair.
Mais déjà là je pense avec vos réponses pouvoir me débrouiller un peu.

Citation:

---

Envoyé par ottog1s

Salut,
Quant à la résolution du système linéaire, je n'avais pas compris avant de poster sur ce forum que l'inversion d'une matrice était plus lente que la résolution d'un système linéaire. En tant que mathématicien, je ne voyais pas de différence.
Otto

---

En théorie, tu auras la même réponse ,que tu inverse une matrice ou que tu résolves un système linéaire.

La différence entre x = A^-1 * b ou x = A\b est que lorsque tu résouts ton système linaire, il y a, de manière caché car c'est inclus dans lapack, un préconditionnement. Si tu fais "bêtement" x = A^-1 * b, tu oublies cette étape ce qui peut être catastrophique. Fais une recherche sur google sur ce qu'est un conditionnement d'une matrice

Lapack et linpack sont des librairies d'algèbres linéaires, très utilisées. De mémoire, Matlab utilise Lapack.

Citation:

---

Envoyé par ottog1s

Pour ce qui est de résoudre x'Ay sur plusieurs processeurs (en réalité je cherche à minimiser cette quantité pour mon 2e algorithme, mais peu importe) c'est vraiment l'objet de ma question sur ce forum. :)

---

Essaie de t'inspirer des méthodes de minimisation d'une forme quadratique (-> google), bien que tu n'aies pas x'Ax mais x'Ay

Mais question bête : où sont tes inconnues (ou paramètres) à minimiser ? dans x ? dans y ?