TR#: | CS0667 |

Class: | CS |

Title: | A NEW DIVIDE AND CONQUER PARALLEL ALGORITHM
FOR THE CHOLESKY DECOMPOSITION OF BAND MATRICES |

Authors: | I. Bar-On |

Not 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. |

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/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