Updating Hierarchical Factorizations
Victor Minden, Stanford University
Many fast direct algorithms for solving linear systems arising from discretized partial differential equations or boundary integral equations rely on a hierarchical tree decomposition of the domain, e.g., methods based on nested dissection for PDEs or recursive skeletonization for integral equations. We show that, given a factorization corresponding to a given problem, we can update the factorization to solve problems related by local changes such as localized modification of the PDE coefficients or perturbation of the problem geometry. In cases where the computational cost per tree node is the same across all nodes, updating is both asymptotically and practically less expensive than re-doing the complete factorization.
Abstract Author(s): Victor Minden, Anil Damle, Kenneth Ho, Lexing Ying