Abstrakt. PHIDAL (Parallel Hierarchical Interface Decomposition ALgoritm) är en parallell ofullständig faktoriseringsmetod som utnyttjar en hierarkisk interface sönderdelning av adjakens graf av koefficientmatrisen. Idén om nedbrytningen är liknande den av de välkända wirebasket tekniker som används i domän sönderdelning. Metoden är dock utformad för allmänna, oregelbundet strukturerade, glesa linjära system. Detta dokument beskriver några algoritmer för att erhålla bra kvalitet hierarkiska graf sönderdelningar och diskuterar det parallella genomförandet av faktoriseringsförfarandet. Numeriska experiment rapporteras för att illustrera skalbarheten av algoritmen och dess effektivitet som en allmän syfte parallell linjär systemlösare. Nyckelord. Parallellofullständig LU faktorisering, ILU, Sparse Gaussian Eliminering, Wirebasket nedbrytning, Interface nedbrytning, Prekonditionering, ILU med tröskel, ILUT, Iterativa metoder, Sparse linjära system. AMS-ämnesklassificeringar. 65F10, 65N06. 1. Vad är det för fel på dig? Inledning. Ett antal Ofullständiga LU factorization tekniker har utvecklats under de senaste åren som försöker kombinera några av de allmänna funktionerna hos standard ILU-förkonditionatorer med de goda skalbarhet attributen för flera nivåer metoder. Exempel är ILU med multieliminering (ILUM, [14] ), MLILU [3], och MRTLU algoritmer [4], och Algebraic Recursive Multilevel Solver (ARMS) [17] och dess parallella version pARMS [9]. En ingrediens som är gemensam för alla dessa metoder är att omordna det linjära systemet för att möjliggöra en parallell (ofullständig) eliminering av grupper av okända. Lösningsalgoritmer som implementerar liknande strategier inom domännedbrytning har också utvecklats och kan till exempel hittas i paketet pARMS [9]. I detta dokument presenteras en ny teknik i denna kategori. Den nya metodens huvudattraktion är att den utnyttjar en statisk "hierarkisk" nedbrytning av grafen som ger naturlig parallellism i faktoriseringsprocessen. Detta står i kontrast till den metod som används i pARMS där de oberoende uppsättningarna och nivåerna definieras dynamiskt. Den underliggande beställning på vilken metoden är baserad påminner om "wirebasket" tekniker för domän nedbrytningsmetoder [18, 19], där korspunkter i en domän partitionering spelar en viktig roll. Korspoäng har spelat en särskild roll i många domännedbrytningstekniker, se [5] till exempel. Man kan också se metoderna från vinkeln av en ILU factorization i kombination med en form av nästlade dissektion ordning där korspunkter i separatorerna spelar en speciell roll. I detta avseende har metoden en viss likhet med FETI-metoden [6]. De idéer som diskuteras i detta dokument liknar också dem som skisserats av Magolu Monga Made och van der Vorst [12, 10, 11], för matriser som härrör från ändlig skillnad diskretiseringar av 2-D partiella differentialekvationer. Algoritmen är baserad på att definiera en "hierarkisk gränssnittsstruktur". Den hierarkiska nedbrytningen börjar med en partitionering av grafen, med ett lager överlappning. Därefter definieras "steg" eller "nivåer" från denna partitionering, där varje nivå består av en uppsättning grupper eller anslutningar (små anslutna subgrafer). Nivåerna lyder en viktig egenskap som är att varje kontakt på en given nivå är en separator för kontakter på en lägre nivå. Således, för en enkel 5-punkts graf anslutningarna på nivå ett är uppsättningar av inre noder för varje subdomän som erhålls från partitioneringen. Nivå två omfattar gränssnitten mellan domäner med undantag av korspunkter, och nivå tre består av alla korspunkter. Vertikerna är globalt ordnade efter nivå, i ökande ordning av nivånummer. Den ofullständiga faktoriseringsprocessen fortskrider efter nivå från lägsta till högsta. På grund av separation egenskap kopplingar på olika nivåer, visar det sig att denna process kan göras mycket parallellt genom att justera släppa strategi till nivåerna. Mer exakt, de släppa strategier kommer att försöka upprätthålla den oberoende uppsättning struktur som extraheras från gränssnittet nedbrytning. Som redan nämnts är en stor skillnad mellan denna metod och befintliga metoder av denna typ, såsom pARMS, att den förordning som används för parallellism, utförs i början i stället för dynamiskt. Detta har både fördelar och nackdelar. Eftersom beställningen är statisk är faktoriseringen ganska snabb.
P MILU REF presenterar en ny teknik för att omordna ett linjärt system för att avslöja större parallellism.
A PARALLEL MULTISTAGE ILU FACTORIZATION BASED ON A HIERARCHICAL GRAPH DECOMPOSITION ∗
{'venue': 'SIAM J. Scientific Computing', 'journal': 'SIAM J. Scientific Computing', 'mag_field_of_study': ['Mathematics', 'Computer Science']}