J1BIH \w fflSBSm \mmfim IIHHBHliBH SnnieHraHS^i HHH ;i nma\ VHRH BBgfflH MaatnB ImSBatiim IHlilllsilll MBBflfflHRmBmffffifufflmBfifl LIBRARY OF THE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 5IO. 84 UQ>r no.?03 -70fe Cop. % Digitized by the Internet Archive in 2013 http://archive.org/details/eigenvalueproble703maci Report No. UIUCDCS-R-75-703 NSF - OCA - GJ-328 - 000003 THE EIGENVALUE PROBLEM IN THE OL/2 LANGUAGE by Ricardo Macias Carrasco May 1975 JH.£ LIBRARY 0,- ", , . MAY 71975 L'M!VFR~ r ' c DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN URBANA, ILLINOIS V Report No. UIUCDCS-R-75-703 THE EIGENVALUE PROBLEM IN THE OL/2 LANGUAGE* by Ricardo Macias Carrasco May 1975 Department of Computer Science University of Illinois at Urbana-Champaign Urbana, Illinois 61801 * This work was supported in part by the National Science Foundation under Grant No. US NSF-GJ-328 and was submitted in partial fulfillment of the requirements for the degree of Master of Science in Computer Science, May 1975. I I I ACKNOWLEDGMENT I wish to thank Professor J. R. Phillips, creator of OL/2, for suggesting this topic and for his helpful suggestions and guidance I would also like to thank D. R. Jurich, member of the OL/2 team who contributed to the effort, and the University of Illinois at Urbana- Champaign for the support it has provided. TABLE OF CONTENTS Page 1 . I NTRODUCT I ON 1 1.1 General Features 1 1.2 Earlier Work 2 2 . ARRAY STRUCTURES k 2. 1 Data Types h 2.2 Array Control Blocks 5 2.3 Partitioning and Array Expressions 7 3. THE EIGENVALUE PROBLEM 11 3 . 1 Def i n i t i on 11 3.2 Algorithm Selection and Control 12 k. THE EIGENVALUE PROBLEM IN OL/2 16 *t.l Eigenvalue Statement 16 h . 2 TACOS 18 ^.3 Compilation of the Eigenvalue Statement 19 k.k Code Generation 21 REFERENCES 25 APPENDIX A. OL/2 SYNTAX FOR THE EIGENVALUE STATEMENT 26 B. SEMANTIC ACTION ROUTINES 27 C. RUN TIME ROUTINES FOR EIGENVALUE STATEMENT 31 D. EXAMPLE OF EIGENVALUE STATEMENTS 36 1. INTRODUCTION OL/2 (Operator Language/Version 2) [k] has been specifically designed to write array algorithms in a natural and efficient way. It adheres to the common mathematical language and is therefore ideal for solving problems in linear algebra. This thesis is concerned with the implementation in the OL/2 language of the well-known eigenvalue problem. The eigenvalue problem consists of finding the nontrivial solutions of Av = \v (1) where A is a matrix of order n, v is a vector of order n, and \ is a sea lar. The problem, as stated, has a number of ramifications which require careful consideration. We will treat the problem with the objective of providing the framework for a very high level language implementation in the context of the OL/2 language. 1.1 General Features The general eigenvalue problem gives rise to a number of "sub-problems". For example, in (l) a user may require the computation of all eigenvectors and eigenvalues (v., A.} 1 <_ i <_ n , only the eigenvalues {A.} 1 <^ i _< n, or only a particular subset of these. Therefore, in this implementation we seek to provide a set of OL/2 statements that allows the various possibilities to be computed by specifying only what has to be computed without specifying how it is computed. The question of how to compute, that is, how to choose the algorithms, is determined entirely within the eigensystem module which is part of the OL/2 implementation. In these statements we have taken advantage of the facilities that the OL/2 language provides to write array expressions and to reference arrays. For example, if the user wants to compute the set of eigenvalues {A.} 1 < i <_ n, of a given matrix A, he would write the following OL/2 statement EIGENVALUES A -*■ V; where V i s a one-dimensional array that will contain the eigenvalues of A. Similar statements are provided for other possible cases. As far as the implementation of the general eigenvalue problem (1) is concerned, we will restrict ourselves to a real matrix and complex V and A. In sections 2, 3 and k we will discuss how the problem is solved in general and how it relates to the current implementation in OL/2. 1 .2 Ear 1 ier Work Some work has been done in this area but with a traditional approach. The most important is the subroutine package EISPACK [8] that uses a more primitive approach. The difference is that the user has to know for example the details that involve each particular problem. For example, if he wishes to get the solutions for (1) he must provide additional JCL statements, and be able to write a call statement involving the exact description of the type of computation he is requesting together with the different operands involved. For example, to get the solution {A.} I < i < n of (l) in a FORTRAN program, he has to include the statement CALL EISPACK(NM, N, MATRIX ('REAL', AR) , VALUES (WR, Wl)) where NM and N specify dimensions for the previously defined arrays AR, WR and Wl. In OL/2 we free the users of these details and provide greater flexibility in solving this problem by including a number of features that will be discussed in the next sections. 2. ARRAY STRUCTURES 2. 1 Data Types Before we consider the eigenvalue problem, it is necessary to give an explanation of the different data types which are available in OL/2, together with the information structures that control the use and access of these data types. The language provides for the declaration of scalars, various types of arrays, vector spaces, and sequences of arrays. In this thesis we denote arrays, usually matrices, by capital letters A, B, C, vectors by small letters x, y, z, and scalars by Greek letters a $ Y • Consider a matrix A with elements a. . 1 < i, j < n. Table I ■ iJ ~ ~ lists the different geometric shapes that are defined in OL/2. By definition, if the geometric shape is not specified in a declaration, then it is assumed to be a square matrix. Table I. Basic Data Types for Square 2-D?mensiona 1 Arrays Geometric Shape of A Abbreviation Stored Elements Strictly Lower Triangular SLT 1 1 j < i < n Lower Triangular LT 1 1 j < i < n Diagonal D 1 < i = j < n Strictly Upper Triangular SUT 1 < i < j < n Upper Triangular UT 1 < i < j < n Tridiagonal T 1 1 i-j 1 < 1 l£i,j£n Square S < i < n 1 < j < n Rectangular R < i < m 1 <_ j < n Some typical declarations are the following: LET T BE A TRIDIAGONAL MATRIX OF ORDER (N) ; LET X AND Y BE VECTORS OF ORDER (M) ; LET S BE A SCALAR; LET L l_K_l BE A SEQUENCE MOD (K) OF LOWER TRIANGULAR MATRICES OF ORDER (N) . For further details of the OL/2 language and its use, see [4, 6] 2.2. Array Control Blocks In this section we describe the internal control structure associated with the various types of arrays [1, 7]. All arrays in OL/2 are described at execution time by an array control block (ACB) which is used to pass information to the various computational routines and to control the partition data structure. For every array explicitly delcared^ an ACB is allocated and all the references to this array are through this block. Figure 1 shows the structure of the ACB and the various fields are described as follows: #NAME The name of the array as actually defined. This field is present in the ACB for diagnostic purposes #ATTRIBUTES The arithmetic attributes of the data stored in the array. #DIM The number of dimensions of the array. #M0D Used to specify sequences of arrays. #TYPE The geometric shape as described in section 2.1. #ROW-INCR ^ Constants related to #TYPE which are used by the #D I AG- I NCR J computational routines. ^LENGTH $0RIGIN The number of elements of the array. A pointer to the actual storage location of the first element of the array. #PARTITION-PTR A pointer to the Partition Control Block (PCB) described in [1 7] . //EXTENT #L0WER #UPPER The extent, lower bound, and upper bound respectively for one array. There is one triple for each dimension up to the number of dimensions specified in #DIM. ACB pointer First element <- of array #DIM #R0W-INCR #EXTENT(1) #EXTENT(2) #EXTENT(8) #NAME //ATTRIBUTES #M0D #DIAG-INCR $ ORIGIN $ PARTITION-PTR #L0WER(1) #L0WER(2) #L0WER(8) #TYPE //LENGTH //UPPER(l) #UPPER(2) #UPPER(8) -> PCB Figure 1 . Array Control Block It has to be pointed out that all data types are stored as linear arrays and are accessed at any time by means of $0RI GIN, #D IAG- INCR and #R0W-INCR variables in the ACB. For further explanation of how this is accomplished, refer to [5, 7] . 2. 3 Partitioning and Array Expressions Together with the concept of geometric shape for an array is the concept of partitioning an array. This is implemented in the language and is used to separate an array into subarrays by defining partition lines between specified rows and columns of the array. This allows a user to reference subarrays as independent arrays. The OL/2 language provides for a very general and dynamic partitioning of any type of array. This capability of the language among other things allows us to rename arrays without actually allocating storage for them. To illustrate this, we consider a typical example of a partition statement and associated LET and SET statement. LET A BE A MATRIX OF ORDER (7); PARTITION A AFTER ROW 3 AND COLUMN 2; SET B = A < 2,1 >, C = A < 2,2 >; It should be clear from these statements that the usual idea of partitioning is easily described by a user. The convention of using A < 2,1 > for the subarray A_. is simply a matter of convenience. The partitioned array is shown below. It is important to realize that we can rename part of an array and treat it independently and not allocate storage for it. In [7] partitioning is explained in detail and includes the dynamic aspects where the position lines may be moved over the parent array A in a nearly arbitrary manner. The different data types and the arrays resulting from partitioning, together with the arithmetic operators +, *, /, ' (transpose) and PL/1 functions, are used to form OL/2 arithmetic array expressions. Table II outlines the types and operators that may be used to construct expressions. At this point it is necessary to remark that OL/2 treats column and row vectors as degenerate arrays. In [3] the compilation of OL/2 arithmetic expressions is explained in detail. Our main concern as far as these expressions are concerned is the possible legal expressions that can be formulated, and these are of course any combination of data types and operators in infix form that do not violate the conventional rules of linear algebra, namely multiplication, division and addition between scalars, vectors and matrices. in c O o z •— < 4-J a: cm nj LU u a. 0) o Q. O CM < X i_ o 1- O a> _J 4-J > ZD o CO a) c UJ > E >« a: 3 03 2 .— s_ O o L. u, o ID o z < a: — LO Q. o ID O CM CO -J >- O CO o I X - CO. + 3 X < •a 3 CO ;>- CJ i II II • 03 03 03 OJ •— »— ^— U 03 0} 03 1_ O U O ro in t/> (/) i_ J_ O o 4-> 4-> u o u OJ 0) TO > > >- 03 >- 03 nj p— s L. U o o o L. u >■ ■M 03 0J O U »- 0) J- J- > O 10 1_ (U >- — 0J oj i- (/) 0J o o 4-> +J o o OJ oj > > o o u o 4-» 4-» u o 1_ 0) a) 0J > 03 >• 0J > nj ^ u L. 5 o o u L. O t/i u «u 03 L. l_ u L. 03 03 >» (D >* r— 03 ^ 0J 03 (0 l_ 0J 1_ O o L. U L. in in 0J W 0) !_ 1_ L. 1_ 1_ o o o o o 4-J 4-> 4-> 4-< 4-1 4-> o o o o o o d) 0) (U OJ »- X !_ OJ 0) 1_ l_ > > >- >- > > o — 0J >^ > > > o >^ >- (0 >- 03 03 4-> 1_ ^ 03 0) 4-1 03 03 •— 03 - 5 L. l_ F*» «— O -M 0) 1_ 3 L. 1— o V- u 03 l_ o o I_ 1_ o o 0J 03 o 1_ o L. o 0) u u O 1_ U l- 03 03 o o > E in 0J !_ 03 o > (D 0) W 03 0) in O -C Q. o IA 03 C 4-> c 4-J 03 u o o O 1_ U 1_ 3 D >« •— 3 03 u 4-> o TJ XI in 0J 4-1 TO t— 0J <4- >> o O in c \m 03 O 03 ^ >~ 03 i_ 1_ E O r— Li O i_ U 0J l_ 03 C l_ Q. Q. u u •— o 03 •— Q. in o 03 >^ l_ o 1_ o O 4-> o 5 .— in ^— • OJ L »— 03 !_ U 4-1 c 03 O _ 03 C c c OJ X OJ OJ E 4-> 4-> E OJ i/> OJ ]_ D> •— c c > •^ Q. E I_ ■^ 3 E E o d) c 4-J " — "" t/> L. 4-> O 4-J O 4-1 3 E o 4-» 4-> 3 in I 4- u c l_ u 3 05 u l_ !_ L. L. L. o >~ OJ o o o E 03 >- o o >- o o >« >• OJ >- 4-* l_ E 4-> 4-* • ^ 9— 03 4-1 4-1 03 4-J *J 0J 0J *— OJ o 0J 0) O o l_ T3 D a) > > > 0J in 03 > > 03 > > 03 (D in 03 i + 10 The following are examples of OL/2 array expressions A = Z * Z 1 B ■ a JL A .;. X X " 3 A A * z a a (x,< f) i< y With these concepts, we may now proceed to the main topic of this thesis, namely, the eigenvalue problem and how we can control the computation of the eigenvalues and eigenvectors within the context of the OL/2 language. 11 3. THE EIGENVALUE PROBLEM 3. 1 Def ini t ion The general eigenvalue problem can be stated as follows: Let V be a vector space over a field F. Given an integer n and an n by n matrix A, find those scalars X. e F and vectors v. e V i i such that A v. = A. v. i i i 1 < i < n (1) This is one of the most important problems in computational linear algebra, and is of practical as well as theoretical interest. We recall that the problem as defined has as a solution a set of n scalars X. and associated vectors v. for 1 < i < n. In i i — — practice, however, users may be interested in computing: i i IV all the eigenvalues and eigenvectors of A. the eigenvalues of A only. the k smallest (or k largest) eigenvalues of A. the eigenvalues of A in an interval (a, $) . the eigenvalues and eigenvectors of A in an interval (a, 8) The solution to the problem of how to choose the appropriate algorithm for each case of these cases depends largely on the charac- teristics of the matrix A. We will discuss this in the next section. 12 3.2 Algorithm Selection and Control The solution of the problem of choosing appropriate algorithms is mainly determined by the symmetry and sparseness of the matrix A. A may be symmetric or unsymmetric. In the former case we will be able to solve the five problems as stated above, while in the latter we will be more restricted. A may also be dense or sparse (band matrix). Since the present implementation of OL/2 does not allow complex, band, or randomly sparse matrices, we will be concerned only with the case in which F is the field of real numbers and A is a dense unsymmetric or symmetric matrix. This does not mean that we cannot store a band or sparse matrix in a square array, but means that the algorithms selected will not be the adequate ones. Tridiagonal matrices are optimally stored. The five cases labeled (i) through (v) above will be denoted below by the value of CASE, namely, 1, 2, 3, k or 5, respectively. The following flow diagram shows the way in which the problem is organized. II III REDUCE A TO UPPER HESSENBERG FORM YES I REDUCE A TO SYMMETRIC TRIDIAGONAL FORM, ACCORDING TO CASE SE1ECT ALGORITHM ACCORDING TO CASE EXECUTE IT E means in the above diagram that the state-of-the-art does not solve the problem satisfactorily for those cases. 13 Next we will explain how operations are performed in the boxes labeled I, II and III respectively. All routines which are referenced belong to the EISPAC subroutine package [8]. CASE=2 CASE=1 or CASE=5 YES > — * TRED 2 !MTQL2 CASE=2 or CASE=3 or CASE=9 CASE=5 TSTURM > TRBAKI TRED 1 CASE=2 > IMTQL 1 RATQR CASE=jt BISECT 2, Figure 2. Path I, III ORTHES CASE=1 CASE=2 ORTRAN HQR HQR 2 ORTBAK Figure 3- Path II, III \k Next, we list the EISPACK routines mentioned in Figs. 2 and 3 and reference their computational characteristics. BISECT: Determines those eigenvalues of a symmetric tridiagonal matrix in a specified interval using Sturm sequencing. HQR: Determines the eigenvalues of a real upper Hessenberg matrix using the QR method. HQR2: Determines the eigenvalues and eigenvectors of a real upper Hessenberg matrix using the QR method. IMTQL1: Determines the eigenvalues of a symmetric tridiagonal matrix using the implicit QL method. IMTQL2: Determines the eigenvalues and eigenvectors of a symmetric tridiagonal matrix. It uses the implicit QL method to compute the eigenvalues and accumulates the QL transformations to compute the eigenvectors. ORTBAK: Backtransforms the eigenvectors of a real general matrix from the eigenvectors of that upper Hessenberg matrix determined by ORTHES. ORTHES: Reduces a real general matrix to upper Hessenberg form using orthogonal transformations. ORTRAN: Accumulates the transformations in the reduction of a real general matrix by ORTHES. RATQR: Determines the algebraically smallest or largest eigenvalues of a symmetric tridiagonal matrix using the rational QR method with Newton corrections. TRBAK1 : Forms the eigenvectors of a real symmetric matrix from the eigenvectors of that symmetric matrix determined by TRED1. TRED1 : Reduces a real symmetric matrix to a symmetric tridiagonal matrix using orthogonal similarity transformations. TRED2: Reduces a real symmetric matrix to a symmetric tridiagonal matrix using and accumulating orthogonal similarity transformations. TSTURM: Determines those eigenvalues of a symmetric tridiagonal matrix in a specified interval and their corresponding eigenvectors, using Sturm sequencing and inverse iteration The reader may refer to [9] which gives the mathematical details about these routines or to [8] for a more detailed explanation. So far we have seen the general framework that can be used to solve the eigenvalue problem. We now proceed to discuss the implementation of this problem in OL/2 using the very high level characteristics of the language. 16 4. THE EIGENVALUE PROBLEM IN OL/2 k. 1 Eigenvalue Statement In this section we will describe the implementation of the eigenvalue problem in the current version of the OL/2 language. As was mentioned earlier, given an array A, the main interest is in comput ing : (?) eigenvalues and eigenvectors (i i ) eigenva lues (iii) extreme (smallest or largest) eigenvalues (iv) eigenvalues in an interval (v) eigenvalues and eigenvectors in an interval The corresponding OL/2 statements for each one of these cases are described next. (?') EIGENSYSTEM A - U, V, B; (??') EIGENVALUES A -» U, V; (iii 1 ) EIGENVALUES A SMALLEST k - U ; EIGENVALUES A LARGEST k - U ; (iv 1 ) EIGENVALUES A IN {a, B) -U; (v 1 ) EIGENSYSTEM A IN ( U, B; We will see how to interpret one of these OL/2 statements, say (i 1 ), the others being interpreted in an analagous way. For statement (i), recall that the matrix A can be symmetric or unsymmetric. In the former case we will have real eigenvalues and in the latter a mixture of real and complex eigenvalues. Therefore, for a 17 matrix of order n, we will expect n eigenvalues and eigenvectors, and we interpret (i') as: compute the eigenvalues and eigenvectors of the matrix A; for the eigenva lues, place the real parts in vector U, imaginary parts in vector V, and place the eigenvectors in the array B. Of course, if we know in advance that A is symmetric, then (i 1 ) reduces to EIGENVALUES A - U, B; The only restriction here is that U and V have to be declared as vectors of order n and B as a matrix of order n. The same reasoning applies to the other statements. Because of the different geometric shapes allowed in the OL/2 language, the partitioning capabilities, and the ease of forming array expressions, we have a very general capability within the eigenvalue statements : a) A may be any OL/2 array expression or part of an array. b) U,V,B may be OL/2 arrays or part of some array (subarray) . c) Ck',P,k may be any OL/2 scalar expression. It can be seen that these facilities allow for a variety of eigenvalue computations, and simultaneously free the user of all details that arise with those computations. The following is an example of part of an OL/2 program that involves eigenvalue statements: LET A AND B BE MATRICES OF ORDER (7), S BE A SCALAR, U AND V BE VECTORS OF ORDER (7), AND W BE A VECTOR OF ORDER (2) ; INPUT A, S; PARTITION A AND B AFTER ROW 1 AND COLUMN 1 ; SET L TO THE LOWER TRIANGULAR PART OF A; 18 EIGENSYSTEM L - U, B; OUTPUT U, B; PARTITION U AND V AFTER ROW 1 ; EIGENVALUES A < 2,1 > * A < 1 ,2 > - U < 2 >, V < 2 >, B < 2,2 >; OUTPUT U<2>, V<1>, B<2,2>; EIGENVALUES L SMALLEST 2*S -• W; OUTPUT W; The rest of this section will be devoted to explain the compilation of the eigenvalue statement. k.2 TACOS The compiler for OL/2 is generated by a general translator writing system called TACOS [2]. TACOS is capable of taking as input the syntax and the semantics of a language and constructing a linked list completely specifying them. A fixed interpretative parser which performs a top-down parse according to the contents of the list makes the compiler complete. The syntax is specified in IBNF (Informal Backus Normal Form) similar to BNF. The differences between IBNF and BNF are the following: (?) Use of parenthetical expressions which considerably reduce the number of phrase classes, (i?) Three different repetition characters are defined to allow the phrase class interpretations given in Table III. (iii) Specification of identifiers as intrinsic terminal symbols to the compiler. The terminal phrase class < »I > causes a routine to attempt the identification of an identifier, instead of the letter by letter parsing. 19 A set of terminal phrase classes is defined which cause semantic action routines to be invoked at various points during execution time to speed the compilation process. < #15 > for example will invoke semantic action routine #15 whenever this action need to be taken at compile time, This introduction is enough to interpret the IBNF system of the EIGENVALUE statement as given in Appendix A. For further details on TACOS, the reader may see reference [2]. Table III. IBNF Repetition Symbols Repetition Number of IBNF BNF Character Occurrences Example Interpretation > 1 : := + >_ : := « or 1 : := ? = | = | = | ^.3 Compilation of the Eigenvalue Statement From now on the reader may reference Appendices A and B that show the syntax and associated semantics for the eigenvalue statement. It will also be helpful to reference the examples shown in Appendix D. We will discuss the implementation of an eigenvalue statement, with the implementation of the others being accomplished in a similar fash ion, Consider the following OL/2 statement: EIGENVALUES a*A*B SMALLEST 3*Y + W; 20 After the recognition of the keywords EIGENVALUES, some flags and counters are set. The parser continues scanning looking for identifiers or array expressions. For identifiers, syntactic and semantic analyis is performed. The array expression process is divided into three phases. First, the syntactic and semantic analysis of the expression, which transforms the source code into an expression tree. Second, this tree is modified in order to allow an optimized coding by the third pass. Last, the coding routine transforms this optimized tree code representation into a sequential list of three operand code (operand, operand, result). Reference [3] is a detailed treatment of this subject. The information extracted then consists of the pointer to the ACB of either the identifier or what will be the result at execution time of the array expression together with the following: 1) A negate flag which indicates whether or not the result of the expression has to be negated. 2) A transpose flag which indicates whether or not the result of the expression has to be transposed. 3) A storage flag which indicates if the space actually occupied by the result of the expression is temporary or not. Note that for array expressions this bit is always set to false in contrast with the bit associated to identifiers, which is always set to true. k) A modulus number which indicates whether the expression or identifier is a member of a sequence of arrays. 21 After having recognized these elements successfully, the parser will continue scanning looking for either "-*■" or the keywords "SMALLEST", "LARGEST" or "IN". After the recognition of the keyword SMALLEST, some flags are set and a process similar to the one described above for OL/2 arithmetic expressions will handle the OL/2 scalar expression. After the recognition of the "->■", the parser will look for any OL/2 identifiers that can appear on the right side (up to three), check for syntax and semantic errors, and extract information similar to that extracted for the OL/2 array expression, i.e., a set of pointers to ACB, negate, transpose, storage flags, and modulus number. The code generated is described in the next section. It is clear that because of the fact that arbitrary array and scalar expressions or identifiers are imbedded in the statement, very little error checking can be done at compile time, so through the different ACB pointers, the rest of the error checking is done at run time. Appendix C contains the run time routines which accomplished this. k.k Code Generation The code generated for the EIGENVALUE statement is in all cases a call to the @E I GEN routine. As was explained before, the information passed to this routine is summarized below. i) ACB information for the array expressions or array or subarray references, in the form of pointers. These are of the form $XYZ or $TEMPXY. The former stands for a declared ACB pointer variable for the OL/2 array identifier Y declared by the programmer in block number Z and block 22 level X. The latter stands for a temporary ACB pointer f h variable for the Y temporary variable whose array dimension is X. Together with this go the negate, transpose, storage and modulus flags. ii) Specific case number (one to five). iii) For case three a flag indicating either SMALLEST or LARGEST and the scalar associated with the request. iv) For cases four and five interval bounds. Once generated, and referring to the program given in section 4.1, the PL/I call statements look as follows: / * EIGENSYSTEM L •> U, W; * I CALL @EIGEN (TB, 'O'B, 'O'B, 0, $IU, 2, 'O'B, 0, 0.0, 0.0, 'l'B, 'O'B, 'O'B, 0, $1UI, 'TB, 'O'B, 0.B, 0, $IWI, 'O'B, 'O'B, 'O'B, 0, $0LNULL); / * EIGENVALUES A<2,1> * A<1 ,2> ■* U<2>, V<2>, W<2,2>; * / CALL @0L0M0 (TB, 'O'B, 'O'B, 0, @0L2_L0CATE-SUBARRAY($1A1 , 2, 1), 'l'B, 'O'B, 'O'B, 0, @0L2_L0CATE_SUBARRAY($1A1, 1,2), 'l'B, 'O'B, 'O'B, 0, $TEMP2_1); CALL @EIGEN ('O'B, !0'B, 'O'B, 0, $TEMP2_1 , 1, 'O'B, 0, 0.0, 0.0, 'l'B, 'O'B, ;0;B, 0, @0L2_L0CATE-SUBARRAY $IUI,2,0 'l'B, 'O'B, 'O'B, 0, @0L2_L0CATE_SUBARRAY($IVI, 2,0), 'l'B, 'O'B, 'O'B, 0, @0L2_L0CATE-SUBARRAY($IWI, 2, 2); 23 / * EIGENVALUES L SMALLEST 2*S -> Z; * / CALL @EIGEN ('I'B, 'O'B, 'O'B, 0, $ILI, 3, 'O'B, (2*S) , 0.0, 0.0, 'l'B, 'O'B, 'O'B, 0, $LZL, 'O'B, 'O'B, 'O'B, 0, $OLNULL, 'O'B, 'O'B, 'O'B, 0, $OLNULL) ; At run time the rest of the error checking is performed by this routine through the ACB's pointers. This error checking mainly consists of detecting any discrepancies between the shape of the source array, the associated request (case number, the associated scalars, interval bounds), and the characteristics of the target arrays. Once free of errors, we perform a copy operation, which is fast and efficient, and pass control to the computational routines. Once the computation is finished hopefully without interruption, a copy operation must be performed from the elements containing the result into the target arrays. The results so obtained can be used in other parts of the OL/2 program and can also be referenced or operated on in arbitrary manner. This completes the processing of the EIGENVALUE statement. DISCUSSION The different eigenvalue problems can be solved with the very- high level language facilities provided by OL/2. The user can combine the partitioning and easy formulation of array expressions capabilities of the language with these statements. This has been accomplished for the mode (real) now available for the different OL/2 types. Once the 2k complex mode is implemented, new additions can be made to enhance the power and generality. The idea has been to take advantage of the existing subroutine packages (EISPACK) to provide by means of the specific language OL/2, a framework for the easy and elegant solution of the eigenvalue problem. It should be clear that the same concept can be applied to other collections of subroutines with great benefit to users who are primarily interested in using well defined, high quality, mathematical software. 25 REFERENCES [1] H. C. Adams II, Dynamic Partitioning in the Array Language OL/2. M.S. Thesis, University of Illinois at Urbana-Champaign, Department of Computer Science Report No. ^21, January 1971. [2] J. L. Gaffney Jr., "TACOS: A Table Driven Compiler-Compiler System", M.S. Thesis, University of Illinois at Urbana-Champaign, Department of Computer Science Report No. 352, June 1969 . [3] D. R. Jurich, An Approach to the Compilation of Array Expressions in the OL/2 Language. M.S. Thesis, University of Illinois at Urbana-Champaign, Department of Computer Science Report No. 550, September 1972. [k] J. R. Phillips, The Structure and Design Philosophy of OL/2 - An Array Language - Part I: Language Overview. University of Illinois at Urbana-Champaign, Department of Computer Science Report No. 5^^, October 1972. [5] J. R. Phillips, The Structure and Design Philosophy of OL/2 - An Array Language - Part II: Algorithms for Dynamic Partitioning. University of Illinois at Urbana-Champaign, Department of Computer Science Report No. ^20, September 1971. [6] J. R. Phillips, OL/2 User Guide. University of Illinois at Urbana-Champaign, Department of Computer Science (to appear). [7] J. R. Phillips and H. C. Adams, Dynamic Partitioning for Array Languages, CACM, December 1972. [8] B. T. Smith, J. M. Boyle, B. S. Garbow, Y. Ikebe, V. Klema, and C. Moler, Matrix Eigensystem Routines - EISPACK Guide. Springer-Ver lag , 197^. [9] J. H. Wilkinson and C. Reinsch, Linear Algebra, Spr inger-Verlag, 1971. 26 APPENDIX A CL/2 SYNTAX FOR THE EIGENVALUE STATEMENT < FOR THE COMPLETE SYNTAX OF OL/2 SEE REFERENCES 1 AND * I ::= {{.EIGENVALUES. <#254> <«250> I .E IGENSYSTEM. <#25*>) <¥251> { •->• I | ) •->• I <#252> { ',* <*259> | <*260> )♦ I <*253> •;• ; :: = <¥163> <*2A3> ; ::= (.SMALLEST. <4255> \ .LARGEST.) <*256> <#257> ; :: = .IN. <¥258> •{• { »,• <*259> | <#260> )♦ •)• ; ::= <*2<»4> ; ::= <¥163> <#246> ; ::= <#163> <#246> ; 27 APPENDIX B SEMANTIC ACTION ROUTINES /** ***** *** ********** ******* **** ************* **** A**********/ /* */ /* */ /* SEMANTIC ACTION ROUTINES 250 TO 260 USED FOR THE */ /* EIGENVALUE STATEMENT, THERE ARE FIVE PGSSI8LE CASES. */ /* DENOTES ANY 0L2 ARITHMETIC EXPRESSION OR */ /* IDENTIFIER. */ /* */ /* */ /* 1) EIGENVALUES */ /* 2) EIGENSYSTEM */ /* 3) EIGENVALUES LARGEST I SMALLEST K */ /* 4) EIGENVALUES IN IN HAS BEEN SUCCESSFULLY PARSED. THE COOE GENERATED INCLUDES TRANSPOSE, NEGATE AND TEMPORARY STORAGE FLAGS AND MODULUS NUMBER AS WELL AS A POINTER TO THE ATTACHED ACB FOR */ */ */ */ */ */ */ */ */ /***********************************************************/ ACTICN_25l: OUTPUT.BUFFER^'CALL 5)EIGEN(» || TEMPSTRING; NAMES_USED(-25)=YES; GO TO RETUPN_TO_PARSER; /***********************************************************/ /* */ /* */ /* SEMANTIC ACTION ROUTINE 252 IS ENTERED WHEN RIGHT HAND */ /* SIDE OF EIGENVALUE STATEMENT IS GOING TO BE PROCESSED. V /* CODE GENERATED CONVEYS INFORMATION ABOUT THE CASE */ /* RECOGNIZED AND ASSOCIATED PARAMETERS. */ /* */ /* */ /***«*******************************************************/ ACTION.252: IF -SYMT THEN DO; IF EV THEN REQUESTS ,l«j ELSE REOUEST=», 2« ; REOUEST=REQUEST II ■ , • • 0« • B, 0, 0.0, 0.0* ; END; CTR,CTR1=0; LMT=3; 0UTPUT_BUFFER=OUTPUT_BUFFER II REQUEST; GO TO RETURN_TO_PARSER; /*******i>:**** ****************************************** *****/ /* /* /* /* /* /* /* SEMANTIC ACTICN ROUTINE 253 IS ENTERED AFTER THE RECOGNITION OF THE STATEMENT TERMINATOR. IT COMPLETES THE CODE GENERATION. */ */ */ */ */ */ */ /***********************************************************/ ACTICN.253: DO 1=1 TO 3-CTR; OUTPUT_PUFFER=OUTPUT_BUFFER I I •, ,, ,, 8, ,, ,, B,'«0 ,, B, , $OLNULL«; END; 0UTPUT_3UFFER=0UTPUT_BUFFER II •);' ; CALL SKIP_ANO_OUTPUT; GO TO RETURN_TO_PARSER; /***********************************************************/ /* /* /* /* /* /* /* SEMANTIC ACTION ROUTINE 254 IS ENTERED AFTER THE RECOGNITION OF AN EIGENVALUE STATEMENT. SOME FLAGS AND COUNTERS ARE RESET */ */ */ */ ♦/ */ */ /***********************************************************/ 29 ACTICN_254: EV, SZE , SYMT*' 0' 8; REQUEST*"; ' i CTR,CTRI,LMT=0; GO TO return_to_parser; /***********************************************************/ /* */ /* ♦/ /* SEMANTIC ACTION ROUTINE 255 IS ENTERED AFTER THE */ /* RECOGNITION OF THE KEYWORD SMALLEST. A FLAG IS SET */ /* */ /* */ /***** *********** ******************************** ***********/ ACTI LMT THEN CALL ¥ERR0R(7l); REQUEST=REQUEST II •,' II TEMPSTRING; GO TO RETURN_TO_PARSER; 31 APPENDIX C RUN TIME ROUTINES FOR EIGENVALUE STATEMENT /* *** ********** **************************** ******************** ********/ /* */ /* */ /* SUBROUTINE 3EIGEN DOES THE ERROR CHECKING AT RUN TIME */ /* THE RESTRICTIONS THAT APPLY ARE: */ /* THE SOURCE ARRAY MUST BE ONE OF THE TYPES SYMMETRIC, SQUARE */ /* LOWER TRIANGULAR, UPPER TRIANGULAR OR TRIOIAGONAL */ /* IF THE ORDER OF THE SOURCE MATRIX IS N THEN J */ /* FOR CASE 1 THE ORDER OF THE TARGET VECTORS MUST BE N */ /* FOR CASE 2 THE ORDER OF THE TARGET VECTORS MUST BE N, AND */ /* THE TARGET MATRIX MUST RE SQUARE OF ORDER N */ /* FOP CASE 3 THE ORDER CF THE TARGET VECTOR MUST BE EQUAL TOTHE */ /*_. NUMBER OF EXTREME EIGENVALUES TO BE COMPUTED */ /* FOR CASE 4 THE ORDER OF THE TARGET VECTOR MUST BE N */ /* FOR CASE 5 THE ORDER OF THE TARGET VECTOR MUST BE N, AND THE */ /* TARGET MATRIX MUST SE SQURE OF ORDER N : _ */ /* */ 7* BFSIDES THIS ERROR CHECKING, SUBROUTINE 3EIGEN ALLOCATES */ /* STORAGE FOR THE ARRAYS ON WHICH EISPAC ROUTINES OPERATE ON */ /* ANO CALLS THEM TOGETHER WITH THE COPY ROUTINES */ /* */ /* */ /******************** *******$ ********************************** ********/ 3EIGEN: PPOCEDURE(SVO,NGQ,TRO,MODO,$PTRi,REQUEST,FLAG,NUM, LB,U8,SV1,NG1,TRL,M0D1,$PTR2,SV2,NG2,TR2,M0D2, $PTR3,SV3,NG3,TR3,M0D3,$PTR4); DCL ($PTR1,$PTR2,$PTR3,$PTR4) POINTER, "PTR POINTER STATIC, (NUM, REQUEST, MODO , tfOI M, MODI v MOD2, MGD3 > FIXED 8IN(15,0) t ALIGNEO, 2 "NAME CHAR124) , 2 "ATTRIBUTES, (3 "DEFINED, 3 "STORAGE, 3 4TEMP_VARIA8LE, 3 "PASE, 3 "SCALE, 3 "MODE) BIT(l)i 3 "PRECISION FIXED BIN(15,0), 2 "LENGTH FIXED 3IN(31,0), (2 "DIMENSIONALITY, 2 "MODULUS, 2 "TYPE, 2 #ROW_INCR, 2 «DIAG_INCR) FIXED BIN(15,0), (2 SCRIGIN, 2 $PARTITION_PTR) POINTER, 2 "BOUND.PAIR ( "DIM REFER ( "DIMENSIONALITY )), (3 "EXTENT, 3 #LOWER, 3 "UPPER) FIXED BIN(15 t 0); DCL HUH1 ENTRYIFLOAT 81 N I 53 ), FLOAT 81 N ( 53 ) ,F IXED BIN(15), FIXED BINI15) ); DCL TPN ENTRY(, FIXED BIN<15,0)); 32 /* DECLARATIONS FOR THE OPERATIONAL EISPAC ROUTINES */ DCL BISEC T ENTRYIFIXEO B IN( 1 5, ) , FLOAT BI N ( 53) , , , , FLOAT PIM153) , FLOAT BIN I 53 ), F I XED BIN( 15, ) , F IXEO BINU5,0), , ,FIXFD 8IN(15,0),, ) t HOP ENTRYIFIXED BIN( 15 ,0 1 , FIXED B IN ( 15 ,0 ) , F IXEO bIN( 15,0) , FIXED 3IN( 15,0),,, , FIXED BINI15,0))» H0R2 ENTRYIFIXED BIN ( 1 5 ,0 ) ,F I XEO BI N( 1 5,0) ,FI XED BIN( 15,01 t FIXED BIN ( 15,0) ,,,,, FIXED BINU5,0)), IMTQLl ENTRYIFIXED B I N( 1 5,0 ) , , , F iXtD BINU5,0)), IMTCL2 ENTRY(FIXED BIN! 15,0), FIXED BI N ( I 5, 0) , , , , FIXED BIN(15,0) ), PRTBAK ENTRYIFIXEO B IN ( 1 5, ) , FI XED BIN ( 15 , 0) , FIXED BIN( 15,0),,, FIXED BIN(15,0),), CRTHES ENTRYIFIXED B IN ( 15, ) , FI XED BIN ( 15 , ) , F IXED BIN( 15,0), FIXED BI N ( 15 ,0) , , ) , ORTPAN ENTRYIFIXED B IN ( 1 5, ) , FI XED BIN ( 15, ) , F IXEO BIN( 15,0), FIXED BI N { 15 ,0) , , , ) , RATOR ENTRY C EI XED 81. MI 15,0), FLOAT BINl 53) ,,,, FIXED BIN(15,0),,,,BIT(1),FIXED BIN! 15,0), FIXED BINt 15,0)), TRBAK1 ENTRYIFIXED B IN I 1 5 , ) , FIXED B I N ( 15,0) , , ,FI XED BIN( 15,0), ) , TRED1 ENTRYIFIXED BINl 15,01 , FIXEO B IN( 15,0 ),,,,) , TPED2 ENTRYIFIXED BI Nl 1 5 , ) , FIXED B IN ( 15,0 ),,,,) , TSTURM ENTRYIFIXED B I N( I 5, ) , FI XED BI N ( 15, ), FLOAT BINl 53) , ,,,FLOAT B IN I 53) , FLOAT BI Nt 53 ), FIXED BIM 15,0), FIXED BINl 15,0) ,, ,F IXED BINl 15,0) ,,, , ,,); DCL SPPSPEC ENTRYIPTR, FIXED BIN131)) RETURNS I PTR) ; DCL COPY ENTRYIBITU) ,3IT( 1) , FIXED B I Nl 1 5 , ) , PTR, PTR, FIXED BIN(15,0), FIXED BINU5,0I); DCL 30L2ICS ENTRYIFIXED BINl 15 ) , FI XED BINl 15)); DCL TESTSYM ENTRYlPTR) RETURNS I BIT 1 1 )) ; DCL (PASS, SHAPE, PARI INIT(1),PAR2 INITll),PAR3 INITli), PAR4 INIT(L) f PARS INITll),PAR6 INITll),PAR7 INIT(l), EXTll, EXT12,EXT21,EXT22,EXT31,EXT32,EXT41,EXT42, ZERO INITIO), CNE INIT(1),TWD IN ITl 2 ) , THREE INIT13), FOUR INITIO), FIVE INIT15),SIX I NIT I 6 ) , SEVEN INZTI7), TEN INITUO) , ELEVEN INITI 1 1 ) ,TYPE3 , TYPE4) FIXED BINU5,0),SYH BITll); «PTR=$PTRl; EXTll= « tfEXTENTU); EXT12= rfPTR ->¥EXTENT (2) ; «PTR=$PTR2; EXT21= «PTR -> ¥EXTENTll); EXT22= MPTR ->¥EXTENT (2) ; *PTP=$PTP3; EXT31= *P T R -> KEXTENTU); EXT32= *PTR ->*EXTENT<2) ; TYPE3= tfPTR -> (KTYPE; ¥PTR=$PTR4; EXT41= «PTR -> ¥EXTENTU); EXT42= *PTR ->*EXTENT(2) ; TYPE4= «PTR -> »TYPE; «PTR=$PTR1; SHAPE=$PTRl -> #TYPE; IF SHAPE -= ZERO THEN SYM=«1'8; ELSE SYM=«0»B; IF REQUEST=ONE | REQUEST=THREE I REQUEST=FOUR THEN PASS=15; ELSE PASS=16; IF EXTll < ZERO | EXT12 < ZERO | EXT21 < ZERO | EXT22 < ZERO THEN CALL 30L2ICS i 24 ,PASS ) ; IF EXTll ^= EXT12 THEN CALL 30L2IC S 124, PASS) ; IF SHAPE=THREE I SHAPE=FOUR I SHAPE=SIX THEN CALL 5PL2ICS124,PASS); IF SPTP1 -> «LENGTH <= ONE THEN CALL S0L2ICS 1 25, PASS ) ; IF SHAPF=FIVE THEN SYM=TESTSYM{ $PTRl ) ; 33 /* EIGENVALUES */ IF REOUEST=CNE THEN DO; IF EXTll -= EXT21 I EXT22 -.= ZERO THEN CALL 3CL2 ICS (26, PASS) ; IF $HAPE=ZERO I -.SYM THEN DO; IF EXT31 < ZERO | EXT32 < ZERO THEN CALL 3GL2ICS ( 27, PASS ) ; IF EXTll -.= EXT31 I EXT32 -.= ZERO THEN CALL 30L2 ICS (26, PASS > ; END; GO TC SKIP_REST; END; /* FIGENSYSTEM */ IF P.EOUEST = TWO THEN DO; IF EXTll -= EXT21 I EXT22 -= ZERO THEN CALL 30L2 ICS ( 26, PASS ) ; IF EXT31 < ZERC I EXT32 < ZERO THEN CALL 30L2ICS ( 27, PASS) ; IF SHAPE=ZERO | -.SYM THEN DO; IF EXTll -i= EXT31 I EXT32 -.=ZERO THEN CALL 3CL2ICS ( 26, PASS ) ; IF EXT41 < ZERO I EXT42 < ZERO THEN CALL 30L2ICS (27 , PASS) ; IF EXTll i= EXT41 I EXT42 -.= EXTll I TYPE4 -= ZERO THEN CALL 30L2ICSC 26, PASS ) ; END; ELSE DO; IF EXTll -*= EXT31 I EXT32 -= EXTll I TYPE3 -.= ZERO THEN CALL 30L2ICS < 26, PASS ) ; END; GO TO SKIP_REST; END; /* EXTREME EIGENV*LUES */ IF PEOUEST=THREE THEN DO; IF SHAPE=ZERO I -SYM THEN CALL 3CL2ICS ( 24, PASS ) ; IF NUM <= ZERO | NUM > EXTll THEN CALL 3GL2 ICS ( 28, PASS) ; IF EXT21-.= (NUM-ONE) I EXT22-»=Z6RO THEN CALL 30L2ICS ( 26, PASS) ; GO TO SKIP_REST; END; /* EIGENVALUES OR EIGENSYSTEM IN AN INTERVAL */ IF SHAPE=ZERO I -SYM THEN CALL 30L2ICS ( 24, PASS ) ; IF (UB-LBK = O.OEO THEN CALL 30L2ICS( 23, PASS) ; IF EXT22 -*= ZERO THEN CALL 30L2ICS (26, PASS ) ; IF REOUEST=FIVE THEN DO; IF EXT31 < ZERO | EXT32 < ZERO. THEN CALL 30L2ICS (27, PASS ) ; IF EXTll - = EXT31 | TYPE3 -= ZERO THEN CALL 30L2ICS ( 26 , PASS ) ; END; SKIP_REST: /* HERE TO ALLOCATE STORAGE, COPY AND EXECUTE */ EXT11=EXT11+0NE; IF SHAPE = ZERO | -.SYM THEN DO; BEGIN; DCL ( A( EXTll, EXT1 1 ), ORTtEXTl I), WR{ EXTll ),Z( PARI, PARI), WKEXT11)) FLOAT BIN(53),IERR FIXED BIN(15,0); IERR=ZERO; CALL COP Y(SVO,TRO,MODO,$PTRl,ADDR( A), SHAPE, ZERO); IF SHAPE = ZERO £ TRO THEN CALL TPN ( A, EXT 1 1 ) ; CALL ORTHES (EXTll, EXT 11, ONE, EXTll, A, ORT); IF REQUEST=CNE THEN DO; CALL HQR ( EXTll, EXTll, ONE, EXT 11, A, WR,WI,IERR); IF IERR-=ZERO THEN CALL 30L2 ICS ( 30, PASS ) ; END; ELSE DO; END; CALL ORTR AN (EXTll, EXTll, ONE, EXTll, A, ORT, Z); CALL HQR2(EXT11,EXT11,CNE,EXT11,A,WR,WI,Z,IERR); IF IERR-.= ZERO THEN CALL 30L2I CS ( 30 , PASS ) ; CALL 0RTBAK(EXT11,0NE,EXTU,A,0RT,EXT11,Z); CALL C0PY(SV3,TR3,M0D3,$PTR4,ADDR(Z), TEN,EXTU-ONE); 3^ IF NGO THEN DO; WR=-WP; WI»-WI| END: CALL COPY(SVl,TRl,MODl,«PTR2,ADOR(WR) ,TEN,ZERO)| CALL COP Y(SV2,TR2,M0D2,$PTR3,ADDR(WI), TEN, ZERO); END; return; end; /* SYMMETRIC MATRICES +/ BEGIN; DECLARE (A(PARl,PARl),D(EXTll),E(EXTll),E2tEXTll), ZIPA*2,PAR2),W(PAR3) , BD( PAR4) , RV1 ( PAR5I, PV2CPAR5) ,RV3(PAR5),RV4(PAR6),RV5IPAR6), RV6(PAR5) ) FLOAT BIN(53) ,IND(PAR7) FIXED BIN(15) f (IERR,APRX) FIXED BIN<15,0); IF SHAPE=FIVE THEN DO; CALL COPY PI 1 B,TRO,MODO,$PTRl,ADDR(D), SIX, ZERO); CALL COPY I SVO,TRO,MODO,$PTRl,ADDR(E), ELEVEN, ZERO); DO I=TWO TO EXT11-ONE; E2JI)=E(I)*E(I); END; END; ELSE DO; CALL COPY (SVO,TRO,MODO,$PTRl,ADOR( A) , SHAPE, ZEROI I IF REQUEST -* = TWO THEN CALL TREDHEXTll, EXT11,A,D,E,E2); ELSE CALL TRED21 EXT1 1, EXT1 L ,A,0,E,Z ) I END; ierr=zero; if request=one then do; call imtqlkextl1,d,e,ierr); if ierr-.= zero then call 30l2icsu0, passi j if ngo then d=-d; call copy (sv1,tr1, mod i,$ptr2,a0dr(d) , ten, zero); return; ENO; IF REQUEST=TWO THEN DO; IF SHAPE=FIVE THEN DO; DO 1=1 TO EXTll; Z( I, I ) = 1.0EO; END; END; CALL IMTQL2(EXT11,EXT11,D,E,Z,IERR); IF IERR-*=ZERO THEN CALL 30L2ICS (30, PASS ) ; IF SHAPE-.= FIVE THEN CALL TRBAK1 { EXT 11 , EXTll, A, E, EXTll, Z) ; IF NGO THEN D=-0; CALL C0PY(SV1,TRI,M0D1,$PTR2,ADDR(D),TEN,ZER0); CALL C0PY(SV2,TR2,M0D2,$PTR3,ADDR(Z) ,TEN, EXT11-1) ; RETURN; END; IF REQUEST=THREE THEN DO; CALL RATQRi EXTll, 1.0E-07,D,E,E2,NUH,W, IND,BD,FLAG,ZERO,IERR); IF IERR-»=ZERO THEN CALL 3QL2ICS(30,PASS ); IF NGO THEN W=-W; CALL C0PY(SV1,TRI,M0D1,$PTR2,ADDR(W) ,TEN,ZEROJ; RETURN; END; 35 IF REQUEST=FOUR THEN DO; APRX=ZERO; CALL 31 SECT (EXT 11 t 1 .OE-07 , D, E , F? ,LB ,UB, EXT11,APRX,W, IND, I ERR , RV4, RV5 ) ; IF IE*R-. = ZERO THEN CALL 30L2I CS ( 30, PASS ) ; IF APRX i= IEXT21+1) THEN CALL HUH1(LB,UB, APRX,EXTli); if ngo then w=»-w; call c0py(sv1,tr1,m0d1 , $ptr2 , addr ( w) ,ten, aprx-1 ) ; return; end; do; CALL TSTURM{EXTii,EXTll,1.0E-07,D,E,E2, LB,UB,EXTll,APRX,W,Z,IERR,RVl,RV2 t rv3,pv4,rv5,rv6); if ie*r-i=zero then call 30l2ics ( 30, p ass ) ; if ngo then w=-w; if shape-=five then call trbak1 ( ext1 i, extl1,a,e,aprx,z); if aprx -= (ext2h-1) then call huhklb, ub,ap^x,ext11}; call c opy ( sv1, tr i, modi, sptr2, ador (w), ten, aprx-1); call c0py(sv2,tr2,m0d2,sptr3,addr(z) ,ten, aprx-1 ) ; return; end; end; end 3eigen; 36 APPENDIX D EXAMPLE OF EIGENVALUE STATEMENTS ***ol/2 operator LANGUAGE/2 university of ILLINCIS VER. 3.1 EXAMPLE: MAIN PPCCEDURE; LET B AND C BE MATRICES CF CPDERI6), AND X AND Y 3E VECTORS CF 0RDER(6), AND W BE A VECTOR OF ORDER12); INPUT B; EIGENVALUES B*3 -> X , Y ; OUTPUT X , Y : PACK; SET L TO THE LOWER TRIANGULAR PART CF B; EIGENSYSTEM L -> X , C ; SET U TO THE UPPE* TRIANGULAR PAPT OF B; EIGENVALUES U SMALLEST 2 -> W ; OUTPUT X , C , W : PACK; END EXAMPLE; OL/2 DIAGNOSTICS. NC ERRORS DETECTED. END CF DIAGNOSTICS. CCRE NOT USED BY COMPILER WAS: 48K BYTES. END CF COMPILATION. CCMPILE TIME: 2.73 SEC. BIBLIOGRAPHIC DATA SHEET 1. Report No. UIUCDCS-R-75-703 3. Recipient's Accession No. 1. Title and Subtitle THE EIGENVALUE PROBLEM IN THE OL/2 LANGUAGE 5. Report Date May 1975 6. '. Author(s) Ricardo Macias Carrasco 8. Performing Organization Rept. N °-UIUCDCS-R-75-703 '. Perlurming Organization Name and Address University of Illinois at Urbana-Champaign Department of Computer Science Urbana, Illinois 61801 10. Project/Task/Work Unit No. 11. Contract /Grant No. US NSF GJ-328 2. Sponsoring Organization Name and Address National Science Foundation Washington, D. C. 13. Type of Report & Period Covered Master's Thesis 14. 5. supplementary Notes 6. Abstracts This report is concerned with the eigenvalue problem in the context of the very high level, array language OL/2. Using the capabilities that are within the OL/2 language together with the high quality software that is present in EISPACK, an (implementation of the eigenvalue problem is presented. The syntax and semantics of the various eigenvalue statements is given along with the parsing of these statements, the generated code, the data structures, and the particular algorithms that are used. 7. Key Words and Document Analysis. 17a. Descriptors Eigenvalue Software *\rray Language Very High Level Language Eigenvalue-Eigenvector Syntax 7b. Identifiers /Open-Ended Terms 7c. C.OSAT1 Field/Group J. Availability Statement PLEASE UNLIMITED 5RM N TIS-35 ( 10-70) 19. Security Class (This Report) UNCLASSIFIED 20. Security Class (This Page UNCLASSIFIED 21. No. of Pages 40 22. Price USCOMM-DC 40329-P7 1 m a €* 29 1277 ISM oil m 8B8I m Wmmm mwmmmMm I ii 19 ll 1 H ■ IS I H H teS HB1 Bra IK 1 H 1 H 9 &$ a Hi ■ H B9I M 1 9 ■SS.TYOF.LL.NO.S-UHBAHA bSSwssr 1 3 0112088401820 B 9. ■ ■ '"