dlarrk.f

Go to the documentation of this file.

*> \brief \b DLARRK computes one eigenvalue of a symmetric tridiagonal matrix T to suitable accuracy.
*
*  =========== DOCUMENTATION ===========
*
* Online html documentation available at 
*            http://www.netlib.org/lapack/explore-html/ 
*
*> \htmlonly
*> Download DLARRK + dependencies 
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.tgz?format=tgz&filename=/lapack/lapack_routine/dlarrk.f"> 
*> [TGZ]</a> 
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.zip?format=zip&filename=/lapack/lapack_routine/dlarrk.f"> 
*> [ZIP]</a> 
*> <a href="http://www.netlib.org/cgi-bin/netlibfiles.txt?format=txt&filename=/lapack/lapack_routine/dlarrk.f"> 
*> [TXT]</a>
*> \endhtmlonly 
*
*  Definition:
*  ===========
*
*       SUBROUTINE DLARRK( N, IW, GL, GU,
*                           D, E2, PIVMIN, RELTOL, W, WERR, INFO)
* 
*       .. Scalar Arguments ..
*       INTEGER   INFO, IW, N
*       DOUBLE PRECISION    PIVMIN, RELTOL, GL, GU, W, WERR
*       ..
*       .. Array Arguments ..
*       DOUBLE PRECISION   D( * ), E2( * )
*       ..
*  
*
*> \par Purpose:
*  =============
*>
*> \verbatim
*>
*> DLARRK computes one eigenvalue of a symmetric tridiagonal
*> matrix T to suitable accuracy. This is an auxiliary code to be
*> called from DSTEMR.
*>
*> To avoid overflow, the matrix must be scaled so that its
*> largest element is no greater than overflow**(1/2) * underflow**(1/4) in absolute value, and for greatest
*> accuracy, it should not be much smaller than that.
*>
*> See W. Kahan "Accurate Eigenvalues of a Symmetric Tridiagonal
*> Matrix", Report CS41, Computer Science Dept., Stanford
*> University, July 21, 1966.
*> \endverbatim
*
*  Arguments:
*  ==========
*
*> \param[in] N
*> \verbatim
*>          N is INTEGER
*>          The order of the tridiagonal matrix T.  N >= 0.
*> \endverbatim
*>
*> \param[in] IW
*> \verbatim
*>          IW is INTEGER
*>          The index of the eigenvalues to be returned.
*> \endverbatim
*>
*> \param[in] GL
*> \verbatim
*>          GL is DOUBLE PRECISION
*> \endverbatim
*>
*> \param[in] GU
*> \verbatim
*>          GU is DOUBLE PRECISION
*>          An upper and a lower bound on the eigenvalue.
*> \endverbatim
*>
*> \param[in] D
*> \verbatim
*>          D is DOUBLE PRECISION array, dimension (N)
*>          The n diagonal elements of the tridiagonal matrix T.
*> \endverbatim
*>
*> \param[in] E2
*> \verbatim
*>          E2 is DOUBLE PRECISION array, dimension (N-1)
*>          The (n-1) squared off-diagonal elements of the tridiagonal matrix T.
*> \endverbatim
*>
*> \param[in] PIVMIN
*> \verbatim
*>          PIVMIN is DOUBLE PRECISION
*>          The minimum pivot allowed in the Sturm sequence for T.
*> \endverbatim
*>
*> \param[in] RELTOL
*> \verbatim
*>          RELTOL is DOUBLE PRECISION
*>          The minimum relative width of an interval.  When an interval
*>          is narrower than RELTOL times the larger (in
*>          magnitude) endpoint, then it is considered to be
*>          sufficiently small, i.e., converged.  Note: this should
*>          always be at least radix*machine epsilon.
*> \endverbatim
*>
*> \param[out] W
*> \verbatim
*>          W is DOUBLE PRECISION
*> \endverbatim
*>
*> \param[out] WERR
*> \verbatim
*>          WERR is DOUBLE PRECISION
*>          The error bound on the corresponding eigenvalue approximation
*>          in W.
*> \endverbatim
*>
*> \param[out] INFO
*> \verbatim
*>          INFO is INTEGER
*>          = 0:       Eigenvalue converged
*>          = -1:      Eigenvalue did NOT converge
*> \endverbatim
*
*> \par Internal Parameters:
*  =========================
*>
*> \verbatim
*>  FUDGE   DOUBLE PRECISION, default = 2
*>          A "fudge factor" to widen the Gershgorin intervals.
*> \endverbatim
*
*  Authors:
*  ========
*
*> \author Univ. of Tennessee 
*> \author Univ. of California Berkeley 
*> \author Univ. of Colorado Denver 
*> \author NAG Ltd. 
*
*> \date September 2012
*
*> \ingroup auxOTHERauxiliary
*
*  =====================================================================
      SUBROUTINE dlarrk( N, IW, GL, GU,
     $                    d, e2, pivmin, reltol, w, werr, info)
*
*  -- LAPACK auxiliary routine (version 3.4.2) --
*  -- LAPACK is a software package provided by Univ. of Tennessee,    --
*  -- Univ. of California Berkeley, Univ. of Colorado Denver and NAG Ltd..--
*     September 2012
*
*     .. Scalar Arguments ..
      INTEGER   INFO, IW, N
      DOUBLE PRECISION    PIVMIN, RELTOL, GL, GU, W, WERR
*     ..
*     .. Array Arguments ..
      DOUBLE PRECISION   D( * ), E2( * )
*     ..
*
*  =====================================================================
*
*     .. Parameters ..
      DOUBLE PRECISION   FUDGE, HALF, TWO, ZERO
      parameter                ( half = 0.5d0, two = 2.0d0,
     $                     fudge = two, zero = 0.0d0 )
*     ..
*     .. Local Scalars ..
      INTEGER   I, IT, ITMAX, NEGCNT
      DOUBLE PRECISION   ATOLI, EPS, LEFT, MID, RIGHT, RTOLI, TMP1,
     $                   tmp2, tnorm
*     ..
*     .. External Functions ..
      DOUBLE PRECISION   DLAMCH
      EXTERNAL   dlamch
*     ..
*     .. Intrinsic Functions ..
      INTRINSIC          abs, int, log, max
*     ..
*     .. Executable Statements ..
*
*     Get machine constants
      eps = dlamch( 'P' )

      tnorm = max( abs( gl ), abs( gu ) )
      rtoli = reltol
      atoli = fudge*two*pivmin

      itmax = int( ( log( tnorm+pivmin )-log( pivmin ) ) /
     $           log( two ) ) + 2

      info = -1

      left = gl - fudge*tnorm*eps*n - fudge*two*pivmin
      right = gu + fudge*tnorm*eps*n + fudge*two*pivmin
      it = 0

 10   CONTINUE
*
*     Check if interval converged or maximum number of iterations reached
*
      tmp1 = abs( right - left )
      tmp2 = max( abs(right), abs(left) )
      IF( tmp1.LT.max( atoli, pivmin, rtoli*tmp2 ) ) THEN
         info = 0
         GOTO 30
      ENDIF
      IF(it.GT.itmax)
     $   GOTO 30

*
*     Count number of negative pivots for mid-point
*
      it = it + 1
      mid = half * (left + right)
      negcnt = 0
      tmp1 = d( 1 ) - mid
      IF( abs( tmp1 ).LT.pivmin )
     $   tmp1 = -pivmin
      IF( tmp1.LE.zero )
     $   negcnt = negcnt + 1
*
      DO 20 i = 2, n
         tmp1 = d( i ) - e2( i-1 ) / tmp1 - mid
         IF( abs( tmp1 ).LT.pivmin )
     $      tmp1 = -pivmin
         IF( tmp1.LE.zero )
     $      negcnt = negcnt + 1
 20   CONTINUE

      IF(negcnt.GE.iw) THEN
         right = mid
      ELSE
         left = mid
      ENDIF
      GOTO 10

 30   CONTINUE
*
*     Converged or maximum number of iterations reached
*
      w = half * (left + right)
      werr = half * abs( right - left )

      RETURN
*
*     End of DLARRK
*
      END