A CHOLESKY UPDATING AND DOWNDATING ALGORITHM FOR SYSTOLIC AND SIMD ARCHITECTURES

This paper presents an algorithm for maintaining Cholesky factors of symmetric positive definite matrices under arbitrary rank-one changes. The algorithm synthesizes Carlson's updating algorithm, and the downdating algorithm recently suggested by Pan to arrive at an algorithm which 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 an 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 emphasize the simplicity and practicality of the proposed scheme.