Research and Advances

This paper is dedicated to the proposition that, in order to take full advantage for real-time computations of highly parallel computers as can be expected to be available in the near future, much of numerical analysis will have to be recast in a more “parallel” form. By this is meant that serial algorithms ought to be replaced by algorithms which consist of several subtasks which can be computed without knowledge of the results of the other subtasks. As an example, a method is proposed for “parallelizing” the numerical integration of an ordinary differential equation, which process, by all standard methods, is entirely serial.

A family of test matrices with the following properties is described here: (a) an explicit inverse is given; (b) the characteristic polynomial is easily obtained; (c) a large measure of control over the eigenvalues is possible; (d) in special cases the eigenvalues and eigenvectors can be given explicitly, and the P-condition number can be arbitrarily assigned.

I was so impressed and pleased by RDNUM, A. Hassitt's General-Purpose Input Routine [Comm. ACM 7, 6 (June 1964), 350-355], that I have transliterated it into FORTRAN II for the IBM 7094. In doing this I stumbled across solutions to a decimal-to-binary conversion problem that has long bugged FORTRAN. Let me hasten to say, before C. H. Weisert [Letter to the Editor, Comm. ACM 7, 5 (May 1964), 314] castigates me for discussing 7090 problems in your columns, that the matter discussed here is relevant to any machine conversion algorithm.

Tests of significance based on analysis of variance calculations often require the determination of the probabilities of obtaining values of F greater than those arising from the analysis. These probabilities are customarily obtained from tables of the F-distribution. However, when the calculations are done on a computer, it would be convenient if estimates of these probabilities could be calculated by the analysis of variance program and presented in the output of the results. This note gives a simple method of doing so.

The United States Military Academy is faced with the situation whereby 700 cadets may in a single subject prepare computer programs in class one day and get their solutions in the form of a computer runoff at their next class attendance. If the programs had to be processed by conventional keypunch techniques the peak requirements for keypunching would be overwhelming. Keypunched cards with operator errors caused by misinterpreted coding sheets could not be returned to students for review and correction prior to the time the solutions are required in class. This situation has caused the Military Academy to investigate methods bypassing the keypunching operation. A number of special type mark-sense and Port-A-Punch cards have been used. Figure 1 shows a card used with SADSAC, a simplified academic design single address computer; Figure 2, a card for SASSY, a symbolic assembly program; Figure 3, a card for CADETRAN, a dialect of FORTRAN. (It contains the arithmetic statement X = 3.5 * A/(K**2 - C**2).) The CADETRAN/FORTRAN card is printed in four colors. Numbers (which require marking of a single position) are printed in black. Letters of the first third of the alphabet are printed in green, as is the 12-zone position which is identified A→I. Middle third letters of the alphabet are printed in red, as is the 11-zone position identified J→R. The final third of the alphabet is printed in blue as is the 0-zone position, and identified as S→Z. Commonly used symbols which would require 3 marks have been brought out to a separate left column where a single mark serves to identify them. Common but lengthy verbs such as FORMAT, DIMENSION and READ may also be represented by a single mark.

The second Remes algorithm is used to approximate the integrals Kis by rational functions. The related coefficients for the approximations of Ki1, Ki2, Ki3 are given for different precisions.

The test matrices given by M. L. Pei [Comm. ACM 5, 10 (Oct. 1962), 508] and R. D. Rodman [Comm. ACM 6, 9 (Sept. 1963, 515] are special cases of a general class of matrices with complex elements for which an explicit form of the inverse can be exhibited. This class of matrices is such that eigenvalues and a set of associated eigenvectors can also be obtained. Then not only inverses, but also eigenvalues of the Pei matrix given by W. S. Lasor [Comm. ACM 6, 3 (Mar. 1963), 102] and eigenvectors given by A. R. C. Newberry [Comm. ACM 6, 9 (Sept. 1963), 515], and eigenvalues of the Rodman matrix follow as special cases.

The very generality of a language like ALGOL renders it inefficient when a number of programs have to be written all dealing with a fairly narrow range of problems. This can be largely overcome by the construction of a package of suitable procedures, each of which embodies a fairly substantial piece of computation that will be required in several different contexts (see, for example [1]). A program for a specific purpose will consist of a set of these procedures linked by a more or less skeletal main program.

Techniques are developed for manipulating bits using only FORTRAN II. These techniques allow individual bits to be tested, certain fields to be shifted, and numbers coded in BCD to be converted to Binary.

Scanning text on a computer, as in forming word lists or editing, usually involves isolating and identifying certain characters or classes of characters. For example, if we scan text to form a list of words, the definition of “word” might be “everything between two blanks that isn't punctuation.” To program this, we must be able to identify a single character (blank) and a class of characters (punctuation). In a computer such as the 7090, where characters are numbers, we can put a character into an index register and index a table of transfers (one table-entry per character), thus getting to a section of code appropriate for handling that particular character. This is not natural for the 1401 because characters are not numbers and turning them into numbers is a bit clumsy. However, 1401 addresses are a combination of numbers and other characters, and we can use characters directly to reference certain addresses provided we can turn all characters (there are 64) into the 40 that are allowable in specifying an address.

The letter by Ackermann appearing in the Communications of the ACM of May 1964, presented one of a number of the very interesting uses of the FORTRAN II CHAIN procedure. Another unusual application of this procedure has been used by some at Lockheed Missiles & Space Company for realizing a very efficient program library tape.