Problème implémentation Algorithme de Strassen

Version imprimable

5 pièce(s) jointe(s)

Bonjour à tous !:D

J'en viens à votre aide et je vous explique mon problème.
Je suis débutant en C++ et pour un ours je dois implémenter l'algorithme de Strassen avec des objets Matrice.

Aussitôt dit aussitôt fait ! Quelques recherches sur le net m'ont permis de voir que le projet était déjà fait par un certain Martin Thomas
cf https://martin-thoma.com/strassen-al...thon-java-cpp/

Je me suis inspiré par conséquent de son code en réécrivant à ma sauce avec mes objets matrices.

Cependant après exécution vérification avec Matlab, le calcul ne se fait pas correctement et je dois louper une étape, un truc tout bête
à n'en pas douter, mais le fait est que après 2 h dessus je ne vois rien.:aie:

Si des habitués de ce genre d'algo en c++ passaient par là, pourriez vous m'indiquez quelle (grosse ) bêtise j'ai faite ?:calim2:

J'ai placé en PJ mes fichiers de code.

mon main ne fait que de creer trois matrice A,B,C et lancer Strassen

Strassen.cpp

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
#include "Strassen.h"
 
int leafsize=1;
 
void ikjalgorithm(Matrice  A,
                                   Matrice  B,
                                   Matrice  &C, int n) {
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
 
 
            }
        }
    }
}
 
void strassenR(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    if (tam <= leafsize) {
 
        ikjalgorithm(A, B, C, tam);
        return;
    }
 
    // other cases are treated here:
    else {
 
        int newTam = tam/2;
 
        Matrice
            a11(newTam), a12(newTam), a21(newTam), a22(newTam),
            b11(newTam), b12(newTam), b21(newTam), b22(newTam),
              c11(newTam), c12(newTam), c21(newTam), c22(newTam),
            p1(newTam), p2(newTam), p3(newTam), p4(newTam),
            p5(newTam), p6(newTam), p7(newTam),
            aResult(newTam), bResult(newTam);
 
 
 
        //dividing the matrices in 4 sub-matrices:
        for (int i = 0; i < newTam; i++) {
            for (int j = 0; j < newTam; j++) {
                a11.ajouterElement(i,j,A.Element(i,j));
                a12.ajouterElement(i,j,A.Element(i,j+newTam));
                a21.ajouterElement(i,j,A.Element(i+newTam,j));
                a22.ajouterElement(i,j,A.Element(i+newTam,j+newTam));
 
                b11.ajouterElement(i,j,B.Element(i,j));
                b12.ajouterElement(i,j,B.Element(i,j+newTam));
                b21.ajouterElement(i,j,B.Element(i+newTam,j));
                b22.ajouterElement(i,j,B.Element(i+newTam,j+newTam));
 
            }
        }
 
        // Calculating p1 to p7:
 
        sum(a11, a22, aResult, newTam); // a11 + a22
        sum(b11, b22, bResult, newTam); // b11 + b22
        strassenR(aResult, bResult, p1, newTam); //p1 = (a11+a22) * (b11+b22)
 
        sum(a21, a22, aResult, newTam); // a21 + a22
        strassenR(aResult, b11, p2, newTam); // p2 = (a21+a22) * (b11)
 
        subtract(b12, b22, bResult, newTam); // b12 - b22
        strassenR(a11, bResult, p3, newTam); // p3 = (a11) * (b12 - b22)
 
        subtract(b21, b11, bResult, newTam); // b21 - b11
        strassenR(a22, bResult, p4, newTam); // p4 = (a22) * (b21 - b11)
 
        sum(a11, a12, aResult, newTam); // a11 + a12
        strassenR(aResult, b22, p5, newTam); // p5 = (a11+a12) * (b22)
 
        subtract(a21, a11, aResult, newTam); // a21 - a11
        sum(b11, b12, bResult, newTam); // b11 + b12
        strassenR(aResult, bResult, p6, newTam); // p6 = (a21-a11) * (b11+b12)
 
        subtract(a12, a22, aResult, newTam); // a12 - a22
        sum(b21, b22, bResult, newTam); // b21 + b22
        strassenR(aResult, bResult, p7, newTam); // p7 = (a12-a22) * (b21+b22)
 
        // calculating c21, c21, c11 e c22:
 
        sum(p3, p5, c12, newTam); // c12 = p3 + p5
        sum(p2, p4, c21, newTam); // c21 = p2 + p4
 
        sum(p1, p4, aResult, newTam); // p1 + p4
        sum(aResult, p7, bResult, newTam); // p1 + p4 + p7
        subtract(bResult, p5, c11, newTam); // c11 = p1 + p4 - p5 + p7
 
        sum(p1, p3, aResult, newTam); // p1 + p3
        sum(aResult, p6, bResult, newTam); // p1 + p3 + p6
        subtract(bResult, p2, c22, newTam); // c22 = p1 + p3 - p2 + p6
 
        // Grouping the results obtained in a single matrix:
        for (int i = 0; i < newTam ; i++) {
            for (int j = 0 ; j < newTam ; j++) {
                C.ajouterElement(i,j,c11.Element(i,j));
                C.ajouterElement(i,j+newTam,c12.Element(i,j));
                C.ajouterElement(i+newTam,j,c21.Element(i,j));
                 C.ajouterElement(i+newTam,j+newTam,c22.Element(i,j));
            }
        }
    }
}
 
unsigned int nextPowerOfTwo(int n) {
    return pow(2, int(ceil(log2(n))));
}
 
void strassen(Matrice &A,
              Matrice &B,
              Matrice &C, unsigned int n) {
    //unsigned int n = tam;
    unsigned int m = nextPowerOfTwo(n);
 
    Matrice APrep(m), BPrep(m), CPrep(m);
    CPrep.initialiser();
 
    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            APrep.ajouterElement(i,j,A.Element(i,j));
 
            BPrep.ajouterElement(i,j,B.Element(i,j));
        }
    }
 
    strassenR(APrep, BPrep, CPrep, m);
    for(unsigned int i=0; i<n; i++) {
        for (unsigned int j=0; j<n; j++) {
            C.ajouterElement(i,j,CPrep.Element(i,j));
        }
    }
}
 
void sum(Matrice &A,
         Matrice &B,
         Matrice &C, int tam) {
    int i, j;
 
    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)+B.Element(i,j));
        }
    }
}
 
void subtract(Matrice &A,
              Matrice &B,
              Matrice &C, int tam) {
    int i, j;
 
    for (i = 0; i < tam; i++) {
        for (j = 0; j < tam; j++) {
            C.ajouterElement(i,j,A.Element(i,j)-B.Element(i,j));
        }
    }
}

Et mon Matrice.cpp

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include "Matrice.h"
#include <math.h>
#include <cmath>
#include <sstream>
#include <string>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#define N_MAX 20
 
using namespace std;
 
int Matrice::rand_a_b(int a, int b){
    return rand()%(b-a) +a;
}
 
Matrice::Matrice()
{
}
 
 
 
Matrice::Matrice(int taille) : m_tailleMatrice(taille)
{
 
 
 
    for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
            m_colonne.push_back(rand_a_b(0,10));
 
        }
    m_ligne.push_back(m_colonne);
    m_colonne.clear();
 
    }
 
}
 
Matrice::~Matrice()
{
 
}
 
 
void Matrice::initialiser()
{
     for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
           m_ligne[i][j]=0;
 
        }
 
 
    }
 
}
 
void Matrice::afficher()
{
 
    for (int i=0 ; i<m_tailleMatrice ;i++)
    {
        for (int j=0 ; j<m_tailleMatrice ;j++)
        {
           cout<< m_ligne[i][j] <<" ";
        }
   cout << endl ;
 
 
    }
 
}
 
 
void Matrice::ajouterElement(int i, int j, int element)
{
            m_ligne[i][j]= element;
}
 
int Matrice::Element (int i, int j)
{
 
    return m_ligne[i][j];
}

Bien cordialement,
Je vous souhaite une excellente journée.

05/05/2016, 23h30
Pyramidev

Après avoir jeté un œil rapide à la page Wikipédia de l'Algorithme de Strassen puis après avoir jeté un œil rapide à ton code, il y a un problème qui saute aux yeux :
Ta fonction ikjalgorithm est supposée faire un produit matriciel.
A la place, elle ne fait... rien.

Citation:

Envoyé par Pyramidev

Après avoir jeté un œil rapide à la page Wikipédia de l'Algorithme de Strassen puis après avoir jeté un œil rapide à ton code, il y a un problème qui saute aux yeux :
Ta fonction ikjalgorithm est supposée faire un produit matriciel.
A la place, elle ne fait... rien.

Erreur de ma part, dans le copier coller .

j'avais ça en vrai :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 void ikjalgorithm(Matrice A, Matrice B, Matrice &C, int n) { for (int i = 0; i < n; i++) { for (int k = 0; k < n; k++) { for (int j = 0; j < n; j++) { C.ajouterElement(i,j,C.Element(i,j)+(A.Element(i,j)*B.Element(i,j))) ; } } } }
ce qui fait que ça n'a l'air toujours pô bon....:(

LA FATIGUE...........

Voici le probleme :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
void ikjalgorithm(Matrice  A,
                                   Matrice  B,
                                   Matrice  &C, int n) {
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < n; k++) {
            for (int j = 0; j < n; j++) {
C.ajouterElement(i,j,(A.Element(i,k)*B.Element(k,j))) ;
 
            }
        }
    }
}

Or avant je faisais C.ajouterElement(i,j, C.element +A*B).... La concatenation se faisait deux fois....

Merci de votre aide .
Bonne journee a bientot !
:D

06/05/2016, 03h27
GuillaumeRosa

Il devait s'agir d'un coup de chance sur un test , mais la ca ne marche plus du tout, encore uen fois le resultat n'est pas du tout celui attendu....:weird:

ENFIN

Alors l'histoire ca marchait avec des matrices carres de multiple de 2 , mais pas pour les autres....
Pourquoi ? bah parcequ ' on separe les matrices en 2 et qu il faut qu'elles soient carres....

Or dans mon code j'avais APrep et BPrep qui etaient generees avec des valeurs aleatoires et non remises a zero, donc lors du passage
de la separation je n'avais pas les bonnes sous matrices.

Voici la methode Strassen corrigee
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 void strassen(Matrice &A, Matrice &B, Matrice &C, unsigned int n) { //unsigned int n = tam; unsigned int m = nextPowerOfTwo(n); Matrice APrep(m), BPrep(m), CPrep(m); APrep.initialiser(); BPrep.initialiser(); CPrep.initialiser(); for(unsigned int i=0; i<n; i++) { for (unsigned int j=0; j<n; j++) { APrep.ajouterElement(i,j,A.Element(i,j)); BPrep.ajouterElement(i,j,B.Element(i,j)); } } strassenR(APrep, BPrep, CPrep, m); for(unsigned int i=0; i<n; i++) { for (unsigned int j=0; j<n; j++) { C.ajouterElement(i,j,CPrep.Element(i,j)); } } }
Bonne nuit :)

Salut,

C'est quoi cette horreur de fonction initialiser dans ta matrice ???

Tu devrais travailler de la manière inverse : ton constructeur qui prend une taille ne fait que créer ta matrice avec des valeurs égales à 0 et créer une fonction (si cela a du sens) -- par exemple fillRandomly --qui fournisse des valeur aléatoires pour remplir ta matrice :)

De cette manière, APrep, BPrep et CPrep seront directement utilisables (avec des valeurs égales à 0) et, si tu veux que ta matrice soit remplie de valeur aléatoire, tu n'as "qu'à" le demander de manière explicite (ce qui est, d'une certaine manière, beaucoup plus logique, non :question: )
De plus, il n'y a absolument aucune raison de faire en sorte que ta variable colonne soit une variable membre : elle ne devrait servir que pour créer ta matrice, et peut donc être locale à la fonction qui s'occupe de cela ;)

Enfin, tu serais sans doute bien inspiré de "linéariser" ta matrice : si tu veux une matrice composée de Lines lignes et de Cols colonnes, ce que tu veux en réalité, c'est disposer de Lines * Cols éléments (en plus, il se fait qu'ici, la matrice est carrée), si bien que tu pourrais créer un seul tableau de Lines * Cols éléments et utiliser une formule toute simple pour trouver une valeur particulière correspondant à élément recherché = ligne demandée* Cols + colonnne demandée, formule que tu pourrais utiliser dans l'opérateur () (qui facilitera l'accès aux différents éléments).

De plus, mais ce n'est vraiment qu'un détail, tu devrais penser à utiliser la fonction reserve de std::vector dés que tu peux connaitre la taille finale de ta matrice, histoire de faire allouer toute la mémoire "d'une seule fois"... sur les (tres) grandes matrices, cela pourrait te faire gagner pas mal de performances à peu de frais ;)

Au final, ta matrice pourrait ressembler à quelque chose comme
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Matrice{ public: Matrice(size_t taille):taille_(taille), datas_(taille*taille){ datas.fill(0); // par défaut, tout vaut 0 } int operator()(size_t line, size_t col) const{ // pour accéder à un élément, sans pouvoir le modifier assert(line < taille_ && col < taille_ && "index out of bound"); return datas_[line*taille_+col]; } int & operator()(size_t line, size_t col) { // pour accéder à un élément, afin de le modifier assert(line < taille_ && col < taille_ && "index out of bound"); return datas_[line*taille_+col]; } void fillRandomly(){ // ce qu'il faudra pour donner toutes les valeurs aléatoires } size_t taille() const{ // permet de connaitre le nombre de lignes et de colonnes return taille_; } private: size_t taille_; // le nombre de lignes (et de colonnes) std::vector<int> datas_; //les données "linéarisée" };
Bien sur, on pourrait ajouter quelques trucs sympa, comme la possibilité de calculer le déterminant ou le produit matriciel (après tout, tu en auras besoin ;) ), mais, avec cela, tu auras déjà beaucoup plus facile à travailler ;)

06/05/2016, 19h22
GuillaumeRosa

Ah que merci !

Merci Koala01 de tes précieux conseils, je vais appliquer cela au mieux !

Pour ce qui est du déterminant etc.... je ne vais pas l'implémenter, je vais rester avec les formules explicites et récursives pour l'exercice suite aux consignes du prof' ;)

Pour information j'ai effectuer tes corrections et j'ai surchargé l'opérateur * pour pouvoir faire la multiplication matricielle de Matrice carrée selon l'algo de Strassen .

En tout cas merci de vos réponses rapides, courtoises et pleines de bon conseils ! ;)

see you ! ;)