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

Description

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

Sujets

• Graphe biparti
• Colonne

Informations

• Publié par: pefav
• Nombre de lectures: 92
• Langue: Français

Extrait

Algorithmique et Programmation Projet:permutationsdematricescreusesetd´ecompositionsdegraphes

Ecolenormalesup´erieure De´partementd’informatique [e-mail] 2011-2012

LepivotdeGauss(etlesm´ethodescomparables)restentunedesalternativeslesplusefficacespour re´soudredessyst`emesline´airesA∙x=y. Quand la matriceAestdensei,nly’pasachd’angrae`os   3 faire,etlacomplexit´eduprocessusestdel’ordredeOnsadeorlgratvueiq(snoselie´poitartimhse asymptotiquement plus rapides existent, mais ils sont rarement plus efficaces en pratique). Par contre, quandAestcreusetdarupplefficoesesosstneicxuage´tn(c’a`d-se-teualriqe`az´ero),ilestpossbiel d’utiliserdesalgorithmesplusefficacesa`lafoisenth´eorieetenpratique.Lessyste`mescreuxapparaissent naturellementdansungrandnombredesituations,etonpeutge´rerdesmatricescreusesbeaucoupplus 6 grandesquelesdenses.Parexemple,ontraiteaujourd’huidessyste`mesde8.7∙´01auqenoitanesutant d’inconnues.Stockerlamatricedense(deflottants64bits)ne´cessiterait≈550 tera-octets, et pivoter la 23.5 matrice dense demanderait≈ga´ietr,acebtlten.’Measitspeansf’snnca,qeium´eptraeitraeoci01o 6 que 66∙lin´`emesystondunoaderpsceroaerienbteotrˆeutpentrap(eues´en-no01trenosenitulllunU.se 9 lesbonnestechniques)apr`es≈45∙e`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.L’int´erˆetdelaproc´edureestmultiple: –Contrairementa`l’e´liminationdeGauss,cetteproce´duren’augmentepaslenombred’entre´esnon- nulles dans la matrice. –Unefoislamatriceenformetriangulaire,ilserasuffisantd’appliqueruner´esolutionline´aire(creuse) auxblocsdiagonauxpourr´esoudrelesyste`meline´airecorrespondant(cequifaitgagnerdutemps et de l’espace).

Matrices et graphes.emUnriatcacesi,eament´eoriraph’ungdecirtamalemmocevureettˆeuep´err pourlesmatricesrectangulairesc’estmoinsclair.Enfait,unematricerectangulairede´critnaturellement un graphebipartidu“socolnnse.”ig“ls”neleetoesnueonl,sdonsesdueadeu:ilyesdextypon-ntne´roei Chaqueentr´eenon-nulledelamatricecorrespond`aunearˆetedugraphe.Leproble`meoriginalsurles matricescreusesetransportedonc(etser´esoud)commeunproble`medede´compositiondegraphes.

1Premie`rephase:de´compositiondeDulmage-Mendelsohn Ons’attaquemaintenanta`lamisesousformetriangulaireparblocdelamatriced’adjacenced’un graphe biparti connexe. On va en fait partitionner les lignes (respectivement, les colonnes) en trois sous- ensembles,cequirevient`apartitionnerlamatriceenneufsous-matrices,donttroisvonts’ave´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(c’est-`a-direunsous-ensembledesarˆetesleplusgrandpossibletelqu’ellesn’aientaucunsommet encommun).Nousintroduisonsci-dessouslaterminologien´ecessaire. ´ Etantdonn´euncouplage,unsommetlibren’appartienta`uaucenraeˆetudnU.egalpuocchemin alternantarhplsgednnaehimepaspassnereequinctueslrapeˆmexuedsioftd,etonsomeetmm uneareˆtesurdeuxappartientaucouplage.Unchemin augmentantest un chemin alternant dont les deuxextre´mite´ssontdessommetslibres.L’ide´ecommune`alaplupartdesalgorithmesquicalculentun couplagemaximalestlere´sultatsuivant:

1