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

Publié par

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


Publié le : mardi 19 juin 2012
Lecture(s) : 91
Source : di.ens.fr
Nombre de pages : 4
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
Theore`me1.Un couplage est maximal si et seulement si il n’existe pas de chemin augmentant. Eneet,´etantdonne´uncouplage,etuncheminaugmentant,alorsonpeutconstruireunnouveau couplageayantuneareˆtedeplus.Ilsutdeipperlesareˆtesducheminaugmentant(siellese´taient danslecouplage,onlesenretire;siellesny´etaientpas,onlesyajoute).
Algorithme de Ford-Fulkerson.Pour trouver un chemin augmentant, on part d’un sommet libre etonfaitunparcoursenprofondeur,enmarquantvutouslessommetsvisit´es.Siaucunchemin nesttrouve´,onpartdunautresommetlibre,maisonnerevisitepaslessommetsvus.Onpeut utiliserdautresm´ethodes,commelalgorithmedEdmonds-Karp,lalgorithmeHongrois,nimportequel algorithme de flot maximal, etc. C’est vous qui voyez.
“Cheap matching”.ueenb´q´entanugmelestts,iehedehcrniashcmerdceanelecarslansedtnavA deconstruireuncouplageleplusgrandpossibledemani`eregloutonne,parcequecestbienplusecace. Parfois, la phase gloutonne trouve toute seule un couplage maximal.
1.2De´compositiondungraphebiparti Unefoisquonacalcul´euncouplagemaximum,onpeutpartitionnerlegraphe.SiLetCgnen´esidt respectivement l’ensemble des sommets lignes et des sommets colonne, on pose :
Lv={engnlietarpp-aonupedtnanmmosnusi´ieosmmtelssiesesblneigccsaanimretlurapehcn} Lh={saccigneblesessitelsosmmntnapudeunismmsourapehcnanimretlari´eteocolnnnenoa-pp} Cv={animehcnurapselbsiesccsaneonolscnoa-ngneteilosmmisundepunantlterarppei´sommet} Ch={asensecccstenolommsootcnoeldnunpnseinaunotslmrmetaenir´uenchemiosni-balpepsapra} Ls=L(LvLh) Cs=C(CvCh)
Onpeutd´emontrer(cenestpasdemand´e)que: iosselbmesnesecsudiuxdea--`uxdentsjoints.)To iicouplage relie les lignes de) LeLv(resp.Lh)eda`locsennoedsCv(respCh). Il s’ensuit que|Lv|>|Cv|, et|Lh|<|Ch|. iii) Lecouplage relie parfaitement les lignes deLsaux colonnes deCsI.eldne´couleque|Cs|=|Ls|. ivreestneˆetdrapasayln,irtpa´eededhpargelsnaD)ChetLs, ni entreChetLv, ni entreCsetLv. Dudernierpoint,ond´eduitquilyaunepermutationdeslignesetdescolonnesquitransformelamatrice (d’adjacence du graphe) en : ChCsCv LhMhA B Ls0MsC
Lv0 0Mv
O`ulasous-matriceMhest plus large que haute, la sous-matriceMstam-eciraltesuostcarr´e,esMv est plus haute que large. L’existence du couplage garantit d’autre partMsti`erementaidenuaneelanog non-nulle,etqueladiagonalequipartdanslecoininfe´rieurdroit(resp.supe´rieurgauche)deMh(resp. Mvlecuesrceunpaltc[snaO.]2tsulde´renparcoursasevdcseneesbmelenilstbi.Ceullenon-sent) profondeur.
2
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.