Research and Advances

This algorithm uses a rational variant of the QR transformation with explicit shift for the computation of all of the eigenvalues of a real, symmetric, and tridiagonal matrix. Details are described in [1]. Procedures tred1 or tred3 published in [2] may be used to reduce any real, symmetric matrix to tridiagonal form. Turn the matrix end-for-end if necessary to bring very large entries to the bottom right-hand corner.

An explicit approximate solution ƒ(h)&agr; is given for the equation ƒ(t) = ∫∞0 k(t - &tgr;)ƒ(&tgr;) d&tgr; + g(t), t > 0, (*) where k, g ∈ L1(- ∞, ∞) ∩ L2(-∞, ∞), and where it is assumed that the classical Wiener-Hopf technique may be applied to (*) to yield a solution ƒ ∈ L1(0, ∞) ∩ L2(0, ∞) for every such given g. It is furthermore assumed that the Fourier transforms K and G+ of k and g respectively are known explicitly, where K(x) = ∫∞-∞ exp (ixt)k(t) dt, G+(x) = ∫∞0 exp (ixt)g(t) dt. The approximate solution ƒ(h)&agr; of (*) depends on two positive parameters, h and &agr;. If K(z) and G+(z) are analytic functions of z = x + iy in the region {x + iy : | y | ≤ d}, and if K is real on (-∞, ∞), then | ƒ(t) - ƒ(h)&agr;(t) | ≤ c1 exp (-&pgr;d/h) + c2 exp (-&pgr;d/&agr;) where c1 and c2 are constants. As an example, we compute ƒ(h)&agr;(t), t = 0.2(0.2)1, h = &pgr;/10, &agr; = &pgr;/50, for the case of k(t) = exp(-| t |)/(2&pgr;), g(t) = t4 exp (-3t). The resulting solution is correct to five decimals.

R.P. Brent in his presentation of a modification to the linear quotient algorithm [1] shares the common misconception that dynamic chaining requires larger table entries because of the space required for link fields.

A generalization of a scheme of Hamming for converting a polynomial Pn(x) into a Chebyshev series is combined with a recurrence scheme of Clenshaw for summing any finite series whose terms satisfy a three-term recurrence formula. An application to any two orthogonal expansions Pn(x) = ∑nm=0 amqm(x) = ∑nm=0 AmQm(x) enables one to obtain Am directly from am, m = 0(1)n, by a five-term recurrence scheme.

Dynamic verification of a decision implies that every time the decision is made there is a consistency check performed on the decision using independent hardware and software. The dynamic verification of operating system decisions is used on the PRIME system being designed and constructed at the University of California, Berkeley. PRIME is an experimental time-sharing system which is to have the properties of continuous availability, data privacy, and cost effectiveness. The technique of dynamic verification allows the construction of an operating system which does not make certain decisions improperly even in the presence of a single hardware or software fault. Furthermore, multiple faults lead to unreliable operation only if the faults happen to reinforce each other. On PRIME, dynamic verification is used to ensure that one user's information cannot become available to another user gratuitously even in the presence of a single hardware or software fault. The amount of additional hardware and software required for dynamic verification can be modest.

Two methods for solving the biharmonic equation are compared. One method is direct, using eigenvalue-eigenvector decomposition. The other method is iterative, solving a Poisson equation directly at each iteration.

Most graphics systems using a raster scan output device (CRT or hardcopy) maintain a display file in the XY or random scan format. Scan converters, hardware or software, must be provided to translate the picture description from the XY format to the raster format. Published scan conversion algorithms which are fast will reserve a buffer area large enough to accommodate the entire screen. On the other hand, those which use a small buffer area are slow because they require multiple passes through the XY display file. The scan conversion algorithm described here uses a linked list data structure to process the lines of the drawing in strips corresponding to groups of scan lines. A relatively small primary memory buffer area is used to accumulate the binary image for a group of scan lines. When this portion of the drawing has been plotted, the buffer is reused for the next portion. Because of the list processing procedures used, only a single pass through the XY display file is required when generating the binary image and only a slight increase in execution time over the fully buffered core results. Results show that storage requirements can be reduced by more than 80 percent while causing less than a 10 percent increase in execution time.

This year the whole world celebrates the five-hundredth birthday of Nicolaus Copernicus, the famous Polish astronomer and mathematician. In 1543, Copernicus published his book, Concerning the Revolutions of Celestial Spheres, which described a new theory about the relative physical movements of the earth, the planets, and the sun. It was in direct contradiction with the earth-centered theories which had been established by Ptolemy 1400 years earlier.

With this note I hope to bridge the gap between the adherents of structured programming and the devotees of the unrestricted goto. I describe a style of programming which combines the advantages of structured programming with nearly all the power of the jump.

A counterexample to the supposed optimality of an algorithm for generating schedules for trees of tasks with unequal execution times is presented. A comparison with the “critical path” heuristic is discussed.

This paper describes a parser-generating system (PGS) currently in use on the CDC-6500 computer at Purdue University. The PGS is a Fortran-coded program that accepts a translation grammar as input and constructs from it a compact, machine-coded compiler. In the input translation grammar, each BNF syntactic rule corresponds to a (possibly empty) “code generator” realizable as an assembly language, Fortran or Algol, subroutine that is called whenever that syntactic rule is applied in the parse of a program. Typical one-pass compilers constructed by the PGS translate source programs at speeds approaching 14,000 cards per minute. For an XPL compiler, the parser program and its tables currently occupy 288 words of 60-bit core memory of which 140 words are parsing table entries and 82 words are links to code generators.

Automatic theorem-provers need to be made much more efficient. With this in mind, Slagle has shown how the axioms for partial ordering can be replaced by built-in inference rules when using a particular theorem-proving algorithm based upon hyper-resolution and paramodulation. The new rules embody the transitivity of partial orderings and the close relationship between the ⊂ and ⊆ predicates. A program has been developed using a modified version of these rules. This new theorem-prover has been found to be very powerful for solving problems involving partial orderings. This paper presents a detailed description of the program and a comprehensive account of the experiments that have been performed with it.