Fast algorithms for computing only the generalized singular values (but not the vectors)

Question

I am interested in computing only the generalized singular values, and was wondering if this was faster (and by how much?) than computing the full GSVD.

In particular, I was wondering what the fastest algorithms are for computing the generalized singular values (ideally the pairs $(\alpha_i, \beta_i)$ instead of just $\sigma_i = \alpha_i/\beta_i$), given two matrices $A$ and $B$, where $A$ is of size $m\times k$ and $B$ is of size $n\times k$? I was also wondering what the run-times of these algorithms are in terms of $n, m$, and $k$?

Also, are there any implementations of these algorithms out there? I know Matlab has a GSVD function, which can compute only the singular values, using the command:

sigma = gsvd(A,B)

However, I doubt from the way it is implemented that it is faster than doing the full GSVD using the command:

[U,V,X,C,S] = gsvd(A,B)

But, maybe I am wrong. Would there potentially be a way in Matlab (or in another language) to just compute $C$ and $S$, and not $U$, $V$, and $X$? If so, how much faster would that be than computing the full GSVD?

An answer to any/all of these questions would be appreciated, or even a relevant reference (it has been hard to find any since most of the algorithms I have seen compute the full GSVD, which is not what I am looking for).

Answer 1

Per http://www.nag.com/numeric/fl/manual/pdf/F08/f08msf.pdf , regarding the LAPACK routine in the NAG Library for complex singular values/singular vectors. (Not generalized, but I think the idea is basically the same for generalized. See http://www.nag.com/numeric/fl/manual/pdf/F08/f08vaf.pdf for real GSVD and http://www.nag.com/numeric/fl/manual/pdf/F08/f08vnf.pdf for complex GSVD, but they don't have discussion of computational effort/)

08MSF (CBDSQ/ZBDSQR) computes the singular value decomposition of a complex general matrix which has been reduced to bidiagonal form.

...

F08MSF (CBDSQR / ZBDSQR) uses two different algorithms. If any singular vectors are required (that is, if NCVT > 0 or NRU > 0 or NCC > 0), the bidiagonal QR algorithm is used, switching between zero- shift and implicitly shifted forms to preserve the accuracy of small singular values, and switching between QR and QL variants in order to handle graded matrices effectively (see Demmel and Kahan (1990)). If only singular values are required (that is, if NCVT = NRU = NCC = 0), they are computed by the differential qd algorithm (see Fernando and Parlett (1994)), which is faster and can achieve even greater accuracy.

...

The total number of real floating-point operations is roughly proportional to n^2 if only the singular values are computed. About 12 n^2 * nru additional operations are required to compute the left singular vectors and about 12 n^^2 * ncvt to compute the right singular vectors. The operations to compute the singular values must all be performed in scalar mode; the additional operations to compute the singular vectors can be vectorized and on some machines may be performed much faster. The real analogue of this routine is F08MEF(SBDSQR/DBDSQR).

See Demmel and Kahan 1990 "Accurate Singular Values of Bidiagonal Matrices" http://www.netlib.org/lapack/lawnspdf/lawn03.pdf for a discussion of why singular values plus vectors takes longer than singular values only. It is because singular vectors converge more slowly than singular values. Table 2 shows some timing results comparing with and without singular vectors.

Here are some quick timing results I ran using MATLAB R2014A WIN64 on an 8 core machine"

>> n=4000;A=randn(n);B=randn(n);tic,sigma = gsvd(A,B);toc,tic,[U,V,X,C,S] = gsvd(A,B);toc
Elapsed time is 31.649874 seconds.
Elapsed time is 33.202460 seconds.

A few other runs give similar results, and the no singular vector version was still faster by about the same amount when it was done second (checked in case the processor was getting overheated and had to decrease turbo level for second calculation). Multiple cores were used by MATLAB.

With n = 1000; the no singular vector version averaged about 8% longer than with singular vectors. I have no idea why.

I am not saying that randn of a square matrix for both A and B is representative of problems you care about, but you can try yourself on your own A and B.