Search

A description is given of a program for computing the solution to a small number of standard numerical analysis problems to any specified accuracy, up to a limit of 2000 correct decimal places. Each computed number is bounded in an interval with a multiple precision midpoint. Arithmetic operations involving these numbers are executed according to interval arithmetic concepts, with non-significant digits automatically discarded. Details are supplied of problem specification and problem computation. [ABSTRACT FROM AUTHOR]

The article presents the procedures for computing, smoothing and interpolating natural splines. Several mathematical formulae with mathematical and numerical analyses are cited. Problems indicating the application of smoothing and interpolating are discussed. The purpose of the procedure is to determine the coefficients in the representation of a natural spline of degrees in terms of a local basis. The procedure is based on algorithms. The parameters maxit should be a positive integer specifying the maximum number of iterations desired in computing the problem. Illustrations in applying such mathematical formulae are offered.

An improved program-synthesizing algorithm based on the algorithm proposed by Waldinger and Lee in 1969 is given In the old algorithm, the program-synthesizing problem is translated into a theorem-proving problem, and a program is obtained by analyzing a proof. For the improved algorithm, the analysis is not necessary, and a program is obtained as soon as the proof is completed. This is achieved by using a modified variable tracing mechanism invented by Green in 1969. The correctness of the Improved algorithm is also proved; i.e. the program thus obtained always satisfies the specification. [ABSTRACT FROM AUTHOR]

The article presents an algorithm for the numerical integration over a finite interval automatically. The algorithm's purpose is to automatically calculate the integral over a finite interval with relative error not exceeding a specified value. It utilizes a basic integration algorithm applied under the control of algorithms which invoke adaptive or nonadaptive subdivision of the range of integration. The subdivision processes will only normally be needed on extremely difficult integrals as the basic algorithm is sufficiently powerful.

The article offers information on a mathematical procedure for constrained optimization. The program aims to identify the maximum of a multivariable, nonlinear function subject to constraints based on the sequential search method of M.J. Box. It has three subroutines such as JCONSX, JCEK1, and JCENT and user supplied subroutines which include JFUNC and JCNTS1. The subroutine argument lists provide the presentation of the communication between the main program and subroutines. A test is conducted to examine the program through various functions computed on a CDC 6400 computer. The search technique process is discussed.

The cubic spline approximation to the fourth-order differential equation yin + p(x)y" + q(x)y' + r(x)y = t(x) is shown to reduce to the solution of a five-term recurrence relationship. For some special cases the approximation is shown to be simply related to a finite difference representation with a local truncation error of order (1/720)δ³y)?. [ABSTRACT FROM AUTHOR]

The paper describes a scheme for symbolic manipulation of index expressions which arise as a by-product of the symbolic manipulation of expressions in the matrix calculi described by the authors in a previous paper. This scheme attempts program optimization by transforming the original algorithm rather than the machine code. The goal is to automatically generate code for handling the tedious address calculations necessitated by complicated data structures. The paper is therefore preoccupied with "indexing by position." The relationship of "indexing by name" and "indexing by position" is discussed. [ABSTRACT FROM AUTHOR]

Most current programming languages treat computation over different classes of objects (e.g. numbers, strings, labels and functions). For correct compilation and execution, the following question then arises: is a program properly constructed so that its operations and operands are compatible? The activity of answering this question is usually called type checking. This paper attempts to isolate the notion of type checking and presents a partial solution to the type checking problem based on the notions of abstraction and application of functions. In particular, a program is mapped into an expression within a decideable subset of the λ-calculus, which characterizes the type relations within the program and eliminates all other information The determination of the type-wise correctness or incorrectness of the program is resolved by reducing its corresponding λ-calculus expression to one of two normal forms, the constant "correct" for a type-wise correct program or the constant "error." An application to type checking in Algol 60 is made, and the attendant problems faced for any notion of type checking are discussed. [ABSTRACT FROM AUTHOR]

This article discusses professor George E. Forsythe's contributions to the establishment of computer science as a recognized discipline. It is generally agreed that he, more than any other man, is responsible for the rapid development of computer science in the world's colleges and universities. His foresight, combined with his untiring efforts to spread the gospel of computing, have had a significant and lasting impact; one might almost regard him as the Martin Luther of the Computer Reformation. His early training and research in numerical analysis was a good blend of theory and practice. Starting in 1948 he worked for the National Bureau of Standards' Institute for Numerical Analysis in Los Angeles, California, where he did extensive programming for the SWAC computer. In 1954 this Institute became part of U.C.L.A. and he put a great deal of energy into the teaching of mathematics and numerical analysis. He also worked on non-numerical problems, such as the tabulation of all possible semi-groups on four elements; at this time, he considered such combinatorial algorithms to be a part of numerical analysis and he regarded automatic programming as another branch. He began to foresee the less obvious implications of programming.

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]

Setting the Reynolds number equal to zero, in a method for solving the Navier-Stokes equations numerically, results in a fast numerical method for biharmonic problems. The equation is treated as a system of two second order equations and a simple soothing process is essential for convergence. An application is made to a crack-type problem. [ABSTRACT FROM AUTHOR]

A simple analysis of some computer-economic factors involved in comparing multimachine installations venus large single machine installations is given, and a mathematical model is derived to assist policy decisions. [ABSTRACT FROM AUTHOR]

An automatic learning capability has been developed and implemented for use with the MULTIPLE (MULTIpurpose Program that LEarns) heuristic tree-searching program, which is presently being applied to resolution theorem-proving in predicate calculus. MULTIPLE's proving program (PP) uses two evaluation functions to guide its search for a proof of whether or not a particular goal is achievable. Thirteen general features of predicate calculus clauses were created for use in the automatic learning of better evaluation functions for PP. A multiple regression program was used to produce optimal coefficients for linear polynomial functions in terms of the features. Also, automatic data-handling routines were written for passing data between the learning program and the proving program, and for analyzing and summarizing results. Data was generally collected for learning (regression analysis) from the experience of PP. A number of experiments were performed to test the effectiveness and generality of the learning program. Results showed that the learning produced dramatic improvements in the solutions to problems which were in the same domain as those used for collecting learning data. Learning was also shown to generalize successfully to domains other than those used for data collection. Another experiment demonstrated that the learning program could simultaneously improve performance on problems in a specific domain and on problems in a variety of domains. Some variations of the learning program were also tested. [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]

This article presents algorithmic solutions to several mathematical problems. One of the problems is based on the numerical inversion of the laplace transforms. Another problem is based on the generator of random numbers satisfying the poisson distribution. Further, an algorithm is presented which generates random numbers from any probability density function, whether it be analytical, hypothetical, or experimentally acquired. Although there are in existence some fast and some general routines, the fast ones are for specific densities whereas the general algorithms are slow.

Numerical Analysis is the study of methods and procedures used to obtain "approximate solutions" to mathematical problems. Much of the emphasis is on scientific calculation. The difficulties of education in such a broad area center around the question of background and emphasis. The Numerical Analysis program in the Computer Science Department should emphasize an awareness of the problems of computer implementation and experimental procedures. Nevertheless, there is a need for a solid background in applied mathematics. [ABSTRACT FROM AUTHOR]

An algorithm for Filon quadrature is described. Considerable attention has been devoted to an analysis of the round-off and truncation errors. The algorithm includes an automatic error control feature. [ABSTRACT FROM AUTHOR]

The running time of programs in a paging machine generally increases as the store in which programs are constrained to run decreases. Experiments, however, have revealed cases in which the reverse is true: a decrease in the size of the store is accompanied by a decrease in running time. An informal discussion of the anomalous behavior is given, and for the case of the FIFO replacement algorithm a formal treatment is presented. [ABSTRACT FROM AUTHOR]

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

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

This paper is concerned with a review and examination of several existing algorithms for the zero-one programming problem. Computational experience is summarized. The machine time and storage requirements of several of the algorithms are compared over several test problems of small and intermediate size. Computer experiments still provide little hope of solving problems with over 100 variables with a reasonable amount of machine time. [ABSTRACT FROM AUTHOR]

Methods of analyzing the control flow and data flow of programs during compilation are applied to transforming the program to improve object time efficiency. Dominance relationships, indicating which statements are necessarily executed before others, are used to do global common expression elimination and loop identification. Implementation of these and other optimizations in OS/360 FORTRAN H are described. [ABSTRACT FROM AUTHOR]

The article presents the procedures for computing the finite Fourier transform of a complex data vector which is based on the Cooley-Tukey algorithm. An overview of the complextransform and realtransform's procedures are offered. Either the complex Fourier transform or its inverse are the procedure computed by complextransform, while realtransform computes either the Fourier coefficients of a sequence of real data points or evaluates a fourier series. The topic also includes orthogonal transformation, permutations, and spectral analysis.

The article presents several algorithms related to computer science and technology. One of the algorithm is based on the roots of low order polynomial equations. It discusses the procedures of finding the (complex) roots of the lower order polynomial equations by the familiar algebraic methods. An another algorithm is based on special functions. One of the algorithms discusses Chi-Squared Integrals.

Presents an algorithm that terminates the iteration process when searching for the root of a polynomial. Calculated bounds for the roundoff error that occurs in evaluating polynomials; Means for accepting a complex number as a zero of a real polynomial.

Examines the Fourier transform algorithm in mathematical analysis. Equation methods for accurately computing trigonometric function values; Applications of the method in computing large mixed radix transforms; Scaling plan for computing the Fourier transform with fixed-point arithmetic.

In the main text of the paper [Comm. ACM 9, 12 (Dec. 1966), 864], a FORMAC program was discussed which is capable of calculating various quantities of interest in tensor calculus. This Appendix is intended as an example of the program output. Christoffel symbols calculated for 12 bask orthogonal coordinate systems are listed. [ABSTRACT FROM AUTHOR]

A procedure is given for continuously computing and monitoring the step size to be used by a self-starting, pth-order numerical integration method to solve an initial value problem. The procedure uses an estimate of the truncation error to calculate the step size. [ABSTRACT FROM AUTHOR]

The FORMAC (FORmula MAnipulation Compiler) programming system provides a powerful tool for performing mathematical analysis. It is an extension of FORTRAN IV which permits the use of the computer to perform the tedious algebraic computations that arise in many different fields. Among the areas in which it has been successfully used are: differentiation of complicated expressions, expansion of truncated power series, solution of simultaneous equations with literal coefficients, nonlinear maximum likelihood estimation, tensor analysis, and generation of the coefficients of equations in Keplerian motion. These types of analysis—which arose in the solution of specific practical problems in physics, engineering, astronomy, statistics and astronautics—are discussed in the paper. In addition to its usage for specific problem solutions, FORMAC can also be used to automate the analysis phase in certain production programming. Several such applications are presented. [ABSTRACT FROM AUTHOR]

An algorithm for finding the symbolic factors of multivariate polynomial with integer coefficients is presented. The algorithm is an extension of a technique used by Kronecker in a proof that the prime factoring of any polynomial may be found in a finite number of steps. The algorithm consists of factoring single-variable instances of the given polynomial by Kronecker's method and introducing the remaining variables by interpolation. Techniques for implementing the algorithm and several examples are discussed. The algorithm promises sufficient power to be used efficiently in an online system for symbolic mathematics. [ABSTRACT FROM AUTHOR]

A procedure for numerically solving systems of ordinary differential equations is shown to also generate symbolic solutions. The procedure is based on finite Taylor series expansion that includes an estimate of the error in the final result. A computer program is described that reads in a system of such equations and then generates the expansions for all of the dependent variables. The expansions are determined symbolically, hence any non-numeric parameters in the original equations are carried automatically into the final expansions. Thus the exact influence of any parameters on the problem solution can be easily displayed. [ABSTRACT FROM AUTHOR]

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 study has been made to determine which methods of numerical integration require the least computation time for a given amount of truncation error when applied to a particular system of ordinary differential equations where function evaluations are relatively trivial. Recent methods due to Butcher and Gear are compared with classic Runge-Kutta Kutta-Nyström and Adams methods. Some of the newer one-step methods due to Butcher are found to be slightly superior, but no one method is found to have any great advantage over the others in the application to this particular problem. [ABSTRACT FROM AUTHOR]

As an investigation in artificial intelligence, computer experiments on deductive question-answering were run with a LISP program called DEDUCOM, an acronym for DEDUctive COMmunicator. When given 68 facts, DEDUCOM answered 10 questions answerable from the facts. A fact tells DEDUCOM either some specific information or a method of answering a general kind of question. Some conclusions drawn in the article ore: (1) DEDUCOM can answer a wide variety of questions. (2) A human can increase the deductive power of DEDUCOM by telling it more facts. (3) DEDUCOM can write very simple programs (it is hoped that this ability is the forerunner of an ability to self-program, which is a way to learn). (4) DEDUCOM is very slow in answering questions. (5) DEDUCOM's search procedure at present has two bad defects: some questions answerable from the given facts cannot be answered and some other answerable questions can be answered only if the relevant fads ore given in the "right" order. (6) At present, DEDUCOM's method of making logical deductions in predicate calculus has two bad defects: some facts have to be changed to logically equivalent ones before being given to DEDUCOM, and some redundant facts have to be given to DEDUCOM. [ABSTRACT FROM AUTHOR]

A large class of problems leading to digital computer processing can be formulated in terms of the numerical solution of systems of ordinary differential equations. Powerful methods are in existence for the solution of such systems. A good general purpose routine for the solution of such systems furnishes a powerful tool for processing many problems. This is true from the point of view of ease of programming, ease of debugging, and minimization of computer time. A number of examples are discussed in detail. [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]

The article presents mathematical procedures using Legendre functions for cases involving arguments larger than one. The integer Legendre 1 procedure is said to generate the associated Legendre functions of the first kind. Integer Legendre 2 generates associated Legendre functions of the second kind to d significant digits. The integer Legendre 3 generates the Legendre functions of the second kind to d significant digits and stores in the array Q. Legendre 1 procedure evaluates the Legendre functions to d significant digits. Other procedures include Legendre 2, conical and toroidal.

This article focuses on the experimental English language question-answering computer systems. Most languages have a small set of rules which can be used for transforming any statement into a question. In English the question mark, intonation, and the rearrangement of subject and verb accomplish this function. In addition to transformal rules, a vocabulary of special question words--who, why, where etc. exists which provides clues as to the nature of the answer that is desired. Machines and programs which attempt to answer English questions have existed for only about five years. But the desire to translate language statements into symbols which can be used in calculus has existed as long as formal logic. Attempts to build machines to test logical consistency date back at least to the thirteenth century. Several logic machines for testing the validity of propositions were constructed in the nineteenth century. However these machines, although they answer questions, do not deal directly with natural languages.

This article discusses various issues related to a procedure, algorithm 484, that evaluates the real and imaginary parts of the modified Bessel functions K0(z) and K1(z) for values of the complex argument. Many previous methods of calculating these functions have simply used the series expansion for arguments z of small magnitude. To have a fast, accurate algorithm, the functions must be evaluated by different methods in different regions of the complex plane. Owing to the singularity at the origin for K1(z), only the series expansions will be useful near z equals to 0. To decide exactly where each method should be used and how good the resulting algorithm is, one must be able to assess the speed and accuracy of each method.

The article discusses the mathematical concept called arrow to precedence network transformation. Many of the application programs in the area of critical path scheduling and resource allocation are written for the precedence networking convention. The method of transforming arrow convention networks into precedence convention is required, because only few of these programs admit networks defined by arrow convention directly. The algorithm generates the required transformation by creating a list of followers for each non-dummy arrow. The logic used in the transformation can be used to create a list of predecessors if they are desirable.

The article discusses matrix transposition in place. Several algorithms have been used for solving the problem of transposing a rectangular matrix in place. A significantly speedier algorithm is described, based on a number of theoretical analysis, and experimentally compared with existing algorithms. The theory calls for the storing of a matrix in a vector in one of two ways, either rowwise or columnwise. The matrix is transposed by its conversion from one mode of storage to the other through permutation.

The article discusses three computer algorithms. The first algorithm is related to circular integer partitioning. The partition, when expresses as a K-tuple may be thought of as a K-digit number in the base V number system. However, since all K-digit numbers do not correspond to circular partitions, it is possible to have the procedure generate only a set of K-tuplets for consideration. Since the numbers are sequentially increasing, a given number is a cyclic permutation of a previously generated number if a cyclic rotation of its digits produces a number with a smaller value. Therefore, the procedure efficiently generates the totality of circular partitions since it can greatly restrict the number of K-tuples that must be considered. The second algorithm is related to complex gamma functions. It evaluates in single precision the gamma function for complex arguments. First the real part of the argument of the gamma function is increased by some integer so that Stirling's asymptotic series for the logarithm of the gamma function may be used with high precisions and a small number of terms.

Explicit error bounds for periodic quintic spline interpolation are developed. The first (third) derivative of the periodic spline is shown to be a sixth (fourth) order approximation at the mesh points to the first (third) derivative of the function being interpolated. [ABSTRACT FROM AUTHOR]

This article presents procedures for solving of equations related to algorithm. Procedure determines the least-cost flow over an upper and lower bound capacitated flow network. Each directed network arc a is defined by nodes I[a] and J[a], has upper and lower flow bounds hi{a] and lo[a], and cost per unit of flow cost[a]. Costs and flow bounds may be any positive or negative integers. An upper flow bound must be greater than or equal to its corresponding lower flow bound for a feasible solution to exist. There may be any number of parallel arcs connecting any two nodes.

An algorithm for assignment of students to classes in a fixed time schedule that allows students to give a preference for sections within courses is given. If consistent with the objective of balanced sections, these preferences will be honored. The algorithm is more stochastic than Monte Carlo in nature. Results are given that compare it to a nonpreference assignment algorithm. [ABSTRACT FROM AUTHOR]

The Bairstow algorithm is generalized to the case of a polynomial which is itself a linear combination of polynomials satisfying a three-term recursion. Convergence properties of the method are derived. [ABSTRACT FROM AUTHOR]

A method of core storage allocation in a certain iterative process is described and estimates of the machine time required are given. The method is applicable to iterative processes in which input data items once chosen are never again needed. In this method the input data is continuously relocated and the space made available apportioned to the output tables when an overflow occurs. Some important special cases are considered in which considerable simplification occurs. [ABSTRACT FROM AUTHOR]

Equations of the form du / di = g(u(t), u(h(t))) arise in a number of scientific contexts. The authors point out some interesting properties of the solution of u′(t) = -u(t - 1 - k sin ωt) + sin at. These properties were obtained by means of numerical solution. [ABSTRACT FROM AUTHOR]

This article presents solution to algorithmic equations. In algorithm 279 Chebyshev quadrature, the routine evaluates the integral of f(x) with lower and upper limits set to a and b respectively. The method consists of fitting point Chebybhev polynomial to integrand and thus finding integral. n is tried equal to 2 and increased by 1 if error, the relative error, is too large. If n reaches maximum nmax without required accuracy obtained a message is printed. Accuracy is determined by assuming that error is less than the contribution to the integral of the last term in the integrated Chebyshev polynomial. After n = 2 has been tried, an estimate of the integral is available and subsequently the last term in the Chebyshev polynomial is found first and this saves evaluating whole polynomial if accuracy not obtained. An extra check is that the next two terms are also tested allowing up to 8 times error on previous term in each case. A reasonable value for nmax is probably 7. Integrals requiring many more points than this would probably be better tackled using some method which subdivides the range.