Technical Report CS0667

TR#:CS0667
Class:CS
Title: A NEW DIVIDE AND CONQUER PARALLEL ALGORITHM FOR THE CHOLESKY DECOMPOSITION OF BAND MATRICES
Authors: I. Bar-On
PDFNot Available
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 appropriate speedup of order \mbox{$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 \mbox{$O(log\ m\ log\ n)$} time using \mbox{$p = (n/m {\cal M}(m)/\ log\ m\ log\ n)$} processors. Here, \mbox{${\cal M}(m) = m^{\beta}, 2 \leq \beta leq 3$}, and \mbox{$m^{\beta}/log\ m$} denotes the least number of processors required in order to multiply two matrices of order \ $m$\ in \mbox{$O(log\ m)$} time. This improves by a factor of \mbox{$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.
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/1991/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 1991
To the main CS technical reports page

Computer science department, Technion
admin