Abstrakt. En parallell algoritm presenteras för LU nedbrytning av en allmän gles matris på en distribuerad MIMD multiprocessor med ett kommunikationsnät med kvadratiska maskor. I algoritmen tilldelas matriselement till processorer enligt nätdistributionen. Varje processor representerar icke-nollelementen i sin del av matrisen genom en lokal, ordnad, tvådimensionell länkad lista datastruktur. Komplexiteten i viktiga verksamheter på denna datastruktur och på flera andra analyseras. Vid varje steg i algoritmen utförs en parallell sökning efter en uppsättning m-kompatibla pivotelement. Markowitz räknar av de pivot elementen är nära till minimum, för att bevara glesheten i matrisen. Pivotelementen uppfyller också ett tröskelkriterium för att säkerställa numerisk stabilitet. Kompatibiliteten av m pivots möjliggör samtidig eliminering av m pivot rader och m pivot kolumner i en rank-m uppdatering av den reducerade matrisen. Experimentella resultat på ett nätverk av 400 transputatorer presenteras för en uppsättning testmatriser från Harwell-Boeing sparse-matrissamlingen.
Till exempel Van der Stappen et al. REF presenterar en algoritm för parallell beräkning av LU-nedbrytningen på ett meshnätverk av transpondrar där varje processor innehar en del av matrisen.
Parallel Sparse LU Decomposition on a Mesh Network of Transputers
{'venue': None, 'journal': 'SIAM Journal on Matrix Analysis and Applications', 'mag_field_of_study': ['Mathematics']}