Generating Extreme-Scale Matrices With Specified Singular Values or Condition Number
Massimiliano Fasi, Nicholas John Higham · SIAM Journal on Scientific Computing · 2021
A widely used form of test matrix is the randsvd matrix constructed as the product $A = U \Sigma V^*$, where $U$ and $V$ are random orthogonal or unitary matrices from the Haar distribution and $\Sigma$ is a diagonal matrix of singular values. Such matrices are random but have a specified singular value distribution. The cost of forming an $m\times n$ randsvd matrix is $m^3 + n^3$ flops, which is prohibitively expensive at extreme scale; moreover, the randsvd construction requires a significant amount of communication, making it unsuitable for distributed memory environments. By dropping the requirement that $U$ and $V$ be Haar distributed and that both be random, we derive new algorithms for forming $A$ that have cost linear in the number of matrix elements and require a low amount of communication and synchronization. We specialize these algorithms to generating matrices with a specified 2-norm condition number. Numerical experiments show that the algorithms have excellent efficiency and scalability.