November 1973 - Vol. 16 No. 11

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.

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.

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.

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.

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.

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 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.

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.

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.