Fast Solution of Linear Systems with Many Right-Hand Sides Based on Skeletonization

For applications with many right-hand sides (RHSs), to avoid the solution of m different RHSs repeatedly, previous work has employed the interpolative decomposition (ID) to figure out skeleton RHSs by exploiting the rank deficient property of the n × m RHS matrix B for a system with n unknowns. However, the peak memory requirement for the skeletonization may degrade the performance of the previously developed algorithms when n becomes very large. To alleviate the associated difficulty, a strategy is proposed to construct a submatrix of B to figure out skeleton RHSs. Numerical experiments on different applications show the accuracy and efficiency of the proposed algorithms.