IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Fortran Discussion :

Vitesse inversion de matrice


Sujet :

Fortran

  1. #1
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut Vitesse inversion de matrice
    Bonjour,

    Je suis sur un ordinateur avec un Intel Core 2CPU T5500 à 1.66 GHz, 2Go de mémoire vive un système d'exploitation 32 bit et je suis sous Vista. Mon compilateur Fortran est Absoft80.

    Je dois inverser des matrices de grande taille (>10000), et j'ai fait quelques tests pour voir la vitesse d'inversion avec Fortran. Auparavant je travaillais sous Gauss mais je voulais améliorer la rapidité de mes programmes.

    Résultat, j'obtiens une vitesse plus lente avec Fortran ce qui m'étonne beaucoup. Avec le programme ci-dessous, l'inversion d'une matrice 2000*2000 (avec une fonction de la bibliothèque IMSL) prend environ 90-100 secondes alors que sous Gauss cela prend environ 3 fois moins de temps (?!?). Je débute sous Fortran donc j'ai plusieurs questions :Est-ce normal ? Faut-il que je spécifie quelque chose de particulier au moment de la compilation qui modifierait beaucoup la vitesse ? Y-a-t-il une fonction d'inversion de matrice plus efficace ? Merci beaucoup d'avance.

    use linear_operators
    implicit none

    integer, parameter :: n=2000
    real :: t1,t2
    REAL, ALLOCATABLE, DIMENSION(:, :: A, x
    ALLOCATE(A(n,n))
    ALLOCATE(x(n,n))
    ! Generate a random matrix.
    A = rand(A)
    call CPU_TIME( t1 )
    ! Compute the matrix inverse.
    x = .i.A;
    call CPU_TIME( t2 )

    ! call WRCRN ('EVAL', 1, n, x, 1, 0)
    print *,t2 - t1


    end

  2. #2
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    Pourquoi veux-tu inverser une matrice? Cela n'est presque jamais nécessaire, ni même utile.
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  3. #3
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut
    ça arrive très souvent en économétrie bayésienne par exemple (voir les articles de Chib pour en avoir une idée)...

  4. #4
    Membre confirmé
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    488
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2007
    Messages : 488
    Points : 593
    Points
    593
    Par défaut
    Bonjour,

    Faut-il que je spécifie quelque chose de particulier au moment de la compilation qui modifierait beaucoup la vitesse ?
    Oui. Tous les compilateurs proposent un certain nombre d'options de compilations qui optimisent le code (voir la doc du compilateur). Par rapport au cas non optimisé on obtient généralement des accélérations assez significatives.

    Ehouarn

  5. #5
    Membre éclairé Avatar de genteur slayer
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juin 2002
    Messages
    710
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2002
    Messages : 710
    Points : 825
    Points
    825
    Par défaut
    'ajoute, à ce jour le compilo le mieux optimisé que je connaisse est Ifort (intel fortran) sous unix... j'ai fait le test avec mon code de calcul (en gros résolution de système linéaire (non parrallèle) et j'ai un gain de 20% sur le temps de calcul simplement en passant de gfortran à ifort (plus quelques optimisation)
    de plus certain compilateur (comme ifort) font de la "parallèlisation" automatique, en gros, ils vectorise certaine boucle etc...

    mais si tu veux vraiment faire un gain de vitesse, tu peux commencer par changer d'algo de résolution... ou bien cherche à parallelisé (plus gros boulot)...
    il n'y a que ceux qui savent qui ne savent pas qu'ils savent...
    Libere-toi hacker, GNU's Not Unix!!!

  6. #6
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    les articles de Chib
    Où les trouve-t-on sur le Web?
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  7. #7
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut
    Bonjour,

    Merci pour ces premières réponses. Mais obtenez vous des temps de calcul comparables aux miens avec vos machines ?
    ça me pose de gros soucis car l'essentiel du temps de mon algorithme réside dans ces inversions de grosses matrices.

    Pour trouver des articles de Chib sur le web, ce n'est pas toujours très simple si on n'a pas d'accès à certaines revues scientifiques mais on trouve quelques liens vers ses working paper ici :

    http://www.olin.wustl.edu/faculty/chib/

    mais quoiqu'il en soit, vu le nombre d'articles pour améliorer les temps des inversions de matrices (un exemple : http://arxiv.org/abs/cs.DS/0412107), j'imagine que c'est utilisé dans d'autres domaines.

  8. #8
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    Pourquoi veux-tu inverser une matrice? Cela n'est presque jamais nécessaire, ni même utile.
    ça arrive très souvent en économétrie bayésienne par exemple (voir les articles de Chib pour en avoir une idée)...
    Sans vouloir lire tous ces article, où je risque de ne pas trouver ce que je cherche, je préfère reformuler ma question différemment:
    1. L'inversion de matrices 10 000*10 000 est-elle pour toi une étape intermédiaire, le but étant de résoudre des systèmes linéaires de 10 000 équations à 10 000 inconnues?
    2. Si c'est vraiment de la matrice inverse elle-même que tu as besoin, comment vas-tu en examiner ensuite les 100 000 000 termes.

    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  9. #9
    Membre éclairé Avatar de genteur slayer
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Juin 2002
    Messages
    710
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juin 2002
    Messages : 710
    Points : 825
    Points
    825
    Par défaut
    perso, non plus je n'inverse pas mes matrices: je résout des système linéaires (bon en plus je ne stoke même pas ces matrices héhéhé) donc je ne peux absolument pas te dire si je calcul plus vite ou pas que toi... cela dit je fait environ 10000 de résolution de système en quelques heures...

    si tu veux vraiment accélérer: si le résultat n'est pas la matrice inverse mais qu'elle est juste une étape intermédiaire, alors ne la calcul pas, y a des algo bien plus rapide!!!
    il n'y a que ceux qui savent qui ne savent pas qu'ils savent...
    Libere-toi hacker, GNU's Not Unix!!!

  10. #10
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    perso, non plus je n'inverse pas mes matrices: je résout des système linéaires
    Enfin quelqu'un qui fait les choses correctement!

    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  11. #11
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut
    Je comprends mieux ce que vous dites...

    Je ne savais pas que les procédures de résolutions de système n'impliquait pas necessairement une inversion de matrice à un moment où un autre (si vous avez de la doc dessus ça m'interesse). En bidouillant mon algorithme, je peux en effet m'y ramener puisque je multiplie ma matrice inverse par un vecteur à un moment.

    Dans ce cas, pour que je puisse comparer avec Gauss, quel temps de calcul avez vous grosso modo pour la resolution d'un système 2000*2000 ? Et si je peux gagner en stockage pour la matrice inverse, je suis très preneur également...

  12. #12
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    si vous avez de la doc dessus ça m'interesse
    J'ai même écrit un cours là-dessus:
    http://jmblanc.developpez.com/algori...mes-lineaires/
    Bonne lecture!

    Comme je vais m'absenter quelques jours, je te pose quelques questions sur tes matrices, afin de pouvoir te proposer la solution la mieux adaptée.
    1. Ta matrice est-elle symétrique?
    2. Si oui, est-elle définie positive (ça, ce n'est pas évident à vérifier, mais on pourra voir après)?
    3. Ta matrice est-elle creuse, voire très creuse (seulement un petit nombre de termes non nuls)? Quel pour-centage?
    4. Si oui, les termes non nuls sont-ils répartis d'une manière systématique ou au contraire aléatoire? Dans le premier cas, selon quelle règle?


    Selon tes réponses, je pourrais peut-être te poser encore une ou deux questions, mais ne te fais pas de soucis: on est sur la bonne voie.

    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  13. #13
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut
    Merci beaucoup.

    Ma matrice n'est pas creuse mais est définie positive par construction (elle est de type (I+uu') ).

  14. #14
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!

    Tout d'abord une petite question pour m'assurer que j'ai bien compris ton dernier message:
    elle est de type (I+uu')
    u est bien un vecteur colonne, ce qui fait que, s'il comporte 10 000 termes, ta matrice est de taille 10 000 * 10 000, et comporte, par conséquent 100 000 000 termes.

    Ce point étant réglé, passons aux choses sérieuses. Quand on fait du calcul numérique, il y a trois exigences:
    • Il ne faut pas dépasser la taille de la mémoire de l'ordinateur (à vérifier).
    • Le temps de calcul doit rester dans des limites acceptables (c'est l'objet de ta question).
    • Les résultats des calculs doivent être corrects (et là, il faut être très prudent).


    C'est pourquoi je te propose de procéder par étapes:
    1. Tu reprends le programme que tu as déjà écrit et tu l'exécutes à nouveau après y avoir ajouter quelques bricoles, soit:
      • affichage de l'heure avant et après la résolution du système linéaire;
      • calcul de c=A*x-b à partir de ta matrice originale A, du second membre b et de la solution calculée x et affichage de la norme euclidienne et du plus grand terme (en valeur absolue) de c, qui devraient théoriquement être nuls l'un et l'autre.
    2. Tu vas sur le site www.netlib.org et, dans la librairie LINPACK, tu prends les routines DGECO et DGESL avec lesquels tu résous ton système linéaire. Tu fais les mêmes chronométrages et contrôles qu'au point 1.; en plus, tu affiches la valeur de la variable RCOND.
    3. Tu recommences avec les routines DSICO et DSISL.
    4. Tu recommences avec les routines DPOCO et DPOSL.


    Quand tu as fait tout ça, tu mets tous ces résultats (chronométrage et contrôles) dans un message sur le forum.

    Bon travail!
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  15. #15
    Débutant
    Inscrit en
    Juillet 2007
    Messages
    386
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 386
    Points : 119
    Points
    119
    Par défaut
    Citation Envoyé par FR119492 Voir le message
    [*]Tu vas sur le site www.netlib.org et, dans la librairie LINPACK, tu prends les routines DGECO et DGESL avec lesquels tu résous ton système linéaire. Tu fais les mêmes chronométrages et contrôles qu'au point 1.; en plus, tu affiches la valeur de la variable RCOND.
    Toujours le meme probleme avec moi, comment utiliser les bibliotheques et le grandes routines?
    Jean Marc as tu un exemple test simple comment utiliser les routines que tu les a cites?
    merci

  16. #16
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    comment utiliser les bibliotheques et le grandes routines?
    Désolé, mais je ne comprend pas la question. Qu'as-tu fait et qu'est-ce qui n'a pas fonctionné?

    u est bien un vecteur colonne
    As-tu une idée de l'ordre de grandeur des composantes de u?
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  17. #17
    Débutant
    Inscrit en
    Juillet 2007
    Messages
    386
    Détails du profil
    Informations forums :
    Inscription : Juillet 2007
    Messages : 386
    Points : 119
    Points
    119
    Par défaut
    Je demandes comment utiliser les librairies en fortran? par exemple si je veux calculer la FFT d une matrice complexe , comment utiliser les bibliotheques? j ai besoin d un petit exemple svp
    merci

  18. #18
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    Je suis désolé, mais ta question est incompréhensible. Sait-tu ce qu'est un fichier .lib ? Connais-tu l'instruction Call ?
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

  19. #19
    Nouveau Candidat au Club
    Inscrit en
    Janvier 2009
    Messages
    7
    Détails du profil
    Informations forums :
    Inscription : Janvier 2009
    Messages : 7
    Points : 1
    Points
    1
    Par défaut
    Merci de toutes ces infos, je vais tester tout ça et mettre sur le fil...

    Pour répondre à ta question, oui, u est bien un vecteur colonne de taille 10 000 et donc la matrice correspondant est de taille 10 000 * 10 000.

    Bonne soirée.

  20. #20
    Rédacteur

    Homme Profil pro
    Comme retraité, des masses
    Inscrit en
    Avril 2007
    Messages
    2 978
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 83
    Localisation : Suisse

    Informations professionnelles :
    Activité : Comme retraité, des masses
    Secteur : Industrie

    Informations forums :
    Inscription : Avril 2007
    Messages : 2 978
    Points : 5 179
    Points
    5 179
    Par défaut
    Salut!
    Pour répondre à ta question, oui, u est bien un vecteur colonne de taille 10 000
    Ce n'est pas ma question: j'avais déjà compris ça. Ce que je veux savoir, ce n'est pas le nombre de composantes, mais leurs valeurs: sont-elles toutes positives? toutes inférieures à 1,0? Leur somme est-elle inférieure à 1, etc.?
    Jean-Marc Blanc
    Calcul numérique de processus industriels
    Formation, conseil, développement

    Point n'est besoin d'espérer pour entreprendre, ni de réussir pour persévérer. (Guillaume le Taiseux)

Discussions similaires

  1. Inversion de matrice
    Par mhooreman dans le forum Mathématiques
    Réponses: 6
    Dernier message: 26/10/2006, 19h35
  2. Probleme d'inversion de matrice subtil
    Par babycrash dans le forum C
    Réponses: 2
    Dernier message: 02/08/2006, 18h41
  3. inversion de matrice?
    Par babycrash dans le forum C
    Réponses: 17
    Dernier message: 21/06/2006, 23h18
  4. Comment inverser une matrice H(2,2) ?
    Par fafa624 dans le forum Langage
    Réponses: 4
    Dernier message: 29/06/2005, 11h23
  5. Calculer un inverse de matrice avec boost?
    Par Clad3 dans le forum Bibliothèques
    Réponses: 6
    Dernier message: 02/06/2005, 19h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo