Speaker
Description
This talk gives a superfast divide-and-conquer algorithm for computing the full singular value decomposition (SVD) of hierarchical rank-structured matrices with small off-diagonal ranks. The method achieves nearly linear complexity while delivering all singular values and singular vectors in structured forms. The structured representation of singular vectors enables near-linear operations with reduced storage. In contrast, classical algorithms for the full SVD require cubic computational cost and quadratic storage. The proposed method directly handles nonsymmetric or rectangular matrices by reducing them to a hierarchical block broken arrow form via stable QL factorizations. This form is then repeatedly decomposed through rank-1 SVD updates in the conquering stage. Several stability-preserving mechanisms are incorporated, including deflation, splitting and shifting, and orthogonality-preserving perturbations, to ensure the robustness of this stage. Efficiency is enhanced via fast kernel methods, such as the fast multipole method (FMM). A rigorous numerical error analysis establishes the backward stability of the overall process. Numerical experiments demonstrate significant advantages in both accuracy and efficiency, yielding the first fast and stable SVD for general hierarchical rank-structured matrices.