Algo multiplication matricielle

Réponses

• ev

  October 2011

  Bonjour Seub.
  
  Je pense qu'il faudrait que tu soies plus précis. Lorsque tu parles d'efficacité est-ce en terme de mémoire ou de vitesse - l'un étant souvent au détriment de l'autre.
  
  Je pense que pour avoir des routines qui tournent rapidement il faut tenir compte du hard. Sauf erreur de ma part, Strassen ne va pas profiter d'une architecture pipe-line par exemple.
  
  amicalement,
  
  e.v.

  Personne n'a raison contre un enfant qui pleure.
  
  
  
• seub

  October 2011

  Salut e.v.,
  
  Je parle d'efficacité en termes de vitesse. En même temps je ne vois pas comment multiplier deux matrices de taille 50 pourrait "overflow" la mémoire.
  
  Bref, pour résumer, je voudrais un algo capable de multiplier rapidement deux matrices carrées de taille inférieure à 50.
• bisam

  October 2011

  La méthode usuelle est en O(n^3), ce qui représente ici environ 125000 opérations... et si tes nombres ne passent pas 2^64, soit environ 10^19, cela devrait se faire en moins d'un dixième de seconde sur un ordinateur usuel de nos jours.
  
  A moins que tu aies plusieurs millions de matrices à multiplier, pourquoi se casser la tête à aller plus vite ?
  Si ton programme ne va pas très vite, c'est peut-être que le langage utilisé n'est pas adapté à ce genre de calculs (je ne connais pas du tout python, alors je dis peut-être une grosse bêtise)
• LEF0

  October 2011

  Salut Seub,
  
  Tu connais ce poly : algo.inria.fr/bostan/publications/Bostan10.pdf ?
  
  Le chapitre 3 devrait t'intéresser. Mais comme l'a dit Bisam, du $O\left(n^3\right)$ c'est déjà bien. Il ne faut pas oublier que les complexités sont asymptotiques et en général, les algos qui ont une meilleure complexité cachent des constantes monstrueuses dans le $O$. Du coup ce n'est pas du tout rentable pour des matrices de petite taille.
• seub

  October 2011

  Merci pour vos réponses.
  
  Et malheureusement non, la méthode basique en O(n^3) ne me suffit pas. J'ai un programme qui demande une soixantaine de multiplications matricielles avec des matrices de taille 50 remplies de coefficients entiers allant jusqu'à un milliard (et le tout doit être calculé modulo un nombre aux alentours de un milliard). Sur mon PC portable, cela prend 5 secondes, et je dois faire tourner le programme de nombreuses fois.
  
  Ce qui m'agace c'est que la multiplication matricielle déjà toute prête de numpy est beaucoup plus rapide que la mienne (mais malheureusement n'est pas suffisamment précise pour mes besoins), ce qui me laisse penser que je dois pouvoir nettement améliorer la vitesse de mon algo.
  
  Après c'est clair, bisam, que python n'est sans doute pas le langage le mieux adapté à mon problème. LeF, je vais aller voir ton poly.
  
  Encore merci pour vos réponses.
• le poulpe

  October 2011

  C'est un problème que je connais particulièrement bien pour avoir travaillé sur une librairie de calcul matriciel.
  
  Je ne peux que te recommander de programmer en C (++)
  Strassen est très (TRES) difficile à coder efficacement. En général on perd toute performance par des défauts d'implémentations.
  Il faut que tu penses à deux choses pour arriver à des vitesses suffisantes:
  - alignement mémoire. (ta matrice doit être stockée sur une seule ligne)
  - vectorisation (utiliser un peu d'assembleur ou au moins un bon compilo (gcc)
  
  par exemple voilà un exemple de code source C:

  // c -> a*b
  void multMatrix(double* a, double* b, double* c, int n) 
  {
      int index=0;
      int index2 = 0;
      for (int i = 0 ; i < n ; ++i, index2 += n)
      {
          for (int j = 0 ; j < n ; ++j, ++index)
          {
               // index vaut ici i*n+j
              c[ index] = 0. ;
              int index3 = j ;
              // c'est ici qu'il faudrait faire de l'asm pour profiter d'avx
              for (int k = 0 ; k < n ; ++k, ++index2, index3 += n)
              {
                  // index2 vaut i*n+k
                  // index3 vaut k*n+j
                  c[ index] += a[ index2]*b[ index3];
              }
          }
      }
      return;
  }
  

  SI la taille de tes matrices est fixe, tu peux fixer n par un #define pour que le compilateur soit au courant
  
  Si tu veux des performances meilleures, il te faudra faire du CUDA ou de l'openCL.
• jobherzt

  October 2011

  Salut,
  
  tu peux aussi regarder du coté de Sage, c'est un logiciel de calcul formel qui repose sur et peux interagir avec Python, et je suis quasiment certain que tu peux regler la precision.
  
  Sinon, je rappelles que Numpy et Schipy sont libres, ce qui fait que tu peux aller regdarder le code source de la multiplication matricielle et t'en inspirer. Ceci dit si c'est une question de type ca m'etonnerait qu'il n'y ait pas moyen de corriger ca sans tout recoder. A mon avis tu peux signaler a ces libraires que tu veux travailler en 64 bits.
• seub

  October 2011

  Merci pour vos réponses!
  
  J'ai travaillé depuis la dernière fois, je peux vous faire partager ce que j'ai appris :
  -On connait pas mal d'algos mathématiques pour réduire la complexité théorique de la multiplication matricielle, mais en pratique très peu d'algos font gagner du temps (et donc sont utilisés), si mes souvenirs sont bons, Strassen, Winograd et variantes, Pan.
  -Strassen et cie, même bien programmés (cf message du poulpe), ne font gagner du temps que pour des matrices assez grosses (de taille plusieurs centaines en gros). J'ai pu observer ça par moi-même. En pratique, d'autres algos prennent le relais pour les "petites" matrices obtenues.
  -Pour gagner du temps, et cela marche très très bien, il faut donc optimiser le côté informatique et non mathématique des algorithmes : accès à la mémoire etc.
  -Effectivement, python est très peu adapté pour faire ça. L'algorithme "naif" programmé en C est déjà beaucoup plus rapide, au point que cela me suffisait pour mon problème. Je n'ai donc pas eu besoin de plus travailler.
  
  Pour info, on trouve plein de références sur internet en anglais. BLAS (Basic Linear Algebra Subprograms, cf wikipedia par exemple) contient des algos très performants. Pour en savoir plus là-dessus, vous pouvez regarder le papier "GotoBLAS - Anatomy of a fast matrix multiplication".
• Aleph

  October 2011

  Bonjour,
  
  tu as tout à fait raison, pour gagner en vitesse d'exécution, il faut optimiser ton implémentation. Cela n'a rien à voir avec le langage de programmation tant qu'il est compilé. Cela dépend beaucoup plus de ton compilateur (sa capacité à optimiser lui-même ton code), de l'architecture de ta machine (notamment les niveaux et tailles des caches) et de ta connaissance des deux précédents points pour aider TON compilateur à optimiser efficacement pour TA machine. La bibliothèque BLAS contient des algorithmes qui furent performants à une certaine époque mais ce n'est plus le cas. Il existe en revanche des bibliothèques qui s'inspirent de cette bibliothèque historique pour faire de l'algèbre linéaire optimisée. Il y a par exemple, ATLAS et GOTO-BLAS. Ces bibliothèques utilisent des langages procéduraux (fortran, c). Si tu t'orientes vers du C++, la situation est un peu plus complexe car il faut faire de la métaprogrammation (expression templates). Tu peux par exemple regarder les bibliothèques BLITZ (non maintenue) et EIGEN. Si tu as les moyens de te procurer la bibliothèque IMKL (Intel Math Kernel Library) c'est l'idéal!
• Mathias.Deshayes

  October 2011

  Pour les boucles, un index descendant et une comparaison à zéro pour la condition améliore un peu les performances il me semble.
  

  for(int i=lastIndex;i!=0;i--) {
    ...
  }
  
• projetmbc

  October 2011

  Bonsoir seub,
  peux-tu poster ton code Python avec des données pour le tester sur mon ordinateur ?
• BtiKa

  January 2012

  je voulais un code source qui permet de multiplier deux matrices carrée et compte leurs temps d'execution
• BtiKa

  January 2012

  salut
  aussi j' ai besoin du code source en java qui permet de faire la multiplication de deux matrice carrée sous forme strassen
• nicolas.patrois

  January 2012

  Dans un Unix, tu peux le faire toi-même avec un script dans ton langage préféré précédé de time.

  Algebraic symbols are used when you do not know what you are talking about.
          -- Schnoebelen, Philippe