Technical Report CS0661

TR#:CS0661
Class:CS
Title: EFFICIENT LOGARITHMIC TIME PARALLEL ALGORITHMS FOR THE CHOLESKY DECO~OSITION OF BAND MATRICES
Authors: Ilan Bar-On
PDFCS0661.pdf
Abstract: We present a parallel algorithm for finding the Cholcsky decomposition of a band symmetric positive definite matrix of order n and bandwidth m in 0(nm2 /p) time using p ~ (n/m)/Iog(n/m) processors. Furthermore, there are only O(log p) interprocessor conununication phases, and the operation count is only as twice as that of the sequential algorithm. We conclude that the algorithm can be efficiently implemented 011 existing parallel computers. We also consider the general bandwidth case and show that the algolithm can be implemented in O(log m log n) time using p = nm2/(log m log n) processors, with at most o(log2p) interprocessor communication phases.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1990/CS/CS0661), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1990
To the main CS technical reports page

Computer science department, Technion
admin