Abstrakt. I detta dokument presenteras utformningen och genomförandet av en minnes skalbar parallell symbolisk faktoriseringsalgoritm för allmänna glesa osymmetriska matriser. Vår parallellalgoritm använder en graf partitionering metod, tillämpas på grafen av  och + på T, att partitionera matrisen på ett sådant sätt att är bra för gleshet bevarande samt för parallell faktorisering. Delningen ger ett s.k. separatorträd som representerar beroendena bland beräkningarna. Vi använder separatorträdet för att distribuera inmatningsmatrisen över processorer med hjälp av ett blockcykliskt tillvägagångssätt och ett delträd till underprocessorkartläggning. Den parallella algoritmen utför en nederst upp traversal av avskiljarträdet. Med en kombination av höger- och vänster-liknande partiella faktoriseringar får algoritmen en kolumnstruktur av L och en radstruktur av U vid varje steg. Algoritmen genomförs i C och MPI. Från en prestandastudie på stora matriser visar vi att den parallella algoritmen avsevärt minskar minneskravet för det symboliska faktoriseringssteget, liksom det övergripande minneskravet hos den parallella lösaren. Det minskar också ofta körtiden för den sekventiella algoritmen, som redan är relativt liten. I allmänhet förhindrar den parallella algoritmen det symboliska faktoriseringssteget från att vara en tid eller minnes flaskhals av den parallella lösaren. 1. Vad är det för fel på dig? Inledning. Vi överväger att lösa ett sparsamt osymmetriskt system av linjära ekvationer Ax = b med en direkt metod, som först faktoriserar matrisen A till produkten av en enhet lägre triangulär matris L och en övre triangulär matris U, sedan löser LU x = b via två triangulära lösningar. En distinkt egenskap hos sparse LU factorization är begreppet infyllnad. Det vill säga, en nolla element i den ursprungliga matrisen A kan bli nonzero i L och U. Syftet med symbolisk faktorisering är att beräkna den icke-noll struktur av faktorerna L och U, som innehåller de ursprungliga icke-noll element i A samt de fyllda elementen. När det inte finns något behov av att pivot under numerisk faktorisering, kan nonzero strukturen av L och U beräknas utan att hänvisa till de numeriska värdena av matrisen. Detta gör att vi kan allokera tillräckligt med minne och organisera beräkningar före numerisk faktorisering. Beräkningsmässigt är symbolisk faktorisering vanligtvis mycket snabbare än numerisk faktorisering, och därför har det inte funnits mycket motivation att parallellisera detta steg. Men eftersom numerisk faktorisering har gjorts mer och mer skalbar, kan symbolisk faktorisering bli en allvarlig flaskhals. I synnerhet kräver en sekventiell algoritm att matris A:s icke-nollstruktur monteras på en processor, vilket leder till en allvarlig flaskhals i minnet (om inte tidsmässigt). Vi har därför konstruerat och implementerat en minnesskalbar symbolisk faktoriseringsalgoritm för distribuerade minnesmaskiner. Den parallella algoritmen och programvaran är lämpliga för sparse LU factorization med statisk vridning [20]. Vi utvecklade denna parallellalgoritm inom ramen för SuperLU DIST [20] lösaren, som är en allmänt använd sparse direktlösare för distribuerade minnesparallelldatorer. SuperLU DIST innehåller flera olika steg i lösningsprocessen: 1. Välj en permutationsmatris P 1 och diagonala matriser D 1 och D 2 så att diagonala poster av P 1 D 1 AD 2 är ±1 och magnituderna av off-diagonala poster begränsas av 1. Ovanstående jämvikt och permutation bidrar till att säkerställa noggrannheten hos den beräknade lösningen. För närvarande uppnås detta med hjälp av HSL-rutinen MC64 [6]. Syftet med den stora diagonala permutationen är att minska sannolikheten för att stöta på små pivoter under faktorisering. 2. Utgångspunkten är följande: Ordna om ekvationerna och variablerna genom att använda en heurist som väljer en per-
I REF används pivoting för att minska antalet fyllningar för LU factorization.
PARALLEL SYMBOLIC FACTORIZATION FOR SPARSE LU WITH STATIC PIVOTING
{'venue': 'ICS', 'journal': None, 'mag_field_of_study': ['Computer Science']}