Research Seminar in Mathematics - Generating extreme-scale matrices with specified singular values or condition number

Speaker

Massimiliano Fasi, Örebro University

Abstract

The randsvd matrix is a widely used test matrix constructed as the product A = USV, where U and V are random orthogonal or unitary matrices from the Haar distribution and S is a diagonal matrix of singular values. Such matrices are random but have a specified singular value distribution. Forming an m-by-n randsvd matrix requires a number of floating-point operations cubic in both m and n, 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 synchronisation. We specialise these algorithms to generating matrices with specified 2-norm condition number. Numerical experiments show that the algorithms have excellent efficiency and scalability.