A matrix X that satisfies the Sylvester equation AX−XB = F, where F is a matrix of rank r, is said to have displacement structure, with an (A,B)-displacement rank of r. In many instances, it is known that if r is very small, then the singular values of X must decay rapidly. This has led to key theoretical results on numerical rank and conditioning for many classes of matrices, and it also justifies the use of low rank approximation methods for solving Sylvester equations in areas such as reduced order modeling, control theory, imaging, and the numerical solving of elliptic partial differential equations (PDEs).

What can we say about the singular values of X when the rank of F is not small, but instead, the singular values of F decay rapidly? To answer this question, we develop a new method for solving Sylvester’s equation with high-rank right hand sides. Our method results in both theoretical and practical gains, including improved bounds on singular values for several classes of matrices, and highly efficient, spectrally accurate low rank solvers for certain elliptic PDEs with smooth right-hand sides.