Black-Box Toolbox: SVD Parameters

Overview

Essential parameters are underlined. These parameters must be correct in order to get a valid result. Although a computation may be useful, even with an incorrect setting, it is necessary to be intimately familiar with the underlying algorithms in order to interpret the result correctly.

It is also possible to use an overly conservative setting, which may not harm the result. This usually comes at the expense of using much more resources (time and memory) than necessary.

Guidance Parameters

These parameters do not directly affect the computation. Instead they control how much information to display during the computation, guide bbsvdopt in choosing the actual parameters, and control the output.

This set of parameters is by far the most useful for a normal user.

Parameter: trip [true | false]

Parameter:	`trip` [`true` \| `false`]
	Determine whether singular triplets should be computed. `bbsvds` returns empty singular matrices if `trip=false`. Default: determined from the output in `bbsvds`, `true` for `bbsvdf` and `bbsvdopt`.

Determine whether singular triplets should be computed. bbsvds returns empty singular matrices if trip=false.

Default: determined from the output in bbsvds, true for bbsvdf and bbsvdopt.

Parameter: atol [scalar]

Parameter:	`atol` [scalar]
	Absolute tolerance of convergence. In most cases one would only set `atol` manually if the default value is known to be very conservative. See `below` for a discussion of this parameter. Default: the value of `tau` specified for the black-box operator.

Absolute tolerance of convergence. In most cases one would only set atol manually if the default value is known to be very conservative. See below for a discussion of this parameter.

Default: the value of tau specified for the black-box operator.

Parameter: disp [-1 | 0 | 1 | 2]

Parameter:	`disp` [`-1` \| `0` \| `1` \| `2`]
	Verbosity level. The idea is that `disp=-1` should quench any output, while `disp=0` only shows error conditions. The normal level show progress information and `disp=2` is good for debugging. Default: `disp=1`.

Verbosity level. The idea is that disp=-1 should quench any output, while disp=0 only shows error conditions. The normal level show progress information and disp=2 is good for debugging.

Default: disp=1.

Parameter: mem [scalar]

Parameter:	`mem` [scalar]
	Available memory, in megabytes. You should not rely too much on this; it is the last priority that will be honored. Use `bbsvdmem` to estim ate the actual usage. The default behaviour is to use as much memory as necessary to get convergence in most cases. Default: unlimited.

Available memory, in megabytes. You should not rely too much on this; it is the last priority that will be honored. Use bbsvdmem to estim ate the actual usage.

The default behaviour is to use as much memory as necessary to get convergence in most cases.

Default: unlimited.

Parameters specific to bbsvds

The following paramaters are specific to bbsvds, and does not affect anything else.

Parameter: sort [true | false]

Parameter:	`sort` [`true` \| `false`]
	Determine if triplets will sorted in order of decreasing singular values, before being returned. Default: `true`.

Determine if triplets will sorted in order of decreasing singular values, before being returned.

Default: true.

Parameter: tol [scalar]

Parameter:	`tol` [scalar]
	This parameter is present for compatibility with and can only be used for Matlab matrices. It will set `atol` in a way that is similar to `svds`. We strongly recommend not to use this parameter, except for situations where compatibility with `svds` is vital.

This parameter is present for compatibility with and can only be used for Matlab matrices. It will set atol in a way that is similar to svds.

We strongly recommend not to use this parameter, except for situations where compatibility with svds is vital.

Restarting Strategy

The best choice of restarting strategy is problem dependent. A restart occurs when the toolbox exhausts the memory allocated for the computation or some triplets converged. The restarting strategy decides what triplets to throw away before starting a new iteration.

There are two reasons that keeping all triplets is a bad idea. First, this will often exhaust the memory rather quickly. Secondly, a restart uses a dense SVD-computation, which uses time that is cubic in the number of triplets at the end of the iteration. Therefore we may be able to keep 100 triplets, but if we keep 200 a restart will take 8 times longer.

The downside is that throwing a triplet away means that we probably need to find it again some time later. Therefore, if the matrix-vector products can be computed fast (say, a very sparse matrix) then we may want to use a low value. On the other hand, if the matrix-vector product is slow (say, built from a series of Fourier transforms and complex processing) we may want to set this somewhat higher.

Parameter:	`K` [integer]
	This is the number of triplets kept in memory for the purpose of converging new triplets. When this many triplets has been the reached, a restart is forced. Generally, one would almost always want to set this to the highest possible value allowed by the available memory.

Parameter:	`rkeep` [integer]
	When a restart occurs, the toolbox will keep at least this many triplets (if there are that many). However, it may keep somewhat more than this number, because it also keeps triplets that are important for the convergence of the chosen triplets. The current version of the toolbox will try to keep `K` at least twice as big as `rkeep`.

Parameter:	`rmaxi` [integer]
	Maximum number of restarts without convergence. It is possible that a high value (e.g. `rmaxi=50`) may extract more triplets than the default setting. Generally speaking, however, the effort spent when several restarts are required for each triplet is rarely justified.

Deflation Strategy

The deflation strategy controls how converged triplets are handled. After convergence, a triplet is explicitly removed from space used to search for new triplets. This is necessary to guarantee that triplets correspond to unique triplets of the operator, allow non-simple triplets to converge, and to keep triplets orthogonal to each other.

Parameter: dgreedy [true | false]

Parameter:	`dgreedy` [`true` \| `false`]
	In a greedy strategy, a triplet will be deflated as soon as it converges to the specified tolerance. A problem with the greedy strategy is that triplets does not converge in any particular order. It is usually the case that some triplets, corresponding to small singular values, will converge at about the same time as a few triplets in a cluster of singular values. To prevent this, a non-greedy strategy is normally preferable for SVD computations. This will only deflate triplets corresponding to a "run" of triplets. The downside with this approach is that some convrged triplets may be kicked out of memory. This may add a significant penalty, since it is likely that these triplets will be found a bit later. Applications, such as equation solving, that relies on a particular starting-vector should always set `dgreedy=true`. Default: `false`

In a greedy strategy, a triplet will be deflated as soon as it converges to the specified tolerance. A problem with the greedy strategy is that triplets does not converge in any particular order. It is usually the case that some triplets, corresponding to small singular values, will converge at about the same time as a few triplets in a cluster of singular values. To prevent this, a non-greedy strategy is normally preferable for SVD computations. This will only deflate triplets corresponding to a "run" of triplets.

The downside with this approach is that some convrged triplets may be kicked out of memory. This may add a significant penalty, since it is likely that these triplets will be found a bit later.

Applications, such as equation solving, that relies on a particular starting-vector should always set dgreedy=true.

Default: false

Parameter: dtail [integer]

Parameter:	`dtail` [integer]
	Triplets with nearly identical singular values must explicitly be kept orthogonal to each other. The "tail" is used to ensure that triplets corresponds to unique triplets of the operator and to keep triplets with nearly identical singular values nearly orthogonal. It is also used to create a gap so converged triplets, that was found previously, can be ignored. If `dtail` is too small you risk skipping clustered singular triplets.

Triplets with nearly identical singular values must explicitly be kept orthogonal to each other. The "tail" is used to ensure that triplets corresponds to unique triplets of the operator and to keep triplets with nearly identical singular values nearly orthogonal.

It is also used to create a gap so converged triplets, that was found previously, can be ignored. If dtail is too small you risk skipping clustered singular triplets.

Parameter: dlead [integer]

Parameter:	`dlead` [integer]
	This is the number of the leading triplets that is kept in memory. This is needed to keep rounding errors in check. If the computer worked in exact arithmetic, you could safely set `dlead=0`. Generally, this should be set large enough to absorb a set of dominating singular triplets of an operator. The number of triplets the software can extract from an operaton may, in the worst case, be limited to about `dlead+dtail`.

This is the number of the leading triplets that is kept in memory. This is needed to keep rounding errors in check. If the computer worked in exact arithmetic, you could safely set dlead=0.

Generally, this should be set large enough to absorb a set of dominating singular triplets of an operator. The number of triplets the software can extract from an operaton may, in the worst case, be limited to about dlead+dtail.

Parameter: dsides [1 | 2]

Parameter:	`dsides` [`1` \| `2`]
	Some applications does not require that individual triplets are accurate. For instance one may be interested in just the singular values or a low-rank approximation of the operator. In this case it is possible to save an enormous amount of effort and memory by using a one-sided deflation strategy. This means that only the vectors corresponding to the smallest dimension of the operator are saved in the leading triplets. This implies that the amount of memory needed scales with the smallest dimension of the operator. Generally one should set `dsides=1` if the application can tolerate it.

Some applications does not require that individual triplets are accurate. For instance one may be interested in just the singular values or a low-rank approximation of the operator.

In this case it is possible to save an enormous amount of effort and memory by using a one-sided deflation strategy. This means that only the vectors corresponding to the smallest dimension of the operator are saved in the leading triplets. This implies that the amount of memory needed scales with the smallest dimension of the operator.

Generally one should set dsides=1 if the application can tolerate it.

Parameter: dorth [scalar]

Parameter:	`dorth` [scalar]
	This option only affects two-sided deflation, i.e. `dsides=2`. The software attempts to keep triplets orthogonal simply by keeping them accurate. However, this is only possible for triplets with large singular values. Therefore triplets must be kept orthogonal when the singular values drops low enough. The option `dorth` determines how orthogonal these triplets needs to be. Note that the number of triplets that can converge may be limited if this value is too small. In most cases the level of orthogonality is sufficient for practical purposes. Default: `dorth=1e-4`

This option only affects two-sided deflation, i.e. dsides=2. The software attempts to keep triplets orthogonal simply by keeping them accurate. However, this is only possible for triplets with large singular values. Therefore triplets must be kept orthogonal when the singular values drops low enough. The option dorth determines how orthogonal these triplets needs to be.

Note that the number of triplets that can converge may be limited if this value is too small. In most cases the level of orthogonality is sufficient for practical purposes.

Default: dorth=1e-4

Tolerance

atol specifies the absolute accuracy of the singular values before a triplet is deemed to converge. A computed singular value, σ, satisfies |σ-σ₀|≤atol, where σ₀ is an exact singular value.

The calculation does not take rounding errors into account. It is often possible to drive the tolerance below the accuracy of the calculation, although this tolerance is fictive. However, if an operator is more accurate than a single value of tau (usually the case), then it is often possible to get surprisingly accurate singular values.

If singular vectors of the operator bb are computed, and dsides=2, then the following holds (with similar comments on rounding errors):

norm(bb*v-sig*u) ≤ atol

norm(bb'*u-sig*v) ≤ atol

abs(v1'*v2) ≤ dorth

Two-sided deflation

BBTools keeps triplets orthogonal implicitly, i.e. by keeping them accurate. This scheme accounts for the fact that more triplets can be computed than will fit in memory. It starts to fall apart for small singular values, because of rounding errors. Therefore, pairs of singular triplets are explicitly kept orthogonal to each other when the singular values start approaching the level of the rounding errors. This place where this starts to take effect is given by dorth.

One-sided deflation

For one-sided deflation, i.e. dsides=1, the norm of the residual in the "long space" is approximately atol*(norm(bb)/σ). The orthogonality of the triplets are impaired similarly, but the singular values are accurate and so are low-rank approximations of the operator.

To be more precise, assume that length(v)<length(u):

norm(bb*v-sig*u) ≤ atol

abs(v1'*v2) ≤ atol

norm(bb'*u-sig*v) ≤ atol*(norm(bb)/sig)

abs(u1'*u2) ≤ atol*(norm(bb)/sig)

`norm(bbv-sigu)`	≤	`atol`
`norm(bb'u-sigv)`	≤	`atol`
`abs(v1'*v2)`	≤	`dorth`