Ring-orienterade algoritmer för parallella matrisfaktoriseringar

Vid tekniska beräkningar är man ofta intresserad av att lösa linjära ekvationssystem AX = B, där matriserna A och B är kända och matrisen X är obekant. Vanligen görs detta genom att matrisen A faktoriseras (LU, QR, Cholesky) till triangulär form varpå enklare tringulära system löses. Eftersom matrisfaktoriseringar har relativt hög komplexitet så kan stora problem ta orimligt lång tid att lösa på en enprocessorsmaskin. Nedan följer en enkel algoritm (stegvis beskrivning) av hur en faktorisering isället kan göras parallellt på en maskin med flera processorer:

Dela in A i ett antal kolumnblock som fördelas jämnt över processorerna (normalt flera block per processor).
Ägaren till det 1:a kolumnblocket faktoriserar blocket och skickar det till de övriga processorerna.
Alla processorer uppdaterar sina resterande block m a p det faktoriserade blocket.
Nu är första blocket klart. Faktoriseringen fortsätter genom att samma algoritm appliceras på den resterande matrisen.

Denna algoritm kan göras mer sofistikerad för att i största möjliga mån undvika att processorer skall vara utan arbete och för att göra algoritmen möjlig att implementera effektivt på ett stort antal olika parallellarkitekturer. Exempel på hur dessa algoritmers kommunikationsmönstret ser ut för olika topologier finns här.

Referenser

K. Dackland, E. Elmroth, B. Kågström, and C. Van Loan. "Parallel Block Matrix Factorizations on the Shared Memory Multiprocessor IBM 3090 VF/600J". International Journal of Supercomputer Applications, 6(1):69--97, 1992.

K. Dackland, E. Elmroth, B. Kågström, and C. Van Loan. "Design and Evaluation of Parallel Block Algorithms: LU Factorization on an IBM 3090 VF/600J". In J. J. Dongarra et al, editor, Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing, pages 3--10, Houston, 1992. SIAM Publications.

K. Dackland and E. Elmroth. "Design and Performance Modeling of Parallel Block Matrix Factorizations for Distributed Memory Multicomputers". In Proceedings of the Industrial Mathematics Week, pages 102--116, Trondheim, 1992.

K. Dackland, E. Elmroth, and B. Kågström. "A Ring-Oriented Approach for Block Matrix Factorizations on Shared and Distributed Memory Architectures". In R. F. Sincovec et al, editor, Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing , pages 330--338, Norfolk, 1993. SIAM Publications.

K. Dackland and E. Elmroth. "Design, Modeling, and Evaluation of Parallel Block Matrix Factorization Algorithms for Shared and Distributed Memory Architectures". Licentiate thesis UMINF-92.07, Institute of Information Processing, University of Umeå, S-901 87 Umeå , Sweden, June 1992.

K. Dackland and E. Elmroth. "Parallel Block Matrix Factorizations for Distributed Memory Multicomputers". Report UMINF-92.03, Institute of Information Processing, University of Umeå, S-901 87 Umeå, Sweden, May 1992.

K. Dackland and E. Elmroth. "Parallella beräkningar på IBM 3090/600E VF: Blockalgoritmer för matrismultiplikation och LU-faktorisering". Master thesis UMNAD-66.90, Institute of Information Processing, University of Umeå, S-901 87 Umeå, Sweden, 1990.

K. Dackland and E. Elmroth. "Ring-oriented Block Matrix Factorization Algorithms for Shared and Distributed Memory Architectures". Report UMINF-92.04, Institute of Information Processing, University of Umeå, S-901 87 Umeå , Sweden, June 1992.