next up previous contents index
Next: Error Bounds for the Up: Error Bounds for the Previous: Error Bounds for the

Further Details: Error Bounds for the Singular Value Decomposition


The usual error analysis of the SVD algorithm  PxGESVD in ScaLAPACK (see subsection 3.2.3)is as follows [71]:

The SVD algorithm is backward stable.     This means that the computed SVD, tex2html_wrap_inline18949, is nearly the exact SVD of A+E where tex2html_wrap_inline18953, and p(m,n) is a modestly growing function of m and n. This means tex2html_wrap_inline18961 is the true SVD, so that tex2html_wrap_inline18963 and tex2html_wrap_inline18965 are both orthogonal, where tex2html_wrap_inline18967, and tex2html_wrap_inline18969. Each computed singular value tex2html_wrap_inline18971 differs from true tex2html_wrap_inline12826 by at most
(we take p(m,n)=1 in the above code fragment). Thus, large singular values (those near tex2html_wrap_inline18977) are computed to high relative accuracy   and small ones may not be.    

The angular difference between the computed left singular vector tex2html_wrap_inline18979 and a true tex2html_wrap_inline12840 satisfies the approximate bound
where tex2html_wrap_inline18985 is the absolute gap   between tex2html_wrap_inline12826 and the nearest other singular value (we take p(m,n)=1 in the above code fragment). Thus, if tex2html_wrap_inline12826 is close to other singular values, its corresponding singular vector tex2html_wrap_inline12840 may be inaccurate. When n < m, then tex2html_wrap_inline18997 must be redefined as tex2html_wrap_inline18999. The gaps may be easily computed from the array of computed singular values using function    SDISNA. The gaps computed by SDISNA are ensured not to be so small as to cause overflow when used as divisors.     The same bound applies to the computed right singular vector tex2html_wrap_inline19001 and a true vector tex2html_wrap_inline12842.

Let tex2html_wrap_inline17614 be the space spanned by a collection of computed left singular vectors tex2html_wrap_inline19007, where tex2html_wrap_inline18724 is a subset of the integers from 1 to n. Let tex2html_wrap_inline17602 be the corresponding true space. Then
is the absolute gap between the singular values in tex2html_wrap_inline18724 and the nearest other singular value. Thus, a cluster  of close singular values which is far away from any other singular value may have a well determined space tex2html_wrap_inline17614 even if its individual singular vectors are ill-conditioned. The same bound applies to a set of right singular vectors tex2html_wrap_inline19021gif.

There is a small possibility that PxGESVD will fail to achieve the above error bounds on a heterogeneous network of processors   for reasons discussed in section 6.2. On a homogeneous network, PxGESVD is as robust as the corresponding LAPACK routine xGESVD. A future release will attempt to detect heterogeneity and warn the user to use an alternative algorithm.

In the special case of bidiagonal matrices, the singular values and singular vectors may be computed much more accurately. A bidiagonal matrix B has nonzero entries only on the main diagonal and the diagonal immediately above it (or immediately below it). PxGESVD computes the SVD of a general      matrix by first reducing it to bidiagonal form B, and then calling xBDSQR (subsection 3.3.6) to compute the SVD of B. Reduction of a dense matrix to bidiagonal form B can introduce additional errors, so the following bounds for the bidiagonal case do not apply to the dense case. For the error analysis of xBDSQR, see the LAPACK manual.

next up previous contents index
Next: Error Bounds for the Up: Error Bounds for the Previous: Error Bounds for the

Susan Blackford
Tue May 13 09:21:01 EDT 1997