Search
Join ACM

Computing Applications

Advertisement

Research and Advances

An algorithm for solving a special class of tridiagonal systems of linear equations

An algorithm is presented for solving a system of linear equations Bu = k where B is tridiagonal and of a special form. This form arises when discretizing the equation - d/dx (p(x) du/dx) = k(x) (with appropriate boundary conditions) using central differences. It is shown that this algorithm is almost twice as fast as the Gaussian elimination method usually suggested for solving such systems. In addition, explicit formulas for the inverse and determinant of the matrix B are given.
Research and Advances

Analysis of boolean program models for time-shared, paged environments

Directed graphs or their associated matrices are frequently used to represent the logical structure of sequences of computer instructions. Such techniques are used and, in addition, data references are represented in a nondirected model. The complete structural specification of a program is represented by a combined model. A transformation of the combined model yields a new model in which additional timing information is also contained. Analysis of these models prior to execution yields information valuable in determining segmentation of instructions and data for a time-shared environment, as well as for initial page loading; during execution, the analysis may be used for “look ahead” control of page turning.
Research and Advances

On coordination reduction and sentence analysis

A class of coordination phenomena in natural languages is considered within the framework of transformational theory. To account for these phenomena it is proposed that certain machinery be added to the syntactic component of a transformational grammar. This machinery includes certain rule schemata, the conditions under which they are to be applied, and conditions determining the sequence of subtrees on which they are to be performed. A solution to the syntactic analysis problem for this class of grammars is outlined. Precise specification of both the generative procedure of this paper and its inverse is given in the form of LISP function definitions.
, , and
Research and Advances

An algorithm for hidden line elimination

The algorithm presented causes the elimination of hidden lines in the representation of a perspective view of concave and convex plane-faced objects on the picture plane. All the edges of the objects are considered sequentially, and all planes which hide every point of an edge are found. The computing time increases roughly as the square of the number of edges. The algorithm takes advantage of a reduced number of concave points and automatically recognizes if only one object with no concave points is considered. In this last case, the result is obtained in a much simpler way.
Research and Advances

Simulation of outpatient appointment systems

An experimental computer program is described which simulates appointment systems employed by outpatient departments of hospitals. Both major kinds of appointment systems—individual and block—can be simulated. The purpose of the Simulator is to enable the user to evaluate the effectiveness of alternative appointment systems in a given clinical environment.
Research and Advances

Organizing matrices and matrix operations for paged memory systems

Matrix representations and operations are examined for the purpose of minimizing the page faulting occurring in a paged memory system. It is shown that carefully designed matrix algorithms can lead to enormous savings in the number of page faults occurring when only a small part of the total matrix can be in main memory at one time. Examination of addition, multiplication, and inversion algorithms shows that a partitioned matrix representation (i.e. one submatrix or partition per page) in most cases induced fewer page faults than a row-by-row representation. The number of page-pulls required by these matrix manipulation algorithms is also studied as a function of the number of pages of main memory available to the algorithm.
and
Research and Advances

Description of FORMAT, a text-processing program

FORMAT is a production program which facilitates the editing and printing of “finished” documents directly on the printer of a relatively small (64k) computer system. It features good performance, totally free-form input, very flexible formatting capabilities including up to eight columns per page, automatic capitalization, aids for index construction, and a minimum of nontext items. It is written entirely in FORTRAN IV.
Research and Advances

Concepts of use in contour map processing

Generalized techniques are developed whose use can simplify the solution of problems relating to contour maps. One of these techniques makes use of the topological properties of contour maps. The topology is represented by a graphical structure in which adjacent contour lines appear as connected nodes. Another generalized technique consists of utilizing geometrical properties to determine the characteristics of straight lines drawn on the contour map. Both of these techniques have been applied to the problem of locating the ground track of an aircraft from elevation readings obtained during a flight.
Research and Advances

Data communications control procedures for the USA standard code for information interchange

This proposed American Standard has been accepted for publication by USA Standards Committee X3, Computers and Information Processing. In order that the final version of the proposed standard reflect the largest public consensus, X3 authorized publication of this document to elicit comment and general public reaction, with the understanding that such a working document is an intermediate result in the standardization process and is subject to change, modification, or withdrawal in part or in whole. Comments should be addressed to the X3 Secretary, Business Equipment Manufacturers Association, 235 East 42 Street, New York, NY 10017.—E. L.
Research and Advances

Coding the Lehmer pseudo-random number generator

An algorithm and coding technique is presented for quick evaluation of the Lehmer pseudo-random number generator modulo 2 ** 31 - 1, a prime Mersenne number which produces 2 ** 31 - 2 numbers, on a p-bit (greater than 31) computer. The computation method is extendible to limited problems in modular arithmetic. Prime factorization for 2 ** 61 - 2 and a primitive root for 2 ** 61 - 1, the next largest prime Mersenne number, are given for possible construction of a pseudo-random number generator of increased cycle length.
, , and
Research and Advances

Extremely portable random number generator

Extremely portable subroutines are sometimes needed for which moderate quality and efficiency suffice. Typically, this occurs for library functions (like random number generation and incore sorting) which are not entirely universal or are not used in a standardized way. The literature on random number generators does not seem to contain an algorithm that meets requirements of this sort. An extremely portable 8-line FORTRAN program is provided which is based on an important paper by Coveyou and MacPherson (1967). Using their methods, Fourier analysis is applied to the probability function for the consecutive n-tuples provided by our generator (with n less than or equal to 4). While the small modulus which must be used to maintain portability prevents the quality of the generator from being high, the generator compares well with the bounds established in the above mentioned paper.
Research and Advances

On arithmetic expressions and trees

A description is given of how a tree representing the evaluation of an arithmetic expression can be drawn in such a way that the number of accumulators needed for the computation can be represented in a straightforward manner. This representation reduces the choice of the best order of computation to a specific problem under the theory of graphs. An algorithm to solve this problem is presented.
Research and Advances

Images from computers and microfilm plotters

Digital computers are widely used for the processing of information and data of all kinds, including the pictorial information contained in photographs and other graphical representations. Efficient conversion facilities for putting graphical information into the computer and retrieving it in graphical form are therefore much needed. One of the most commonly employed devices for obtaining permanent graphical output from digital computers is the microfilm plotter. Regrettably, present models have no provision for producing images with a continuous gray scale or “halftones.” In this note several programming techniques are described for obtaining halftone pictures from a microfilm plotter under the control of a digital computer. Illustrative examples of several methods are given.
Research and Advances

Exclusive simulation of activity in digital networks

A technique for simulating the detailed logic networks of large and active digital systems is described. Essential objectives sought are improved ease and economy in model generation, economy in execution time and space, and a facility for handling simultaneous activities. The main results obtained are a clear and useful separation of structural and behavioral model description, a reduction of manual tasks in converting Boolean logic into a structural model, the elimination of manual processes in achieving exclusive simulation of activity, an event-scheduling technique which does not deteriorate in economy as the event queue grows in length, and a simulation procedure which deals effectively with any mixture of serial and simultaneous activities. The passage of time is simulated in a precise, quantitative fashion, and systems to be simulated may be combinations of synchronous and asynchronous logic. Certain aspects of the techniques described may be used for the simulation of network structures other than digital networks.
Research and Advances

Variable length tree structures having minimum average search time

Sussenguth suggests in a paper (1963) that a file should be organized as a doubly-chained tree structure if it is necessary both to search and to update frequently. Such a structure provides a compromise between the fast search/slow update characteristics of binary searching and the slow search/fast update characteristics of serial searching. His method, however, contains the limiting restriction that all terminal nodes lie on the same level of the tree. This paper considers the effect of relaxing this restriction. First, trees which have the property that a priori the filial set of each node is well defined are studied. It is proved that coding the nodes within each filial set with respect to the number of terminal nodes reachable from each is necessary and sufficient to guarantee minimum average search time. Then the more general case (that is, where the entire structure of the tree is changeable) is treated. A procedure is developed for constructing a tree with a minimum average search time. A simple closed expression for this minimum average search time is obtained as a function of the number of terminal nodes. The storage capacity required to implement the doubly-chained tree structure on a digital computer is also determined. Finally, the total cost of the structure, using Sussenguth's cost criterion, is computed. It is shown that significant improvements in both the average search time and the total cost can be obtained by relaxing Sussenguth's restriction that all terminal nodes lie on the same level of the tree.
Research and Advances

CODAS: a data display system

CODAS, a Customer Oriented Data System, is a user-oriented data retrieval and display system. The command language of the system provides the user with an easy means for specifying data retrieval and display requests. Data is displayed as tables and graphs produced in a format ready for publication. In this paper the statements of the request language and the general system design are described.
, , and
Research and Advances

Some criteria for time-sharing system performance

Time-sharing systems, as defined in this article, are those multiaccess systems which permit a terminal user to utilize essentially the full resources of the system while sharing its time with other terminal users. It is each terminal user's ability to utilize the full resources of the system that makes quantitative evaluation of time-sharing systems particularly difficult. Six criteria are described which have been successfully used to perform first-level quantitative time-sharing system performance evaluation.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More