Discussion :

[Matthieu Brucher]

On a pas la même précision ? Ah bon...
D'ailleurs, je ne vois pas pourquoi on n'a pas le même ordre, tu peux un peu développer stp ?

[alveric]

Heu dans la page tout le monde me fouette !!!!! Ca fait mal.

Allez-y

Si on fait la division, puis la multiplication, on a pas la même précision que si on fait l'inverse... Voila. Ce coup ci c'est bon... Pas de fouet.

C'est possible...
Ca causerait combien de difference entre calculer d'abord le 1/akk, puis faire les multiplications (dont la multiplication par 1/akk), et faire toutes les multiplications suivies de la division par akk ? Ca doit dependre des ordres de grandeur des valeurs, je suppose...

Es ce que l'appel est fréquent ou pas ?

Bonne question, faudrait pas non plus perdre deux semaines a optimiser une fonction qui ne prend que 0,01% du temps de l'appli...

[DrTopos]

Bonjour à tous.

Vous ne seriez pas un peu en train de jouer aux shadocks ?

J'ai du mal à comprendre pourquoi tout le monde veut diviser pour calculer un déterminant (surtout 4x4). Le déterminant est un polynôme par rapport aux coefficients de la matrice, et dans un polynôme il n'y a que des additions et des multiplications. Je sais qu'on enseigne des tas de recettes de cuisine à base de pivot de Gauss, mais franchement pour le déterminant ce n'est pas très utile.

Si on applique la formule du développement par rapport à la première colonne récursivement, et qu'on fait attention de ne pas calculer deux fois les déterminants 2x2 que je note ci-dessous D_12, D_13, D_14, D_23, D_24, D_34, et qui sont tous ceux qu'on obtient en rayant les deux première colonnes, et les deux lignes indiquées en indices:

Code :

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

1
2
3
4
5
6
7
 
D_12 = a_33a_44 - a_34a_43
D_13 = a_23a_44 - a_24a_43
D_14 = a_23a_34 - a_24a_33
D_23 = a_13a_44 - a_14a_43
D_24 = a_13a_34 - a_14a_33
D_34 = a_13a_24 - a_14a_23

le déterminant de la matrice est simplement:

Code :

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

1
2
3
4
5
 
D =   a_11(a_22D_12 - a_32D_13 + a_42D_14)
    - a_21(a_12D_12 - a_32D_23 + a_42D_24)
    + a_31(a_12D_13 - a_22D_23 + a_42D_34)
    - a_41(a_12D_14 - a_22D_24 + a_32D_34)

(Vérifiez quand même mes calculs, je ne suis pas infaillible.)

Finalement, on fait 28 multiplications, 17 additions ou soustractions, et c'est tout. Pas de test, pas de boucle, pas de recopiage, pas de division. Je crois que cet algo tient la route en vitesse et en simplicité.

[Rafy]

Il faudrai essayer de voir avec le pivot de gauss combien il y a d'opérations, mais je pense qu'il y en a moins...
Certe c'est une methode bête et méchante, elle marche, je suis d'accord.
Mais si c'est pour calculer 1000 déterminants par frames, il vaut mieux optimiser un peu, un déterminant c'est lourd

Finalement, on fait 28 multiplications, 17 additions ou soustractions, et c'est tout.

28 multiplications, ça fait mal quand même.
Je vais faire le calcul du nombre d'opération avec le pivot. je vous tiens au courant.

C'est possible...
Ca causerait combien de difference entre calculer d'abord le 1/akk, puis faire les multiplications (dont la multiplication par 1/akk), et faire toutes les multiplications suivies de la division par akk ? Ca doit dependre des ordres de grandeur des valeurs, je suppose...

Ben en fait ça dépend de plein de choses :
Le type de donnée utilisé (float ou double ou long double)
Ca dépend des ordres de grandeurs (si on est proche de 0 vaut mieux multiplier puis diviser car on s'écarte de 0 => plus grande présicion... Je m'explique ensuite)

[Rafy]

Ca dépend des ordres de grandeurs (si on est proche de 0 vaut mieux multiplier puis diviser car on s'écarte de 0 => plus grande présicion... Je m'explique ensuite)

Si on a un nombre qui est déjà petit, (donc on a un certain nombre de chiffre après la virgule), on le divise par un nombre grand. On va avoir un nombre encore plus petit. (on va être encore plus près de 0 donc moins de chiffre.) Si on remultiplie par un nombre, les chiffres qu'on a perdu ne vont pas revenir.
Il vaut donc mieux multiplier d'abord, s'écarter de 0, décaller vers la gauche nos chiffres (par rapport à la virgule), avant de repartir vers la droite en divisant...
Je sais pas si vous avez tout compris, dite moi.
Je vais regarder avec le pivot combien on a d'opérations.

[Matthieu Brucher]

Ca m'étonnerait que 28 multiplications fassent moins de mal que 4 divisions et 6 multiplications.

Sinon pourquoi diviser ? C'était dans le cas où on avait un déterminant plus gros à calculer et effectivement c'est pas le cas ici...

[Rafy]

Alors voila, pour le pivot de gauss, si tous mes calculs sont bon :
multiplications = 18
divisions = 14
soustractions = 14
additions = 0
en version bourine (recalcul du coefficient multiplicateur d'une ligne à chaque appel)

multiplication = 18
divisions = 6
soustractions = 14
additions = 0
en version un peu mieux.

[Rafy]

Je suppose que faire une soustraction ca prend autant de temps qu'une addition.
Par contre je ne sais pas pour une divison par rapport à une multiplication.
Si c'est le même temps, ca marche mieux que la technique littérale de DrTopos.

D'ailleurs, je ne vois pas pourquoi on n'a pas le même ordre, tu peux un peu développer stp ?

Je suppose que tu parles de la complexité de l'algorithme
Si c'est le cas, la complexité est moins grande quand tu fais des methodes qui amène à faire des factorisations, car il y a moins de calculs.
Dans notre cas, le pivot est puissant car on est psa obligé de connaitre tous les termes de la matrices pour pouvoir calculer son déterminant (des qu'elle est triangulaire c'est gagné !) Ca évite donc les calculs des coéfficients du triangle qui est dans la matrice. Moins de calculs => Moins de complexité.

[Rafy]

Dans la methode de DrTopos, on a besoin de tous les coefficients. pas pour le pivot (enfin si mais indirectement).

[alveric]

Par contre je ne sais pas pour une divison par rapport à une multiplication.

Sans connaitre le nombre de cycles machines habituellement necessaires pour l'un ou l'autre, il me semble qu'une division est plus lourde qu'une multiplication.
En recomptant pour un pivot de Gauss d'ordre 4 un petit peu optimise, j'ai 23 multiplications, 3 divisions, 14 soustractions, et 23 affectations. Mais c'est dans le cas optimal, il faut ajouter les tests de nullite (au moins 3) et les permutations eventuelles qui alourdissent la complexite...
Et, de plus, cela vaut dans le cas ou les boucles sont deroulees. Si on fait les boucles "pour" et autres, il faut ajouter d'autres tests, affectations et additions...
Du coup la methode de DrTopos est bien evidemment la meilleure a l'ordre 4, sans appel.

Mais on a bien le droit de s'amuser a reinventer la roue, non ?

Et je rappelle que le sujet a vite devie sur l'ordre quelconque des la premiere page

Bonjour, je fais remonter ce topic, car moi aussi j'aurais besoin d'un algo permettant de calculer le déterminant d'une matrice. Mais il me faudrait une formule générale, car l'ordre de mes matrices va varier de 2 à 6 en général.

EDIT: mais c'est vrai que, pour une telle fenetre d'ordres, il serait plus efficace de creer des sous-fonctions optimisees pour chaque ordre jusqu'a 5 ou 6, puis une sous-fonction generale pour les ordres superieurs...

[Rafy]

En recomptant pour un pivot de Gauss d'ordre 4 un petit peu optimise, j'ai 23 multiplications, 3 divisions, 14 soustractions, et 23 affectations.

ben je ne sais pas comment tu as fais pour trouver autant d'opérations !
Je viens de le refaire, je trouve comme j'ai dit tout à l'heure...
Alors 23 multiplications je ne trouve pas ça... 3 divisions, non plus je ne vois pas comment tu fais ça....

[alveric]

En recomptant pour un pivot de Gauss d'ordre 4 un petit peu optimise, j'ai 23 multiplications, 3 divisions, 14 soustractions, et 23 affectations.

ben je ne sais pas comment tu as fais pour trouver autant d'opérations !
Je viens de le refaire, je trouve comme j'ai dit tout à l'heure...
Alors 23 multiplications je ne trouve pas ça... 3 divisions, non plus je ne vois pas comment tu fais ça....

• premiere iteration:[list:ec7f398d05]
• 1/a11 soit une division
• pour la deuxieme ligne: a21 * (1/a11)
• a22 = a22 - (a21/a11) * a12
• a23 = a23 - (a21/a11) * a13
• a24 = a24 - (a21/a11) * a14
• idem pour les 3e et 4e lignes, soit 4 multiplications, 3 soustractions par ligne (pas de calcul de a21 qu'on negligera de toute facon apres...), d'ou 1 division, 12 multiplications et 9 soustractions pour la premiere etape

[*]1/a22[*]a33 = ...[*]idem jusqu'a a44 = a44 - a43/a33 * a34[/list:u:ec7f398d05]Pour la seconde etape: 1 division, 2*3 = 6 multiplications et 2*2 = 4 soustractions.
Pour la troisieme etape: 1 divison, puis deux multiplications et une soustraction.
Et enfin les trois multiplications pour calculer le produit de la diagonale.
D'ou 3 divisions, 12 + 6 + 2 + 3 = 23 multiplications, et 9 + 4 + 1 = 14 soustractions.
Mais evidemment on perd en precision par rapport a calculer d'abord les multiplications puis faire les divisions... C'est un compromis (inutile pour l'ordre 4, comme vu precedemment).

[Matthieu Brucher]

Oui, 3 divisions, je suis d'accord, une par pivot - d'ailleurs ou stock toujours l'inverse du pivot pour ne pas avoir à le recalculer -

Je ne parlais pas de l'ordre de complexité, je parlais de l'ordre par rapport à ce que tu disais multiplication puis division ou division puis multiplication ! La complexité, je sais ce que c'est merci !

[DrTopos]

Entre ce que j'ai proposé et la méthode du pivot, il n'y a pas seulement une question de performances. Ce qui me chagrine encore une fois est que le déterminant étant un polynôme, le fait d'introduire des divisions est un peu comme passer par New York pour aller de Châtelet à Saint-Lazare.

De toute façon, les résultats risquent de ne pas être les mêmes. Le problème avec le pivot, en plus de la division, est qu'il faut tester la nullité de coefficients. Or ce test est loin d'être rigoureux, car comme cela a été dit précédemment, c'est une comparaison avec un nombre petit et assez arbitraire. Il est possible que le pivot soit plus rapide (j'en doute beaucoup), mais sur le plan de la justesse il laisse un peu à désirer (encore que cela dépende de l'application qu'on a en vue).

Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.

[alveric]

Entre ce que j'ai proposé et la méthode du pivot, il n'y a pas seulement une question de performances. Ce qui me chagrine encore une fois est que le déterminant étant un polynôme, le fait d'introduire des divisions est un peu comme passer par New York pour aller de Châtelet à Saint-Lazare.

Je suis d'accord. La methode du pivot etait la premiere qui m'etait venue a l'idee (avec le fait d'ecrire la formule complete), mais je n'avais pas etudie sa complexite ni sa precision.

Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.

J'aimerais bien avoir l'algorithme qui fait ca, pour m'instruire... Ca se trouve ou ? Au moins, que je connaisse d'autres methodes que celles vues lors de mes cours...

[DrTopos]

Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.

J'aimerais bien avoir l'algorithme qui fait ca, pour m'instruire... Ca se trouve ou ? Au moins, que je connaisse d'autres methodes que celles vues lors de mes cours...

C'est une question d'algèbre extérieure. Je fais d'abord remarquer que le point important dans ce que j'ai proposé pour la dimension 4 est le fait que les 6 déterminants 2x2 ne sont calculés qu'une fois (et utilisés 2 fois chacun). Dans le cas d'une matrice 5x5, si on applique brutalement la méthode récursive de développement par rapport à une colonne, on calcule deux fois les déterminants 3x3 et 6 fois les déterminants 2x2. Dans le cas d'une matrice 6x6, on calcule 2 fois les déterminants 4x4, 6 fois les déterminants 3x3 et 24 fois les déterminants 2x2. Evidemment, c'est du gachis.

Donc toute la question est de savoir quoi calculer à l'avance pour le réutiliser plusieurs fois, et c'est là que l'algèbre extérieure intervient. On trouve des exposés d'algèbre extérieure dans les bouquins d'algèbre évidemment, mais aussi dans les bouquins de géométrie différentielle, car ces notions sont cruciales pour la définition des formes différentielles. Toutefois, pour ce qui nous occupe, il y a peu de choses à savoir.

Si E est un espace vectoriel de dimension n (disons sur le corps des réels), dans lequel on a choisi une base (e_1,...,e_n), et si k est un entier naturel, on peut considérer la k-ième puissance extérieure de E, qui est un espace vectoriel noté /\k(E) (c'est un lambda majuscule) ayant naturellement pour base toutes les parties à k éléments de l'ensemble {1,...,n}. Sa dimension est donc C(n,k) (coefficient du binôme de Newton). Par exemple en dimension 4, la dimension de /\2(R^4) est 6, et c'est pour cela qu'on devait stoker les 6 valeurs D_12, D_13, etc... Une base de /\2(R^4), pourrait être notée (e_12,e_13,e_14,e_23,e_24,e_34), mais elle est plutot notée:

Code :

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

1
2
 
(e_1^e_2, e_1^e_3, e_1^e_4, e_2^e_3, e_2^e_4, e_3^e_4)

où x^y n'est pas x à la puissance y, mais le produit extérieur des vecteurs x et y. Le produit exterieur est en fait une application de Ex...xE (produit cartésien de k facteurs) vers /\k(E) qui est multilinéaire alternée. En fait, ceci peut être vu comme la généralisation du calcul du déterminant aux matrices qui ne sont pas carrées.

Il est facile de calculer un produit extérieur par exemple celui des vecteurs (a,b) et (c,d) de R^2. Comme (a,b) = ae_1 + be_2, et (c,d) = ce_1 + de_2, la multiilinéarité, et l'antisymétrie (e_1^e_1 = e_2^e_2 = 0, e_2^e_1 = -e_1^e_2, etc...) donnent (a,b)^(c,d) = (ad-bc)(e_1^e_2). Tiens, revoila le déterminant ! Dans le cas de /\2(R^4), si on calcule (a_13,a_23,a_33,a_43)^(a_14,a_24,a_34,a_44) on trouve le vecteur de coordonnées D_12, D_13, etc... Donc dans la méthode que j'ai proposée, on commence par calculer le produit extérieur des deux dernière colonnes.

La méthode générale, pour une matrice nxn, dont les colonnes sont les vecteurs (de R^n) v_1,...,v_n, consiste à calculer le produit extérieur:

Code :

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

1
2
 
v_1^v_2^...^v_n

Dans le cas de la dimension 4, comme /\4(R^4) est de dimension 1 (car C(4,4) = 1), le produit ci-dessus est de la forme d(e_1^....^e_4), où d est un réel. En fait, d est tout simplement le déterminant de notre matrice. Ceci peut d'ailleurs ête considéré comme une définition du déterminant.

On voit donc, par exemple dans le cas d'une matrice 6x6, c'est à dire du produit extérieur v_1^...^v_6, qu'il faut commencer par calculer u = v_5^v_6 (15 coordonnées), puis w = v_4^u (20 coordonnées), puis t = v_3^w (15 coordonnées), puis s = v_2^t (6 coordonnées) et enfin v_1^s qui a une seule coordonnée qui est le déterminant cherché. On sait donc exactement compien de tableaux de nombres on doit réserver pour le calcul et de quelle taille.

J'espère avoir été clair, même si mon texte contient quelques affirmations non démontrées.

[alveric]

Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.

J'aimerais bien avoir l'algorithme qui fait ca, pour m'instruire... Ca se trouve ou ? Au moins, que je connaisse d'autres methodes que celles vues lors de mes cours...

C'est une question d'algèbre extérieure.

Je ne connaissais pas... On apprend tous les jours

Je fais d'abord remarquer(...)

J'espère avoir été clair, même si mon texte contient quelques affirmations non démontrées.

Fouia, ca m'a l'air interessant tout ca ! Il faudra que je relise a tete reposee, mais ca m'a l'air bien explique Merci !

[Matthieu Brucher]

Ouah...

[phlip]

Note: la méthode que j'ai proposée peut se généraliser en toute dimension. En particulier jusqu'à 6 ça ne pose pas de problème.

J'aimerais bien avoir l'algorithme qui fait ca, pour m'instruire... Ca se trouve ou ? Au moins, que je connaisse d'autres methodes que celles vues lors de mes cours...

C'est une question d'algèbre extérieure. Je fais d'abord remarquer que le point important dans ce que j'ai proposé pour la dimension 4 est le fait que les 6 déterminants 2x2 ne sont calculés qu'une fois (et utilisés 2 fois chacun).

La méthode se généralise à n'importe quelle dimension si on ne stocke pas les valeurs des 'petits' déterminant dans des variables mais dans un tableau.

L'explication donnée par DrTopos est très mathématique. Un aspect plus algorithmique de sa solution est qu'elle fait appel à la programmation dynamique, dont le principe est de résoudre un problème en le décomposant en sous problèmes plus faciles à résoudre, en stockant les solutions de ces sous problèmes dans un tableau pour éviter à les résoudre plusieurs fois (beaucoup de fois!).

[Rafy]

J'ai pas calculé comme ça... C'est pour ça quer je ne trouve pas le même nombre d'opérations :
-> Je calcul a11/a21, je multiplie chaque terme de la seconde ligne par ça.
Je fais la différence avec la première ligne (1 /, 3*, 3-)
-> De même avec la seconde ligne et la troisième (en tout 3/, 9*, 9-)
-> Je recommence au cran en dessous donc (2/, 4*, 4-)
-> Encore une fois (1/, 1*, 1-)
En tout 6/, 17*, 14-
Comme je l'avais dit au coup d'avant (je m'étais trompé sur la dernière multiplication j'en avais compté 4 au lieu de 3), donc j'ai moins d'opérations que toi Alveric, et aussi moins que DrTopos.
Même résultat, mais pas même démarche...