On the singular values of matrices with high displacement rank
It provides theoretical bounds and practical algorithms for solving large-scale matrix equations, benefiting numerical linear algebra and scientific computing communities.
This paper introduces an ADI-based low-rank solver for Sylvester-type equations with rapidly decaying singular values, deriving new singular value bounds for high-displacement-rank matrices and achieving spectral accuracy with optimal complexity for Poisson solvers.
We introduce a new ADI-based low rank solver for $AX-XB=F$, where $F$ has rapidly decaying singular values. Our approach results in both theoretical and practical gains, including (1) the derivation of new bounds on singular values for classes of matrices with high displacement rank, (2) a practical algorithm for solving certain Lyapunov and Sylvester matrix equations with high rank right-hand sides, and (3) a collection of low rank Poisson solvers that achieve spectral accuracy and optimal computational complexity.