BBTools

bbsvds

Compute a set of leading singular values or triplets.

NOTE: triplets are not guaranteed to convergence in any particular order. If you need a predetermined number of the dominating triplets of the operator, please compute a few extra triplets and discard any unwanted triplets.

Syntax

Description

bbsvds is designed to replace in the case where the leading singular triplets are desired. It provides a simpler interface than bbsvdf, but is not as flexible or efficient.

This function is capable of extracting singular values that exceeds the memory required to store the individual triplets. Unlike most other software, this does not come at a loss of accuracy of the small singular values.

Note: unlike , bbsvds specifically exploits the case where only singular values are required. If L is large, it may be significantly more expensive to compute singular triplets than singular values alone.

Input Arguments

opt is a structure with options that control the computation of the SVD. The most useful options are described in bbsvdopt (the full list is given in the reference documentation).

The parameter trip can be used to suppress the output of the singular vectors. This is only useful if you need flag or h. In this case the matrices U and V will be empty.

In addition bbsvds takes a few additional options.

If sort=false, the triplets appears in the order they converged. This may be useful if you suspect that some triplets in a cluster was missed. The default, sort=true, is to sort the triplets in order of decreasing singular values before returning the result.

Specifies a tolerance level relative to a bound on the largest singular value of bb. This is different, but comparable, to svds. This option only works if bb is a Matlab matrix, and its use is not recommended. Please use atol, which overrides tol if present, instead.

Setting tol is equivalent to setting atol=tol*sqrt(norm(bb,1)*norm(bb,inf)).

Note: the default behaviour of bbsvds is to compute the result as accurately as possible. It is rarely necessary to specify the tolerance explicitly.

Result

With a single output, sig is a column-vector containing the leading singular values of bb.

With multiple outputs, the result in U, S, and V follows the same convention as .

flag is zero if all the requested triplets was computed, and non-zero otherwise.

h is a structure that contains internal information resulting from the computation. It may be useful for debugging, and the contents is subject to change.

Tracking Operation Counts

If bb is a counting blackbox (created with bbcount), then the number of computed matrix-vector products is recorded after each triplet converges. When the computation has been completed, the counts can be extracted using bbcountstat:

stat=bbcountstat(bb,'bbsvds_count')

stat is array of counter structs such that stat(k) is the status returned by bbcountstat after k triplets converged.

bbsvds does not reset the operation count of the operator before it starts. If you want to count only the operations used by bbsvds, you must run bbcountreset before bbsvds:

stat=bbcountreset(bb)

Examples

The matrix west0479 is a 479-by-479 sparse matrix bundled with MATLAB. You may compare the result of the following computations.

load west0479; t=cputime; s1 = svd(full(west0479)); t1=cputime-t, t=cputime; s2 = bbsvds(west0479,50); t2=cputime-t, t=cputime; s3 = svds(west0479,50); t3=cputime-t, t=cputime; s4 = bbsvds(west0479,479); t4=cputime-t

Algorithm

svds uses bbsvdf to compute the SVD. It allocates storage for the singular triplets (if requested), and set up a call-back function that copy the SVD into these matrices as they are computed. After completing the computation, it optionally sort the result in order of decreasing singular values.

If bb is a counting blackbox (created with bbcount it also records the statistics as each triplet converges.

See Also

bbsvdf, bbsvdopt,

bbsvdoptbbtauest