A CHOLESKY UPDATING AND DOWNDATING ALGORITHM FOR SYSTOLIC AND SIMD ARCHITECTURES

This paper presents an algorithm for maintaining Cholesky factors of s ymmetric positive definite matrices under arbitrary rank-one changes. The algorithm synthesizes Carlson's updating algorithm, and the downda ting algorithm recently suggested by Pan to arrive at an algorithm whi ch is both simple and allows for the pipelining of up- and downdates ( in any order). On an array of O(n2) processors, the algorithm allows a n n x n matrix to be updated at a cost per update that is independent of n. Implementation results on the 1024-processor AMT DAP-510 emphasi ze the simplicity and practicality of the proposed scheme.