Algo multiplication matricielle — Les-mathematiques.net The most powerful custom community solution in the world

Algo multiplication matricielle

Bonjour,

Je programme en python (je suis plutôt débutant), et j'aurais besoin d'un algorithme qui calcule efficacement des produits de matrices (carrées).

Remarque : Je sais qu'il existe déjà des fonctions (comme dot) dans numpy et scipy mais elles ne me conviennent pas car celles-ci calculent avec une précision de 32 bits (int ou float), sauf erreur de ma part, et il me faut plus de précision (format long). Je n'ai pas réussi à contourner ce problème, j'ai donc abandonné l'idée de recourir aux fonctions existantes dans ces librairies, et décidé de tout écrire moi-même.

J'ai programmé l'algorithme de Strassen mais celui-ci ne me convient pas car il est plus efficace que l'algorithme "naif" seulement pour des matrices assez grosses (de taille égale à plusieurs centaines), alors que mes matrices sont au plus d'ordre 50.

Je remarque que dans wikipedia, il est dit que "En pratique l'algorithme de Strassen est utilisé pour les matrices de grande taille. Il divise la taille jusqu'aux dizaines ou centaines et un autre algorithme de multiplication prend ensuite le relais pour calculer le produit des « petites matrices » obtenues." Je me dis donc que c'est cet "autre algorithme de multiplication" qu'il me faudrait implémenter, mais j'ai aucune idée de ce que cela peut être.

En tous cas, c'est sûr qu'on peut faire bien mieux que l'algorithme naif, même pour mes "petites" matrices, car la fonction dot de numpy effectue les produits de mes matrices en bien moins de temps que mon algo naif, mais malheureusement, avec des petites erreurs d'arrondis (mes matrices ont des coeffs pouvant aller jusqu'au milliard).

Avez-vous des suggestions pour m'aider?

Merci d'avance.

Réponses

  • 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.
    À ta naissance, tu pleurais tout le temps et tout le monde souriait autour de toi. Fais en sorte qu'à ta mort, ce soit l'inverse. (Proverbe arabe)
  • 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.
  • 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)
  • 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.
  • 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.
  • 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.
  • 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.
  • 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".
  • 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!
  • 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--) {
      ...
    }
    
  • Bonsoir seub,
    peux-tu poster ton code Python avec des données pour le tester sur mon ordinateur ?
  • je voulais un code source qui permet de multiplier deux matrices carrée et compte leurs temps d'execution
  • salut
    aussi j' ai besoin du code source en java qui permet de faire la multiplication de deux matrice carrée sous forme strassen
  • 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
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!