Modifying a sparse Cholesky factorization

Given a sparse symmetric positive definite matrix AA(T) and an associated s parse Cholesky factorization LDLT or LLT, we develop sparse techniques for obtaining the new factorization associated with either adding a column to A or deleting a column from A. Our techniques are based on an analysis and m anipulation of the underlying graph structure and on ideas of Gill et al. [ Math. Comp., 28 (1974), pp. 505-535] for modifying a dense Cholesky factori zation. We show that our methods extend to the general case where an arbitr ary sparse symmetric positive definite matrix is modified. Our methods are optimal in the sense that they take time proportional to the number of nonz ero entries in L and D that change.