| Description | The matrix MA of dimensions [ht, len] is decomposed into a product
MA = MU * MW * MVT,
where MU has the dimensions [max(ht,len), len]. MW is a diagonal matrix with all elements positive or zero. Actually, only the diagonal of this matrix is stored in the vector W of size [len], MV, finally, is a square matrix [len, len]. Both MU and MV are orthogonal:
MUT * MU = MVT * MV = (1).
Due to these orthogonality relations, the solution of a linear system MA * X = B is straightforward, once MA has been singular-value decomposed:
X = MV * W-1 * MUT
(This equation must be evaluated from right to left.) As MU and MV are orthogonal, only W must explicitly be inverted. This, however, is again easy, as W is diagonal, and the inverse of a diagonal matrix consists of the inverse of the diagonal elements. This is the important point which makes SVD so useful, because it provides both a diagnose and a cure for singularities. If any element of W is very small compared to the largest element, this corresponds to a singularity (at least in the numerical sense, where dividing by extremely small numbers is almost as bad as dividing by zero). A singularity means that the underlying linear system is under-determined. This, in turn, means that one can arbitrarily choose one particular solution. Specifically, one may choose W-1ii = 0 for very small Wii, which is one of the rare cases where it makes sense to set the result of a division by (near-)zero to zero instead of infinity. This reduction of the dimension by "Singular Value editing" is the crucial point in all functions relying on SVD, like MF_SVsolve, MF_safeSolve), VF_linfit and others. The editing threshold is set by MF_SVDsetEdit.
This function may not be called while the FPU is set to reduced accuracy, or else it might fail to achieve convergence. See V_setFPAccuracy.
If you compare results of MF_SVdecompose with SVD-routines of other vendors, please note the following points:
- MF_SVdecompose itself does not perform a dimension reduction (replacement of small singular values by 0), but leaves this step to following functions or to manual inspection by the user.
- Singular values can be permutated, if the same permutation is also applied to the corresponding columns of both MU and MV. Sometimes, this property of SVD is exploited to bring the singular values into a certain (for example, into descending) order. As the price for this increased beauty is an increased work-load, MF_SVdecompose keeps the singular values in arbitrary order.
- The sign of a singular value may be exchanged if the corresponding column of MV is also multiplied by -1. MF_SVdecompose uses this property to make all non-vanishing singular values positive.
|