Previous: bandv Up: ../eispad.html Next: bqr
SUBROUTINE BISECT(N,EPS1,D,E,E2,LB,UB,MM,M,W,IND,IERR,RV4,RV5)
C
INTEGER I,J,K,L,M,N,P,Q,R,S,II,MM,M1,M2,TAG,IERR,ISTURM
DOUBLE PRECISION D(N),E(N),E2(N),W(MM),RV4(N),RV5(N)
DOUBLE PRECISION U,V,LB,T1,T2,UB,XU,X0,X1,EPS1,TST1,TST2,EPSLON
INTEGER IND(MM)
C
C THIS SUBROUTINE IS A TRANSLATION OF THE BISECTION TECHNIQUE
C IN THE ALGOL PROCEDURE TRISTURM BY PETERS AND WILKINSON.
C HANDBOOK FOR AUTO. COMP., VOL.II-LINEAR ALGEBRA, 418-439(1971).
C
C THIS SUBROUTINE FINDS THOSE EIGENVALUES OF A TRIDIAGONAL
C SYMMETRIC MATRIX WHICH LIE IN A SPECIFIED INTERVAL,
C USING BISECTION.
C
C ON INPUT
C
C N IS THE ORDER OF THE MATRIX.
C
C EPS1 IS AN ABSOLUTE ERROR TOLERANCE FOR THE COMPUTED
C EIGENVALUES. IF THE INPUT EPS1 IS NON-POSITIVE,
C IT IS RESET FOR EACH SUBMATRIX TO A DEFAULT VALUE,
C NAMELY, MINUS THE PRODUCT OF THE RELATIVE MACHINE
C PRECISION AND THE 1-NORM OF THE SUBMATRIX.
C
C D CONTAINS THE DIAGONAL ELEMENTS OF THE INPUT MATRIX.
C
C E CONTAINS THE SUBDIAGONAL ELEMENTS OF THE INPUT MATRIX
C IN ITS LAST N-1 POSITIONS. E(1) IS ARBITRARY.
C
C E2 CONTAINS THE SQUARES OF THE CORRESPONDING ELEMENTS OF E.
C E2(1) IS ARBITRARY.
C
C LB AND UB DEFINE THE INTERVAL TO BE SEARCHED FOR EIGENVALUES.
C IF LB IS NOT LESS THAN UB, NO EIGENVALUES WILL BE FOUND.
C
C MM SHOULD BE SET TO AN UPPER BOUND FOR THE NUMBER OF
C EIGENVALUES IN THE INTERVAL. WARNING. IF MORE THAN
C MM EIGENVALUES ARE DETERMINED TO LIE IN THE INTERVAL,
C AN ERROR RETURN IS MADE WITH NO EIGENVALUES FOUND.
C
C ON OUTPUT
C
C EPS1 IS UNALTERED UNLESS IT HAS BEEN RESET TO ITS
C (LAST) DEFAULT VALUE.
C
C D AND E ARE UNALTERED.
C
C ELEMENTS OF E2, CORRESPONDING TO ELEMENTS OF E REGARDED
C AS NEGLIGIBLE, HAVE BEEN REPLACED BY ZERO CAUSING THE
C MATRIX TO SPLIT INTO A DIRECT SUM OF SUBMATRICES.
C E2(1) IS ALSO SET TO ZERO.
C
C M IS THE NUMBER OF EIGENVALUES DETERMINED TO LIE IN (LB,UB).
C
C W CONTAINS THE M EIGENVALUES IN ASCENDING ORDER.
C
C IND CONTAINS IN ITS FIRST M POSITIONS THE SUBMATRIX INDICES
C ASSOCIATED WITH THE CORRESPONDING EIGENVALUES IN W --
C 1 FOR EIGENVALUES BELONGING TO THE FIRST SUBMATRIX FROM
C THE TOP, 2 FOR THOSE BELONGING TO THE SECOND SUBMATRIX, ETC..
C
C IERR IS SET TO
C ZERO FOR NORMAL RETURN,
C 3*N+1 IF M EXCEEDS MM.
C
C RV4 AND RV5 ARE TEMPORARY STORAGE ARRAYS.
C
C THE ALGOL PROCEDURE STURMCNT CONTAINED IN TRISTURM
C APPEARS IN BISECT IN-LINE.
C
C NOTE THAT SUBROUTINE TQL1 OR IMTQL1 IS GENERALLY FASTER THAN
C BISECT, IF MORE THAN N/4 EIGENVALUES ARE TO BE FOUND.
C
C QUESTIONS AND COMMENTS SHOULD BE DIRECTED TO BURTON S. GARBOW,
C MATHEMATICS AND COMPUTER SCIENCE DIV, ARGONNE NATIONAL LABORATORY
C
C THIS VERSION DATED AUGUST 1983.
C
C ------------------------------------------------------------------
C