I detta papper beskriver vi skalbara parallella algoritmer för sparse matris factorization, analysera deras prestanda och skalbarhet, och presentera experimentella resultat för upp till 1024 processorer på en Cray T3D parallelldator. Genom vår analys och experimentella resultat visar vi att våra algoritmer avsevärt förbättrar teknikens tillstånd i parallell direkt lösning av glesa linjära system – både i form av skalbarhet och övergripande prestanda. Det är ett välkänt faktum att tät matris factorization skalar väl och kan genomföras effektivt på parallella datorer. I detta dokument presenterar vi de första algoritmerna för att faktor en bred klass av glesa matriser (inklusive de som uppstår från två- och tredimensionella finita elementproblem) som är asymptotiskt lika skalbara som täta matrisfaktoriseringsalgoritmer på en mängd parallella arkitekturer. Våra algoritmer medför mindre kommunikation overhead och är mer skalbara än någon tidigare känd parallell formulering av gles matris factorization. Även om vi i detta dokument diskuterar Cholesky factorization av symmetriska positiva bestämda matriser, algoritmerna kan anpassas för att lösa glesa linjära problem minst kvadrater och för Gaussian eliminering av diagonalt dominerande matriser som är nästan symmetriska i struktur. En implementering av en av våra glesa Cholesky factorization algoritmer levererar upp till 20 GFlops på en Cray T3D för medelstora strukturteknik och linjära programmeringsproblem. Såvitt vi vet är detta den högsta prestanda som någonsin erhållits för gles Cholesky factorization på någon superdator.
Gupta m.fl. REF beskriver skalbara parallella algoritmer för sparse matris factorization, analysera deras prestanda och skalbarhet.
Highly Scalable Parallel Algorithms for Sparse Matrix Factorization
{'venue': 'IEEE Trans. Parallel Distrib. Syst.', 'journal': None, 'mag_field_of_study': ['Computer Science']}