Search

Presents several letters to the editor about the computing machinery. Dissatisfaction with the quality and nature of the average technical paper presented at the Joint Computer Conferences; Comment on the article "One-Pass Compilation of Arithmetic Expressions for a Parallel Processor," by Harold S. Stone; Use of a coordinate system or characteristic indices for the progress of an algorithm.

The article reports on finding all subgraphs of an undirected graph [H]. A maximal complete subgraph is also called clique which refers to a complete subgraph that is not included in any other complete subgraph. According to the authors, a research paper was released wherein descriptions of techniques to find maximal complete subgraphs are provided. The authors discussed two algorithms using a branch-and-bound technique so that there will be no clique. The first algorithm produces cliques in lexicographic order while the second is derived from the first algorithm.

The method of nested multiplication is commonly used in function evaluation routines to evaluate approximation polynomials. New polynomial evaluation methods have been developed in recent years which require fewer multiplications than nested multiplication and may therefore be preferable for use in function evaluation routines. Although some of these methods do not appear to be practically useful because of rounding-error difficulties, several methods of evaluating low-degree polynomials have been found to be satisfactory. Three such methods are described and illustrated. [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]

Presents the author's comments on the paper "A Multiple-Precision Division Algorithm," by C.J. Mifsud, published in the November 1970 issue of the journal "Communications of the ACM." Account of difficulties that arises with the programming and implementation of the algorithm described in the paper; Avoidance of the possibility of overflow in the calculation of trial cipher; Solution to the problems the algorithm described in the paper; Suggestions for additional informative statements that should be inserted in the original algorithm.

A list of a number of natural developments for the field of algebraic manipulation is given. Then the prospects for a general theory of functions defined by ordinary differential equations are discussed. The claim is made that recent developments in mathematics indicate that it should be possible to algorithmically generate many properties of solutions to differential equations. Such a theory is preferable to a less general effort to make algebraic manipulation systems knowledgeable about the usual special functions (e g exponential, hyper geometric) [ABSTRACT FROM AUTHOR]

Describes applications of symbolic algebra systems to problem of general relativity. Derivation of field equations; Petrov classification of a metric; Solution of field equations in the presence of matter; Algebraic difficulties encountered in the study.

Several letters to the editor are presented in response to articles in previous issues including "A Candidate for the Simplest Uncomputable Function," published in a 1965 issue, "More on Rounding in Commercial Applications," published in a 1965 issue, and "On the Double-Precision Square Root Routine" also published in the 1965 issue.

Items can be retrieved from binary trees grown with a form of the Algorithm Quicksort in an average time proportional to log n, where n is the number of items in the tree. The binary trees grown by this algorithm sometimes have some branches longer than others; therefore, it is possible to reduce the average retrieval time by restructuring the tree to make the branches as uniform in length as possible. An algorithm to do this is presented. The use of this algorithm is discussed, and it is compared with another which restructures the tree after each new item is added. [ABSTRACT FROM AUTHOR]

Considers the applications of automated algebraic manipulation which have been made in celestial mechanics. Use of Poisson series; Description of a typical problem in perturbation theory; Requirements of processors for use in celestial mechanics.

Examines automated algebraic simplification from the point of view of a user who needs to comprehend a large expression and from that of a designer who wants to construct a useful and efficient computer system. Techniques akin to substitution; Spectrum of approaches to the design of automatic simplification capabilities in an algebraic manipulation system; Theoretical results related to algebraic manipulation.

An algorithm is displayed which yields the merge orders such that the total read time, defined to be the sum of seek time plus data-transfer time, is minimized for a sort using mass storage. The analysis is parameterized in terms of the ratio of seek time to the time it takes to fill available core with records, and the file size in units of core lengths; and thus it can be applied to any conventional CPU mass storage combination. An explicit formula for total read time is derived, in terms of the parameters, which correlates very well with the total read time calculated using the optimum merge orders yielded by the algorithm. The formula involves the roots of a simple transcendental equation. A short table of these roots is included. Numerical results are graphically displayed for a wide range of the parameters. It is found that the normalized read time for optimum merging on a given hardware configuration is proportional to the file length times the logarithm of the file length. [ABSTRACT FROM AUTHOR]

The article presents various mathematical analysis regarding algorithms. Algorithm 401 procedure generates complex prime numbers while Algorithm 402 procedure sorts mathematical elements into nondescending order. Algorithm 343 contains certain failures during its application to pathological matrices which include incorrect computed eigenvalues resulting to 2 or more percent maximum error. Remarks about Algorithm 372 and 401 are also discussed. Diagrams of the algorithm procedures are also presented.

The downhill method is a numerical method for solving complex equations f(z) = 0 on which the only restriction is that the function w = f(z) must be analytical. An introduction to this method is given and a critical review of relating literature is presented. Although in theory the method always converges, it is shown that a fundamental dilemma exists which may cause o breakdown in practical applications. To avoid this difficulty and to improve the rate of convergence toward a root, some modifications of the original method are proposed and a program (FORTRAN) based on the modified method is given in Algorithm 365. Some numerical examples are included. [ABSTRACT FROM AUTHOR]

Algorithms for computing the resultant of two polynomials in several variables, a key repetitive step of computation in solving systems of polynomial equations by elimination, are studied. Determining the best algorithm for computer implementation depends upon the extent to which extraneous factors are introduced, the extent of propagation of errors caused by truncation of real coeffcients, memory requirements, and computing speed. Preliminary considerations narrow the choice of the best algorithm to Bezout's determinant and Collins' reduced polynomial remainder sequence (p.r.s.) algorithm. Detailed tests performed on sample problems conclusively show that Bezout's determinant is superior in all respects except for univariate polynomials, in which case Collins' reduced p.r.s. algorithm is somewhat faster. In particular Bezout's determinant proves to be strikingly superior in numerical accuracy, displaying excellent stability with regard to round-off errors. Results of tests ore reported in detail. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The article reports on several algorithms with their specific computational dynamics. A specific algorithm with its corresponding formula which provides for the procedure for deriving a certain value is provided. The algorithms include, among others, algorithm 290 for linear equations, algorithm 291 for logarithm of gamma functions, and algorithm 178 for direct search. Moreover, the algorithms are written in the ALGOL 60 Reference Language, Standard FORTRAN, and Basic FORTRAN. Specific instructions on how to submit algorithms are also included.

A programming language is described which is applicable to problems conveniently described by transformation rules. By this is meant that patterns may be prescribed, each being associated with a skeleton, so that a series of such pairs may be searched until a pattern is found which matches an expression to be transformed. The conditions for a match are governed by a code which also allows subexpressions to be identified and eventually substituted into the corresponding skeleton. The primitive patterns and primitive skeletons are described, as well as the principles which allow their elaboration into more complicated patterns and skeletons. The advantages of the language are that it allows one to apply transformation rules to lists and arrays as easily as strings, that both patterns and skeletons may be defined recursively, and that as a consequence programs may be stated quite concisely. [ABSTRACT FROM AUTHOR]

A medium-scale programming system is written in MAD and FAP on the IBM 7094 to manipulate some of the objects of modern algebra: finite groups, maps and sets of maps, subsets and sets of subsets, constant integers and truth-values. Designed to operate in a time-sharing environment, the system can serve as teacher's aid to the undergraduate student of modern algebra, as well as for the working scientist or engineer wishing to familiarize himself with the subject. [ABSTRACT FROM AUTHOR]

A method which finds simultaneously all the zeros of a polynomial, developed by H. Rutishauser, has been tested on a number of polynomials with real coefficients. This slowly converging method (the Quotient-Difference (Q-D) algorithm) provides starting values for a Newton or a Bairstow algorithm for more rapid convergence. Necessary and sufficient conditions for the existence of the Q-D scheme ore not completely known; however, failure may occur when zeros have equal, or nearly equal magnitudes. Success was achieved, in most of the cases tried, with the failures usually traceable to the equal magnitude difficulty. In some cases, computer roundoff may result in errors which spoil the scheme. Even if the Q-D algorithm does not give all the zeros, it will usually find a majority of them. [ABSTRACT FROM AUTHOR]

Describes how a series of four problems of increasing difficulty were solved using a set of subroutines created to allow algebraic manipulations on the IBM 7094 computer. Representation of algebraic expressions; Notation and memory organization; Descriptions of routines which were developed for algebraic manipulation.

The assignment problem, together with Munkres proposed algorithm for its solution in square matrices, is presented first. Then the authors develop an extension of this algorithm which permits a solution for rectangular matrices. Timing results obtained by using an adapted version of Silver's Algol procedure are discussed, and a relation between solution time and problem size is given. [ABSTRACT FROM AUTHOR]

A technique for using a digital computer to draw both ordinary and time-lag root locus diagrams is described. Ordinary diagrams are drawn much faster and more accurately than ever before. Time-lag diagrams, which had been impossible to obtain, are drawn with the same speed and accuracy as ordinary diagrams. [ABSTRACT FROM AUTHOR]