Search

Comments on author M.L. Patrick's paper related to numerical mathematics. Suggestion of a modification on parallel algorithm.

This paper modifies an earlier algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. The algorithms considered in this paper perform limited search and, accordingly, do not necessarily result in globally optimal solutions. However, the greater search effort needed to obtain a globally optimal solution for complex decision tables is usually not justified by sufficient savings in execution time. There is an analogy between the problem of converting decision tables into efficient flowcharts and the well-understood problem in information theory of noiseless coding. The results of the noiseless coding literature are used to explore the limitations of algorithms used to solve the decision table problem. The analogy between the two problems is also used to develop improvements to the information algorithm in extending the depth of search under certain conditions and in proposing additional conditions to be added to the decision table. Finally, the information algorithm is compared with an algorithm proposed in a recent paper by Verhelst. [ABSTRACT FROM AUTHOR]

The article presents information on professional activities within the Association for Computing Machines (ACM). ACM Southeastern Regional Meeting will be conducted on April 18-20, the ACM Southeastern Region will hold a meeting at the Sheraton-Nashville Hotel in Nashville, Tennessee. The Association for Computing Machinery will sponsor the Sixth International Users Conference on May 14-17 at the Sheraton-Anaheim Hotel in Anaheim California. Coast Community. The Boy Scouts of America (BSA) recently published a booklet for use in its merit badge program on Computing. BSA is now looking for computer professionals to help Scouts attain the required skilk for this badge interested persons should contact their local Boy Scout offices.

In this paper the Ritz-Trefftz algorithm is applied to the computer solution of the state regulator problem. The algorithm represents a modification of the Ritz direct method and is designed to improve the speed of solution and the storage requirements to the point where real-time implementation becomes feasible. The modification is shown to be more stable computationally than the traditional Ritz approach. The first concern of the paper is to describe the algorithm and establish its properties as a valid and useful numerical technique. In particular such useful properties as definiteness and reasonableness of condition are established for the method. The second part of the paper is devoted to a comparison of the new techniques with the standard procedure of numerically integrating a matrix Riccati equation to determine a feedback matrix. The new technique is shown to be significantly faster for comparable accuracy. [ABSTRACT FROM AUTHOR]

STAGE2 is the second level of a bootstrap sequence which is easily implemented on any computer. It is a flexible, powerful macro processor designed specifically as a tool for constructing machine-independent software. In this paper the features provided by STAGE2 are summarized, and the implementation techniques which have made it possible to have STAGE2 running on a new machine with less than one man-week of effort are discussed. The approach has been successful on over 15 machines of widely varying characteristics. [ABSTRACT FROM AUTHOR]

A previous paper presented an efficient algorithm, called the Recomputation Algorithm, for evaluating a rational expression to within any desired tolerance on a computer which performs variable-precision arithmetic operations. The Recomputation Algorithm can be applied to expressions involving any variable-precision operations having O(10-... + Σ ∣ε∣) error bounds, where p denotes the operation's precision and ε, denotes the error in the operation's with argument. This paper presents an efficient variable-precision exponential operation with an error bound of the above order. Other operations, such as log, sin, and cos, which have simple series expansions, can be handled similarly. [ABSTRACT FROM AUTHOR]

This paper introduces the notion of usage counts, shows how usage counts can be developed by algorithms that eliminate redundant computations, and describes how usage counts can provide the basis for register allocation. The paper compares register allocation based on usage counts to other commonly used register allocation techniques, and presents evidence which shows that the usage count technique is significantly better than these other techniques. [ABSTRACT FROM AUTHOR]

Sequencing to minimize mean finishing time (or mean time in system) is not only desirable to the user, but it also tends to minimize at each point in time the storage required to hold incomplete tasks. In this paper a deterministic model of independent tasks is introduced and new results are derived which extend and generalize the algorithms known for minimizing mean finishing time. In addition to presenting and analyzing new algorithms it is shown that the most general mean-finishing-time problem for independent tasks is polynomial complete, and hence unlikely to admit of a non-enumerative solution. [ABSTRACT FROM AUTHOR]

This paper presents a new approach to the analysis of performance of the various key-to-address transformation methods. In this approach the keys in a file arc assumed to have been selected from the key space according to a certain probabilistic selection algorithm. All files with the same number of keys selected from this key space will be suitably weighted in accordance with the algorithm, and the average performance of the transformation methods on these files will be used as the potential of these methods. Using this analysis, methods with the same overall performance can be classified and key distributions partial to certain transformations can be identified. All this can be done analytically. The approach is applied to a group of transformation methods using files whose keys are selected randomly. [ABSTRACT FROM AUTHOR]

This paper discusses the multiplication of conformable sequences of row vectors, column vectors, and square matrices. The minimum time required to evaluate such products on ordinary serial computers as well as parallel computers is discussed. Algorithms are presented which properly parse suck matrix sequences subject to the constraints of the machine organization. [ABSTRACT FROM AUTHOR]

In list processing there is typically a growing demand for space during program execution. This paper examines the practical implications of this growth within a virtual memory computer system, proposes two new garbage collection techniques for virtual memory systems, and compares them with traditional methods by discussion and by simulation. [ABSTRACT FROM AUTHOR]

This paper presents a canonical form for context-sensitive derivations and a parsing algorithm which finds each context-sensitive analysis once and only once. The amount of memory required by the algorithm is essentially no more than that required to store a single complete derivation. In addition, a modified version of the basic algorithm is presented which blocks infinite analyses for grammars which contain loops. The algorithm is also compared with several previous parsers for context-sensitive grammars and general rewriting systems, and the difference between the two types of analyses is discussed. The algorithm appears to be complementary to an algorithm by S. Kuno in several respects, including the space-time trade-off and the degree of context dependence involved. [ABSTRACT FROM AUTHOR]

The article presents comments on several algorithms. The algorithms offer information on factorial analysis of variance, shortest-path forest with topological ordering, permanent function of a square matrix I and II, generation of random permutations, complex error function, associated legendre functions of the first kind for real or imaginary arguments, computation of Fourier coefficients, generalized least squares fit by orthogonal polynomials and generation of permutations in pseudolexicographic order.

This article discusses various issues related to the three-dimensional plot programming and algorithm 483. PLOT3D will accept three-dimensional data in various forms, rotate it in three-space, and plot the projection of the resulting figure onto the x-y plane. Those lines or portions of lines that should be hidden by previous lines are masked. Each call to PLOT3D causes one line to be plotted. A line consists of a sequence of points in three-space that will be connected using linear interpolation between adjacent points. This sequence of points is specified by three sequences of real numbers, the x, y, and z components of each point. Each of these sequences of real numbers can be specified either as being equally spaced, and therefore denoted by an initial value and an increment, or as being contained in a real array. PLOT3D attempts to minimize plotter movement by beginning at the alternate end of successive lines. A more detailed description of the parameters is contained in the comments at the beginning of the program listing. This routine was developed at the Applied Research Laboratories on their Control Data Corp. 3200 computer system.

This paper presents the goals and organization of a course about programming designed to provide entering students in a graduate program with a cultural enrichment in their professional lives. The students are expected to have taken at least two programming courses prior to this one and, therefore, to be familiar with at least two programming languages, both as students and users. Teaching someone how to program is similar to teaching him to play a musical instrument; neither skill can be taught—they must be learned. However, the teacher still serves several vital purposes: to present a set of rules for producing well-formed utterances; to offer numerous demonstrations of his own skill; and to function as an involved critic. Finally, the teacher is the source of information about the process in which the student is involved. [ABSTRACT FROM AUTHOR]

In certain data base organization schemes the cost per access may increase due to structural inefficiencies caused by updates. By reorganizing the data base the cost per access may be reduced. However, the high cost of a reorganization prohibits frequent reorganizations. This paper examines strategies for selecting the optimum reorganization points. [ABSTRACT FROM AUTHOR]

A cellular array is a two-dimensional, checkerboard type interconnection of identical modules (or cells), where each cell contains a few hits of memory and a small amount of combinational logic, and communicates mainly with its immediate neighbors In the array. The chief computational advantage offered by cellular arrays is the improvement in speed achieved by virtue of the possibilities for parallel processing. In this paper it is shown that cellular arrays are inherently well suited for the solution of many graph problems. For example, the adjacency matrix of a graph is easily mapped onto an array; each matrix element is stored in one cell of the array, and typical row and column operations are readily implemented by simple cell logic. A major challenge in the effective use of cellular arrays for the solution of graph problems is the determination of algorithms that exploit the possibilities for parallelism, especially for problems whose solutions appear to be inherently serial. In particular, several parallelized algorithms are presented for the solution of certain spanning tree, distance, and path problems, with direct applications to wire routing, PERT chart analysis, and the analysis of many types of networks. These algorithms exhibit a computation time that in many cases grows at a rate not exceeding log2, n, where n is the number of nodes in the graph. Straight. forward cellular implementations of the well-known serial algorithms for these problems require about n steps, and noncellular implementations require from n2 to n3 steps. [ABSTRACT FROM AUTHOR]

Given the horizontal and vertical projections of a finite binary pattern f, can we reconstruct the original pattern f? In this paper we give a characterization of patterns that ore reconstructable from their projections. Three algorithms ore developed to reconstruct both unambiguous and ambiguous patterns, it is shown that an unambiguous pattern can be perfectly reconstructed in time m × n and that a pattern similar to an ambiguous pattern can also be constructed in time m × n, where m, n are the dimensions of the pattern frame. [ABSTRACT FROM AUTHOR]

That the pattern feature "width as a function of angle" possesses several possible interpretations is demonstrated in this paper, which is a review of the width concept in pattern recognition and the geometrical concept itself. The object of the work is to clarify how the word description can be made precise so that computer algorithms for feature extraction may be obtained; the focus is on theoretical subject matter. The results consist of a set-theoretic definition of width-at-angle, a theorem relating it to the pattern boundary radius vector, and descriptions of alternate widths. All widths are calculated for an illustrative example; graphical and tabular comparisons are given. Substantial variation in width-at-angle magnitude is found. The principal conclusion is that the set-theoretic width-at-angle is a useful pattern feature when it can be easily computed. Further investigation of the information contained in only port of a width function is recommended for cases where computation of width-at-angle is difficult. [ABSTRACT FROM AUTHOR]

ASP is a general purpose Associative Data Structure Package in which an arbitrary number of data items and an arbitrary number of the relationships between these data items may be represented. A special picture language is described which has proved very useful for drawing ASP structures on paper. ASP structures are built and manipulated by means of a series of macro coils, which are outlined in the Appendix. Emphasis is on the philosophy of the system rather than a particular implementation, though sufficient information is included to enable the reader to produce his own implementation of ASP. [ABSTRACT FROM AUTHOR]

Neely has discussed computational error generated by some algorithms used to compute various statistics. In the present paper methods are described which are error-free, simple in concept, and usually less costly in machine time than those mentioned by Neely. [ABSTRACT FROM AUTHOR]

The article presents information on events related to computers and technology. The Association for Computing Machinery (ACM) Joint User Group (JUG) and Council to Advance Programming would hold a workshop on November 7, 1966 in the Garden Lounge of the Del Webb Town House, San Francisco. Major topics would be the purpose and effectiveness of user groups, inter-relationships between user groups, and their relationship to JUG. Scientists, engineers and law enforcement officials throughout the nation were being extended an open invitation to submit papers for presentation at a symposium to study application of science and technology to law enforcement scheduled for March 7-9, 1967. "Systems Approach to Biology" was the theme of the Third Systems Symposium sponsored by the National Science Foundation and Case Institute of Technology. It would be held at Case on October 20-21, 1966. The University of Pittsburgh would hold its second national conference on "Electronic Information Handling" on April 12-14, 1967.

The article presents the periodical's editorial policy of publishing articles related to programming language development, compiler management and construction, numerical methods, and computer algorithms.

The article discusses the computation of rational approximations using existing algorithms. In a recent paper it is shown that minimax logarithmic approximations are optimal for square root calculations, making the minimax logarithmic problem of practical interest. The authors point out how rational approximations which are best with respect to maximum logarithmic error can be computed by existing algorithms. Suppose one wishes to approximate a positive continuous function "f" by a positive rational function R, then the logarithmic error at a point x is log (f(x))-- log (R(x)). The approximation problem is thus equivalent to ordinary approximation of continuous function g = log (f) by log {R).

A new integration algorithm is found, and an implementation is compared with other programmed algorithms. The new algorithm is a step-by-step procedure for solving the initial value problem in ordinary differential equations. It is designed to approximate poles of small integer order in the solutions of the differential equations by continued fractions obtained by manipulating the sums of truncated Taylor series expansions. The new method is compared with the Gragg-Bulirsch-Stoer, and the Taylor series method. The Taylor series method and the new method are shown to be superior in speed and accuracy, while the new method is shown to be most superior when the solution is required near a singularity. The new method can finally be seen to pass automatically through singularities where all the other methods which are discussed will have failed. [ABSTRACT FROM AUTHOR]

Presents the methods for computing the equilibrium distribution of customers in closed queueing networks with exponential servers. Evaluation of expressions for various marginal distributions; Computational algorithms based on two-dimensional iterative techniques; Examination of the storage allocation strategies and order of evaluation.

An algorithm is described for reducing the generalized eigenvalue problem Ax = λBx to an ordinary problem, in case A and B are symmetric hand matrices with B positive definite. If n is the order of the matrix and m the bandwidth, the matrices A and B are partitioned into m-by-m blocks; and the algorithm is described in terms of these blocks. The algorithm reduces the generalized problem to an ordinary eigenvalue problem for a symmetric hand matrix C whose bandwidth is the same as A and B. The algorithm is similar to those of Rutishauser and Schwartz for the reduction of symmetric matrices to band form. The calculation of C requires order n²m operation. The round-off error in the calculation of C is of the same order as the sum of the errors at each of the n2m steps of the algorithm, the latter errors being largely determined by the condition of B with respect to inversion. [ABSTRACT FROM AUTHOR]

An algorithm is described based on Newton's method I which simultaneously approximates all zeros of a polynomial with only real zeros. The algorithm, which is conceptually suitable for parallel computation, determines its own starting values so that convergence to the zeros is guaranteed. Multiple zeros and their multiplicity are readily determined. At no point in the method is polynomial deflation used. [ABSTRACT FROM AUTHOR]

This article presents information on the Association for Computing Machinery's (ACM) Council Meeting that was held on May 14, 15, and 19, 1972. The spring Council Meeting consisted of three sessions. The Sunday evening meeting on May 14 dealt exclusively with AFIPS business; the session on Monday, May 15, was devoted to a report of the ACM financial status, and a critique of the proposed FY73 budget presented by the chairman pro tem of the Finance Committee, Herbert R.J. Grosch. Action items were handled at the Friday, May 19, session. The Council passed a motion that it is the sense of the ACM Council that AFIPS should be a strong and effective society of societies representing the whole information community. A motion to instruct the ACM representatives to AFIPS to strive for an AFIPS constitutional change to provide for only one class of membership in AFIPS failed. The ACM Council instructed its representatives to AFIPS to vote against full membership of Society for Industrial and Applied Mathematics and Instrument Society of America in AFIPS.

Numerical mathematics is viewed as the analysis of continuous algorithms. Four of the components of numerical mathematics are discussed. These are: foundations (finite precision number systems, computational complexity), synthesis and analysis of algorithms, analysis of error, programs and program libraries. [ABSTRACT FROM AUTHOR]

An affirmative partial answer is provided to the question of whether it is possible to program parallel-processor computing systems to efficiently decrease execution time for useful problems. Parallel-processor systems ore multiprocessor systems in which several of the processors con simultaneously execute separate tasks of o single job, thus cooperating to decrease the solution time of a computational problem. The processors have independent instruction counters, meaning that each processor executes its own task program relatively independently of the other processors. Communication between cooperating processors is by means of data in storage shared by oil processors. A program for the determination of the distribution of current in an electrical network was written for a parallel-processor computing system, and execution of this program was simulated. The data gathered from simulation runs demonstrate the efficient solution of this problem, typical of a large class of important problems. It is shown that, with proper programming, solution time when Np processors are applied approaches 1/Np times the solution time for a single processor, while improper programming con actually lead to an increase of solution time with the number of processors. Storage interference and other measures of performance are discussed. Stability of the method of solution was also investigated. [ABSTRACT FROM AUTHOR]

A brief description is given of the implementation technique for the replacement rule of the AMBIT programming language. The algorithm for the "AMBIT scan" and an example of its application are given. The algorithm is applicable to other members of the family of string transformation languages of which AMBIT is a member, and it provides a rationale for the design of the AMBIT language. [ABSTRACT FROM AUTHOR]

The article focuses on an algorithm related to quadrature. FSER1 evaluates the integrals using the Filon quadrature algorithm. The user may request an evaluation of C only, S only, or both C and S. FSER1 contains an automatic error-control feature which selects an integration step size on the basis of an error parameter supplied by the user. The Filon quadrature formulas, truncation error, rounding error, and automatic error control are described in a companion paper by the authors. The calling parameters for this subroutine are defined as follows. F is the name of a FUNCTION subprogram F(X), supplied by the user, which evaluates F(X) appearing in the integrand, EPS is the name for "e" appearing in inequalities. It is used in the error control portion of the algorithm. The error in the computed values of C and S is related to "e" by the inequality. The user must assign a value to EPS before calling FSER1. MAX specifies the maximum number of halvings of the step size that are allowed.

Presents letters to the editor referencing issues published in previous issues of the periodical "Communications of the ACM." Remarks on Syntax specification in computer software; Views on technical meetings; Comments on molecular orbitals.

Presents several letters to the editor commenting on various topics related to the field of computer science. Arguments pertaining to the publication of computer programs; Publication of computer algorithm and programs; Discussion on structured computer programming; Discussion on the computer models of psychopathic behavior.

Analyzes a petroleum blending problem to compare primal and primal-dual decomposition algorithms. Relevance of a substructure to the relative performance of the algorithms; Comparison of the absolute performance of the algorithms with a standard primal-Simplex solution without decomposition.

Describes a technique for triple-precision floating-point arithmetic. Machine with a word length of 48 bits; Derivation of the negative of each number with a bit-by-bit complementing of the binary representation; Description of the multiplication and division algorithms.