January 1974 - Vol. 17 No. 1
Features
Syntax-directed least-errors analysis for context-free languages: a practical approach
A least-errors recognizer is developed informally using the well-known recognizer of Earley, along with elements of Bellman's dynamic programming. The analyzer takes a general class of context-free grammars as drivers, and any finite string as input. Recognition consists of a least-errors count for a corrected version of the input relative to the driver grammar. The algorithm design emphasizes practical aspects which help in programming it.
A fast method for solving a class of tridiagonal linear systems
The solution of linear systems having real, symmetric, diagonally dominant, tridiagonal coefficient matrices with constant diagonals is considered. It is proved that the diagonals of the LU decomposition of the coefficient matrix rapidly converge to full floating-point precision. It is also proved that the computed LU decomposition converges when floating-point arithmetic is used and that the limits of the LU diagonals using floating point are roughly within machine precision of the limits using real arithmetic. This fact is exploited to reduce the number of floating-point operations required to solve a linear system from 8n - 7 to 5n + 2k - 3, where k is much less than n, the order of the matrix. If the elements of the subdiagnals and superdiagonals are 1, then only 4n + 2k - 3 operations are needed. The entire LU decomposition takes k words of storage, and considerable savings in array subscripting are achieved. Upper and lower bounds on k are obtained in terms of the ratio of the coefficient matrix diagonal constants and parameters of the floating-point number system.
Various generalizations of these results are discussed.
A method of bivariate interpolation and smooth surface fitting based on local procedures
A method is designed for interpolating values given at points of a rectangular grid in a plane by a smooth bivariate function z = z(x, y). The interpolating function is a bicubic polynomial in each cell of the rectangular grid. Emphasis is on avoiding excessive undulation between given grid points. The proposed method is an extension of the method of univariate interpolation developed earlier by the author and is likewise based on local procedures.
Tridiagonalization by permutations
Tridiagonalizing a matrix by similarity transformations is an important computational tool in numerical linear algebra. Consider the class of sparse matrices which can be tridiagonalized using only row and corresponding column permutations. The advantages of using such a transformation include the absence of round-off errors and improved computation time when compared with standard transformations. A graph-theoretic algorithm which examines an arbitrary n × n matrix and determines whether or not it can be permuted into tridiagonal form is given. The algorithm requires no arithmetic while the number of comparisons, the number of assignments, and the number of increments are linear in n. This compares very favorably with standard transformation methods. If the matrix is permutable into tridiagonal form, the algorithm gives the explicit tridiagonal form. Otherwise, early rejection will occur.
Computation of Legendre series coefficients
LEGSER approximates the first N + 1 coefficients Bn of the Legendre series expansion of a function ƒ(x) having known Chebyshev series coefficients An. Several algorithms are available for the computation of coefficients An of the truncated Chebyshev series expansion on [-1, 1] ƒ(x) ≃ ∑′Nn=0 AnTn(x), (1) where ∑′ donotes a sum whose first term is halved. The commonly used algorithms are based on the orthogonal property of summation of the Chebyshev polynomials [1]. The application of the analogous property of the Legendre polynomials for the calculation of the coefficients Bn of the expansion ƒ(x) ≃ ∑Nn=0 BnPn(x) (2) is less suitable for practical use since it requires the abscissas and weights of the Gauss-Legendre quadrature formulas [2].
A new family of clipping algorithms is described. These algorithms are able to clip polygons against irregular convex plane-faced volumes in three dimensions, removing the parts of the polygon which lie outside the volume. In two dimensions the algorithms permit clipping against irregular convex windows.
Polygons to be clipped are represented as an ordered sequence of vertices without repetition of first and last, in marked contrast to representation as a collection of edges as was heretofore the common procedure. Output polygons have an identical format, with new vertices introduced in sequence to describe any newly-cut edge or edges. The algorithms easily handle the particularly difficult problem of detecting that a new vertex may be required at a corner of the clipping window.
The algorithms described achieve considerable simplicity by clipping separately against each clipping plane or window boundary. Code capable of clipping the polygon against a single boundary is reentered to clip against subsequent boundaries. Each such reentrant stage of clipping need store only two vertex values and may begin its processing as soon as the first output vertex from the preceeding stage is ready. Because the same code is reentered for clipping against subsequent boundaries, clipping against very complex window shapes is practical.
For perspective applications in three dimensions, a six-plane truncated pyramid is chosen as the clipping volume. The two additional planes parallel to the projection screen serve to limit the range of depth preserved through the projection. A perspective projection method which provides for arbitrary view angles and depth of field in spite of simple fixed clipping planes is described. This method is ideal for subsequent hidden-surface computations.
In his interesting contribution to the study of the conversion of limited-entry decision tables to flowcharts or sequential testing procedures, Verhelst [1] presents two algorithms, one of which is claimed to produce the optimal flowchart with respect to run-time. Unfortunately this minimum run-time algorithm does not always produce the result claimed, as we illustrate by example below.
A numbering system for combinations
It is often necessary to generate the sequence of combinations of s things chosen from among n things, or to generate a random member of this sequence. Various algorithms have been given for these tasks. Algorithm 94 [1] is a good combination generator, and methods for generating a random combination are discussed in [2, pp. 121-125].
