| TR#: | CS0661 |
| Class: | CS |
| Title: | EFFICIENT LOGARITHMIC TIME PARALLEL ALGORITHMS FOR THE CHOLESKY DECO~OSITION OF BAND MATRICES |
| Authors: | Ilan Bar-On |
| CS0661.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. |
| Copyright | The 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