Institution: Stanford University, Department of Computer Science

Title: The solution of large systems of algebraic equations

Author: Pavkovich, John M.

Date: December 1963

Abstract: The solution of a system of linear algebraic equations using a computer is not a difficult problem as long as the equations are not ill-conditioned and all of the coefficients can be stored in the computer. However, when the number of coefficients is so large that supplemental means of storage, such as magnetic tape, are required, the problem of solving the system in an efficient manner increases considerably. This paper describes a method of solution whereby such systems of equations can be solved in an efficient manner. The problems associated with ill-conditioned systems of equations are not discussed.

CS-TR-63-2

Report Number: CS-TR-64-6

Institution: Stanford University, Department of Computer Science

Title: A fast direct solution of Poisson's equation using Fourier analysis

Author: Hockney, Roger W.

Date: April 1964

Abstract: The demand for rapid procedures to solve Poisson's equation has lead to the development of a direct method of solution involving Fourier analysis which can solve Poisson's equation in a square region covered by a 48 x 48 mesh in 0.9 seconds on the IBM 7090. This compares favorably with the best iterative methods which would require about 10 seconds to solve the same problem. The method is applicable to rectangular regions with simple boundary conditions and the maximum observed error in the potential for several random charge distributions is $5 \times\ 10^{-7}$ of the maximum potential charge in the region.

CS-TR-64-6

Report Number: CS-TR-64-9

Institution: Stanford University, Department of Computer Science

Title: The QD-algorithm as a method for finding the roots of a polynomial equation when all roots are positive

Author: Andersen, Christian

Date: June 1964

Abstract: The Quotient-Difference (QD)-scheme, symmetric functions and some results from the theory of Hankel determinants are treated. Some well known relations expressing the elements of the QD-scheme by means of the Hankel determinants are presented. The question of convergence of the columns of the QD-scheme is treated. An exact expression for $q_{n}^{k}$ is developed for the case of different roots. It is proved that the columns of the QD-scheme will converge not only in the well known case of different roots, but in all cases where the roots are positive. A detailed examination of the convergence to the smallest root is presented. An exact expression for $q_{n}^{N}$ is developed. This expression is correct in all cases of multiple positive roots. It is shown that the progressive form of the QD-algorithm is only 'mildly unstable'. Finally, some ALGOL programs and some results obtained by means of these are given.

CS-TR-64-9

Report Number: CS-TR-64-11

Institution: Stanford University, Department of Computer Science

Title: Elastic-plastic analysis of trusses by the gradient projection method

Author: Nakamura, Tsuneyoshi

Author: Rosen, Judah Ben

Date: July 1964

Abstract: The gradient projection method has been applied to the problem of obtaining the elastic-plastic response of a perfectly plastic ideal truss with several degrees of redundancy to several independently varying sets of quasi-static loads. It is proved that the minimization of stress rate intensity subject to a set of yield inequalities is equivalent to the maximization process of the gradient projection method. This equivalence proof establishes the basis of the computational method. The technique is applied to the problem of investigating the possibilities of shake down and to limit analysis. A closed convex "safe load domain" is defined to represent the load carrying capacity characteristics of a truss subjected to various combinations of the several sets of loads.

CS-TR-64-11

Report Number: CS-TR-64-12

Institution: Stanford University, Department of Computer Science

Title: Numerical methods for solving linear least squares problems (by G. Golub); An Algol procedure for finding linear least squares solutions (by Peter Businger)

Author: Golub, Gene H.

Author: Businger, Peter A.

Date: August 1964

Abstract: A common problem in a Computer Laboratory is that of finding linear least squares solutions. These problems arise in a variety of areas and in a variety of contexts. Linear least squares problems are particularly difficult to solve because they frequently involve large quantities of data, and they are ill-conditioned by their very nature. In this paper, we shall consider stable numerical methods for handling these problems. Our basic tool is a matrix decomposition based on orthogonal Householder transformations.

CS-TR-64-12

Report Number: CS-TR-64-13

Institution: Stanford University, Department of Computer Science

Title: Computation of the pseudoinverse of a matrix of unknown rank

Author: Pereyra, Victor

Author: Rosen, Judah Ben

Date: September 1964

Abstract: A program is described which computes the pseudoinverse, and other related quantities, of an m $\times$ n matrix A of unknown rank. The program obtains least square solutions to singular and/or inconsistent linear systems Ax = B, where m $\leq$ n or m > n and the rank of A may be less than min(m,n). A complete description of the programs and its use is given, including computational experience on a variety of problems.

CS-TR-64-13

Report Number: CS-TR-65-16

Institution: Stanford University, Department of Computer Science

Title: Maximizing a second-degree polynomial on the unit sphere

Author: Forsythe, George E.

Author: Golub, Gene H.

Date: February 1965

Abstract: Let A be a hermitian matrix of order n, and b a known vector in $C^n$. The problem is to determine which vectors make $\Phi (x) = {(x-b)}^H\ A(x-b)$ a maximum or minimum on the unit sphere U = {x : $x^H$x = 1}. The problem is reduced to the determination of a finite point set, the spectrum of (A,b). The theory reduces to the usual theory of hermitian forms when b = 0.

CS-TR-65-16

Report Number: CS-TR-65-17

Institution: Stanford University, Department of Computer Science

Title: Automatic grading programs

Author: Forsythe, George E.

Author: Wirth, Niklaus

Date: February 1965

Abstract: The ALGOL grader programs are presented for the computer evaluation of student ALGOL programs. One is for a beginner's program; it furnishes random data and checks answers. The other provides a searching test of the reliability and efficiency of a rootfinding procedure. There is a statement of the essential properties of a computer system, in order that grader programs can be effectively used.

CS-TR-65-17

Report Number: CS-TR-65-18

Institution: Stanford University, Department of Computer Science

Title: The difference correction method for non-linear two-point boundary value problems

Author: Pereyra, Victor

Date: February 1965

Abstract: The numerical solution of non-linear two-point boundary value problems is discussed. It is shown that for a certain class of finite difference approximations the a posteriori use of a difference correction raises the order of the approximation by at least two orders. The difference correction itself involves only the solution of one system of linear equations. If Newton's method is used in the early stage, then it is shown that the matrices in both processes are identical, which is a useful feature in coding the method for an automatic computer. Several numerical examples are given.

CS-TR-65-18

Report Number: CS-TR-65-20

Institution: Stanford University, Department of Computer Science

Title: EULER: a generalization of ALGOL, and its formal definition

Author: Wirth, Niklaus

Author: Weber, Helmut

Date: April 1965

Abstract: A method for defining programming languages is developed which introduces a rigorous relationship between structure and meaning. The structure of a language is defined by a phrase structure syntax, the meaning in terms of the effects which the execution of a sequence of interpretation rules exerts upon a fixed set of variables, called the Environment. There exists a one-to-one correspondence between syntactic rules and interpretation rules, and the sequence of executed interpretation rules is determined by the sequence of corresponding syntactic reductions which constitute a parse. The individual interpretation rules are explained in terms of an elementary and obvious algorithmic notation. A constructive method for evaluating a text is provided, and for certain decidable classes of languages their unambiguity is proven. As an example, a generalization of ALGOL is described in full detail to demonstrate that concepts like block-structure, procedures, parameters etc. can be defined adequately and precisely by this method.

CS-TR-65-20

Report Number: CS-TR-65-21

Institution: Stanford University, Department of Computer Science

Title: Vectorcardiographic analysis by digital computer, selected results

Author: Fisher, Donald D.

Author: Groeben, Jobst von der

Author: Toole, J. Gerald

Date: May 1965

Abstract: Instrumentation, recording devices and digital computers now may be combined to obtain detailed statistical measures of physiological phenomena. Computers make it possible to study several models of a system in depth as well as breadth. This report is concerned with methods employed in a detailed statistical study of some 600 vectorcardiograms from different "normal" individuals which were recorded on analog magnetic tape using two different orthogonal lead systems (Helm, Frank) giving a total of 1200 cardiograms. A "normal" individual is defined as one in which no abnormal heart condition was detected by either medical history or physical examination. One heartbeat in a train of 15 or 20 was selected for digitization. An average of 1.2 seconds worth of data was digitized from each of the three vector leads simultaneously at a rate of 1000 samples per second for each lead giving a total of over ${4.10}^6$ values. Statistical models by sex and lead system of the P wave and QRS complex (at 1 millisecond intervals) and T wave (normalized to 60 points in time) were obtained for 43 age groups from age 19 to 61 in rectangular coordinates, polar coordinates and ellipsoidal fit (F-test) coordinates. Several programs were written to perform the analyses on an IBM 7090. Two of the programs used 300000+ words of disk storage to collect the necessary statistics. Various aspects of the study are presented in this report.

CS-TR-65-21

Report Number: CS-TR-65-23

Institution: Stanford University, Department of Computer Science

Title: Convex polynomial approximation

Author: Rudin, Bernard D.

Date: June 1965

Abstract: Let f(t) be a continuous function on [0,1], or let it be discretely defined on a finite point set in [0,1]. The problem is the following: among all polynomials p(t) of degree n or less which are convex on [0,1], find one which minimizes the functional $\l p(t)-f(t)\l$, where $\l\ \l$ is a suitably defined norm (in particular, the $L^p$, ${\ell}^p$, and Chebyshev norms). The problem is treated by showing it to be a particular case of a more general problem: let f be an element of a real normed linear space V; let $x_{1}(z),...,x_{k}(z)$ be continous functions on a subset S of the Euclidean space $E^n$ into V such that for each $z_o$ in S the set {$x_{1}(z_{o}),...,x_{k}(z_{o})$} is linearly independent in V; let $(y_{1},...,y_{k})$ denote an element of the Euclidean space $E^k$ and let H be a subset of $K^k$; then among all (y,z) in H $\times$ S, find one which minimizes the functional $\l y_1\ x_{1}(z)+ ... +y_{k}x_{k}(z) - f\l$. It is shown that solutions to this problem exist when H is closed and S is compact. Conditions for uniqueness and location of solutions on the boundary of H $\times$ S are also given. Each polynomial of degree n + 2 or less which is convex on [0,1] is shown to be uniquely representable in the form $y_{o}+y_{1}t+y_2\ \int\int\ p(z,t)dt^2$, where p(z,t) is a certain representation of the polynomials positive on [0,1], $y_2\ \geq\ 0$, and z is constrained to lie in a certain convex hyperpolyhedron. With this representation, the convex polynomial approximation problem can be treated by the theory mentioned above. It is reduced to a problem of minimizing a functional subject to linear constraints. Computation of best least squares convex polynomial approximation is illustrated in the continuous and discrete cases.

CS-TR-65-23

Report Number: CS-TR-65-25

Institution: Stanford University, Department of Computer Science

Title: Yield-point load determination by nonlinear programming

Author: Hodge, Philip G. Jr.

Date: June 1965

Abstract: The determination of the yield-point load of a perfectly plastic structure can be formulated as a nonlinear programming problem by means of the theorems of limit analysis. This formulation is discussed in general terms and then applied to the problem of a curved beam. Recent results in the theory of nonlinear programming are called upon to solve typical problems for straight and curved beams. The theory of limit analysis enables intermediate answers to be given a physical interpretation in terms of upper and lower bounds on the yield-point load. The paper closes with some indication of how the method may be generalized to more complex problems of plastic yield-point load determination.

CS-TR-65-25

Report Number: CS-TR-65-26

Institution: Stanford University, Department of Computer Science

Title: Stanford University's Program in Computer Science

Author: Forsythe, George E.

Date: June 1965

Abstract: This report discusses the nature and objectives of Stanford University's Program in Computer Science. Listings of course offerings and syllabi for Ph.D. examinations are given in appendices.

CS-TR-65-26

Report Number: CS-TR-65-28

Institution: Stanford University, Department of Computer Science

Title: Matrix theorems for partial differential and difference equations

Author: Miller, John J. H.

Author: Strang, Gilbert

Date: July 1965

Abstract: We extend the work of Kreiss and Morton to prove: for some constant K(m), where m is the order of the matrix A, $|A^(n)v| \leq C(v)$ for all n $geq$ 0 and |v| = 1 implies that $|{SAS}^{-1}| \leq 1$ for some S with $|S^{-1}| \leq 1$, |Sv| $\leq$ k(m)C(v). We establish the analogue for exponentials $e^{Pt}$, and use it to construct the minimal Hilbert norm dominating $L_2$ in which a given partial differential equation with constant coefficients is well-posed.

CS-TR-65-28

Report Number: CS-TR-65-29

Institution: Stanford University, Department of Computer Science

Title: On improving an approximate solution of a functional equation by deferred corrections

Author: Pereyra, Victor

Date: August 1965

Abstract: The improvement of discretization algorithms for the approximate solution of nonlinear functional equations is considered. Extensions to the method of difference corrections by Fox are discussed and some general results are proved. Applications to nonlinear boundary problems and numerical examples are given in some detail.

CS-TR-65-29

Report Number: CS-TR-65-31

Institution: Stanford University, Department of Computer Science

Title: On the approximation of weak solutions of linear parabolic equations by a class of multistep difference methods

Author: Raviart, Pierre Arnaud

Date: December 1965

Abstract: We consider evolution equations of the form (1) du(t)/dt + A(t)u(t) = f(t), $0 \leq\ t \leq\ T$, f given, with the initial condition (2) u(o) = $u_o$, $u_o$ given, where each A(t) is an unbounded linear operator in a Hilbert space H, which is in practice an ellilptic partial differential operator subject to appropriate boundary conditions. Let $V_h$ be a Hilbert space which depends on the parameter h. Let k be the time-step such that m = $\frac{T}{k}$ is an integer. We approximate the solution u of (1), (2) by the solution $u_{h,k}$ ($u_{h,k}$ = {$u_{h,k}(rk) \in V_{h}$, r = 0,1,...,m-1}) of the multistep difference scheme (3) $\frac{u_{h,k}(rk) - u_{h,k}((r-1)k)}{k} = \sum_{{\ell}=0}^{p} {\gamma}_{\ell} A_{h}((r-{\ell})k) u_{h,k}((r-{\ell}k) = \sum_{{\ell}=0}^{p} {\gamma}_{\ell} f_{h,k}((r-{\ell})k), r = p,...,m-1$ (4) $u_{h,k}(o),...,u_{h,k}((p-1)k)$ given, where each $A_{h}(rk) is a linear continuous operator from $V_h$ into $V_h$, $f_{h,k}(rk)$ (r = 0,1,...,m-1) are given, and ${\gamma}_{\ell}({\ell}=0,...,p) are given complex numbers. Our paper is mainly concerned by the study of the stability of the approximation. The methods used here are very closely related to those developed in the author's thesis and we shall refer to the thesis frequently. In Section 1,2, we define the continuous and approximate problems in precise terms. In Section 4, we find sufficient conditions for $u_{h,k}$ to satisfy some a priori estimates. The definition of the stability is given in Section 5 and we use the a priori estimates for proving a general stability theorem. In Section 6 we prove that the stability conditions may be weakened when A(t) is a self-adjoint operator (or when only the principal part of A(t) is self-adjoint). We give in Section 7 a weak convergence theorem. Section 8 is concerned with regularity properties. We apply our abstract analysis to a class of parabolic partial differential equations with variable coefficients in Section 9. Strong convergence theorems can be obtained as in the author's thesis (via compactness arguments) or as in the thesis of J.P. Aubin. We do not study here the discretization error (see author's thesis). For the study of the stability of multistep difference methods in the case of the Cauchy problem for parabolic differential operators, we refer to Kreiss [1959], Widlund [1965].

CS-TR-65-31

Report Number: CS-TR-65-32

Institution: Stanford University, Department of Computer Science

Title: Minimum multiplication Fourier analysis

Author: Hockney, Roger W.

Date: December 1965

Abstract: Fourier analysis and synthesis is a frequently used tool in applied mathematics but is found to be a time consuming process to apply on a digital computer and this fact may prevent the practical application of the technique. This paper describes an algorithm which uses the symmetries of the sine and cosine functions to reduce the number of arithmetic operations by a factor between 10 and 30. The algorithm is applicable to a finite fourier (or harmonic) analysis on $12 \bigotimes\ 2^q$ values, where q is any integer $\geq$ 0 and is applicable to a variety of end conditions. A complete and tested B5000 Algol program known as FOURIER12 is included.

CS-TR-65-32

Report Number: CS-TR-65-33

Institution: Stanford University, Department of Computer Science

Title: A programming language for the 360 computers

Author: Wirth, Niklaus

Date: December 1965

Abstract: This paper is a prelimary definition of a programming language which is specifically designed for use on IBM 360 computers, and is therefore appropriately called PL360.

CS-TR-65-33

Report Number: CS-TR-66-34

Institution: Stanford University, Department of Computer Science

Title: Eigenvectors of a real matrix by inverse iteration

Author: Varah, James M.

Date: February 1966

Abstract: This report contains the description and listing of an ALGOL 60 program which calculates the eigenvectors of an arbitrary real matrix, using the technique of inverse iteration.

CS-TR-66-34

Report Number: CS-TR-66-37

Institution: Stanford University, Department of Computer Science

Title: COGENT 1.2 operations manual

Author: Reynolds, John C.

Date: April 1966

Abstract: This document is an addendum to the COGENT Programming Manual (Argonne National Laboratory, ANL-7022, March 1965, hereafter referred to as CPM) which describes a specific implementation of the COGENT system, COGENT 1.2, written for the Control Data 3600 Computer. Chapters I and II describe a variety of features available in COGENT 1.2 which are not mentioned in CPM; these chapters parallel the material in Chapters II and III of CPM. Chapter III of this report gives various operational details concerning the assembly and loading of both COGENT-compiled programs and the compiler itself. Chapter IV describes system and error messages. Familiarity with the contents of CPM is assumed throughout this report. In addition, a knowledge of the 3600 operating system SCOPE, and the assembler COMPASS is assumed in Chapter III.

CS-TR-66-37

Report Number: CS-TR-66-39

Institution: Stanford University, Department of Computer Science

Title: A university's educational program in computer science

Author: Forsythe, George E.

Date: May 1966

Abstract: After a review of the power of contemporary computers, computer science is defined in several ways. The objectives of computer science education are stated, and it is asserted that in a U.S. university these will be achieved only through a computer science department. The program at Stanford University is reviewed as an example. The appendix includes syllabi of Ph.D. qualifying examinations for Stanford's Computer Science Department. This is a revision of a previous Stanford Computer Science Department report, CS 26.

CS-TR-66-39

Report Number: CS-TR-66-40

Institution: Stanford University, Department of Computer Science

Title: How do you solve a quadratic equation?

Author: Forsythe, George E.

Date: June 1966

Abstract: The nature of the floating-point number system of digital computers is explained to a reader whose university mathematical background is very limited. The possibly large errors in using mathematical algorithms blindly with floating-point computation are illustrated by the formula for solving a quadratic equation. An accurate way of solving a quadratic is outlined. A few general remarks are made about computational mathematics, including the backwards analysis of rounding error.

CS-TR-66-40

Report Number: CS-TR-66-41

Institution: Stanford University, Department of Computer Science

Title: Accurate eigenvalues of a symmetric tri-diagonal matrix

Author: Kahan, William

Date: July 1966

Abstract: Having established tight bounds for the quotient of two different lub-norms of the same tri-diagonal matrix J, the author observes that these bounds could be of use in an error-analysis provided a suitable algorithm were found. Such an algorithm is exhibited, and its errors are thoroughly accounted for, including the effects of scaling, over/underflow and roundoff. A typical result is that, on a computer using rounded floating point binary arithmetic, the biggest eigenvalue of J can be computed easily to within 2.5 units in its last place, and the smaller eigenvalues will suffer absolute errors which are no larger. These results are somewhat stronger than had been known before.

CS-TR-66-41

Report Number: CS-TR-66-42

Institution: Stanford University, Department of Computer Science

Title: When to neglect off-diagonal elements of symmetric tri-diagonal matrices

Author: Kahan, William

Date: July 1966

Abstract: Given a tolerance $\epsilon$ > 0, we seek a criterion by which an off-diagonal element of the symmetric tri-diagonal matrix J may be deleted without changing any eigenvalue of J by more than $\epsilon$. The criterion obtained here permits the deletion of elements of order $\sqrt{\epsilon }$ under favorable circumstances, without requiring any prior knowledge about the separation between the eigenvalues of J.

CS-TR-66-42

Report Number: CS-TR-66-43

Institution: Stanford University, Department of Computer Science

Title: Two working algorithms for the eigenvalues of a symmetric tridiagonal matrix

Author: Kahan, William

Author: Varah, James M.

Date: August 1966

Abstract: Two tested programs are supplied to find the eigenvalues of a symmetric tridiagonal matrix. One program uses a square-root-free version of the QR algorithm. The other uses a compact kind of Sturm sequence algorithm. These programs are faster and more accurate than the other comparable programs published previously with which they have been compared.

CS-TR-66-43

Report Number: CS-TR-66-44

Institution: Stanford University, Department of Computer Science

Title: Relaxation methods for an eigenproblem

Author: Kahan, William

Date: August 1966

Abstract: A theory is developed to account for the convergence properties of certain relaxation iterations which have been widely used to solve the eigenproblem $(A - \lambda B) \underline{x} = 0, \underline{x} \neq 0, with large symmetric matrices A and B and positive definite B. These iterations always converge, and almost always converge to the right answer. Asymptotically, the theory is essentially that of the relaxation iteration applied to a semi-definite linear system discussed in the author's previous report [Stanford University Computer Science Department report CS45, 1966].

CS-TR-66-44

Report Number: CS-TR-66-45

Institution: Stanford University, Department of Computer Science

Title: Relaxation methods for semi-definite systems

Author: Kahan, William

Date: August 1966

Abstract: Certain non-stationary relaxation iterations, which are commonly applied to positive definite symmetric systems of linear equations, are also applicable to a semi-definite system provided that system is consistent. Some of the convergence theory of the former application is herein extended to the latter application. The effects of rounding errors and of inconsistency are discussed too, but with few helpful conclusions. Finally, the application of these relaxation iterations to an indefinite system is shown here to be ill-advised because these iterations will almost certainly diverge exponentially.

CS-TR-66-45

Report Number: CS-TR-66-47

Institution: Stanford University, Department of Computer Science

Title: An interpreter for "Iverson notation"

Author: Abrams, Philip S.

Date: August 1966

Abstract: Kenneth E. Iverson's book, "A Programming Language" [New York: Wiley, 1962], presented a highly elegant language for the description and analysis of algorithms. Although not widely acclaimed at first, "Iverson notation" (referred to as "the language" in this report) is coming to be recognized as an important tool by computer scientists and programmers. The current report contains an up-to-date definition of a subset of the language, based on recent work by Iverson and his colleagues. Chapter III describes an interpreter for the language, written jointly by the author and Lawrence M. Breed of IBM. The remainder of the paper consists of critiques of the implementation and the language, with suggestions for improvement. This report was originally submitted in fulfillment of a Computer Science 239 project supervised by Professor Niklaus Wirth, Stanford University, May 30, 1966.

CS-TR-66-47

Report Number: CS-TR-66-52

Institution: Stanford University, Department of Computer Science

Title: Lecture notes on a course in systems programming

Author: Shaw, Alan C.

Date: December 1966

Abstract: These notes are based on the lectures of Professor Niklaus Wirth which were given during the winter and spring of 1965/66 as CS 236a and part of CS 236b, Computer Science Department, Stanford University.

CS-TR-66-52

Report Number: CS-TR-66-53

Institution: Stanford University, Department of Computer Science

Title: A programming language for the 360 computers

Author: Wirth, Niklaus

Date: December 1966

Abstract: A programming language for the IBM 360 computers and its implementation are described. The language, called PL360, provides the facilities of a symbolic machine language, but displays a structure defined by a recursive syntax. The compiler, consisting of a precedence syntax analyser and a set of interpretation rules with strict one-to-one correspondence to the set of syntactic rules directly reflects the definition of the language. | k-th syntax rule | k-th interpretation rule | $S_0 ::= S_1 S_2 ... S_n$ | $V_0 := f_k (V_1 , V_2 , ... , V_n)$ | PL360 was designed to improve the readability of programs which must take into account specific characteristics and limitations of a particular computer. It represents an attempt to further the state of the art of programming by encouraging and even forcing the programmer to improve his style of exposition and his principles and discipline in program organization, and not by merely providing a multitude of "new" features and facilities. The language is therefore particularly well suited for tutorial purposes. The attempt to present a computer as a systematically organized entity is also hoped to be of interest to designers of future computers.

CS-TR-66-53

Report Number: CS-TR-67-54

Institution: Stanford University, Department of Computer Science

Title: A generalized Bairstow algorithm

Author: Golub, Gene H.

Author: Robertson, Thomas N.

Date: January 1967

Abstract: This report discusses convergence and applications for the generalized Bairstow algorithm.

CS-TR-67-54

Report Number: CS-TR-67-55

Institution: Stanford University, Department of Computer Science

Title: A stopping criterion for polynomial root finding

Author: Adams, Duane A.

Date: February 1967

Abstract: When solving for the roots of a polynomial, it is generally difficult to know just when to terminate the iteration process. In this paper an algorithm is derived and discussed which allows one to terminate the iteration process on the basis of calculated bounds for the roundoff error.

CS-TR-67-55

Report Number: CS-TR-67-56

Institution: Stanford University, Department of Computer Science

Title: QD-method with Newton shift

Author: Bauer, Friedrich L.

Date: March 1967

Abstract: Theoretically, for symmetric matrices, a QR-step is equivalent to two successive LR-steps, and the LR-transformation for a tridiagonal matrix is, apart from organizational details, identical with the qd-method. For non-positive definite matrices, however, the LR-transformation cannot be guaranteed to be numerically stable unless pivotal interchanges are made. This has led to preference for the QR-transformation, which is always numerically stable. If, however, some of the smallest or some of the largest eigenvalues are wanted, then the QR-transformation will not necessarily give only these, and bisection might seem too slow with its fixed convergence rate of 1/2. In this situation, Newton's method would be fine if the Newton correction can be computed sufficiently simply, since it will always tend monotonically to the nearest root starting from a point outside the spectrum. Consequently, if one always worked with positive (or negative) definite matrices, there would be no objection to using the now stable qd-algorithm. The report shows that for a qd-algorithm, the Newton correction can very easily be calculated, and accordingly a shift which avoids under-shooting, or a lower bound. Since the last diagonal element gives an upper bound, the situation is quite satisfactory with respect to bounds.

CS-TR-67-56

Report Number: CS-TR-67-57

Institution: Stanford University, Department of Computer Science

Title: The use of transition matrices in compiling

Author: Gries, David

Date: March 1967

Abstract: The construction of efficient parsing algorithms for programming languages has been the subject of many papers in the last few years. Techniques for efficient parsing and algorithms which generate the parser from a grammar or phrase structure system have been derived. Some of the well-known methods are the precedence techniques of Floyd, and Wirth and Weber, and the production langauge of Feldman. Perhaps the first such discussion was by Samelson and Bauer. There the concept of the push-down stack was introduced, along with the idea of a transition matrix. A transition matrix is just a switching table which lets one determine from the top element of the stack (denoting a row of the table) and the next symbol of the program to be processed (represented by a column of the table) exactly what should be done. Either a reduction is made in the stack, or the incoming symbol is pushed onto the stack. Considering its efficiency, the transition matrix technique does not seem to have achieved much attention, probably because it was not sufficiently well-defined. The purpose of this paper is to define the concept more formally, to illustrate that the technique is very efficient, and to describe an algorithm which generates a transition matrix from a suitable grammar. The report also describes other uses of transition matrices besides the usual ones of syntax checking and compiling.

CS-TR-67-57

Report Number: CS-TR-67-59

Institution: Stanford University, Department of Computer Science

Title: Almost diagonal matrices with multiple or close eigenvalues

Author: Wilkinson, James H.

Date: April 1967

Abstract: If A = D + E where D is the matrix of diagonal elements of A, then when A has some multiple or very close eigenvalues, E has certain characteristic properties. These properties are considered both for hermitian and non-hermitian A. The properties are important in connexion with several algorithms for diagonalizing matrices by similarity transformations.

CS-TR-67-59

Report Number: CS-TR-67-60

Institution: Stanford University, Department of Computer Science

Title: Two algorithms based on successive linear interpolation

Author: Wilkinson, James H.

Date: April 1967

Abstract: The method of successive linear interpolation has a very satisfactory asymptotic rate of convergence but the behavior in the early steps may lead to divergence. The regular falsi has the advantage of being safe but its asymptotic behavior is unsatisfactory. Two modified algorithms are described here which overcome these weaknesses. Although neither is new, discussions of their main features do not appear to be readily available in the literature.

CS-TR-67-60

Report Number: CS-TR-67-61

Institution: Stanford University, Department of Computer Science

Title: On the asymptotic directions of the s-dimensional optimum gradient method

Author: Forsythe, George E.

Date: April 1967

Abstract: The optimum s-gradient method for minimizing a positive definite quadratic function f(x) on $E_n$ has long been known to converge for s $\geq$ 1. For these $\underline{s}$ the author studies the directions from which the iterates $x_k$ approach their limit, and extends to s > 1 a theory proved by Akaike for s = 1. It is shown that f($x_k$) can never converge to its minimum value faster than linearly, except in degenerate cases where it attains the minimum in one step.

CS-TR-67-61

Report Number: CS-TR-67-62

Institution: Stanford University, Department of Computer Science

Title: Varying length floating point arithmetic: a necessary tool for the numerical analyst

Author: Tienari, Martti

Date: April 1967

Abstract: The traditional floating point arithmetic of scientific computers is biased towards fast and easy production of numerical results without enough provision to enable the programmer to control and solve problems connected with numerical accuracy and cumulative round-off errors. The author suggests the varying length floating point arithmetic as a general purpose solution for most of these problems. Some general philosophies are outlined for applications of this feature in numerical analysis. The idea is analyzed further discussing hardware and software implementations.

CS-TR-67-62

Report Number: CS-TR-67-63

Institution: Stanford University, Department of Computer Science

Title: Graeffe's method for eigenvalues

Author: Polya, George

Date: April 1967

Abstract: Let an entire function F(z) of finite genus have infinitely many zeros which are all positive, and take real values for real z. Then it is shown how to give two-sided bounds for all the zeros of F in terms of the coefficients of the power series of F, and of coefficients obtained by Graeffe's algorithm applied to F. A simple numerical illustration is given for a Bessel function.

CS-TR-67-63

Report Number: CS-TR-67-64

Institution: Stanford University, Department of Computer Science

Title: Floating-point number representations: base choice versus exponent range

Author: Richman, Paul L.

Date: April 1967

Abstract: A digital computer whose memory words are composed of r-state devices is considered. The choice of the base, $\Beta$, for the internal floating-point numbers on such a computer is discussed. Larger values of $\Beta$ necessitate the use of more r-state devices for the mantissa, in order to preserve some "minimum accuracy," leaving fewer r-state devices for the exponent of $\Beta$. As $\Beta$ increases, the exponent range may increase for a short period, but it must ultimately decrease to zero. Of course, this behavior depends on what definition of accuracy is used. This behavior is analyzed for a recently proposed definition of accuracy which specifies when it is to be said that the set of q-digit base $\Beta$ floating-point numbers is accurate to p-digits base t. The only case of practical importance today is t=10 and r=2; and in this case we find that $\Beta$ = 2 is always best. However the analysis is done to cover all cases.

CS-TR-67-64

Report Number: CS-TR-67-65

Institution: Stanford University, Department of Computer Science

Title: On certain basic concepts of programming languages

Author: Wirth, Niklaus

Date: May 1967

Abstract: Recent developments of programming languages have led to the emergence of languages whose growth showed cancerous symptoms: the proliferation of new elements defied every control exercised by the designers, and the nature of the new cells often proved to be incompatible with the existing body. In order that a language be free from such symptoms, it is necessary that it be built upon basic concepts which are sound and mutually independent. The rules governing the language must be simple, generally applicable and consistent. In order that simplicity and consistency can be achieved, the fundamental concepts of a language must be well-chosen and defined with utmost clarity. In practice, it turns out that there exists an optimum in the number of basic concepts, below which not only implementability of these concepts on actual computers, but also their appeal to human intuition becomes questionable because of their high degree of generalization. These informal notes do not abound with ready-made solutions, but it is hoped they shed some light on several related subjects and inherent difficulties. They are intended to summarize and interrelate various ideas which are partly present in existing languages, partly debated within the IFIP Working Group 2.1, and partly new. While emphasis is put on clarification of conceptual issues, consideration of notation cannot be ignored. However, no formal or concise definitions of notation (syntax) will be given or used; the concepts will instead be illustrated by examples, using notation based on Algol as far as possible.

CS-TR-67-65

Report Number: CS-TR-67-67

Institution: Stanford University, Department of Computer Science

Title: Computational considerations regarding the calculation of Chebyshev solutions for overdetermined linear eqauation systems by the exchange method

Author: Bartels, Richard H.

Author: Golub, Gene H.

Date: June 1967

Abstract: An implementation, using Gaussian LU decomposition with row interchanges, of Stiefel's exchange algorithm for determining a Chebyshev solution to an overdetermined system of linear equations is presented. The implementation is computationally more stable than those usually given in the literature. A generalization of Stiefel's algorithm is developed which permits the occasional exchange of two equations simultaneously. Finally, some experimental comparisons are offered.

CS-TR-67-67

Report Number: CS-TR-67-68

Institution: Stanford University, Department of Computer Science

Title: The PL360 system

Author: Wirth, Niklaus

Date: June 1967

Abstract: This report describes the use and the organization of the operating system which serves as the environment of the PL360 language defined in the companion report, CS 53 [Niklaus Wirth, "A Programming Language for the 360 Computers," Stanford University Department of Computer Science, June 1967]. Edited by Niklaus Wirth.

CS-TR-67-68

Report Number: CS-TR-67-69

Institution: Stanford University, Department of Computer Science

Title: Translator writing systems

Author: Feldman, Jerome A.

Author: Gries, David

Date: June 1967

Abstract: Compiler writing has long been a glamour field within programming and has a well developed folklore. More recently, the attention of researchers has been directed toward various schemes for automating different parts of the compiler writer's task. This paper contains neither a history of nor an introduction to these developments; the references at the end of this section provide what introductory material there is in the literature. Although we will make comparisons between individual systems and between various techniques, this is certainly not a consumer's guide to translator writing systems. Our intended purpose is to carefully consider the existing work in an attempt to form a unified scientific basis for future research.

CS-TR-67-69

Report Number: CS-TR-67-70

Institution: Stanford University, Department of Computer Science

Title: On computation of flow patterns of compressible fluids in the transonic region

Author: Bergman, Stefan

Author: Herriot, John G.

Author: Richman, Paul L.

Date: July 1967

Abstract: The first task in devising a numerical procedure for solving a given problem is that of finding a constructive mathematical solution to the problem. But even after such a solution is found there is much to be done. Mathematical solutions normally involve infinite processes such as integration and differentiation as well as infinitely precise arithmetic and functions defined in arbitrarily involved ways. Numerical procedures suitable for a computer can involve only finite processes, fixed or at least bounded length arithmetic and rational functions. Thus one must find efficient methods which yield approximate solutions. Of interest here are the initial and boundary value problems for compressible fluid flow. Constructive solutions to these problems can be found in [Bergman, S., "On representation of stream functions of subsonic and supersonic flows of compressible fluids," Journal of Rational Mechanics and Analysis, v.4 (1955), no. 6, pp. 883-905]. As presented there, solution of the boundary value problem is limited to the subsonic region, and is given symbolically as a linear combination of orthogonal functions. A numerical continuation of this (subsonic) solution into the supersonic region can be done by using the (subsonic) solution and its derivative to set up an intial value problem. The solution to the initial value problem may then be valid in (some part of) the supersonic region. Whether this continuation will lead to a closed, meaningful flow is an open question. In this paper, we deal with the numerical solution of the initial value problem. We are currently working on the rest of the procedure described above.

CS-TR-67-70

Report Number: CS-TR-67-72

Institution: Stanford University, Department of Computer Science

Title: Chebyshev approximation of continuous functions by a Chebyshev system of functions

Author: Golub, Gene H.

Author: Smith, Lyle B.

Date: July 1967

Abstract: The second algorithm of Remez can be used to compute the minimax approximation to a function, f(x), by a linear combination of functions, ${\{Q_i (x)\}}^{N}_{O}$, which form a Chebyshev system. The only restriction on the function to be approximated is that it be continuous on a finite interval [a,b]. An Algol 60 procedure is given which will accomplish the approximation. This implementation of the second algorithm of Remez is quite general in that the continuity of f(x) is all that is required whereas previous implementations have required differentiability, that the end points of the interval be "critical points," and that the number of "critical points" be exactly N+2. Discussion of the method used and its numerical properties is given as well as some computational examples of the use of the algorithm. The use of orthogonal polynomials (which change at each iteration) as the Chebyshev system is also discussed.

CS-TR-67-72

Report Number: CS-TR-67-75

Institution: Stanford University, Department of Computer Science

Title: Theory of norms

Author: Bauer, Friedrich L.

Date: August 1967

Abstract: These notes are based on lectures given during the winter of 1967 as CS 233, Computer Science Department, Stanford University.

CS-TR-67-75

Report Number: CS-TR-67-76

Institution: Stanford University, Department of Computer Science

Title: Collectively compact operator approximations.

Author: Anselone, Phillip M.

Date: September 1967

Abstract: This report consists of notes based on lectures presented July-August 1967. The notes were prepared by Lyle Smith. A general approximation theory for linear and nonlinear operators on Banach spaces is presented. It is applied to numerical integration approximations of integral operators. Convergence of the operator approximations is pointwise rather than uniform on bounded sets, which is assumed in other theories. The operator perturbations form a collectively compact set, i.e., they map each bounded set into a single compact set. In the nonlinear case, Frechet differentiability conditions are also imposed. Principal results include convergence and error bounds for approximate solutions and, for linear operators, results on spectral approximations.

CS-TR-67-76

Report Number: CS-TR-67-77

Institution: Stanford University, Department of Computer Science

Title: What to do till the computer scientist comes

Author: Forsythe, George E.

Date: September 1967

Abstract: The potential impact of computer science departments in the field of education is discussed. This is an expanded version of a presentation to a panel session before the Mathematics Association of America, Toronto, 30 August 1967.

CS-TR-67-77

Report Number: CS-TR-67-78

Institution: Stanford University, Department of Computer Science

Title: Machine utilization of the natural language word 'good'

Author: Colby, Kenneth Mark

Author: Enea, Horace J.

Date: September 1967

Abstract: Using the term 'good' as an example, the effect of natural language input on an interviewing computer program is described. The program utilizes syntactic and semantic information to generate relevant plausible inferences from which statements for a goal-directed man-machine dialogue can be constructed.

CS-TR-67-78

Report Number: CS-TR-67-79

Institution: Stanford University, Department of Computer Science

Title: 360 O.S. FORTRAN IV free field input/output subroutine package

Author: Doran, Robert W.

Date: October 1967

Abstract: Programmers dealing with aspects of natural language processing have a difficult task in choosing a computer language which enables them to program easily, produce efficient code and accept as data freely written sentences with words of arbitrary length. List processing languages such as LISP are reasonably easy to program in but do not execute very quickly. Other, formula oriented, languages like FORTRAN are not provided with free field input. The Computational Linguistics group at the Stanford University Computer Science Department is writing a system for testing transformational grammars. As these grammars are generally large and complicated, it is important to make the system as efficient as possible, so we are using FORTRAN IV (O.S. on IBM 360-65) as our language. To enable us to handle free field input we have developed a subroutine package which we describe here in the hope that it will be useful to others embarking on natural language tasks. The package consists of two main programs, free field reader, free field writer, with a number of utility routines and constant COMMON blocks.

CS-TR-67-79

Report Number: CS-TR-67-80

Institution: Stanford University, Department of Computer Science

Title: Directed random generation of sentences

Author: Friedman, Joyce

Date: October 1967

Abstract: The problem of producing sentences of a transformational grammar by using a random generator to create phrase structure trees for input to the lexical insertion and transformational phases is discussed. A purely random generator will produce base trees which will be blocked by the transformations, and which are frequently too long to be of practical interest. A solution is offered in the form of a computer program which allows the user to constrain and direct the generation by the simple but powerful device of restricted subtrees. The program is a directed random generator which accepts as input a subtree with restrictions and produces around it a tree which satisfies the restrictions and is ready for the next phase of the grammar. The underlying linguistic model is that of Noam Chomsky, as presented in "Aspects of the Theory of Syntax." The program is written in Fortran IV for the IBM 360/67 and is part of the Stanford Transformational Grammar Testing System. It is currently being used with several partial grammars of English.

CS-TR-67-80

Report Number: CS-TR-67-81

Institution: Stanford University, Department of Computer Science

Title: Calculation of Gauss quadrature rules

Author: Golub, Gene H.

Author: Welsch, John H.

Date: November 1967

Abstract: Most numerical integration techniques consist of approximating the integrand by a polynomial in a region or regions and then integrating the polynomial exactly. Often a complicated integrand can be factored into a non-negative 'weight' function and another function better approximated by a polynomial, thus $\int_{a}^{b} g(t)dt = \int_{a}^{b} \omega (t)f(t)dt \approx \sum_{i=1}^{N} w_i f(t_i)$. Hopefully, the quadrature rule ${\{w_j, t_j\}}_{j=1}^{N}$ corresponding to the weight function $\omega$(t) is available in tabulated form, but more likely it is not. We present here two algorithms for generating the Gaussian quadrature rule defined by the weight function when: a) the three term recurrence relation is known for the orthogonal polynomials generated by $\omega$(t), and b) the moments of the weight function are known or can be calculated.

CS-TR-67-81

Report Number: CS-TR-68-83

Institution: Stanford University, Department of Computer Science

Title: Iterative refinements of linear least squares solutions by Householder transformations

Author: Bjorck, Ake

Author: Golub, Gene H.

Date: January 1968

Abstract: An algorithm is presented in ALGOL for iteratively refining the solution to a linear least squares problem with linear constraints. Numerical results presented show that a high degree of accuracy is obtained.

CS-TR-68-83

Report Number: CS-TR-68-84

Institution: Stanford University, Department of Computer Science

Title: A computer system for transformational grammar

Author: Friedman, Joyce

Date: January 1968

Abstract: A comprehensive system for transformational grammar has been designed and is being implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's "Aspects of the Theory of Syntax." The major innovations include a full and formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, and a simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the philosophy underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider particular aspects of the system in detail.

CS-TR-68-84

Report Number: CS-TR-68-85

Institution: Stanford University, Department of Computer Science

Title: Computer-aided language development in nonspeaking mentally disturbed children

Author: Colby, Kenneth Mark

Date: December 1967

Abstract: Experience with a computer-based method for aiding language development in nonspeaking mentally disturbed children is described. Out of a group of 10 children 8 improved linguistically while 2 were unimproved. Problems connected with the method and its future prospects are briefly discussed.

CS-TR-68-85

Report Number: CS-TR-68-86

Institution: Stanford University, Department of Computer Science

Title: ALGOL W

Author: Bauer, Henry R.

Author: Becker, Sheldon I.

Author: Graham, Susan L.

Date: January 1968

Abstract: The textbook "Introduction to Algol" by Baumann, Feliciano, Bauer, and Samelson describes the internationally recognized language ALGOL 60 for algorithm communication. ALGOL W can be viewed as an extension of ALGOL. This document consists of (1) "Algol W Notes for Introductory Computer Science Courses" [by Henry R. Bauer, Sheldon Becker, and Susan L. Graham] which describes the differences between ALGOL 60 and ALGOL W and presents the new features of ALGOL W; (2) "Deck Set-Up"; (3) "Algol W Language Description" [by Henry R. Bauer, Sheldon Becker, and Susan L. Graham], a complete syntactic and semantic description of the language; (4) "Unit Record Equipment"; and (5) "Error Message."

CS-TR-68-86

Report Number: CS-TR-68-87

Institution: Stanford University, Department of Computer Science

Title: CS139 lecture notes. Part I: Sections 1 thru 21. Preliminary version

Author: Ehrman, John R.

Date: 1968

Abstract: These notes are meant to provide an introduction to the IBM System/360 which will help the reader to understand and to make effective use of the capabilities of both the machinery and some of its associated service programs. They are largely self-contained, and in general the reader should need to make only occasional reference to the "System/360 Principles of Operation" manual (IBM File No. S360-01, Form A22-6821) and to the "Operating System/360 Assembler Language" manual (IBM File No. S360-21, Form C28-6514).

CS-TR-68-87

Report Number: CS-TR-68-88

Institution: Stanford University, Department of Computer Science

Title: Relaxation methods for convex problems

Author: Schechter, Samuel

Date: February 1968

Abstract: Extensions and simplifications are made for convergence proofs of relaxation methods for nonlinear systems arising from the minimization of strictly convex functions. This work extends these methods to group relaxation, which includes an extrapolated form of Newton's method, for various orderings. A relatively simple proof is given for cyclic orderings, sometimes referred to as nonlinear overrelaxation, and for residual orderings where an error estimate is given. A less restrictive choice of relaxation parameter is obtained than that previously. Applications are indicated primarily to the solution of nonlinear elliptic boundary problems.

CS-TR-68-88

Report Number: CS-TR-68-89

Institution: Stanford University, Department of Computer Science

Title: ALGOL W (revised)

Author: Bauer, Henry R.

Author: Becker, Sheldon I.

Author: Graham, Susan L.

Author: Forsythe, George E.

Author: Satterthwaite, Edwin H.

Date: March 1968

Abstract: The textbook "Introduction to Algol" by Baumann, Feliciano, Bauer, and Samelson describes the internationally recognized language ALGOL 60 for algorithm communication. ALGOL W can be viewed as an extension of ALGOL. This document consists of (1) "Algol W Deck Set-Up" [by E.H. Satterthwaite, Jr.]; (2) "Algol W Language Description" [by Henry R. Bauer, Sheldon Becker, and Susan L. Graham], a complete syntactic and semantic description of the language; (3) "Algol W Error Messages" [by Henry R. Bauer, Sheldon Becker, and Susan L. Graham]; (4) "Algol W Notes for Introductory Computer Science Courses" [by Henry R. Bauer, Sheldon Becker, and Susan L. Graham] which describes the differences tween ALGOL 60 and ALGOL W and presents the new features of ALGOL W; and (5) "Notes on Number Representation on System/360 and relations to Algol W" [by George E. Forsythe].

CS-TR-68-89

Report Number: CS-TR-68-90

Institution: Stanford University, Department of Computer Science

Title: A multi-level computer organization designed to separate data-accessing from the computation

Author: Lesser, Victor R.

Date: March 1968

Abstract: The computer organization to be described in this paper has been developed to overcome the inflexibility of computers designed around a few fixed data structures, and only binary operations. This has been accomplished by separating the data-accessing procedures from the computational algorithm. By this separation, a new and different language may be used to express data-accessing procedures. The new language has been designed to allow the programmer to define the procedures for generating the names of the operands for each computation, and locating the value of an operand given its name.

CS-TR-68-90

Report Number: CS-TR-68-91

Institution: Stanford University, Department of Computer Science

Title: The PL360 system

Author: Wirth, Niklaus E.

Author: Wells, Joseph W.

Author: Satterthwaite, Edwin H.

Date: April 1968

Abstract: This report describes the use of two operating systems which serve as environments for the PL360 language defined in the companion report [Niklaus Wirth, "A Programming Language for the 360 Computers," Stanford University Computer Science Department report CS 53 (revised), June 1967]. Some additions to that language, not described in CS 53, are documented in the Appendix.

CS-TR-68-91

Report Number: CS-TR-68-92

Institution: Stanford University, Department of Computer Science

Title: MLISP

Author: Enea, Horace J.

Date: March 1968

Abstract: Mlisp is an Algol-like list processing language based on Lisp 1.5. It is currently implemented on the IBM 360/67 at the Stanford Computation Center, and is being implemented on the DEC PDP-6 at the Stanford Artificial Intelligence Project. The balance of this paper is a very informal presentation of the language so that the reader will be able to run programs in Mlisp with a minimum of effort. The language has an extremely simple syntax which is presented in Appendix I.

CS-TR-68-92

Report Number: CS-TR-68-95

Institution: Stanford University, Department of Computer Science

Title: A formal syntax for transformational grammar

Author: Friedman, Joyce

Author: Doran, Robert W.

Date: March 1968

Abstract: A formal definition of the syntax of a transformational grammar is given using a modified Backus Naur Form as the metalanguage. Syntax constraints and interpretation are added in English. The underlying model is that presented by Chomsky in "Aspects of the Theory of Syntax." Definitions are given for the basic concepts of tree, analysis, restriction, complex symbol, and structural change, as well as for the major components of a transformational grammar, phrase structure, lexicon, and transformations. The syntax was developed as a specification of input formats for the computer system for transformational grammar described in [Joyce Friedman, "A Computer System for Transformational Grammar," Stanford University Computer Science Department report CS-84, January 1968]. It includes as a subcase a fairly standard treatment of transformational grammar, but has been generalized in many respects.

CS-TR-68-95

Report Number: CS-TR-68-96

Institution: Stanford University, Department of Computer Science

Title: Interval arithmetic determinant evaluation and its use in testing for a Chebyshev system

Author: Smith, Lyle B.

Date: April 1968

Abstract: Two recent papers by Hansen and by Hansen and R. R. Smith have shown how interval arithmetic (I.A.) can be used effectively to bound errors in matrix computations. This paper compares a method proposed by Hansen and R. R. Smith to straight-forward use of I.A. in determinant evaluation. Computational results show what accuracy and running times can be expected when using I.A. for determinant evaluation. An application using I.A. determinants in a program to test a set of functions to see if they form a Chebyshev system is then presented.

CS-TR-68-96

Report Number: CS-TR-68-98

Institution: Stanford University, Department of Computer Science

Title: ALGOL W implementation

Author: Bauer, Henry R.

Author: Becker, Sheldon I.

Author: Graham, Susan L.

Date: May 1968

Abstract: In writing a compiler of a new language (ALGOL W) for a new machine (IBM System/360) we were forced to deal with many unforeseen problems in addition to the problems we expected to encounter. This report describes the final version of the compiler. The implemented language ALGOL W is based on the Wirth/Hoare proposal for a successor to ALGOL 60. The major differences from that proposal are in string definition and operations and in complex number representation.

CS-TR-68-98

Report Number: CS-TR-68-100

Institution: Stanford University, Department of Computer Science

Title: A computer model of information processing in children

Author: Bredt, Thomas H.

Date: June 1968

Abstract: A model of cognitive information processing has been constructed on the basis of a protocol gathered from a child taking an object association test. The basic elements of the model are a graph-like data base and strategy. The data base contains facts that relate objects in the experiment. The graph distance that separates two objects in the data base is the measure of how well a relation is known. The strategy used in searching for facts that relate two objects is sequential in nature. The model has been programmed for computer testing in the LISP programming language. The responses of the computer model and the original subject are compared. To aid in the model evaluation a revised test was defined and administered to two children. The results were modeled and the correspondence of model and subject performance is discussed.

CS-TR-68-100

Report Number: CS-TR-68-102

Institution: Stanford University, Department of Computer Science

Title: Integer programming over a cone

Author: Pnueli, Amir

Date: July 1968

Abstract: The properties of a special form integer programming problem are discussed. We restrict ourselves to optimization over a cone (a set of n constraints in n unconstrained variables) with a square matrix of positive diagonal and non positive off-diagonal elements. (Called a bounding form by F. Glover [1964]). It is shown that a simple iterational process gives the optimal integer solution in a finite number of steps. It is then shown that any cone problem with bounded rational solution can be transformed to the bounding form and hence solved by the outlined method. Some extensions to more than n constraints are discussed and a numerical example is shown to solve a bigger problem.

CS-TR-68-102

Report Number: CS-TR-68-103

Institution: Stanford University, Department of Computer Science

Title: Lexical insertion in transformational grammar

Author: Friedman, Joyce

Author: Bredt, Thomas H.

Date: June 1968

Abstract: In this paper, we describe the lexical insertion process for generative transformational grammars. We also give detailed descriptions of many of the concepts in transformational theory. These include the notions of complex symbol, syntactic feature (particularly contextual feature), redundancy rule, tests for pairs of complex symbols, and change operations that may be applied to complex symbols. Because of our general interpretation of redundancy rules, we define a new complex symbol test known as compatibility. This test replaces the old notion of nondistinctness. The form of a lexicon suitable for use with a generative grammar is specified. In lexical insertion, vocabulary words and associated complex symbols are selected from a lexicon and inserted at lexical category nodes in the tree. Complex symbols are lists of syntactic features. The compatibility of a pair of complex symbols and the analysis procedure used for contextual features are basic in determining suitable items for insertion. Contextual features (subcategorization and selectional) have much in common with the structural description for a transformation and we use the same analysis procedure for both. A problem encountered in the insertion of a complex symbol that contains selectional features is side effects. We define the notion of side effects and describe how these effects are to be treated. The development of the structure of the lexicon and the lexical insertion algorithm has been aided by a system of computer programs that enable the linguist to study transformational grammar. In the course of this development, a computer program to perform lexical insertion was written. Results obtained using this program with fragments of transformational grammar are presented. The paper concludes with suggestions for extensions of this work and a discussion of interpretations of transformational theory that do not fit immediately into our framework.

CS-TR-68-103

Report Number: CS-TR-68-107

Institution: Stanford University, Department of Computer Science

Title: A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration

Author: Jenkins, M. A.

Author: Traub, Joseph F.

Date: August 1968

Abstract: We introduce a new three-stage process for calculating the zeros of a polynomial with complex coefficients. The algorithm is similar in spirit to the two-stage algorithms studied by Traub in a series of papers. The algorithm is restriction free, that is, it converges for any distribution of zeros. A proof of global convergence is given. Z eros are calculated in roughly increasing order of magnitude to avoid deflation instability. Shifting is incorporated in a natural and stable way to break equimodularity and speed convergence. The three stages use no shift, a fixed shift, and a variable shift, respectively. To obtain additional insight we recast the problem and algorithm into matrix form. The third stage is inverse iteration with the companion matrix, followed by generalized Rayleigh iteration. A program implementing the algorithm was written in a dialect of ALGOL 60 and run on Stanford University's IBM 360/67. The program has been extensively tested and testing is continuing. For polynomials with complex coefficients and of degrees ranging from 20 to 50, the time required to calculate all zeros averages $8n^2$ milliseconds. Timing information and a numerical example are provided. A description of the implementation, an analysis of the effects of finite-precision arithmetic, an ALGOL 60 program, the results of extensive testing, and a second program which clusters the zeros and provides a posteriori error bounds will appear elsewhere.

CS-TR-68-107

Report Number: CS-TR-68-109

Institution: Stanford University, Department of Computer Science

Title: A computer system for writing and testing transformational grammars: final report

Author: Friedman, Joyce

Date: September 1968

Abstract: A comprehensive system for transformational grammar has been designed and is being implemented on the IBM 360/67 computer. The system deals with the transformational model of syntax, along the lines of Chomsky's "Aspects of the Theory of Syntax." The major innovations include a full and formal description of the syntax of a transformational grammar, a directed random phrase structure generator, a lexical insertion algorithm, and a simple problem-oriented programming language in which the algorithm for application of transformations can be expressed. In this paper we present the system as a whole, first discussing the philosophy underlying the development of the system, then outlining the system and discussing its more important special features. References are given to papers which consider particular aspects of the system in detail.

CS-TR-68-109

Report Number: CS-TR-68-110

Institution: Stanford University, Department of Computer Science

Title: ALGOL W (revised)

Author: Bauer, Henry R.

Author: Becker, Sheldon I.

Author: Graham, Susan L.

Author: Floyd, Robert W.

Author: Forsythe, George E.

Author: Satterthwaite, Edwin H.

Date: September 1969

Abstract: "A Contribution to the Development of ALGOL" by Niklaus Wirth and C. A. R. Hoare [Comm. ACM, v.9, no. 6 (June 1966), pp. 413-431] was the basis for a compiler developed for the IBM 360 at Stanford University. This report is a description of the implemented language, ALGOL W. Historical background and the goals of the language may be found in the Wirth and Hoare paper.

CS-TR-68-110

Report Number: CS-TR-68-111

Institution: Stanford University, Department of Computer Science

Title: Analysis in transformational grammar

Author: Friedman, Joyce

Author: Martner, Theodore S.

Date: August 1968

Abstract: In generating sentences by means of a transformational grammar, it is necessary to analyze trees, testing for the presence or absence of various structures. This analysis occurs at two stages in the generation process -- during insertion of lexical items (more precisely, in testing contextual features), and during the transformation process, when individual transformations are being tested for applicability. In this paper we describe a formal system for the definition of tree structure of sentences. The system consists of a formal language for partial or complete definition of the tree structure of a sentence, plus an algorithm for comparison of such a definition with a tree. It represents a significant generalization of Chomsky's notion of "proper analysis", and is flexible enough to be used within any transformational grammar which we have seen.

CS-TR-68-111

Report Number: CS-TR-68-112

Institution: Stanford University, Department of Computer Science

Title: A control language for transformational grammar

Author: Friedman, Joyce

Author: Pollack, Bary W.

Date: August 1968

Abstract: Various orders of application of transformations have been considered in transformational grammar, ranging from unorder to cyclical orders involving notions of "lowest sentence" and of numerical indices on depth of embedding. The general theory of transformational grammar does not yet offer a uniform set of "traffic rules" which are accepted by most linguists. Thus, in designing a model of transformational grammar, it seems advisable to allow the specification of the order and point of application of transformations to be a proper part of the grammar. In this paper we present a simple control language designed to be used by linguists for this specification. In the control language the user has the ability to: 1. Group transformations into ordered sets and apply transformations either individually or by transformation set. 2. Specify the order in which the transformation sets are to be considered. 3. Specify the subtrees in which a transformation set is to be applied. 4. Allow the order of application to depend on which transformations have previously modified the tree. 5. Apply a transformation set either once or repeatedly. In addition, since the control language has been implemented as part of a computer system, the behavior of the transformations may be monitored giving additional information on their operation. In this paper we present the control language and examples of its use. Discussion of the computer implementation will be found in [Pollack, B.W. The Control Program and Associated Subroutines. Stanford University. Computer Science Department. Computational Linguistics Project. Report no. AF-28. June 1968.].

CS-TR-68-112

Report Number: CS-TR-68-113

Institution: Stanford University, Department of Computer Science

Title: The impact of storage management on plex processing language implementation

Author: Hansen, Wildred J.

Date: July 1969

Abstract: A plex processing system is implemented within a set of environments whose relationships are vital to the system's time/space efficiency: Data Environment Stack Structures Data Structures Subroutine Environment Routine Linkage Variable Binding Storage Management Environment Memory Organization for Allocation Storage Control This paper discusses these environments and their relationships in detail. For each environment there is some discussion of alternative implementation techniques, the dependence of the implementation on the hardware, and the dependence of the environment on the language design. In particular, two language features are shown to affect substantially the environment design: variable length plexes and 'release' of active plexes. Storage management is complicated by the requirement for variable length plexes, but they can substantially reduce memory requirements. If inactive plexes are released, a garbage collector can be avoided; but considerable tedious programming may be required to maintain the status of each plex. Many plex processing systems store numbers in strange formats and compile arithmetic operations as subroutine calls, thus handicapping the computer on the only operations it does well. Careful coordination of the system environments can permit direct numeric computation, that is, a single instruction for each arithmetic operation. This paper considers with each environment, the requirements for direct numeric computation. To explore the techniques discussed, a collection of environments called Swym was implemented. This system permits variable length plexes and compact lists. The latter is a list representation requiring less space than chained lists because pointers to the elements are stored in consecutive words. In Swym, a list can be partly compact and partly chained. The garbage collector converts chained lists into compact lists when possible. Swym has careful provision for direct numeric computation, but no compiler has been built. To illustrate Swym, an interpreter was implemented for a small language similar to LISP 1.5. Details of Swym and the langauge are in a series of appendices.

CS-TR-68-113

Report Number: CS-TR-68-114

Institution: Stanford University, Department of Computer Science

Title: Calgen - an interactive picture calculus generation system

Author: George, James E.

Date: December 1968

Abstract: A sub-set of the Picture Calculus was implemented on the IBM 360/75 to experiment with the proposed data structure, to study the capability of PL/1 for implementing the Picture Calculus and to evaluate the usefulness of drawing pictures with this formalized language. The system implemented is referred to as Calgen. Like many other drawing proggrams, Calgen utilizes a graphic display console; however, it differs from previous drawing systems in one major area, namely, Calgen retains structure information. Since the Picture Calculus is highly structured, Calgen retains structure information, and only scope images where convenient; further, these scope images saved may be altered by changing the structure information. The only reason scope images are saved by Calgen is to avoid regeneration of a previously generated picture.

CS-TR-68-114

Report Number: CS-TR-68-115

Institution: Stanford University, Department of Computer Science

Title: Programmers manual for a computer system for transformational grammar

Author: Friedman, Joyce

Author: Bredt, Thomas H.

Author: Doran, Robert W.

Author: Martner, Theodore S.

Author: Pollack, Bary W.

Date: August 1968

Abstract: This volume provides programming notes on a computer system for transformational grammar. The important ideas of the system have been presented in a series of reports which are listed in Appendix B; this document is the description of the system as a program. It is intended for programmers who might wish to maintain, modify or extend the system.

CS-TR-68-115

Report Number: CS-TR-68-119

Institution: Stanford University, Department of Computer Science

Title: MPL: Mathematical Programming Language

Author: Bayer, Rudolf

Author: Bigelow, James H.

Author: Dantzig, George B.

Author: Gries, David J.

Author: McGrath, Michael B.

Author: Pinsky, Paul D.

Author: Schuck, Stephen K.

Author: Witzgall, Christoph

Date: May 1968

Abstract: The purpose of MPL is to provide a language for writing mathematical programming algorithms that will be easier to write, to read, and to modify than those written in currently available computer languages. It is believed that the writing, testing, and modification of codes for solving large-scale linear programs will be a less formidable undertaking once MPL becomes available. It is hoped that by the Fall of 1968, work on a compiler for MPL will be well underway.

CS-TR-68-119

Report Number: CS-TR-69-120

Institution: Stanford University, Department of Computer Science

Title: MUTANT 0.5: an experimental programming language

Author: Satterthwaite, Edwin H.

Date: February 1969

Abstract: A programming language which continues the extension and simplification of ALGOL 60 in the direction suggested by EULER is defined and described. Techniques used in an experimental implementation of that language, called MUTANT 0.5, are briefly summarized. The final section of this report is an attempt to assess the potential value of the approach to procedural programming language design exemplified by MUTANT 0.5. Implementation and use of the experimental system have indicated a sufficient number of conceptual and practical problems to suggest that the general approach is of limited value; however, a number of specific features were found to be convenient, useful, and adaptable to other philosophies of language design.

CS-TR-69-120

Report Number: CS-TR-69-121

Institution: Stanford University, Department of Computer Science

Title: Accurate bounds for the eigenvalues of the Laplacian and applications to rhombical domains

Author: Moler, Cleve B.

Date: February 1969

Abstract: We deal with the eigenvalues and eigenfunctions of Laplace's differential operator on a bounded two-dimensional domain G with zero values on the boundary. The paper describes a new technique for determining the coefficients in the expansion of an eigenfunction in terms of particular eigenfunctions of the differential operator. The coefficients are chosen to make the sum of the expansion come close to satisfying the boundary conditions. As an example, the eigenvalues and eigenfunctions are determined for a rhombical membrane.

CS-TR-69-121

Report Number: CS-TR-69-122

Institution: Stanford University, Department of Computer Science

Title: Heuristic analysis of numerical variants of the Gram-Schmidt orthonormalization process

Author: Mitchell, William C.

Author: McCraith, Douglas L.

Date: February 1969

Abstract: The Gram-Schmidt orthonormalization process is a fundamental formula of analysis which is notoriously unstable computationally. This report provides a heuristic analysis of the process, which shows why the method is unstable. Formulas are derived which describe the propagation of round-off error through the process. These formulas are supported by numerical experiments. These formulas are then applied to a computational variant of a basic method proposed by John R. Rice, and this method is shown to offer significant improvement over the basic algorithm. This finding is also supported by numerical experiment. The formulas for the error propagation are then used to produce a linear corrector for the basic Gram-Schmidt process, which shows significant improvement over both previous methods, but at the cost of slightly more computations.

CS-TR-69-122

Report Number: CS-TR-69-124

Institution: Stanford University, Department of Computer Science

Title: Matrix decompositions and statistical calculations

Author: Golub, Gene H.

Date: March 1969

Abstract: Several matrix decompositions which are of some interest in statistical calculations are presented. An accurate method for calculating the canonical correlation is given.

CS-TR-69-124

Report Number: CS-TR-69-125

Institution: Stanford University, Department of Computer Science

Title: Grammatical complexity and inference

Author: Feldman, Jerome A.

Author: Gips, James

Author: Horning, James J.

Author: Reder, Stephen

Date: June 1969

Abstract: The problem of inferring a grammar for a set of symbol strings is considered and a number of new decidability results obtained. Several notions of grammatical complexity and their properties are studied. The question of learning the least complex grammar for a set of strings is investigated leading to a variety of positive and negative results. This work is part of a continuing effort to study the problems of representation and generalization through the grammatical inference question. Appendices A and B and Section 2a.0 are primarily the work of Reder, Sections 2b and 3d of Horning, Section 4 and Appendix C of Gips, and the remainder the responsibility of Feldman.

CS-TR-69-125

Report Number: CS-TR-69-126

Institution: Stanford University, Department of Computer Science

Title: Complementary spanning trees

Author: Dantzig, George B.

Date: March 1969

Abstract: Given a network G whose arcs partition into non-overlapping 'clubs' (sets) $R_i$, D. Ray Fulkerson has considered the problem of constructing a spanning tree such that no two of its arcs belong to (represent) the same club and has stated necessary and sufficient conditions for such trees to exist. When each club $R_i$ consists of exactly two arcs, we shall refer to each of the arc pair as the 'complement' of the other, and the representative tree as a complementary tree. Our objective is to prove the following theorem: If there exists one complementary tree, there exists at least two.

CS-TR-69-126

Report Number: CS-TR-69-128

Institution: Stanford University, Department of Computer Science

Title: The method of odd/even reduction and factorization with application to Poisson's equation

Author: Buzbee, B. L.

Author: Golub, Gene H.

Author: Nielson, C. W.

Date: April 1969

Abstract: Several algorithms are presented for solving block tridiagonal systems of linear algebraic equations when the matrices on the diagonal are equal to each other and the matrices on the subdiagonals are all equal to each other. It is shown that these matrices arise from the finite difference approximation to certain elliptic partial differential equations on rectangular regions. Generalizations are derived for higher order equations and non-rectangular regions.

CS-TR-69-128

Report Number: CS-TR-69-129

Institution: Stanford University, Department of Computer Science

Title: Research in the Computer Science Department, Stanford University

Author: Miller, William F.

Date: April 1969

Abstract: The research program of the Computer Science Department can perhaps be best summarized in terms of its research projects. The chart on the following page lists the projects and the participation by faculty and students. Two observations should be made to complete the picture. Within the Artificial Intelligence Project, the Stanford Computation Center, the SLAC Computation Group, and the INFO project, there are a large number of highly competent professional computer scientists who add greatly to the total capability of the campus. Also, there are a number of projects in other schools or departments which are making significant contributions to computer science. These, too, add to the total computer environment. Summarized by Professor W. F. Miller.

CS-TR-69-129

Report Number: CS-TR-69-134

Institution: Stanford University, Department of Computer Science

Title: Linear least squares and quadratic programming

Author: Golub, Gene H.

Author: Saunders, Michael A.

Date: May 1969

Abstract: Several algorithms are presented for solving linear least squares problems; the basic tool is orthogonalization techniques. A highly accurate algorithm is presented for solving least squares problems with linear inequality constraints. A method is also given for finding the least squares solution when there is a quadratic constraint on the solution.

CS-TR-69-134

Report Number: CS-TR-69-135

Institution: Stanford University, Department of Computer Science

Title: CIL: Compiler Implementation Language

Author: Gries, David

Date: May 1969

Abstract: This report is a manual for the proposed Compiler Implementation Language, CIL. It is not an expository paper on the subject of compiler writing or compiler-compilers. The language definition may change as work progresses on the project.

CS-TR-69-135

Report Number: CS-TR-69-137

Institution: Stanford University, Department of Computer Science

Title: Fixed points of analytic functions

Author: Henrici, Peter

Date: July 1969

Abstract: A continuous mapping of a simply connected, closed, bounded set of the euclidean plane into itself is known to have at least one fixed point. It is shown that the usual condition for the fixed point to be unique, and for convergence of the iteration sequence to the fixed point, can be relaxed if the mapping is defined by an analytic function of a complex variable.

CS-TR-69-137

Report Number: CS-TR-69-141

Institution: Stanford University, Department of Computer Science

Title: Bounds for the error of linear systems of equations using the theory of moments

Author: Dahlquist, Germund

Author: Eisenstat, Stanley C.

Author: Golub, Gene H.

Date: October 1969

Abstract: Consider the system of linear equations $A\underset ~\to x = \underset ~\to b$ where A is an n$\times$n real symmetric, positive definite matrix and $\underset ~\to b$ is a known vector. Suppose we are given an approximation to $\underset ~\to x$, $\underset ~\to \xi$, and we wish to determine upper and lower bounds for $\Vert \underset ~\to x\ - \underset ~\to \xi \Vert$ where $\Vert ...\Vert$ indicates the euclidean norm. Given the sequence of vectors ${\{ {\underset ~\to r}_i \} }^{k}_{i=0}$ where ${\underset ~\to r}_i\ = A{\underset ~\to r}_{i-1}$ and ${\underset ~\to r}_o\ = \underset ~\to b -A\underset ~\to \xi$, it is shown how to construct a sequence of upper and lower bounds for $\Vert \underset ~\to x\ - \underset ~\to \xi \Vert$ using the theory of moments. In addition, consider the Jacobi algorithm for solving the system $\underset ~\to x\ = M\underset ~\to x +\underset ~\to b \underline{viz.} {\underset ~\to x}_{i+1} = M{\underset ~\to x}_i +\underset ~\to b$. It is shown that by examining ${\underset ~\to \delta}_i\ = {\underset ~\to x}_{i+1} - {\underset ~\to x}_i , it is possible to construct upper and lower bounds for $\Vert {\underset ~\to x}_i -\underset ~\to x \Vert$.

CS-TR-69-141

Report Number: CS-TR-69-142

Institution: Stanford University, Department of Computer Science

Title: Stationary values of the ratio of quadratic forms subject to linear constraints

Author: Golub, Gene H.

Author: Underwood, Richard R.

Date: November 1969

Abstract: Let A be a real symmetric matrix of order n, B a real symmetric positive definite matrix of order n, and C an n$\times$p matrix of rank r with r $\leq$ p < n. We wish to determine vectors $\underset ~\to x$ for which ${\underset ~\to x}^T\ A\underset ~\to x\ / {\underset ~\to x}^T\ B\underset ~\to x$ is stationary and $C^T \underset ~\to x\ = \underset ~\to \Theta$, the null vector. An algorithm is given for generating a symmetric eigensystem whose eigenvalues are the stationary values and for determining the vectors $\underset ~\to x$. Several Algol procedures are included.

CS-TR-69-142

Report Number: CS-TR-69-144

Institution: Stanford University, Department of Computer Science

Title: The maximum and minimum of a positive definite quadratic polynomial on a sphere are convex functions of the radius

Author: Forsythe, George E.

Date: July 1969

Abstract: It is proved that in euclidean n-space the maximum M($\rho$) and minimum m($\rho$) of a fixed positive definite quadratic polynomial Q on spheres with fixed center are both convex functions of the radius $\rho$ of the sphere. In the proof, which uses elementary calculus and a result of Forsythe and Golub, $m^" (\rho) and M^" (\rho)$ are shown to exist and lie in the interval [$2{\lambda}_1 ,2{\lambda}_n$], where ${\lambda}_i$ are the eigenvalues of the quadratic form of Q. Hence $m^" (\rho) > 0 and M^" (\rho) > 0$.

CS-TR-69-144

Report Number: CS-TR-69-145

Institution: Stanford University, Department of Computer Science

Title: Methods of search for solving polynomial equations

Author: Henrici, Peter

Date: December 1969

Abstract: The problem of determining a zero of a given polynomial with guaranteed error bounds, using an amount of work that can be estimated a priori, is attacked here by means of a class of algorithms based on the idea of systematic search. Lehmer's "machine method" for solving polynomial equations is a special case. The use of the Schur-Cohn algorithm in Lehmer's method is replaced by a more general proximity test which reacts positively if applied at a point close to a zero of a polynomial. Various such tests are described, and the work involved in their use is estimated. The optimality and non-optimality of certain methods, both on a deterministic and on a probabilistic basis, are established.

CS-TR-69-145