Discussion :

[un passant]

j'ai programme un code qui me resoud une equation de type a*x=b avec a etant une matrice carree et x et b des vecteurs.
pour ce faire j'utilise une resolution par la methode du pivot de gauss.
au depart je faisai avec des exemple de petite matrice (200*200)
mais maintenant je dois resoudre des systemes avec des matrices de plus de 1500*1500. le resulta est toujours bon, le seul probleme est que le temps de calcul est eleve et jaimerai savoir si il y a des methodes pour l'optimiser.

[contremaitre]

Tu es dans le forum C, donc il faudrait montrer ton code pour voir ce qu'ily a à améliorer...
Mais tu aurais peut etre plus de chance dans le forum algorithme

[un passant]

j'ai mis l'essentiel du code;
je savais pas qu'il y avait un forun algorithme.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
main()
{
float **K, *q, *f;
int nnoeuds;//lu ds le fichier d'entree
 
//Allocation de memoire
    FILE * fp;
    fp=fopen("erreur.txt","w");
    K = (float **)calloc ( nnode , sizeof(float*) );
    if( K == NULL )
    {
        fprintf(fp,"Allocation de K impossible");
        exit(EXIT_FAILURE);
    }
    for(int j=0 ;j<nnode; j++ )
    {
        K[j] =(float *)calloc(nnode, sizeof(float));
        if( K[j] == NULL )
        { 
            fprintf(fp,"Allocation de a impossible");
            exit(EXIT_FAILURE);
        }
    }
    q =(float *)calloc(nnode, sizeof(float));
    if( q == NULL )
    {
        fprintf(fp,"Allocation de q impossible");
        exit(EXIT_FAILURE);
    }
    f =(float *)calloc(nnode, sizeof(float));
    if( f == NULL )
    {
        fprintf(fp,"Allocation de f impossible");
        exit(EXIT_FAILURE);
    }
 
//creation de la matrice de rigidite et du vecteur chargement
    matrig(K);
    vectfor(f);
 
//Resolution de K*Q=F
    gauss(K, q, f, nnoeuds);
    return 0;
}
 
void gauss(float **a,float *x,float *b,int n)
{
	float p,s;
    int i,j,k;
	for(k=0;k<n-1;k++)
    {
		if (a[k][k]==0)
        {
		    printf("\n\n * Un pivot nul ! => methode de Gauss non applicable\n\n");
		    break;
		}
		for(i=k+1;i<n;i++)  //triangularisation de la matrice
        {
			p=a[i][k]/a[k][k];
			for (j=k;j<n;j++) a[i][j]=a[i][j]-p*a[k][j];
			b[i]=b[i]-p*b[k];
		}
	}
	for(i=n-1;i>=0;i--) //Résolution du systeme
    {
		s=0;
		for(j=i+1;j<n;j++)s=s+a[i][j]*x[j];
		x[i]=(b[i]-s)/a[i][i];
	}
}

[je®ome]

Un petit truc en regardant vite fait. Il faut savoir que en langage C, les tableaux sont stoqués ligne par ligne
Cela veut dire que les accès au tableau peuvent être plus ou moins rapides dépendant de la manière dont ont les accède.
P.ex.:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[j][i]=a[j-1][i]+i;

Sera plus lent que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[i][j]=a[i-1][j]+i;

Car la mémoire est lue par bloc (une partie de la ligne).
Dans le premier code, chaque tour de boucle demande une lecture, par contre, dans le deuxième bout de code, la donnée nécessaire se trouvera déjà quelques fois dans le cache.

Si je n'ai pas été clair, n'hésites pas, mais je pense que cela fera déjà speeder un peu plus.

[Vincent Rogier]

Un petit truc en regardant vite fait. Il faut savoir que en langage C, les tableaux sont stoqués ligne par ligne
Cela veut dire que les accès au tableau peuvent être plus ou moins rapides dépendant de la manière dont ont les accède.
P.ex.:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[j][i]=a[j-1][i]+i;

Sera plus lent que

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for(i=0;i<N;i++)
for(j=0;j<N;j++)
a[i][j]=a[i-1][j]+i;

Car la mémoire est lue par bloc (une partie de la ligne).
Dans le premier code, chaque tour de boucle demande une lecture, par contre, dans le deuxième bout de code, la donnée nécessaire se trouvera déjà quelques fois dans le cache.

Si je n'ai pas été clair, n'hésites pas, mais je pense que cela fera déjà speeder un peu plus.

Sauf que le compilo aura généré un code différent ou lui même fait ses propres optimisations.

Le code généré n'est jamais une traduction du code écrit !

Ne pas se prendre la tête sur ce genre de détails, laisser le compilo faire ses optimisations tout seul comme un grand.

Mais effectivement, voir plutôt du coté du forum algo...

[souviron34]

une première optimisation de code qui t'accélérera pas mal (sans parler de l'algo) :

sort tout ce qui peut être sortie des boucles ..

Exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
    b1 = b[k] /* 1 calcul en moins à chaque boucle i */
    c1 = a[k][k] /* 1 calcul en moins à chaque boucle i */
    for(i=k+1;i<n;i++)  //triangularisation de la matrice
        {
            p=a[i][k]/c1;
            for (j=k;j<n;j++) a[i][j]=a[i][j]-p*a[k][j];
            b[i]=b[i]-p*b1 ;
       }