A qd-type method for computing generalized singular values of BF matrix pairs with sign regularity to high relative accuracy

Source abstract

Structured matrices such as Vandermonde and Cauchy matrices frequently appear in various areas of modern computing, and they tend to be badly ill-conditioned, but a desirable property is that they admit accurate bidiagonal factorizations (BFs). In this paper, we propose a qd-type method to compute the generalized singular values of BF matrix pairs. A mechanism involving sign regularity of BF generators is provided to guarantee that there is no subtraction of like-signed numbers for the qd-type method. Consequently, all the generalized singular values are computed to high relative accuracy, independent of any conventional condition number. Error analysis and numerical experiments are presented to confirm the high relative accuracy.