Kyng's randomized approximate Cholesky factorization versus classical incomplete factorizations

Kyng's randomized approximate Cholesky (AC) factorization can be better preconditioners than classical incomplete factorizations (IC) for graph Laplacian matrices and related matrices. One possible advantage of AC is that it may be better, on average, at preserving row sums than IC, i.e., if A is the matrix, L is an approximate or incomplete Cholesky factor, and e is the vector of all ones, L L' e is closer to A e for AC than IC, for similar numbers of nonzero entries. This begs a comparison of AC with modified IC (MIC), which is designed to preserve row sums. AC may still be better in this case, which means that preserving row sums is not the entire story. We will attempt to give a full explanation with numerical experiments with different modified/unmodified incomplete factorizations (threshold and level-based) and different matrix orderings. We will also propose some potential applications of AC in stochastic particle simulations that take advantage of the fact that its factorization is exact in expectation.