# Technical Report CS0665

 TR#: CS0665 Class: CS Title: NEW DIVIDE AND CONQUER PARALLEL ALGORITHMS FOR THE CHOLESKY DECOMPOSITION AND GRAM-SCHMIDT PROCESS Authors: I. Bar-On PDF Not Available Abstract: We present a new divide and conquer parallel algorithm for the Cholesky decomposition of dense symmetric positive definite matrices. The decomposition problem is reduced to \ $p$\ independent smaller decomposition problems in \ $log\ p$\ stages. We introduce a new iterative method employing only matrix add and multiply operations for that purpose. The new algorithm offers an \ $O(p)$\ speed-up over the sequential algorithm and can be implemented efficiently on many existing parallel computers. More theoretically, the algorithm runs in \ $O(log^{2}n)$\ time using\ $p = {\cal M}(n)/log^{2}n$\ processors. We conclude with an application to the \ $QR$\ factorization of a full rank matrix. 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/CS0665), rather than to the URL of the PDF files directly. The latter URLs may change without notice.