Technical Report CS0667

TR#:CS0667
Class:CS
Title: A NEW DIVIDE AND CONQUER PARALLEL ALGORITHM FOR THE CHOLESKY PECOMPOSITION OF BAND MATRICES
Authors: I1an Bar-On
PDFCS0667.pdf
Abstract: We present a new divide and conquer parallel algorithm for finding the Cholesky decomposition of a band symmetric positive definite matrix. This is the first time such an algorithm is presented. All previously known parallel algorithms for this problem are direct implementations of the sequential methods, which as though, offer almost no speedup. Here, for the first time a parallel oriented algorithm is presented, with an approximate speedup of order p/3 given p processors. Moreover, the algorithm can be efficiently implemented on many existing parallel computers. We further discuss the more theoretical aspects of the algorithm, and show that it can be implemented efficiently in O(log m log n) time using p =(n/m)M(m)/{log m log n) processors. Here, M(m) = mfJ , 2 :0:::: f3 :5 3, and mfJ /log m denotes the least number of processors required in order to multiply two matrices of order m in O(1og m) time. This improves by a factor of log m the best previously known result for this problem. We conclude with an application of the algorithm to the finding of the eigenvalues of a non-singular band symmetric matrix. We show for the first time how to implement each iteration of the QR algorithm in the same complexity as above. Key Words. Cholesky decomposition, band matrices, parallel algorithm, QR algorithm.
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/CS0667), 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