En ny metod presenteras för att distribuera data i gles matris-vektor multiplikation. Metoden är tvådimensionell, försöker minimera den sanna kommunikationsvolymen, och försöker också sprida beräkning och kommunikation fungerar jämnt över processorer. Metoden börjar med en rekursiv tvådelning av sparse matris, varje gång dela en rektangulär matris i två delar med ett nästan lika antal nonzeros. Kommunikationsvolymen som orsakas av splittringen är minimerad. Efter matrixpartitioneringen partitioneras in- och utmatningsvektorerna med målet att minimera den maximala kommunikationsvolymen per processor. 1. Vad är det för fel på dig? Inledning. Sparse matris-vektor multiplikation ligger i hjärtat av många iterativa lösare för linjära system och eigensystem. I dessa lösare, en multiplikation u := Av måste utföras upprepade gånger för samma m × n sparse matris A, varje gång för en annan ingång vektor v. På en distribuerad-minne parallell dator, effektiv multiplikation kräver en lämplig distribution av data och tillhörande arbete. Detta kräver i synnerhet att den glesa matrisen och ingångs- och utgångsvektorerna distribueras över p-processorerna i den parallella datorn så att varje processor har ungefär samma antal nonzeros och så att kommunikationens overhead är minimal. Den naturliga parallella algoritmen för gles matris-vektor multiplikation med en godtycklig fördelning av matrisen och vektorerna består av följande fyra faser: 1. Varje processor skickar sina komponenter v j till de processorer som har en nonzero a ij i kolumn j.
Vastenhouw och Bisseling REF föreslår rekursiv bidelning av den allmänna glesa matrisen, växlande mellan rad- och kolumnriktningar.
A two-dimensional data distribution method for parallel sparse matrix-vector multiplication
{'venue': 'SIAM Review', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}