INTEGER FUNCTION : NSINGV 1 PURPOSE: The function NSINGV computes the number of singular values of the bidiagonal matrix: !Q(1) E(2) . ... 0 ! ! 0 Q(2) E(3) . ! J = ! . ! (1) ! E(K)! ! 0 ... 0 Q(K)! which are <= THETA + TOL1, for given bound THETA and tolerance TOL1. 2 SPECIFICATION: INTEGER FUNCTION NSINGV(Q, E, K, THETA, TOL1, TOL2) INTEGER K DOUBLE PRECISION Q(K), E(K), THETA, TOL1, TOL2 3 ARGUMENT LIST: 3.1 ARGUMENTS IN Q - DOUBLE PRECISION array of DIMENSION (K). Contains the diagonal entries of the bidiagonal matrix J. E - DOUBLE PRECISION array of DIMENSION (K). E(2),..., E(K) contains the superdiagonal entries of the bidiagonal matrix J. K - INTEGER. Dimension of the bidiagonal matrix J. THETA - DOUBLE PRECISION. Given bound. 3.4 TOLERANCES TOL1 - DOUBLE PRECISION. This parameter specifies that all singular values S(i) of J satisfying !S(i) - THETA! <= TOL1 are considered to be equal to THETA. TOL2 - DOUBLE PRECISION. This parameter specifies that Q(i) and/or E(i), which are <= TOL2 in absolute value, are considered to be zero. 6 METHOD DESCRIPTION: The computation of the number of singular values S(i) of J which are <= THETA is based on applying Sylvester's Law of Inertia, or equivalently, Sturm sequences [1,p.52] to unreduced symmetric tridiagonal matrices associated with J. Let T be the following symmetric matrix associated with J: ! 0 J'! T = ! ! ! J 0 ! The eigenvalues of T are the singular values of J and their negatives [4]. Then by permuting the rows and columns of T into the order 1, K+1, 2, K+2,..., K, 2K it follows that T is orthogonally similar to the tridiagonal matrix T" with zeros on its diagonal and Q(1), E(2), Q(2), E(3), ..., E(K), Q(K) on its offdiagonals [3,4]. If all Q(i) and all E(i) are nonzero, Sylvester's Law of Inertia may be applied to T". If one or more Q(i) or E(i) are zero, then T" is block diagonal and each diagonal block (which is then unreduced) must be analyzed separately by applying Sylvester's Law of Inertia. 7 REFERENCES: [1] B.N. Parlett, The Symmetric Eigenvalue Problem. Prentice Hall, Englewood Cliffs, New Jersey (1980). [2] J. Demmel and W. Kahan, Computing Small Singular Values of Bidiagonal Matrices with Guaranteed High Relative Accuracy. Technical Report, Courant Inst., New York, Oct. 13 1987. [3] S. Van Huffel and J. Vandewalle, The Partial Total Least Squares Algorithm. J. Comput. and Applied Math., 21 (1988), to appear. [4] G.H. Golub and W. Kahan, Calculating the Singular Values and Pseudo-inverse of a Matrix. SIAM J. Numer. Anal., Ser.B, 2 (1965), 205 - 224. 8 NUMERICAL ASPECTS: S(i) could also be obtained with the use of the symmetric tridiagonal matrix T = J'J, whose eigenvalues are the squared singular values of J [4,p.213]. However, the method actually used is more accurate, see [2], and equally efficient. With respect to the accuracy the following holds, see [2]: - if the established value is denoted by S then at least S singular values of J are <= THETA/(1 - (3K-1.5)EPS) and no more than S singular values are <= THETA x (1 - (6K-2)EPS)/(1 - (3K-1.5)EPS), where EPS is the machine precision. *********************************************************************** 1988, February 15. 