#! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh 'INPUT' <<'END_OF_FILE' X 2 X 1.0D-3 X 50 X -1.2 1.0 X 2 X 1.0 X 0 X 256 END_OF_FILE if test 49 -ne `wc -c <'INPUT'`; then echo shar: \"'INPUT'\" unpacked with wrong size! fi # end of 'INPUT' fi if test -f 'create.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'create.f'\" else echo shar: Extracting \"'create.f'\" \(7366 characters\) sed "s/^X//" >'create.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)create.F 1.1 3/16/92 XC X PROGRAM CREATE XC XC SAMPLE PROGRAM TO CREATE A SEARCH STRATEGY FOR THE PARALLEL DIRECT XC SEARCH METHODS. XC XC WRITTEN BY VIRGINIA TORCZON. XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER DIM, MAX, LIMIT X PARAMETER (DIM = 10, MAX = 5000, LIMIT=(DIM+2)*(DIM+1+MAX)) XC XC VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER ERROR, FACTOR, IN, N, OUT, UNIQUE X INTEGER INDEX(LIMIT), LIST(LIMIT) X INTEGER SCHEME(LIMIT) XC XC SINCE THE SIZE OF THE WORKSPACE PLAYS A CRITICAL ROLE IN THE TOTAL XC NUMBER OF POINTS GENERATED FOR THE SEARCH SCHEME, A BRIEF XC EXPLANATION OF HOW THIS WORKSPACE IS USED IS INCLUDED HERE FOR XC THOSE WHO WISH TO OPTIMIZE THE USE OF MEMORY. XC XC UPON ENTRY INTO THE SUBROUTINE `SEARCH' THE VECTOR `SCHEME' IS XC PARTITIONED INTO A MATRIX OF THE FOLLOWING FORM XC INTEGER SCHEME(-1:N,-N:?) XC WHERE THE TOTAL NUMBER OF COLUMNS DEPENDS ON THE AMOUNT OF SPACE XC ALLOCATED IN THE CALLING PROGRAM. XC XC THE VECTOR `INDEX' IS USED AS A PERMUTATION ARRAY TO KEEP TRACK OF XC EVERY COLUMN OF `SCHEME'. IN `SEARCH' IT IS AN ARRAY OF THE FORM XC INTEGER INDEX(-N:?) XC THE VECTOR `LIST' IS USED TO KEEP TRACK OF EACH UNIQUE N-TUPLE IN XC IN `SCHEME'. AND THUS IS DECLARED TO BE AN ARRAY OF THE FORM XC INTEGER LIST(?) XC THUS, `INDEX' AND `LIST' REALLY ONLY NEED TO BE LARGE ENOUGH TO XC TRACK THE TOTAL NUMBER OF COLUMNS IN SCHEME BUT ARE DECLARED TO BE XC AS LARGE AS `SCHEME' TO PREVENT ANY POSSIBLE OVERFLOW. XC XC FOR THE MOST EFFICIENT USE OF SPACE---WHICH MAY BECOME AN ISSUE XC WHEN GENERATING VERY LARGE SEARCH SCHEMES ON A PROCESSOR WITH A XC LIMITED AMOUNT OF MEMORY, THE CONSTANT `DIM' CAN BE SET EQUAL TO XC THE DIMENSION OF THE PROBLEM(S) FOR WHICH THE SEARCH SCHEME IS XC BEING GENERATED AND THE CONSTANT `MAX' CAN BE SET EQUAL TO THE XC NUMBER OF COLUMNS OF WORKSPACE TO BE ALLOWED IN `SCHEME' SO THAT XC THE ACTUAL AMOUNT OF SPACE FOR `SCHEME' BECOMES XC INTEGER SCHEME(-1:DIM,-DIM:MAX) XC NOTE THAT THE CONSTANT `LIMIT' AUTOMATICALLY TAKES CARE OF THIS IN XC THE DRIVER. XC XC THE WORKSPACE FOR INDEX AND LIST CAN THEN BE REDEFINED---IN THE XC DRIVER--AS XC INTEGER INDEX(1+DIM+MAX), LIST(MAX) XC WITHOUT ANY DANGER OF OVERFLOW. XC XC THUS ALL SPACE CREATED IN THE CALLING PROGRAM WILL BE USED IN THE XC SUBROUTINE `SEARCH'. XC X IN = 7 XC X OPEN(UNIT=IN, FILE='INPUT', STATUS='UNKNOWN', FORM='FORMATTED') X READ(IN,*) N X CLOSE(IN) XC X OUT = 8 XC X OPEN(UNIT=OUT,FILE='SCHEME', STATUS='UNKNOWN', FORM='UNFORMATTED') X CALL SEARCH(N,OUT,LIMIT,SCHEME,INDEX,LIST,UNIQUE,FACTOR,ERROR) X CLOSE(OUT) XC X OPEN(UNIT=OUT, FILE='RESULT', STATUS='UNKNOWN', FORM='FORMATTED') X IF (ERROR .EQ. 0) THEN X WRITE(OUT,100) N X 100 FORMAT('SUCCESSFULLY COMPLETED A SEARCH STRATEGY FOR PROBLEMS ', X > 'OF DIMENSION', I6) X WRITE(OUT,200) UNIQUE X 200 FORMAT('THE TOTAL NUMBER OF UNIQUE POINTS AVAILABLE IS', I26) X WRITE(OUT,300) FACTOR X 300 FORMAT('THE FACTOR NEEDED TO RESTORE THESE POINTS TO THEIR ', X > 'REAL VALUES IS', I7) X ELSE X WRITE(OUT,400) X 400 FORMAT('RETURNED WITHOUT A COMPLETED SEARCH STRATEGY BECAUSE') X WRITE(OUT,500) X 500 FORMAT('OF INTERNAL STACK OVERFLOW IN THE QUICKSORT ROUTINES.') X WRITE(OUT,600) X 600 FORMAT('CHECK THE DOCUMENTATION FOR FURTHER DETAILS.') X ENDIF X CLOSE(OUT) XC X END END_OF_FILE if test 7366 -ne `wc -c <'create.f'`; then echo shar: \"'create.f'\" unpacked with wrong size! fi # end of 'create.f' fi if test -f 'depth.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'depth.f'\" else echo shar: Extracting \"'depth.f'\" \(5196 characters\) sed "s/^X//" >'depth.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)depth.F 1.1 3/16/92 XC X INTEGER FUNCTION DEPTH(N,BETA,MAX) XC XC THIS A SERVICE FUNCTION USED TO FIGURE OUT HOW MANY LOOK-AHEADS XC WILL BE NEEDED TO GENERATE A LIST WITH A TOTAL OF `MAX' POINTS. XC USING THE CONTRACTION FACTOR, WE CALCULATE A RESCALING FACTOR SO XC THAT ALL WORK TO GENERATE THIS LIST OF POINTS CAN BE DONE IN XC INTEGER ARITHMETIC. XC XC THE RETURN VALUE DEPENDS ON THE CONTRACTION FACTOR AND THE MAXIMUM XC NUMBER OF POINTS THAT CAN BE GENERATED GIVEN THE AMOUNT OF XC WORKSPACE ALLOCATED IN THE MAIN PROGRAM. XC XC WRITTEN BY VIRGINIA TORCZON XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER N, BETA, MAX XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC INPUT XC N THE DIMENSION OF THE PROBLEM TO BE SOLVED XC BETA THE CONTRACTION FACTOR USED TO REDUCE THE SIZE OF XC THE SIMPLEX XC MAX UPPER LIMIT ON THE NUMBER OF POINTS THAT CAN BE XC CONSIDERED FOR THE TEMPLATE XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER FACTOR, GROWTH, SUM, TEMP XC X FACTOR = BETA X GROWTH = 3*N + 1 X TEMP = GROWTH X SUM = TEMP XC X 1000 IF (SUM .LT. MAX) THEN X TEMP = TEMP*GROWTH X SUM = SUM + TEMP X FACTOR = FACTOR*BETA X GO TO 1000 X ENDIF XC X DEPTH = FACTOR XC X RETURN X END END_OF_FILE if test 5196 -ne `wc -c <'depth.f'`; then echo shar: \"'depth.f'\" unpacked with wrong size! fi # end of 'depth.f' fi if test -f 'order.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'order.f'\" else echo shar: Extracting \"'order.f'\" \(4965 characters\) sed "s/^X//" >'order.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)order.F 1.1 3/16/92 XC X INTEGER FUNCTION ORDER(N,X,Y) XC XC THIS IS A SERVICE FUNCTION USED TO COMPARE TWO INTEGER XC N-TUPLES TO ALLOW FOR A PARTIAL ORDERING. XC XC THE RETURN VALUES ARE: XC XC -1 IF X < Y XC 0 IF X = Y XC 1 IF X > Y XC XC NOTE THAT THE PARTIAL ORDERING OF THE N-TUPLES IS DETERMINED BY XC SCANNING THE TUPLES FROM THE FIRST ELEMENT TO THE NTH ELEMENT. XC XC WRITTEN BY VIRGINIA TORCZON XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER N, X(N), Y(N) XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC INPUT XC N DIMENSION OF THE PROBLEM TO BE SOLVED XC X FIRST N-TUPLE FOR COMPARISON XC Y SECOND N-TUPLE FOR COMPARISON XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER I, SAME XC X SAME = 0 X I = 1 XC X 1000 IF (SAME .EQ. 0) THEN X IF (X(I) .LT. Y(I)) THEN X SAME = -1 X ELSE IF (X(I) .GT. Y(I)) THEN X SAME = 1 X ENDIF X IF (I .LT. N) THEN X I = I + 1 X GOTO 1000 X ENDIF X ENDIF XC X ORDER = SAME XC X RETURN X END END_OF_FILE if test 4965 -ne `wc -c <'order.f'`; then echo shar: \"'order.f'\" unpacked with wrong size! fi # end of 'order.f' fi if test -f 'quick.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'quick.f'\" else echo shar: Extracting \"'quick.f'\" \(10021 characters\) sed "s/^X//" >'quick.f' <<'END_OF_FILE' XC XC Copyright (C) 1986 Robert Michael Lewis. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)quick.F 1.2 3/16/92 XC X SUBROUTINE QUICK(N,ARRAY,ERROR) XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER N, ARRAY(N), ERROR XC XC*********************************************************************** XC XC THIS IS A FORTRAN IMPLEMENTATION OF THE NON-RECURSIVE VERSION FOR XC SORTING AN ARRAY OF NUMBERS. THE ALGORITHM IS THAT WHICH APPEARS XC AS PROGRAM 2.11 IN WIRTH'S BOOK "ALGORITHMS + DATA STRUCTURES XC = PASCAL PROGRAMS", PRENTICE-HALL, 1976. THE MODIFICATION TO XC MINIMIZE THE STACK SIZE DESCRIBED IN (2.16) OF THIS REFERENCE IS XC ALSO USED. XC XC-----ON INPUT----- XC ARRAY -- THE ARRAY OF NUMBERS TO BE SORTED : XC THIS ROUTINE ASSUMES THAT THESE NUMBERS ARE INTEGER. XC N -- THE NUMBER OF ITEMS TO BE SORTED XC-----ON OUTPUT---- XC ARRAY -- THE NUMBERS SORTED IN ASCENDING ORDER : XC NOTE THAT THE ORIGINAL ARRAY OF NUMBERS IS WRITTEN OVER AND LOST XC ERROR -- FLAG TO INDICATE THAT THE ARRAY TO BE SORTED IS TOO XC LONG FOR THE INTERNAL STACK (SEE COMMENTS BELOW) XC XC WRITTEN BY R.M.LEWIS JULY,1986 XC XC LAST MODIFICATION BY VIRGINIA TORCZON FEBRUARY 27, 1992 XC XC*********************************************************************** XC XC LOCAL CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER M, LEFT, RIGHT X PARAMETER (M = 32, LEFT = 1, RIGHT = 2) XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER S, L, R, I, J, X, TEMP, STACK(M,2), X > LENGTH, POWER, REMAIN XC XC*********************************************************************** XC XC WIRTH'S REMEDY TO KEEP THE LENGTH OF THE STACK STACK (`M') LESS XC THAN THE LENGTH OF THE LIST TO BE SORTED (`N') LIES IN STACKING XC THE SORT REQUEST FOR THE LONGER PARTITION AND CONTINUING DIRECTLY XC WITH THE FURTHER PARTITIONING OF THE SMALLER SECTIONS. IF THIS IS XC ENFORCED THEN THE LENGTH OF THE STACK CAN BE LIMITED TO M = LOG N. XC 2 XC XC IN THIS IMPLEMENTATION, WE HAVE ALLOCATED THE STACK LOCALLY TO XC BE OF LENGTH M, WHICH ALLOWS US TO SORT ARRAYS OF LENGTH UP TO XC 2**M. TO MAKE SURE THAT WE DO NOT EXCEED THIS UPPER BOUND, THE XC FOLLOWING TEST IS MADE BEFORE BEGINNING THE SEARCH. XC X POWER = 0 X REMAIN = 0 X LENGTH = N X 50 IF (LENGTH .GT. 1) THEN X POWER = POWER + 1 X REMAIN = REMAIN + MOD(LENGTH,2) X LENGTH = LENGTH / 2 X GOTO 50 X ENDIF X IF (REMAIN .GT. 0) POWER = POWER + 1 XC X IF (POWER .LE. M) THEN XC XC----------------------------------------------------------------------- XC *** INITIALIZE THE STACK : WE BEGIN THE PARTITIONING AT THE LEFT AND XC RIGHT ENDS OF THE ARRAY XC----------------------------------------------------------------------- XC X S = 1 X STACK(S,LEFT) = 1 X STACK(S,RIGHT) = N XC XC------------------------------------------- XC *** BEGIN THE LOOP TO SIMULATE RECURSION XC------------------------------------------- XC X 100 CONTINUE XC XC------------------------------------------------------------- XC *** TAKE THE TOP REQUEST OFF THE STACK XC------------------------------------------------------------- XC X L = STACK(S,LEFT) X R = STACK(S,RIGHT) X S = S - 1 XC XC------------------------------------------------------ XC *** SPLIT { ARRAY(L) , .... , ARRAY(R) } XC------------------------------------------------------ XC X 200 CONTINUE XC X I = L X J = R X X = ARRAY( (L + R)/2 ) XC X 300 CONTINUE XC XC------------------------------------------------------------------- XC **** THE FOLLOWING IS EQUIVALENT TO : DO WHILE( ARRAY(I) < X ) XC I = I + 1 XC END DO XC------------------------------------------------------------------- XC X 330 CONTINUE X IF( ARRAY(I) .LT. X ) THEN X I = I + 1 X GO TO 330 X ENDIF XC XC------------------------------------------------------------------- XC **** THE FOLLOWING IS EQUIVALENT TO : DO WHILE( ARRAY(J) > X ) XC J = J + 1 XC END DO XC------------------------------------------------------------------- XC X 350 CONTINUE X IF( ARRAY(J) .GT. X ) THEN X J = J - 1 X GO TO 350 X ENDIF XC XC---------------------------------------------------------- XC **** PERFORM A SWAP, AND THEN MOVE ON IN THE SCAN XC---------------------------------------------------------- XC X IF( I .LE. J ) THEN XC X TEMP = ARRAY(I) X ARRAY(I) = ARRAY(J) X ARRAY(J) = TEMP XC X I = I + 1 X J = J - 1 XC X ENDIF XC X IF( I .LE. J ) THEN X GO TO 300 X ENDIF XC XC-------------------------------------------------------------------- XC **** PLACE ON THE STACK THE REQUEST TO SORT THE LONGER PARTITION XC AND BEGIN FURTHER PARTIONING OF THE SMALLER PARTITIONS XC-------------------------------------------------------------------- XC X IF( (J - L) .LT. (R - I) ) THEN X IF( I .LT. R ) THEN X S = S + 1 X STACK(S,LEFT) = I X STACK(S,RIGHT) = R X ENDIF XC X R = J X ELSE X IF( L .LT. J ) THEN X S = S + 1 X STACK(S,LEFT) = L X STACK(S,RIGHT) = J X ENDIF XC X L = I X ENDIF XC XC----------------------------------------------------------------------- XC *** THE FOLLOWING TWO IF-THEN BLOCKS MARK THE ENDS OF TWO REPEAT-UNTIL XC BLOCKS. CAN YOU SEE WHAT THEY ARE ??? XC----------------------------------------------------------------------- XC X IF( L .LT. R ) THEN X GO TO 200 X ENDIF XC X IF( S .GT. 0 ) THEN X GO TO 100 X ELSE X RETURN X ENDIF XC X ENDIF XC X ERROR = 1 X RETURN X END END_OF_FILE if test 10021 -ne `wc -c <'quick.f'`; then echo shar: \"'quick.f'\" unpacked with wrong size! fi # end of 'quick.f' fi if test -f 'search.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'search.f'\" else echo shar: Extracting \"'search.f'\" \(15766 characters\) sed "s/^X//" >'search.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)search.F 1.1 3/16/92 XC X SUBROUTINE SEARCH(N,OUT,MAX,SCHEME,INDEX,LIST,UNIQUE,FACTOR,ERROR) XC XC THIS IS A CONTROLLING ROUTINE TO CONSTRUCT AN ACTUAL SEARCH XC STRATEGY. FOR A FURTHER DESCRIPTION OF THIS ALGORITHM, AS IT XC RELATES TO THE PARALLEL DIRECT SEARCH METHODS, SEE XC J. E. DENNIS, JR. AND VIRGINIA TORCZON, "DIRECT SEARCH METHODS XC ON PARALLEL MACHINES," SIAM J. OPTIMIZATION, VOL. 1, NO. 4, XC PP. 448-474, NOVEMBER 1991. XC XC THE CONSTRUCTION OF THIS SEARCH STRATEGY IS DISCUSSED ON XC PP. 459-462 AND PP. 463-466; THE ALGORITHM IMPLEMENTED BELOW IS XC FORMALLY STATED IN TABLE 3, P. 465. XC XC WRITTEN BY VIRGINIA TORCZON XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER N, MAX, OUT, UNIQUE, FACTOR, ERROR X INTEGER SCHEME(-1:N,-N:((MAX-N*N-3*N-2)/(N+2))), X > INDEX(-N:((MAX-N*N-3*N-2)/(N+2))), X > LIST((MAX-N*N-3*N-2)/(N+2)) XC NOTE THAT THESE RATHER MESSY DIMENSION STATEMENTS XC ARE TO ALLOW THE MAXIMUM POSSIBLE NUMBER OF XC COLUMNS IN `SCHEME' GIVEN `N', THE DIMENSION OF XC THE PROBLEM, AND `MAX', THE SIZE OF `SCHEME' XC DECLARED IN THE MAIN PROGRAM. XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC INPUT XC N THE DIMENSION OF THE PROBLEM TO BE SOLVED XC MAX THE DECLARED DIMENSION OF THE VECTOR `SCHEME' XC OUT UNIT NUMBER FOR THE FILE TO WHICH THE POINTS IN XC THE SEARCH SCHEME ARE TO BE WRITTEN XC WORK XC SCHEME A WORK VECTOR PASSED FROM THE MAIN PROGRAM THAT XC IS REPARTITIONED INTO A MATRIX WITH ROWS FROM XC -1 TO N AND AS MANY COLUMNS AS THE ORIGINAL XC DIMENSION OF THE VECTOR WILL ALLOW. THIS ARRAY XC IS USED TO HOLD THE N-TUPLES (IN ROWS 1 THROUGH XC N) FOR EVERY POINT GENERATED AS A POSSIBLE POINT XC IN THE SEARCH STRATEGY. IN ROWS -1 AND 0 ARE THE XC SCALAR `A' AND THE POINT `BEST' NECESSARY TO XC RECONSTRUCT THE SIMPLEX ASSOCIATED WITH THAT XC N-TUPLE. XC INDEX ARRAY TO KEEP TRACK OF EACH COLUMN OF `SCHEME' XC LIST ARRAY TO KEEP TRACK OF A LIST OF DISTINCT XC N-TUPLES IN SCHEME (IF AN N-TUPLE OCCURS MORE XC THAN ONCE IN `SCHEME', `LIST' RECORDS ONLY THE XC FIRST OCCURRENCE) XC OUTPUT XC UNIQUE THE FINAL LENGTH OF `LIST' (I.E., THE TOTAL XC NUMBER OF DISTINCT POINTS GENERATED) XC FACTOR THE SCALING FACTOR USED TO GENERATE THE LIST; XC `FACTOR' IS CHOSEN TO ALLOW ALL THE WORK TO BE XC DONE IN INTEGER ARITHMETIC BOTH TO SAVE STORAGE XC AND TO ELIMINATE ANY AMBIGUITIES ABOUT THE XC DISTINCTIVENESS OF N-TUPLE---AMBIGUITIES THAT XC COULD POSSIBLE OCCUR WHEN USING FLOATING POINT XC ARITHMETIC XC ERROR ERROR FLAG TO SIGNAL WHETHER OR NOT PREMATURE XC TERMINATION OCCURRED. IF `ERROR' IS SET TO ZERO, XC THEN NO ERRORS HAVE BEEN FLAGGED. CURRENTLY, THE XC ONLY ERROR FLAGGED IS WHEN THE QUICKSORT ROUTINES XC RETURN BECAUSE THE LENGTH OF THE ARRAY PASSED TO XC SORT EXCEEDS THE CAPACITY OF THE INTERNAL STACK. XC FOR FURTHER INFORMATION ON THIS ERROR, SEE THE XC COMMENTS IN THE ROUTINES `SORT' AND `QUICK'. XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC LOCAL CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER A, BEST X INTEGER ALPHA, BETA, GAMMA X PARAMETER (A = -1, BEST = 0) X PARAMETER (ALPHA = -1, BETA = 2, GAMMA = -2) XC THE PARAMETERS ALPHA, BETA, AND GAMMA SET THE SIZE OF THE XC REFLECTION, CONTRACTION, AND EXPANSION STEPS, RESPECTIVELY. THESE XC CONSTANTS ARE CURRENTLY SET TO THE DEFAULT VALUES RECOMMENDED BY XC NELDER AND MEAD (NOTE THAT WE DIVIDE BY BETA!). THE ALGORITHM XC BELOW ASSUMES THAT EACH CONSTANT IS A POWER OF TWO SO THAT THE XC WORK CAN BE DONE IN INTEGER ARITHMETIC. XC XC LOCAL VARIABLES CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER C, I, J, K, LEAF, LIMIT, TOTAL XC XC FUNCTIONS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC INTRINSIC FLOAT, NINT X INTEGER ORDER, DEPTH XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC XC THE CRITICAL "PIECES" OF THE SEARCH SCHEME RESIDE IN THE DATA XC STRUCTURE `SCHEME'. THE MATRIX `SCHEME' CAN BE THOUGHT OF AS TWO XC VECTORS, `A', WHICH IS STORED IN THE -1 ROW OF `SCHEME', AND XC `BEST', WHICH IS STORED IN THE 0 ROW OF `SCHEME', AND ONE MATRIX XC `NTUPLES', WHICH IS STORED IN THE REMAINING ROWS OF `SCHEME'. XC XC THE PURPOSE OF THESE PIECES ARE AS FOLLOWS: XC XC A AN INTEGER ARRAY WHICH CONTAINS THE SCALAR NECESSARY TO XC RECONSTRUCT THE SIMPLEX ASSOCIATED WITH A GIVEN POINT I XC BEST AN INTEGER ARRAY WHICH CONTAINS THE POINTER TO THE VERTEX XC IN THE ORIGINAL SIMPLEX ASSOCIATED WITH A GIVEN POINT I XC NTUPLES AN INTEGER MATRIX WHICH CONTAINS THE SCALARS NECESSARY TO XC CONSTRUCT POINT I FROM THE N EDGES ADJACENT TO THE BEST XC VERTEX IN THE ORIGINAL SIMPLEX; THE N-TUPLES ARE STORED XC BY COLUMN XC XC NOTE THAT FOR ALL THREE STRUCTURES WE ALSO KEEP INFORMATION ABOUT XC THE N+1 VERTICES IN THE ORIGINAL SIMPLEX IN POSITIONS/COLUMNS -N XC THROUGH 0 SO THAT WE HAVE ALL THE INFORMATION WE NEED BOTH TO XC GENERATE THE NEW POINTS AND TO DETECT DUPLICATION. XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC XC INITIALIZE THE OPTIMIZATION PROCEDURE BY DETERMINING THE POINTS XC TO BE COMPUTED AT EACH ITERATION ON THE HYPERCUBE. XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC XC THERE IS AN UPPER LIMIT ON THE NUMBER OF POINTS WE CAN CONSIDER XC WHICH IS BASED ON THE DIMENSION OF THE PROBLEM `N' AND THE SIZE OF XC `SCHEME'. CALCULATE THAT LIMIT. X LIMIT = (MAX - N*N - 3*N - 2)/(N + 2) XC XC WE WILL ALSO RESCALE BY THE "GREATEST COMMON DENOMINATOR" XC (DETERMINED BY `BETA'). IN ESSENCE, WE ARE TRYING TO GUESS HOW XC MANY "LOOK-AHEADS" WE MUST DO TO FILL OUT THE "RAW" LIST OF POINTS XC WE WILL GENERATE. THE SIZE OF THE RAW LIST IS DETERMINED BY XC `LIMIT' (I.E., THE MAXIMUM SIZE OF `SCHEME'). ONCE WE RESCALE XC ACCORDINGLY, WE CAN WORK STRICTLY IN INTEGER ARITHMETIC. X FACTOR = DEPTH(N,BETA,LIMIT) XC XC INITIALIZE THE ROOT OF THE TREE, WHICH IS THE CURRENT BEST VERTEX. X LEAF = 0 X J = 0 X INDEX(J) = 0 X SCHEME(A,J) = FACTOR X SCHEME(BEST,J) = 0 X DO 1000 K = 1, N X SCHEME(K,LEAF) = 0 X 1000 CONTINUE XC XC INITIALIZE THE REMAINING VERTICES IN THE SIMPLEX SO THAT THEY ARE XC NOT LATER DUPLICATED. X DO 3000 I = 1, N X INDEX(-I) = -I X SCHEME(A,-I) = FACTOR X SCHEME(BEST,-I) = 0 X DO 2000 K = 1, N X SCHEME(K,-I) = 0 X 2000 CONTINUE X SCHEME(I,-I) = FACTOR X 3000 CONTINUE XC XC CHECK TO PREVENT OVERFLOW (I.E., SO THAT `LIMIT' IS NOT EXCEEDED). X 4000 IF (J .LE. (LIMIT - (3*N + 1))) THEN XC X C = SCHEME(BEST,LEAF) XC XC FIRST COMPUTE ALL N REFLECTION POINTS. X DO 6000 I = 0, C - 1 X J = J + 1 X INDEX(J) = J X SCHEME(A,J) = SCHEME(A,LEAF) * ALPHA X SCHEME(BEST,J) = I X DO 5000 K = 1, N X SCHEME(K,J) = SCHEME(K,LEAF) X 5000 CONTINUE X IF (I .NE. 0) SCHEME(I,J) = SCHEME(I,J) + SCHEME(A,J) X SCHEME(C,J) = SCHEME(C,J) - SCHEME(A,J) X 6000 CONTINUE X DO 8000 I = C + 1, N X J = J + 1 X INDEX(J) = J X SCHEME(A,J) = SCHEME(A,LEAF) * ALPHA X SCHEME(BEST,J) = I X DO 7000 K = 1, N X SCHEME(K,J) = SCHEME(K,LEAF) X 7000 CONTINUE X SCHEME(I,J) = SCHEME(I,J) + SCHEME(A,J) X IF (C .NE. 0) X > SCHEME(C,J) = SCHEME(C,J) - SCHEME(A,J) X 8000 CONTINUE XC XC NEXT COMPUTE ALL N + 1 CONTRACTION POINTS. XC WE INCLUDE THE POSSIBILITY THAT THE BEST IS NOT REPLACED. X DO 10000 I = 0, N X J = J + 1 X INDEX(J) = J X SCHEME(A,J) = SCHEME(A,LEAF) / BETA X SCHEME(BEST,J) = I X DO 9000 K = 1, N X SCHEME(K,J) = SCHEME(K,LEAF) X 9000 CONTINUE X IF (I .NE. 0) SCHEME(I,J) = SCHEME(I,J) + SCHEME(A,J) X IF (C .NE. 0) X > SCHEME(C,J) = SCHEME(C,J) - SCHEME(A,J) X10000 CONTINUE XC XC FINALLY, COMPUTE ALL N EXPANSION POINTS. X DO 12000 I = 0, C - 1 X J = J + 1 X INDEX(J) = J X SCHEME(A,J) = SCHEME(A,LEAF) * GAMMA X SCHEME(BEST,J) = I X DO 11000 K = 1, N X SCHEME(K,J) = SCHEME(K,LEAF) X11000 CONTINUE X IF (I .NE. 0) SCHEME(I,J) = SCHEME(I,J) + SCHEME(A,J) X SCHEME(C,J) = SCHEME(C,J) - SCHEME(A,J) X12000 CONTINUE X DO 14000 I = C + 1, N X J = J + 1 X INDEX(J) = J X SCHEME(A,J) = SCHEME(A,LEAF) * GAMMA X SCHEME(BEST,J) = I X DO 13000 K = 1, N X SCHEME(K,J) = SCHEME(K,LEAF) X13000 CONTINUE X SCHEME(I,J) = SCHEME(I,J) + SCHEME(A,J) X IF (C .NE. 0) X > SCHEME(C,J) = SCHEME(C,J) - SCHEME(A,J) X14000 CONTINUE XC X LEAF = LEAF + 1 XC X GOTO 4000 XC X ENDIF XC X TOTAL = J XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC XC XC NOW, ELIMINATE ALL THE DUPLICATE POINTS. WHEN THERE ARE XC DUPLICATES, KEEP THE POINT THAT WAS GENERATED FIRST. XC XCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X ERROR = 0 XC XC FIRST SORT THE LIST OF "RAW" POINTS; THE SORT IS KEYED ON THE XC N-TUPLES IN `SCHEME'. X CALL SORT(N,TOTAL,INDEX,SCHEME,ERROR) XC X IF (ERROR .EQ. 0) THEN XC NOW GO THROUGH THIS SORTED LIST AND BUILD A NEW LIST OF UNIQUE XC N-TUPLES (THE INDEX FOR THIS LIST IS STORED IN THE ARRAY XC `LIST'). X UNIQUE = 0 X I = -N X DO 15000 J = -N+1, TOTAL X IF (ORDER(N,SCHEME(1,INDEX(I)),SCHEME(1,INDEX(J))) .NE. 0) X > THEN XC YOU HAVE ANOTHER (UNIQUE) POINT TO ADD TO THE LIST. XC (MAKE SURE YOU ARE NOT ADDING ONE OF THE ORIGINAL VERTICES!) X IF (INDEX(I) .GT. 0) THEN X UNIQUE = UNIQUE + 1 X LIST(UNIQUE) = INDEX(I) X ENDIF X I = J X ELSE XC YOU HAVE A DUPLICATE POINT. X IF (INDEX(I) .GT. INDEX(J)) THEN XC KEEP THE POINT WHICH WAS GENERATED "FIRST." X I = J X ENDIF X ENDIF X15000 CONTINUE XC ADD THE LAST POINT TO THE LIST. X IF (INDEX(I) .GT. 0) THEN XC AGAIN, MAKE SURE YOU ARE NOT ADDING ONE OF THE ORIGINAL XC VERTICES! X UNIQUE = UNIQUE + 1 X LIST(UNIQUE) = INDEX(I) X ENDIF XC XC NOW RESORT THE LIST OF UNIQUE POINTS, KEYED ON `LIST', SO THAT XC THE POINTS CAN BE LOADED IN THE CORRECT ORDER. X CALL QUICK(UNIQUE,LIST,ERROR) XC X IF (ERROR .EQ. 0) THEN XC WRITE ALL THIS INFORMATION OUT TO A FILE FOR LATER USE. X CALL WRITES(OUT,N,TOTAL,UNIQUE,FACTOR,BETA,SCHEME,LIST) X ENDIF X ENDIF XC X RETURN XC X END END_OF_FILE if test 15766 -ne `wc -c <'search.f'`; then echo shar: \"'search.f'\" unpacked with wrong size! fi # end of 'search.f' fi if test -f 'sort.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'sort.f'\" else echo shar: Extracting \"'sort.f'\" \(10836 characters\) sed "s/^X//" >'sort.f' <<'END_OF_FILE' XC XC Copyright (C) 1986 Robert Michael Lewis. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)sort.F 1.2 3/16/92 XC X SUBROUTINE SORT(N,TOTAL,ARRAY,SCHEME,ERROR) XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER N, TOTAL, ARRAY(-N:TOTAL), SCHEME(-1:N,-N:TOTAL), X > ERROR XC XC*********************************************************************** XC XC THIS IS A FORTRAN IMPLEMENTATION OF THE NON-RECURSIVE VERSION FOR XC SORTING AN ARRAY OF NUMBERS. THE ALGORITHM IS THAT WHICH APPEARS XC AS PROGRAM 2.11 IN WIRTH'S BOOK "ALGORITHMS + DATA STRUCTURES XC = PASCAL PROGRAMS", PRENTICE-HALL, 1976. THE MODIFICATION TO XC MINIMIZE THE STACK SIZE DESCRIBED IN (2.16) OF THIS REFERENCE IS XC ALSO USED. XC XC-----ON INPUT----- XC ARRAY -- INDEX ARRAY OF POINTERS FOR THE N-TUPLES IN `SCHEME' XC SCHEME -- THE INTEGER N-TUPLES FOR THE SEARCH STRATEGY XC NOTE THAT WE ARE ACTUALLY SORTING THE N-TUPLES IN `SCHEME', BUT XC WE USE `ARRAY' TO STORE THIS ORDERING XC N -- THE DIMENSION OF THE PROBLEM TO BE SOLVED XC TOTAL -- THE NUMBER OF "RAW" POINTS GENERATED FOR `SCHEME' XC NOTE THAT THE NUMBER OF ITEMS TO BE SORTED IS THUS N + 1 + TOTAL XC-----ON OUTPUT---- XC ARRAY -- THE INDEX DENOTING A SORTING FOR THE N-TUPLES IN XC `SCHEME'. XC NOTE THAT THE ORIGINAL ARRAY OF NUMBERS IS WRITTEN OVER AND LOST XC ERROR -- FLAG TO INDICATE THAT THE ARRAY TO BE SORTED IS TOO XC LONG FOR THE INTERNAL STACK (SEE COMMENTS BELOW) XC XC WRITTEN BY R.M.LEWIS JULY,1986 XC XC LAST MODIFICATION BY VIRGINIA TORCZON FEBRUARY 27, 1992 XC XC*********************************************************************** XC XC LOCAL CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER M, LEFT, RIGHT X PARAMETER (M = 32, LEFT = 1, RIGHT = 2) XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER S, L, R, I, J, X, TEMP, STACK(M,2), X > LENGTH, POWER, REMAIN XC XC LOCAL FUNCTIONS FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF XC IMPLICIT MOD X INTEGER ORDER XC XC*********************************************************************** XC XC WIRTH'S REMEDY TO KEEP THE LENGTH OF THE STACK STACK (`M') LESS XC THAN THE LENGTH OF THE LIST TO BE SORTED (`N') LIES IN STACKING XC THE SORT REQUEST FOR THE LONGER PARTITION AND CONTINUING DIRECTLY XC WITH THE FURTHER PARTITIONING OF THE SMALLER SECTIONS. IF THIS IS XC ENFORCED THEN THE LENGTH OF THE STACK CAN BE LIMITED TO M = LOG N. XC 2 XC XC IN THIS IMPLEMENTATION, WE HAVE ALLOCATED THE STACK LOCALLY TO XC BE OF LENGTH M, WHICH ALLOWS US TO SORT ARRAYS OF LENGTH UP TO XC 2**M. TO MAKE SURE THAT WE DO NOT EXCEED THIS UPPER BOUND, THE XC FOLLOWING TEST IS MADE BEFORE BEGINNING THE SEARCH. XC X POWER = 0 X REMAIN = 0 X LENGTH = TOTAL + N + 1 X 50 IF (LENGTH .GT. 1) THEN X POWER = POWER + 1 X REMAIN = REMAIN + MOD(LENGTH,2) X LENGTH = LENGTH / 2 X GOTO 50 X ENDIF X IF (REMAIN .GT. 0) POWER = POWER + 1 XC X IF (POWER .LE. M) THEN XC XC----------------------------------------------------------------------- XC *** INITIALIZE THE STACK : WE BEGIN THE PARTITIONING AT THE LEFT AND XC RIGHT ENDS OF THE ARRAY XC----------------------------------------------------------------------- XC X S = 1 X STACK(S,LEFT) = -N X STACK(S,RIGHT) = TOTAL XC XC------------------------------------------- XC *** BEGIN THE LOOP TO SIMULATE RECURSION XC------------------------------------------- XC X 100 CONTINUE XC XC------------------------------------------------------------- XC *** TAKE THE TOP REQUEST OFF THE STACK XC------------------------------------------------------------- XC X L = STACK(S,LEFT) X R = STACK(S,RIGHT) X S = S - 1 XC XC------------------------------------------------------ XC *** SPLIT { ARRAY(L) , .... , ARRAY(R) } XC------------------------------------------------------ XC X 200 CONTINUE XC X I = L X J = R X X = ARRAY( (L + R)/2 ) XC X 300 CONTINUE XC XC------------------------------------------------------------------- XC **** THE FOLLOWING IS EQUIVALENT TO: DO WHILE XC (SCHEME(*,I) < SCHEME(*,X)) XC I = I + 1 XC END DO XC------------------------------------------------------------------- XC X 330 CONTINUE X IF( ORDER(N,SCHEME(1,ARRAY(I)),SCHEME(1,X)).LT.0 ) X > THEN X I = I + 1 X GO TO 330 X ENDIF XC XC------------------------------------------------------------------- XC **** THE FOLLOWING IS EQUIVALENT TO: DO WHILE XC (SCHEME(*,J) > SCHEME(*,X)) XC J = J + 1 XC END DO XC------------------------------------------------------------------- XC X 350 CONTINUE X IF( ORDER(N,SCHEME(1,ARRAY(J)),SCHEME(1,X)).GT.0 ) X > THEN X J = J - 1 X GO TO 350 X ENDIF XC XC---------------------------------------------------------- XC **** PERFORM A SWAP, AND THEN MOVE ON IN THE SCAN XC---------------------------------------------------------- XC X IF( I .LE. J ) THEN XC X TEMP = ARRAY(I) X ARRAY(I) = ARRAY(J) X ARRAY(J) = TEMP XC X I = I + 1 X J = J - 1 XC X ENDIF XC X IF( I .LE. J ) THEN X GO TO 300 X ENDIF XC XC-------------------------------------------------------------------- XC **** PLACE ON THE STACK THE REQUEST TO SORT THE LONGER PARTITION XC AND BEGIN FURTHER PARTIONING OF THE SMALLER PARTITIONS XC-------------------------------------------------------------------- XC X IF( (J - L) .LT. (R - I) ) THEN X IF( I .LT. R ) THEN X S = S + 1 X STACK(S,LEFT) = I X STACK(S,RIGHT) = R X ENDIF XC X R = J X ELSE X IF( L .LT. J ) THEN X S = S + 1 X STACK(S,LEFT) = L X STACK(S,RIGHT) = J X ENDIF XC X L = I X ENDIF XC XC----------------------------------------------------------------------- XC *** THE FOLLOWING TWO IF-THEN BLOCKS MARK THE ENDS OF TWO REPEAT-UNTIL XC BLOCKS. CAN YOU SEE WHAT THEY ARE ??? XC----------------------------------------------------------------------- XC X IF( L .LT. R ) THEN X GO TO 200 X ENDIF XC X IF( S .GT. 0 ) THEN X GO TO 100 X ELSE X RETURN X ENDIF XC X ENDIF XC X ERROR = 1 X RETURN X END END_OF_FILE if test 10836 -ne `wc -c <'sort.f'`; then echo shar: \"'sort.f'\" unpacked with wrong size! fi # end of 'sort.f' fi if test -f 'writes.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'writes.f'\" else echo shar: Extracting \"'writes.f'\" \(6555 characters\) sed "s/^X//" >'writes.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)writes.F 1.1 3/16/92 XC X SUBROUTINE WRITES(LPR,N,TOTAL,UNIQUE,FACTOR,BETA,SCHEME,LIST) XC XC WRITE THE POINTS IN THE SEARCH SCHEME OUT TO AN UNFORMATTED XC FORTRAN FILE FOR LATER USE BY THE PARALLEL DIRECT SEARCH METHODS. XC XC NOTE THAT BEFORE THE POINTS IN THE SEARCH STRATEGY ARE WRITTEN OUT XC TO A FILE, WE WRITE OUT FOUR PIECES OF "HEADER" INFORMATION: N, XC UNIQUE, FACTOR, AND BETA. THE FIRST TWO PIECES ARE FOR ERROR XC CHECKING WHEN THE FILE IS LATER USED BY THE PARALLEL DIRECT SEARCH XC METHODS; THE SECOND TWO PIECES OF INFORMATION ARE USED TO XC ACCELERATE THE CONTRACTION STEP WHEN THE BEST VERTEX IS NOT XC REPLACED. XC XC WRITTEN BY VIRGINIA TORCZON XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER LPR, N, TOTAL, UNIQUE, FACTOR, BETA, X > SCHEME(-1:N,-N:TOTAL), LIST(UNIQUE) XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC INPUT XC LPR UNIT NUMBER TO WHICH THE SCHEME IS TO BE WRITTEN XC N DIMENSION USED TO GENERATE THE SEARCH SCHEME XC TOTAL THE TOTAL NUMBER OF POINTS CREATED (BASED ON THE XC AMOUNT OF WORKSPACE ALLOCATED IN THE MAIN XC PROGRAM) XC UNIQUE THE TOTAL NUMBER OF UNIQUE POINTS CREATED AFTER XC CHECKING FOR DUPLICATE N-TUPLES XC FACTOR THE SCALING FACTOR USED TO GENERATE THE SEARCH XC SCHEME; NOTE THAT THIS SCALING FACTOR IS XC NECESSARY TO RECONSTRUCT THE REAL (OR DOUBLE XC PRECISION) COUNTERPARTS TO THE INTEGER TUPLES XC BETA THE CONTRACTION FACTOR USED TO GENERATE THE XC POINTS IN THE SEARCH SCHEME (INFORMATION REQUIRED XC BY THE OPTIMIZATION TO ACCELERATE CONTRACTIONS XC WHEN THE BEST VERTEX IS NOT REPLACED) XC SCHEME THE INTEGER TUPLES USED TO DEFINE EACH POINT IN XC THE SEARCH SCHEME XC LIST INDEX ARRAY USED TO POINT TO THE UNIQUE N-TUPLES XC IN THE SEARCH SCHEME; THE ONES ACTUALLY TO BE XC WRITTEN OUT TO THE FILE XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC LOCAL CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER INT, A, BEST X PARAMETER (INT = 4, A = -1, BEST = 0) XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER I, J XC X WRITE(LPR) N X WRITE(LPR) UNIQUE X WRITE(LPR) FACTOR X WRITE(LPR) BETA X DO 2000 I = 1, UNIQUE X WRITE(LPR) SCHEME(A,LIST(I)) X WRITE(LPR) SCHEME(BEST,LIST(I)) X DO 1000 J = 1, N X WRITE(LPR) SCHEME(J,LIST(I)) X 1000 CONTINUE X 2000 CONTINUE XC X RETURN X END END_OF_FILE if test 6555 -ne `wc -c <'writes.f'`; then echo shar: \"'writes.f'\" unpacked with wrong size! fi # end of 'writes.f' fi if test -f 'writes.intel.f' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'writes.intel.f'\" else echo shar: Extracting \"'writes.intel.f'\" \(6844 characters\) sed "s/^X//" >'writes.intel.f' <<'END_OF_FILE' XC Copyright (C) 1992 Virginia Torczon. All rights reserved. XC See below for limited use and distribution authorization. XC XC PDS, the collection of sofware for executing the parallel direct XC search methods, was written by Dr. Virginia Torczon, Department XC of Mathematical Sciences, Rice University, Houston, Texas. The XC two versions of Quicksort included in this release were written XC by Dr. Robert Michael Lewis, Department of Mathematical Sciences, XC Rice University, Houston, Texas. This software is distributed by XC CITI, the Computer and Information Technology Institute of Rice XC University. CITI Catalog Number PD92005, released for distribution XC March 16, 1992. XC XC Subject to the terms below, this software may be copied, XC distributed, or modified in any way desired without permission XC from the author(s) or from Rice University. XC XC If the software is distributed in complete, unmodified form, no XC charge may be made for any copies so distributed, except that a XC nominal fee not exceeding the reasonable cost of distribution may XC be charged. In addition, this legend must be included in all XC such complete, unmodified copies so distributed (but otherwise no XC reference may be made to the author(s) or to Rice University or XC CITI). XC XC Neither the author(s)' names nor that of their affiliated insti- XC tutions (if any), nor the names of Rice University or CITI, may XC be used by any person or entity, in any manner, without his/her/ XC its express prior written consent. XC XC This software was created in the course of academic and/or re- XC search endeavors and not as a commercial package. Its present XC version (which may still be in development) is distributed for a XC nominal fee to cover the cost of distribution and administrative XC costs, "AS IS, WITH ALL DEFECTS." By using the software, each XC user agrees to assume all responsibility for any and all such XC use. The author(s) and Rice University are not aware that the XC software or the use thereof infringe any proprietary right be- XC longing to a third party. However, NO WARRANTY OR REPRESENTA- XC TION OF ANY KIND, EXPRESS OR IMPLIED, is made about the software, XC including without limitation any warranty of title, noninfringe- XC ment, merchantability, or fitness for a particular purpose, by XC the author(s) or by Rice University. XC XC Independent of the foregoing disclaimer of warranties, the user XC agrees, by using the software, that NEITHER RICE UNIVERSITY NOR XC THE AUTHOR(S) SHALL BE LIABLE FOR ANY INCIDENTAL OR CONSEQUENTIAL XC DAMAGES IN CONNECTION WITH THE USE OF THIS SOFTWARE, INCLUDING XC WITHOUT LIMITATION LOST PROFITS OR INJURY TO BUSINESS, WHETHER OR XC NOT RICE UNIVERSITY AND/OR THE AUTHOR(S) KNOW OR HAVE REASON TO XC KNOW OF THE POSSIBILITY OF SUCH DAMAGES. XC XC By using this software, the user agrees to indemnify and defend XC Rice University and the author(s) and their affiliated institu- XC tions (if any), or any of them, against any loss, expense, claim, XC damage, or liability of any kind arising from or connected with XC the licensee's use of the software, and to hold them or any of XC them harmless from any of the same, WHETHER OR NOT ARISING IN XC WHOLE OR IN PART FROM THE NEGLIGENCE OR GROSS NEGLIGENCE OF RICE XC UNIVERSITY OR ANY OF THE AUTHOR(S) OR THEIR AFFILIATED INSTITU- XC TIONS (IF ANY). XC XC @(#)writes.intel.F 1.1 3/16/92 XC X SUBROUTINE WRITES(LPR,N,TOTAL,UNIQUE,FACTOR,BETA,SCHEME,LIST) XC XC INTEL VERSION XC XC WRITE THE POINTS IN THE SEARCH SCHEME OUT TO AN UNFORMATTED XC FORTRAN FILE FOR LATER USE BY THE PARALLEL DIRECT SEARCH METHODS. XC XC NOTE THAT BEFORE THE POINTS IN THE SEARCH STRATEGY ARE WRITTEN OUT XC TO A FILE, WE WRITE OUT FOUR PIECES OF "HEADER" INFORMATION: N, XC UNIQUE, FACTOR, AND BETA. THE FIRST TWO PIECES ARE FOR ERROR XC CHECKING WHEN THE FILE IS LATER USED BY THE PARALLEL DIRECT SEARCH XC METHODS; THE SECOND TWO PIECES OF INFORMATION ARE USED TO XC ACCELERATE THE CONTRACTION STEP WHEN THE BEST VERTEX IS NOT XC REPLACED. XC XC WRITTEN BY VIRGINIA TORCZON XC XC LAST MODIFICATION: MARCH 11, 1992. XC XC PARAMETERS PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP X INTEGER LPR, N, TOTAL, UNIQUE, FACTOR, BETA, X > SCHEME(-1:N,-N:TOTAL), LIST(UNIQUE) XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC INPUT XC LPR UNIT NUMBER TO WHICH THE SCHEME IS TO BE WRITTEN XC N DIMENSION USED TO GENERATE THE SEARCH SCHEME XC TOTAL THE TOTAL NUMBER OF POINTS CREATED (BASED ON THE XC AMOUNT OF WORKSPACE ALLOCATED IN THE MAIN XC PROGRAM) XC UNIQUE THE TOTAL NUMBER OF UNIQUE POINTS CREATED AFTER XC CHECKING FOR DUPLICATE N-TUPLES XC FACTOR THE SCALING FACTOR USED TO GENERATE THE SEARCH XC SCHEME; NOTE THAT THIS SCALING FACTOR IS XC NECESSARY TO RECONSTRUCT THE REAL (OR DOUBLE XC PRECISION) COUNTERPARTS TO THE INTEGER TUPLES XC BETA THE CONTRACTION FACTOR USED TO GENERATE THE XC POINTS IN THE SEARCH SCHEME (INFORMATION REQUIRED XC BY THE OPTIMIZATION TO ACCELERATE CONTRACTIONS XC WHEN THE BEST VERTEX IS NOT REPLACED) XC SCHEME THE INTEGER TUPLES USED TO DEFINE EACH POINT IN XC THE SEARCH SCHEME XC LIST INDEX ARRAY USED TO POINT TO THE UNIQUE N-TUPLES XC IN THE SEARCH SCHEME; THE ONES ACTUALLY TO BE XC WRITTEN OUT TO THE FILE XC XCPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP XC XC LOCAL CONSTANTS CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC X INTEGER INT X PARAMETER (INT = 4) XC XC LOCAL VARIABLES VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV X INTEGER HEADER(4), I, J XC XC NOTE THAT ON THE INTEL DISTRIBUTED MEMORY MACHINES IT IS *MUCH* XC FASTER TO AGGREGATE DATA ON THE NODE AND WRITE IT OUT TO THE FILE XC AS A SINGLE BLOCK THAN TO WRITE OUT A PIECE AT A TIME WHEN USING XC THE INTEL LIBRARY ROUTINES FOR I/0. XC X HEADER(1) = N X HEADER(2) = UNIQUE X HEADER(3) = FACTOR X HEADER(4) = BETA X CALL CWRITE(LPR,HEADER,4*INT) XC X DO 2000 J = 1, UNIQUE X DO 1000 I = -1, N X SCHEME(I,J) = SCHEME(I,LIST(J)) X 1000 CONTINUE X 2000 CONTINUE X CALL CWRITE(LPR,SCHEME(-1,1),UNIQUE*(N+2)*INT) XC X RETURN X END END_OF_FILE if test 6844 -ne `wc -c <'writes.intel.f'`; then echo shar: \"'writes.intel.f'\" unpacked with wrong size! fi # end of 'writes.intel.f' fi echo shar: End of shell archive. exit 0