git.maemo.org Git - opencv/blob - 3rdparty/lapack/dlagtf.c

   1 #include "clapack.h"
   2
   3 /* Subroutine */ int dlagtf_(integer *n, doublereal *a, doublereal *lambda,
   4         doublereal *b, doublereal *c__, doublereal *tol, doublereal *d__,
   5         integer *in, integer *info)
   6 {
   7     /* System generated locals */
   8     integer i__1;
   9     doublereal d__1, d__2;
  10
  11     /* Local variables */
  12     integer k;
  13     doublereal tl, eps, piv1, piv2, temp, mult, scale1, scale2;
  14     extern doublereal dlamch_(char *);
  15     extern /* Subroutine */ int xerbla_(char *, integer *);
  16
  17
  18 /*  -- LAPACK routine (version 3.1) -- */
  19 /*     Univ. of Tennessee, Univ. of California Berkeley and NAG Ltd.. */
  20 /*     November 2006 */
  21
  22 /*     .. Scalar Arguments .. */
  23 /*     .. */
  24 /*     .. Array Arguments .. */
  25 /*     .. */
  26
  27 /*  Purpose */
  28 /*  ======= */
  29
  30 /*  DLAGTF factorizes the matrix (T - lambda*I), where T is an n by n */
  31 /*  tridiagonal matrix and lambda is a scalar, as */
  32
  33 /*     T - lambda*I = PLU, */
  34
  35 /*  where P is a permutation matrix, L is a unit lower tridiagonal matrix */
  36 /*  with at most one non-zero sub-diagonal elements per column and U is */
  37 /*  an upper triangular matrix with at most two non-zero super-diagonal */
  38 /*  elements per column. */
  39
  40 /*  The factorization is obtained by Gaussian elimination with partial */
  41 /*  pivoting and implicit row scaling. */
  42
  43 /*  The parameter LAMBDA is included in the routine so that DLAGTF may */
  44 /*  be used, in conjunction with DLAGTS, to obtain eigenvectors of T by */
  45 /*  inverse iteration. */
  46
  47 /*  Arguments */
  48 /*  ========= */
  49
  50 /*  N       (input) INTEGER */
  51 /*          The order of the matrix T. */
  52
  53 /*  A       (input/output) DOUBLE PRECISION array, dimension (N) */
  54 /*          On entry, A must contain the diagonal elements of T. */
  55
  56 /*          On exit, A is overwritten by the n diagonal elements of the */
  57 /*          upper triangular matrix U of the factorization of T. */
  58
  59 /*  LAMBDA  (input) DOUBLE PRECISION */
  60 /*          On entry, the scalar lambda. */
  61
  62 /*  B       (input/output) DOUBLE PRECISION array, dimension (N-1) */
  63 /*          On entry, B must contain the (n-1) super-diagonal elements of */
  64 /*          T. */
  65
  66 /*          On exit, B is overwritten by the (n-1) super-diagonal */
  67 /*          elements of the matrix U of the factorization of T. */
  68
  69 /*  C       (input/output) DOUBLE PRECISION array, dimension (N-1) */
  70 /*          On entry, C must contain the (n-1) sub-diagonal elements of */
  71 /*          T. */
  72
  73 /*          On exit, C is overwritten by the (n-1) sub-diagonal elements */
  74 /*          of the matrix L of the factorization of T. */
  75
  76 /*  TOL     (input) DOUBLE PRECISION */
  77 /*          On entry, a relative tolerance used to indicate whether or */
  78 /*          not the matrix (T - lambda*I) is nearly singular. TOL should */
  79 /*          normally be chose as approximately the largest relative error */
  80 /*          in the elements of T. For example, if the elements of T are */
  81 /*          correct to about 4 significant figures, then TOL should be */
  82 /*          set to about 5*10**(-4). If TOL is supplied as less than eps, */
  83 /*          where eps is the relative machine precision, then the value */
  84 /*          eps is used in place of TOL. */
  85
  86 /*  D       (output) DOUBLE PRECISION array, dimension (N-2) */
  87 /*          On exit, D is overwritten by the (n-2) second super-diagonal */
  88 /*          elements of the matrix U of the factorization of T. */
  89
  90 /*  IN      (output) INTEGER array, dimension (N) */
  91 /*          On exit, IN contains details of the permutation matrix P. If */
  92 /*          an interchange occurred at the kth step of the elimination, */
  93 /*          then IN(k) = 1, otherwise IN(k) = 0. The element IN(n) */
  94 /*          returns the smallest positive integer j such that */
  95
  96 /*             abs( u(j,j) ).le. norm( (T - lambda*I)(j) )*TOL, */
  97
  98 /*          where norm( A(j) ) denotes the sum of the absolute values of */
  99 /*          the jth row of the matrix A. If no such j exists then IN(n) */
 100 /*          is returned as zero. If IN(n) is returned as positive, then a */
 101 /*          diagonal element of U is small, indicating that */
 102 /*          (T - lambda*I) is singular or nearly singular, */
 103
 104 /*  INFO    (output) INTEGER */
 105 /*          = 0   : successful exit */
 106 /*          .lt. 0: if INFO = -k, the kth argument had an illegal value */
 107
 108 /* ===================================================================== */
 109
 110 /*     .. Parameters .. */
 111 /*     .. */
 112 /*     .. Local Scalars .. */
 113 /*     .. */
 114 /*     .. Intrinsic Functions .. */
 115 /*     .. */
 116 /*     .. External Functions .. */
 117 /*     .. */
 118 /*     .. External Subroutines .. */
 119 /*     .. */
 120 /*     .. Executable Statements .. */
 121
 122     /* Parameter adjustments */
 123     --in;
 124     --d__;
 125     --c__;
 126     --b;
 127     --a;
 128
 129     /* Function Body */
 130     *info = 0;
 131     if (*n < 0) {
 132         *info = -1;
 133         i__1 = -(*info);
 134         xerbla_("DLAGTF", &i__1);
 135         return 0;
 136     }
 137
 138     if (*n == 0) {
 139         return 0;
 140     }
 141
 142     a[1] -= *lambda;
 143     in[*n] = 0;
 144     if (*n == 1) {
 145         if (a[1] == 0.) {
 146             in[1] = 1;
 147         }
 148         return 0;
 149     }
 150
 151     eps = dlamch_("Epsilon");
 152
 153     tl = max(*tol,eps);
 154     scale1 = abs(a[1]) + abs(b[1]);
 155     i__1 = *n - 1;
 156     for (k = 1; k <= i__1; ++k) {
 157         a[k + 1] -= *lambda;
 158         scale2 = (d__1 = c__[k], abs(d__1)) + (d__2 = a[k + 1], abs(d__2));
 159         if (k < *n - 1) {
 160             scale2 += (d__1 = b[k + 1], abs(d__1));
 161         }
 162         if (a[k] == 0.) {
 163             piv1 = 0.;
 164         } else {
 165             piv1 = (d__1 = a[k], abs(d__1)) / scale1;
 166         }
 167         if (c__[k] == 0.) {
 168             in[k] = 0;
 169             piv2 = 0.;
 170             scale1 = scale2;
 171             if (k < *n - 1) {
 172                 d__[k] = 0.;
 173             }
 174         } else {
 175             piv2 = (d__1 = c__[k], abs(d__1)) / scale2;
 176             if (piv2 <= piv1) {
 177                 in[k] = 0;
 178                 scale1 = scale2;
 179                 c__[k] /= a[k];
 180                 a[k + 1] -= c__[k] * b[k];
 181                 if (k < *n - 1) {
 182                     d__[k] = 0.;
 183                 }
 184             } else {
 185                 in[k] = 1;
 186                 mult = a[k] / c__[k];
 187                 a[k] = c__[k];
 188                 temp = a[k + 1];
 189                 a[k + 1] = b[k] - mult * temp;
 190                 if (k < *n - 1) {
 191                     d__[k] = b[k + 1];
 192                     b[k + 1] = -mult * d__[k];
 193                 }
 194                 b[k] = temp;
 195                 c__[k] = mult;
 196             }
 197         }
 198         if (max(piv1,piv2) <= tl && in[*n] == 0) {
 199             in[*n] = k;
 200         }
 201 /* L10: */
 202     }
 203     if ((d__1 = a[*n], abs(d__1)) <= scale1 * tl && in[*n] == 0) {
 204         in[*n] = *n;
 205     }
 206
 207     return 0;
 208
 209 /*     End of DLAGTF */
 210
 211 } /* dlagtf_ */