Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Algorithmique et Programmation Projet permutations de matrices creuses et decompositions de graphes

4 pages
Algorithmique et Programmation Projet : permutations de matrices creuses et decompositions de graphes Ecole normale superieure Departement d'informatique 2011-2012 Le pivot de Gauss (et les methodes comparables) restent une des alternatives les plus efficaces pour resoudre des systemes lineaires A · x = y. Quand la matrice A est dense, il n'y a pas grand'chose a faire, et la complexite du processus est de l'ordre de O ( n3 ) operations (il est vrai que des algorithmes asymptotiquement plus rapides existent, mais ils sont rarement plus efficaces en pratique). Par contre, quand A est creuse (c'est-a-dire que la plupart de ses coefficients sont egaux a zero), il est possible d'utiliser des algorithmes plus efficaces a la fois en theorie et en pratique. Les systemes creux apparaissent naturellement dans un grand nombre de situations, et on peut gerer des matrices creuses beaucoup plus grandes que les denses. Par exemple, on traite aujourd'hui des systemes de 8.7 · 106 equations en autant d'inconnues. Stocker la matrice dense (de flottants 64 bits) necessiterait ≈ 550 tera-octets, et pivoter la matrice dense demanderait ≈ 1023.5 operations, ce qui n'est pas gerable. Mais en fait, cette matrice n'a que 66 · 106 entrees non-nulles. Une solution du systeme lineaire correspondant peut etre obtenue (par les bonnes techniques) apres ≈ 45 · 109 operations arithmetiques, ce qui est par contre tres faisable.

  • graphe biparti

  • colonne

  • bloc diagonal

  • permutation des lignes

  • decomposition de dulmage-mendelsohn

  • resoudre des systemes lineaires

  • probleme de decomposition de graphes


Voir plus Voir moins
Algorithmique et Programmation Projet:permutationsdematricescreusesetd´ecompositionsdegraphes
Ecolenormalesup´erieure De´partementdinformatique td-algo@di.ens.fr 2011-2012
LepivotdeGauss(etlesm´ethodescomparables)restentunedesalternativeslesplusecacespour re´soudredessyst`emesline´airesAx=y. Quand la matriceAestdensei,nlypasachdangrae`os   3 faire,etlacomplexit´eduprocessusestdelordredeOnsadeorlgratvueiq(snoselie´poitartimhse asymptotiquement plus rapides existent, mais ils sont rarement plus efficaces en pratique). Par contre, quandAestcreusetdarupplecoesesosstneicxuage´tn(ca`d-se-teualriqe`az´ero),ilestpossbiel dutiliserdesalgorithmesplusecacesa`lafoisenth´eorieetenpratique.Lessyste`mescreuxapparaissent naturellementdansungrandnombredesituations,etonpeutge´rerdesmatricescreusesbeaucoupplus 6 grandesquelesdenses.Parexemple,ontraiteaujourdhuidessyste`mesde8.7´01auqenoitanesutant dinconnues.Stockerlamatricedense(deottants64bits)ne´cessiterait550 tera-octets, et pivoter la 23.5 matrice dense demanderaitga´ietr,acebtlten.Measitspeansfsnnca,qeium´eptraeitraeoci01o 6 que 66lin´`emesystondunoaderpsceroaerienbteotrˆeutpentrap(eues´en-no01trenosenitulllunU.se 9 lesbonnestechniques)apr`es45e`fserrtlb.eiaas10op´eratiorasnmhtiite´seuqeq,cesuiartpntco
Objectif du projet.ahuosnOrgorpetinarumeamhmitorlgeciruercnueetameneder´ntuieqenprse, et qui produit une permutation des lignes et une permutation des colonnes qui mettent la matrice sous formetriangulaireparblocs.Lint´erˆetdelaproc´edureestmultiple: Contrairementa`le´liminationdeGauss,cetteproce´durenaugmentepaslenombredentre´esnon-nulles dans la matrice. Unefoislamatriceenformetriangulaire,ilserasusantdappliqueruner´esolutionline´aire(creuse) auxblocsdiagonauxpourr´esoudrelesyste`meline´airecorrespondant(cequifaitgagnerdutemps et de l’espace).
Matrices et graphes.emUnriatcacesi,eament´eoriraphungdecirtamalemmocevureettˆeuep´err pourlesmatricesrectangulairescestmoinsclair.Enfait,unematricerectangulairede´critnaturellement un graphebipartidusocolnnse.iglsneleetoesnueonl,sdonsesdueadeu:ilyesdextypon-ntne´roei Chaqueentr´eenon-nulledelamatricecorrespond`aunearˆetedugraphe.Leproble`meoriginalsurles matricescreusesetransportedonc(etser´esoud)commeunproble`medede´compositiondegraphes.
1Premie`rephase:de´compositiondeDulmage-Mendelsohn Onsattaquemaintenanta`lamisesousformetriangulaireparblocdelamatricedadjacencedun graphe biparti connexe. On va en fait partitionner les lignes (respectivement, les colonnes) en trois sous-ensembles,cequirevient`apartitionnerlamatriceenneufsous-matrices,donttroisvontsave´rereˆtre nulles. On utilise lacemo´dnldmealgdee-MDeutionspoohsninocaontiesedqunien´dseutopiscemo,qui graphes bipartis.
1.1 CouplageMaximum Il faut dans un premier temps calculer uncouplage maximum(en anglais unmatching) dans le graphe biparti(cest-`a-direunsous-ensembledesarˆetesleplusgrandpossibletelquellesnaientaucunsommet encommun).Nousintroduisonsci-dessouslaterminologien´ecessaire. ´ Etantdonn´euncouplage,unsommetlibrenappartienta`uaucenraeˆetudnU.egalpuocchemin alternantarhplsgednnaehimepaspassnereequinctueslrapeˆmexuedsioftd,etonsomeetmm uneareˆtesurdeuxappartientaucouplage.Unchemin augmentantest un chemin alternant dont les deuxextre´mite´ssontdessommetslibres.Lide´ecommune`alaplupartdesalgorithmesquicalculentun couplagemaximalestlere´sultatsuivant:
1
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin