Computational Mathematics Abstracts

LIBRARY OF THE

UNIVERSITY OF ILLINOIS

AT URBANA-CHAMPAIGN

5I0.84

y^o.8l-90

"PsiNEEm^

AUG 51976

I'he person charging this material is re-
sponsible for its return to the hbrary from
which it was withdrawn on or before the
Latest Date stamped below.

Theft, mutilation, and underlining of books
are reasons for disciplinary action and may
result in dismissal from the University.

UNIVERSITY OF ILLINOIS LIBRARY AT URBAfclA-CHAMPAIGN

lllli

•iwa^isil^S'

i^yy^ii

L161 — O-1096

Digitized by the Internet Archive

in 2012 with funding from

University of Illinois Urbana-Champaign

http://archive.org/details/computationalmat90belf

510.81;
U63c
no. 90

EnKin.

FERENCE ROOM

ENGWSERING UBRARy
mmRsljy OF ILLINOIS

ed Computa

UNlVERSlW OF ItLINOrS At URBANA-CHAMPAIGN

URBANA. ILLINOIS 61801

BIBLIOGRAPHIC DATA
SHEET

1. Report No.

UIUC-CAC-DN-T3-90

3. Recipient's Accession No.

4. Title and Subtitle

COMPUTATIONAL MATHEMATICS ABSTRACTS

7. Author(s) Edited Dy: (ieneva Bej.rora, jonatnan Lermit,
George Purdy, and Ahmed Sameh

5. Report Date

October 1973

8. Performing Organization Rept.

No. CAC-90

9. Performing Organization Name and Address

Center for Advanced Computation
University of Illinois at Urbana-Champaign
Urbana, 111. 618OI

10. Project/Task/Work Unit No.

11. Contract/Grant No.

DAHCOU-72-C-OOOI

12. Sponsoring Organization Name and Address

U.S. Army Research Office

Duke Station

Durham, North Carolina

13. Type of Report & Period
Covered

Re search- interim

14.

15. Supplementary Notes

16. Abstracts

None

17. Key Words and Document Analysis. 17a. Descriptors

Numerical Analysis
Graph Theory
Mathematical Programming

17b. Identifiers/Open-Ended Terms

17c. COSATI Field/Group

18. Availability Statement ^^ restriction On distribution

ft-vailable from the National Technical Information
Service.

FORM NTIS-3S (REV. 3-72)

19. Security Class (This
Report)

VNCLASSIFIED

20. Security Class (This
Page

UNCLASSIFIED

21. No. of Paees

^

22. Price

USCOMM-DC 14952-P72

CAC DocTjment No. 90

Computat lonal
Matheinatics Abstracts

Edited by

Geneva Belford
Jonathan Lermit
George Purdy
Ahmed Sameh

Applied Mathematics Group
Center for Advanced Computation
University of Illinois at Urban a- Champaign
Urbana, Illinois 618OI

October 1973

This work was supported in part by the Advanced Research Projects
Agency of the Department of Defense and was monitored by the U.S.
Array Research Office-Durham under Contract No. DAHC0U-T2-C-0001.

!^iii^^^^

TABLE OF CONTENTS

Page

ERROR ANALYSIS 1

FUNCTION EVALUATION AND COMPLEXITY THEORY k

APPROXIMATION 6

LINEAR ALGEBRA. 10

NONLINEAR EQUATIONS , 15

QUADRATURE - l6

ORDINARY DIFFERENTIAL EQUATIONS l8

PARTIAL DIFFERENTIAL EQUATIONS 21

FUNCTIONAL EQUATIONS 22

OPTIMIZATION 22

ROOT FINDING , 25

GRAPH ALGORITHMS. 26

MISCELLANEOUS 27

KEY TO REPORT SOURCES 29

ERROR MALYSIS

An Error Analysis of a Method for Solving Matrix Equations
by C. C. Paige

Let B = [L 0]Q be a decomposition of the m by n matrix B
of rank m such that L is lower triangular and Q is orthonormal. It
is possible to solve Bx, = b using L but not Q in the following manner:
solve Ly = b , solve L'^w = y , and form x = B w. It is shown that the
numerical stability of this method is comparable to that of the method
which uses Q. This is important for some methods used in mathematical
programming where B is very large and sparse and Q is discarded to save
storage.

STAN-CS-T2-29T June 1972

Rundungsfehleranalyse einiger Verfahren zur Summation endlicher Summen
by Arnold Neumaier

Der bei einer Summation auftretende Rundungsfehler kann als Mag
fur die Gute des verwendeten Verfahrens gelten. Im folgenden werden fllr
mehrere Suiranierungs verfahren, unter anderem fur das "ubliche" und das
Kahan-Babuska-Verfahren, a-priori-Schranken fur diese Rundungsfehler
S'^gegeben und miteinander verglichen.

PRAK 73/1 1973 28 pages

Fehlerabschatzung bei nichtlinearen Gleichungssystemen
by Rudolf Krawczyk

Fiir eine Losimg x* eines nichtlinearen Gleichungssystems f(x) = 0
wird eine Fehlerabschatzung bezuglich einer Halbordn\mg angegeben.
Gleichzeitig kann auch eine Aussage uber die Eindeutigkeit der Losung
gemacht werden. Die Ergebnisse werden auf Differenzengleichxmgen und auf ein
algebraisches Eigenwert problem angewandt .

PRAK 73/3 1973 ik pages

Komplexe Kreisarithmetik
by Norbert Krier

In dieser Arbeit werden Kreise der Gau3schen Zahlenebene als kom-
plexe Fehlerschrankenzahlen betrachtet. Da aus arithmetischen Verkniipfungen
solcher Kreise Mengen hervorgehen, die im allgemeinen keine Kreise sind,
werden diese Verkniipfungsmengen diirch Kreise abgeschatzt. Es wird eine
opt imal-abs chat zende Kreisarithmetik entwickelt sowie eine auf dem
Permanenzprinzip aufbauende, zentrierte Kreisarithmetik angegeben.

Um auch mit Mengen reeller oder imaginarer Zahlen rechnen zu
kbnnen, wird die Menge der komplexen Kreise eiveitert, indem Intervalle
der reellen sowie der imaginaren Achse als spezielle Kreiszahlen
aufgefasst werden. Dadiorch kann ausserdem eine fiir achsenparallele
Rechtecke der komplexen Ebene erklarte Intervallrechnung mit Kreiszahlen
nachvollzogen werden.

PEAK 73/2 1973 117 pages

Approximation durch Intervallfunktionen
by R. Krawczyk

Die bekannte Appro ximat ions aufgabe, eine gegebene Funktion f(x)
mit Hilfe eines Fimktionensystems zu approximleren, wird erweitert. Es
wird eine Intervall funktion (Funktion mit Intervallkoeffizienten) derart
bestimmt, dass die zu appro ximierende Funktion in dem diirch die
Intervall funktion definierten Streifen liegt. Diese Methode wird
anschliessend auf den diskreten Fall der Ausgleichung von n gegebenen
F-unktionswerten angewandt, und zwar 1. mit Hilfe eines Intervallpolynoms ,
2. durch eine trigonometrische Intervall funktion. Insbesondere wird fur
den Spezialfall der Interpolation die Fehlerabhangigkeit \intersucht . Ftir
eine Anzahl von Beispielen wird derjenige Grad der Ausgleichs funktion
ermittelt, fur welchen der entsprechende Streifen am schmalsten ist .

KARL 69/7 1969 12 pages

On the Computation of Rigorous Boirnds for the Solutions of Linear Integral
Equations with the Aid of Interval Arithmetic
by C. W. Cryer

A method is given for approximately solving linear Fredholm
integral equations of the second kind with non-negative kernels. The basis
of the method is the construction of piecewise-polynomial degenerate kernels
which bound the given kernel. The method is a generalization of a method
suggested by Gerberich. When implemented on a computer, interval arithmetic
is used so that rigorous bounds for the solution of the integral equations
are obtained.

The method is applied to two problems: the equation considered
by Gerberich; and the equation of Love which arises in connection with the
problem of determining the capacity of a circular plate condenser.

WIS 70 1969 ^0 pages

Iterationsverfahren in halbgeordneten Raumen
by R. Krawczyk

In der vorliegenden Arbeit werden Iterationsverfahren zur
Berechnung einer Folge von Intervallen in halbgeordneten linearen Raumen

"behandelt. Es verden atstrakte Satze ziir Einschliessung xind Existenz einer
Losung einer Operatorgleich-ung imd zur Konvergenz der Intervallfolgen
formuliert. Im zvelten Tell dieser Arbeit warden diese Satze aui* eine
Anzahl von Beispielen: Losung einer Gleichimg, N-ullstellenbestiimnung einer
analytischen F-unktion, Eigenvert- und Eigenvektorbestimmung von Matrizen,
Integralgleichung angewandt.

KARL 70/2 April 1970 30 pages

Bibliography on Proving the Correctness of Computer Programs — Addition No. 1
by Ralph L. London

The continued research activity in proving the correctness of
computer programs and the widespread interest in my previous program proving
bibliography (London 1970a) encourage me to compile these additional updating
citations. The selection criteria remain essentially unchanged; only the
form of the citation is trivially changed. As before, I wo"uld be most
interested in learning of corrections and additional citations to update
matters.

WIS-10i| December 1970 8 pages

FUNCTION EVALUATION AND COMPLEXITY THEORY

Computational Complexity of One-Point and Multipoint Iteration
by H. T. Kung and J. F. Traub

Let (|) "be an iteration for ^proximating the solution of a problem
f. We define a new efficiency measure e((|), f). For a given problem f,
we define the optimal efficiency E(f) and establish lower and upper boimds
for E(f) with respect to different families of iterations. We conjecture
an upper bound on E(f) for any iteration without memory.

CMU No # April 1973

Fast Evaluation and Interpolation
by H. T. Kung

A method for dividing a polynomial of degree (2n - l) by a pre-
computed nth degree polynomial in 0(n log n) arithmetic operations is given,
This is used to prove that the evaluation of an nth degree polynomial at
n+1 arbitrary points can be done in 0(n log n) arithmetic operations, and
consequently, its dual problem, interpolation of an nth degree polynomial
from n+1 arbitrary points can be performed in 0(n log n) arithmetic
operations. The best previously known algorithms required 0(n log n)
arithmetic operations.

CMU Wo # January 1973

Optimal Order of One-Point and Multipoint Iteration
by H. T. Kung and J. F. Traub

The problem is to calculate a simple zero of a non-linear function
f by iteration. We exhibit a family of iterations of order 2 which use

n evaluations of f and no derivative evaluations, as well as a second family
of iterations of order 2 based on n - 1 evaluations of f and one of f.

In particular, with four evaluations we construct an iteration of eighth
order. The best previous result for four evaluations was fifth order.

We prove that the optimal order of one general class of multipoint
iterations is 2 and that an upper bound on the order of a multipoint

iteration based on n evaluations of f (no derivatives) is 2 .

CONJECTURE. A multipoint iteration without memory based on n
evaluations has optimal order 2

CMU No # February 1973

The Computational Complexity of Algebraic Numbers
by H. T. Kung

Let {x.} be a sequence approximating an algebraic n-umber a of

degree r, and let x. ,^ = tf)(x.,x. ^,...,x. -,.,), for some rational fimction 4
" 1+1 1 1-1 i-d+1 ^

with integral coefficients. Let M denote the number of miiltipli cat ions or
divisions needed to compute (^ and let M denote the number of multiplications

or divisions, except by constants, needed to compute <^. Define the multipli-

loggP loggP

cation efficiency measure of {x. } as E({x })= — — — or as E({x. }) = — - — ,

1 1 ' M 1 M

where p is the order of convergence of {x.}. Kung [l] showed that
E({x. }) <_ 1 or equivalently, M >_ log p. In this paper we show that
(i) M >_ log2[r([pl-l) + 1] - 1; (ii) if E({x.}) = 1 then a is a rational
number; (iii) if E({x.}) = 1 then a is a rational or quadratic irrational
niimber. This settles the question of when the multiplication efficiency
E({x.}) or E({x.}) achieves its optimal value of unity.

CMU No # March 1973

Diagonal Theorems for Random Access Machines
by Stephen A. Cook and Robert A. Reckhow

Turing Machines have often been criticized for not being good models
for real computing machines. In this report we describe the RAM, an abstract
model of a (fixed-program) random access computer. A unique featvire of the
RAM is that the execution time of an instruction depends on the size of the
numbers being manipulated. We then describe- RAM-ALGOL, an ALGOL 60-like
programming language for RAM's. This language helps to clarify constructive
proofs of theorems involving RAM's. Using RAM-ALGOL programs we show that
the computing speeds of fixed-program and stored-program random access machines
and Turing Machines are not too widely divergent.

Our main result states that if T2(n) is a function such that there is
a RAM that computers T2(n) in time 0(T2(n) j, and if T-]_(n) is any function

inf ^1^^)
such that 7;r-7 — r = 0 , then there is a set S that can be recognized by

n-x» T2(n) ' ?= j'

some RAM in time 0(T2(n)) but no RAM recognizes S in time 0(T-j_(n)). This is
a sharper diagonal res\ilt than has been obtained for Tioring Machines.

TOR-1+2 J-une 1972 ll^l

pages

APPROXIMATION

Korovkin Sets (Sets of Convergence)
by G. G. Lorentz

This report treats sets of convergence of positive operators,
and of contractions, on the space of continuoTis fiinctions, and on other
Banach function spaces. Chapter 3 of the report is entirely new, while the
other two chapters present the existing theory in a new and more general
setting.

CNA-59 September 1972

An Application of the Theory of Approximation by Families with a Fixed Point
by G. G. Belford

Recently developed theorems characterizing best uniform
approximations from a family with a fixed point are shown to be useful in
the estimation of errors in computational techniques for solving linear
algebraic equations. Specifically, a gap in the proof of a published
theorem is filled in.

CAC TM No. 11 May 1973 6 pages

Simultaneous Fitting of Exponential Decay Curves
by G. G. Belford

This paper deals with characterization of best approximations to
vector-valued functions. The approximations are themselves vector-valued
functions with components depending nonlinearly on the approximation para-
meters. The constraint is imposed that certain of the parameters should be
identical for all components. An application to exponential approximation
is discussed in some detail.

CAC No. 6l April 1, 1973 30 pages

The Cholesky Factorization for Derivative-Free Nonlinear Least Squares
by Richard H. Bartels

In a previous technical report the author presented an algorithm
for minimizing sums of squares of nonlinear functions in several variables
without the use of derivatives. A subsection of this algorithm required that
the least-squares solution to an overdetermined linear system be found. The
implementation which was presented in the report accomplished this via the
QR factorization of the system's matrix. However, if the number of functions
in a nonlinear least-squares problem greatly exceeds the number of variables
involved, the matrix Q of the factorization requires a disproportionate
amount of storage space. To overcome this we present an alternate imple-

mentation In which the linear least-squares subproblem is solved via the
Cholesky factorization of the normal equation. A FORTRAN program -with test
results is included.

CM-6i| March 1973 Program Incl.

Constructive Aspects of Discrete Polynomial Spline Functions
by L. L. Schumaker

Discrete polynomial splines are vectors consisting of pieces of
polynomials tied together on knot intervals. They arise in optimal siammation
formulae and are expected to have applications to approximate solution of
discrete operator equations. Here ve obtain representations and local
Support bases (with recursions for them), discuss the total posit ivity of a
fundamental Green's function, and give certain basic interpolation resiilts.

CNA-62 January 1973 I8 pages

On the Convergence of Cubic Interpolating Splines
by Tom Lyche and L. L. Schumaker

Given a sequence of partitions A = (O = x <x^<...<x = l) and a

n o 1 n

corresponding sequence of cubic spline projections P , we find properties of

A which guarantee that f - P f -K) as n->°° for arbitrary continuous
n ' ' n ' '

functions on [O, l]. Results are obtained for cubic natural and cubic Type-I
spline interpolation.

CNA-61 September 1972

Computation of g-Splines Via a Factorization Method
by Harold D. Eidson and L. L. Schumaker

Fortran subroutines are presented for the purpose of computing and
evaluating g-splines interpolating Hermit e-Birkhoff data. The subroutines
are based on a factorization method for computing g-splines discussed by
Munteanu and Schumaker (CNA 25, Center for Numerical Analysis, UT Austin, 1971)

CNA-60 September 1972 Program Incl.

Uber A-usgleichs-Splines
by Klaus Bohmer

Combining the intrinsic properties of splines and the method of
least squares we discuss an extremal problem. We-show the existence -of a

solution and give the conditions for the uniqueness. For g -^ 0 resp. g ->-

we receive the usual interpolation spline resp. a solution of a problem

minimizing a sum of squares. We conclude in characterizing the solutions
for EHB- Interpolation problems.

KARL 71/5 September 1971 11 pages

On Best Simultaneoiis Approximation in Normed Linear Spaces
by D. S. Goel, A.S.B. Holland, C. Nasim, and B. N. Sahney

Let S be a non-empty family of real valued continuous functions on
[a, 3]. Diaz and McLaughlin [l], [2], and Dunham [3] have considered the
problem of simultaneously approximating two continuous functions f and f
by elements of S. If | | • | | denotes the supremum norm, then the problem is
to find an element s* e S, if it exists, for which

max ( I I f - s* I I , I I f - s* I I ) = inf max ( | | f - s | | , | | f - s | | ) .

s e S
The above problem is studied in general normed linear spaces.

CAL-186 March 1973 7 pages

Best Approximation by a Saturation Class of Polynomial Operators
by D. S. Goel, A.S.B. Holland, C. Nasim and B. N. Sahney

In this paper we prove that a method of summation involving Norlund
operators is saturated with the order Pn and related resiolts.

Pn

CAL-191 June 1973 10 pages

Characterisation of an Element of Best 1 -Simultaneous Approximation
by D. S. Goel, A.S.B. Holland, C Nasim, and B. N. Sahney

Let X be a normed linear space and K a subset of X. In CAL-186
we have considered the problem of best simiiltaneous approximation of two
elements xi,X2 e X from the elements of K.

The object of the present paper is to give a characterisation of
an element of best simultaneous approximation under a more general definition
of simultaneous approximation.

CAL-188 May 1973 6 pages

Splines with Non-Negative B-Spline Coefficients
"by C. de Boor and James W. Daniel

We consider the question of the approximation of non-negative
functions by non-negative splines of order k (degree < k) compared with
approximation by that subclass of non-negative splines of order k consisting
of all those whose B-spline coefficients are non-negative; while approximation
by the former gives errors of order h-^, the latter may yield only h^. These
results are related to certain facts about quasi-interpolants.

CNA-65 March 1973 5 pages

The Continuity of Metric Projections as Functions of the Data
by James W. Daniel

Let X be a Hilbert space, and consider the point xq minimizing,
for a given f in X, the distance | |x - f | | as x ranges over a polyhedral set
C defined by a finite niomber of real -valued equalities and inequalities. We
w^sh to see how xq varies when f and C vary. It is easy to see that xq is
Holder continuous with exponent 1/2 in its dependence on these parameters;
this estimate is in general sharp. We show, however, that in certain cases
XQ is actually Lipschitz continuoiis in its dependence on the parameters which
are used to define the set C.

CNA-68 April 1973 9 pages

LINEAR ALGEBRA.

A Fast Method for Solving a Class of Tri-Diagonal Linear Systems
"by Michael A. Malcolm and John Palmer

The solution of linear systems having real, symmetric, diagonally
dominant, tri diagonal coefficient matrices vith constant diagonals is
considered. It is proved that the diagonals of the LU decomposition of
the coefficient matrix rapidly converge to full floating-point precision.
It is also proved that the computed LU decomposition converges when floating-
point arithmetic is used and that the limits of the LU diagonals using
floating point are roughly within machine precision of the limits using real
arithmetic. This fact is exploited to reduce the niimber of floating-point
operations required to solve a linear system from 8n-7 to 5n+2k-3, where k
is much less than n, the order of the matrix. If the elements of the sub-
and super diagonals are 1, then only i+n+2k-3 operations are needed. The
entire LU decomposition takes k words of storage, and considerable savings
in array subscripting are achieved. Upper and lower boxinds on k are obtained
in terms of the ratio of the coefficient matrix diagonal constants and para-
meters of the floating-point number system.

Various generalization of these results are discussed.

STAU-CS-T2-323 November 1972 l6 pages

Iterative Solution of Tridi agonal Systems on Parallel or Vector Computers
by J. F. Traub

We study the iterative solution of a tridiagonal linear system of
size m on a parallel or vector computer. Such systems arise commonly in
the numerical solution of partial differential equations.

The Gauss algorithm takes time linear in m. We introduce a
Parallel Gauss iteration and show it can be used to solve a tridiagonal
system in time independent of m. Furthermore, the error norm is reduced at
each iteration step. A Parallel LP decomposition is also defined.

Parallel Gauss is based on "multiplicative splitting". We intro-
duce parallel algorithms based on "additive splitting". These are Jacobi,
JOR, Parallel Gauss-Seidel, and Parallel SOR.

We compare these parallel algorithms on a model problem and
conclude that JOR, Gauss-Seidel, and SOR are not competitive. Jacobi is best
if there is a "large amount" of diagonal dominance while Parallel Gauss is
best if there is only "limited" diagonal dominance.

CMU No # January 1973 ^2 pages

10

Methods for Modifying Matrix Factorizations

ty P. E. Gill, G. H. Golub, ¥. Murray, and M. A. Saunders

In recent years several algorithms have appeared for modifying
the factors of a matrix following a rank-one change. These methods have
always been given in the context of specific applications and this has
probably inhibited their use over a wider field. In this report several
methods are described for modifying Cholesky factors. Some of these have
been published previously while others appear for the first time. In addition,
a new algorithm is presented for modifying the complete orthogonal factor-
ization of a general matrix, from which the conventional QR factors are
obtained as a special case. A uniform notation has been used and emphasis
has been placed on illustrating the similarity between different methods.

STAN-CS-72-322 November 1972

Modifying Pivot Elements in Gaussian Elimination
by G. ¥. Stewart

The rounding-error analysis of Gaussian elimination shows that the
method is stable only when the elements of the matrix do not grow excessively
in the course of the reduction. Usually such growth is prevented by inter-
changing rows and columns of the matrix so that the pivot element is
acceptably large. In this paper the alternative of simply altering the pivot
element is examined. The alteration, which amounts to a rank one modification
of the matrix, is undone at a later stage by means of the well-known formula
for the inverse of a modified matrix. The technique should prove useful in
applications in which the pivoting strategy has been fixed, say to preserve
Spars eness in the reduction.

CMU No # March 1973

The SAC-1 Polynomial Linear Algebra System
by G. E. Collins and M. T. McClellan

This system is the tenth in a series of subsystems comprising
the SAC-1 System for Symbolic and Algebraic Calculation. The present sub-
system consists of programs implementing modular algorithms for linear
equations solution, matrix inversion, determinant calculation, null space
basis generation, and matrix miiltipli cation, all for matrices with integer
or polynomial entries. For each program in the system is given a fimctional
specification, an algorithm description, an analytical computing time, and a
Fortran program listing. Empirically observed computing times for some of
the key programs are presented. Also, a test program is supplied as an aid
in implementing the system and to illustrate its use.

WIS-15^ April 1972 Program Incl .

11

A Determinant Theorem with Application to Parallel Algorithms
"by Don Heller

We state and pix)ve an expansion theorem for the determinant of any
Hessenherg matrix. The expansion is expressed as a vector-matrix-vector
product which can he efficiently evaluated on a parallel machine. We con-
sider the computation of the first N terms of a sequence defined by a general
linear recurrence. On a sequential machine this problem is 0(N'^), with N
processors it is 0(N), and with 0(N ) processors it is O(log^N) using our
expansion. Other applications include locating roots of analytic functions
and proving doubling formulas for linear reciorrences with constant coefficients.

CMU No # March 1973

On a Characterization of the Best I Scaling of a Matrix
by G. H. Golub and J. M. Varah

This paper is concerned with best two-sided scaling of a general
square matrix, and in particular with a certain characterization of that best
scaling: namely that the first and last singular vectors (on left and right)
of the scaled matrix have components of equal modulus. Necessity, sufficiency,
and its relation with other characterizations are discussed. Then the problem
of best scaling for rectangular matrices is introduced and a conjecture made
regarding a possible best scaling. The conjectiore is verified for some
special cases.

STAN-CS-T2-319 October 1972

The LU-Factorization of Totally Positive Matrices
by Colin W. Cryer

An n X n real matrix A is an STP (strictly totally positive) matrix
if all its minors are strictly positive. An n x n real triangular matrix A
is a ASTP matrix if all its non-trivial minors are strictly positive. It is
proved that A is an STP matrix iff A = LU where L is a lower triangular matrix,
U is an upper triangiolar matrix, and both L and U are ASTP matrices. Several
related results are proved. These results lead to simple proofs of many of
the determinantal properties of STP matrices.

WIS-131 December 1971 23 pages

Convergent Generalized Monotone Splitting of Matrices
by 0. L. Mangasarian

Let B and T be n x n real matrices and r an n-vector and consider
the system u = BTu + r. A new sufficient condition is given for the existence

12

of a solution and convergence of a monotone process to a solution. The mono-
tone process is a generalization of the Collatz-Schroder procedure.

WIS-105

December 1970

11 pages

Monotone Splitting of Matrices
hy 0.- L. Mangasarian

Given the iterative scheme x = BT x + r where B, T are fixed

n X n real matrices, r a fixed real n-vector and x a real n-vector we

investigate the convergence and monotonicity of schemes of the type

V

i+1

w

i+1

•^

B

0

0

B

-\

— • — <

r ~]

^11

-^12

1

V

+

r

^21

S22_

i
w

r

where S. , are n x n real matrices related to T. The n-vector iterates v ,w
bracket in a certain sense solutions x of x = BTx+r. We also give necessary
and sufficient conditions for the monotonicity of the original iterative
scheme itself x = BTx + r. This leads to monotonicity results for
classicial Iterative schemes such as the Jacobi, Gauss-Seidel and successive
overrelaxation methods.

WIS-106

December 1970

19 pages

Zeros of X-Matrices, A Survey
by Jon Rokne

We present a survey of results for computing zeros of X-matrices
and matrix polynomials. Most of the results are not new, except for the
results in section 3. The results that are collected here do not seem to
"be known to a large audience, however.

CAL-181

March 1973

17 pages

13

Characterizations of Real Matrices of Monotone Kind
by 0. L. Mangasarian

An m by n real matrix A is said to be of monotone kind if

(l) Ax ^ 0 ■ ■> x^O .

Collatz treats square matrices of monotone kind and shows that for such
matrices the above implication is equivalent to: A exists and A~l >_ 0.

It is the piorpose of this note to generalize Collatz 's result to
rectangular matrices, and also to show that, for the general rectangular
case, a matrix of monotone kind can be further characterized as one for
which the convex conical hull of the rows contains the nonnegative orthant.

WIS-15 February 1968 8 pages

A Linear Programming Implementation
by Jonathan Lermit

This document discusses the implementation of a recently developed
version of the simplex method for linear programming using Cholesky
factorization (where the basis is expressed as a product of a lower tri-
angular and an orthogonal matrix) rather than the more usual product form of
the inverse. Storage schemes for the resulting lower triangular matrix
suitable for an array processor (the orthogonal matrix is not retained) and
necessaiy adaptations to the algorithm when the constraint matrix is
expressed as a linear operator are also discussed.

CAC No. h6 May 7, 1973 30 pages

Fehlerabs chat z long reeller Eigenwerte und Eigenvektoren von Matrizen
by R. Krawczyk

Reelle einfache Eigenwerte und die dazugehorigen reellen Eigen-
vektoren einer quadratischen Matrix werden mit Hilfe einer Intervallarithmetik
\anter Berucksichtigung aller Run dungs fehler abgeschatzt. Fur diese Fehler-
abschatzTing benbtigt man als Daten die Nah e rungs we rte eines Eigenwertes und
des entsprechenden Eigenvektors , welche man sich nach irgendeinem numerischen
Verfahren verschafft hat. Als ergebnis erhalt man ein Intervall und einen
Intervallvektor, welche den exakten Eigenwert bzw. den exakten Eigenvektor,
enthalten. Gleichzeitig ergibt sich daraus auch die Existenz eines reellen
Eigenwertes .

KARL 68/5 March 1968 15 pages

Verbesserung von Schranken fur Eigenwerte und Eigenvektoren von Matrizen
by R. Krawczyk

Es wird ein Verfahren beschrieben, wie man die Fehlerschranken
eines Eigenwertes und des zugeordneten Eigenvektors einer Matrix mit Hilfe

lU

elner Intervallarithmetik verbessern kann. Dabei wird dem komplexen Eigen-
wertproblem n-ter Ordnung ein reelles nichtlineares Gleichungssystem der
OrdnTong n+2 zugeordnet, so dass nur ein geringer Mehraufwand an Rechenarbeit
im Vergleich zur Einschliessung reeller Eigenwerte erforderlich ist. Die
Konvergenz der Iterationsfolge hangt im wesentllchen von den Anfangs-Schranken
des Eigenwertes imd nicht von den Schranken des Eigenvektors ab.

KARL 69/5 April I969 8 pages

Einschrankung von Eigenwerten reellsymmetrischer Matrizen
by Oswald Kreg

Im folgenden wird ein Algorithmus angegeben, der ausgehend von
einem Einschliegungssatz von Collatz die Einschliegung von Eigenwerten einer
reellsymmetrischen Matrix A leistet.

Ntunerische Schwierigkeiten , die auftreten konnen, wenn die vorge-
gebene Waherung z fur einen Eigenvektor Komponenten enthalt , die Null oder
sehr klein sind, werden durch eine Ahnlichkeitstransformation beseitigt.

KARL 70/10 August 19T0 2U pages

NONLINEAR EQUATIONS

The Convergence of Multipoint Iterations to Multiple Zeros
"by G. W. Stewart

This paper fills a gap in the theory of multipoint iteration func-
tion exemplified by the question: how does the secant method converge to a
mioltiple zero. A general theory of the linear convergence of multipoint
iterations is developed, and it is shown that two broad classes of iterative
methods fit this theory- The results of numerical investigations based on
the theoiy suggest that Muller's method applied to a multiple zero will
inevitably produce complex iterates.

CMU No.# Januaiy 1973

Some Iterations for Factoring a Polynomial II. A Generalization of the
Secant Method
by G. ¥. Stewart

This paper describes an iterative method for factoring a polynomial
that bears the same relation to Bairstow's method as the secant method in a

15

single variable bears to Newton's method. Like the secant method, the
generalized secant method requires only one function evaluation for each
iteration, and like the secant method it converges to a simple factor with
order (l+/5")/2.

CMU No. # February 1973

A Quadratically Convergent Lagrangian Algorithm for Nonlinear Constraints
by J. B. Rosen and J. L. Kreuser

An algorithm for the nonlinearly constrained optimization problem
is presented. The algorithm consists of a sequence of major iterations
generated by linearizing each nonlinear constraint about the current point,
and adding to the objective function a linear penalty for each nonlinear
constraint. The resulting fimction is essentially the Lagrangian. A
Kantorovich-type theorem is given, showing quadratic convergence in terms of
major iterations. This theorem insures quadratic convergence if the starting
point (or any subsequent point) satisfies a condition which can be tested
using computable bounds on the objective and constraint functions.

WIS-166 November 1972 33 pages

QUADRATURE

Computing Integrals Involving B-Splines by Means of Specialized Gaussian

Quadrature R-uLes

by J. L. Phillips and R. J. Hanson

In this paper a technique and algorithm are given to efficiently
compute integrals involving products of splines and general functions.

Using the B-Splines as weighting functions, we show how to gener-
ate Gaussian quadrature rules for approximating the integrals.

Tables of abscissas and weights, together with procedures for
their use, are given for the important special case in which the interval
breakpoints of the B-Splines are equally spaced.

WSU-73001 1973

16

On Weight Functions for Chebyshev Quadrature
by K. Salkauskas

The Chebyshev quadrature problem is to determine real k and real,

distinct t^ ,...,t in [0, l] such that
l,n n,n

(1.1) / w(t)f(t)dt = k I f(t. ^), V f e P^, n = 1,2,... .
0 1=1 '

1

I
0

Here w is a given weight function that is normally taken to be non-negative

on [0, l]. It is well known that if w = 1, the problem cajinot be solved with

real {t }^ when n = 8 or n > 9. On the other hand, for (l.l) transfomied
l,n 1=1

to the Interval [-1, l], Ullman [5] has found a one-parameter family of weight
functions of the form

f^\ 1 1 + 2at 111

w(t) = 2"Y72 ' 2 ' 1^' -h •>

with the property that the problem has solutions for all n. When a = 0,
one recovers the classical Chebyshev weight function, for which the Gauss
and Chebyshev quadrature formulas coincide.

The purpose of this paper is to show that weight functions for
which the Chebyshev problem is solvable are scarce in a probabilistic sense.

CAL-1T5 January 1973 9 pages

IT

ORDINARY DIFFERENTIAL EQUATIONS

Necessary and Sufficient Criteria for A-Statility of Linear Mijlti-Step
Integration Formulae
by Colin W. Cryer

k . k

Let p(^) = 2 o' . S and a(5) = I 3 . C "be the characteristic
j=0 ^ j=0 J

polynomials of a linear multi-step method for the n-umerical solution of an

initial value problem for ordinary differential equations. It is shown

that the method is A-stable iff all the following conditions hold:

(i) & ^ 0; (il) Re[p(C)a(?)J >_ 0 for |c| =1; (iii) P and a satisfy the

root condition, that is, their zeros lie inside or on the unit circle and

any zeros on the unit circle are simple. For the case when p and a have

integer coefficients, a program has been developed which uses the SAC-1

system (system for Symbolic and Algebraic Calculations, version (l))

determine whether the multi-step method (p,a) is A-stable.

WIS-IUT March 1972 36 pages

18

A Proof of the Instability of Backward-Difference Multistep Methods for
the Numerical Integration of Ordinary Differential Equations
by Colin ¥. Cryer

It is shown that the backward difference m\iltistep method

I i V"^ y = hf
m=l ^ P P

for the numerical integration of y'(x) = f(x,y) is stable in the sense of
Dahlquist iff 1 <_ q <_ 6.

WIS-llT May 1971 52 pages

A Note on the Non-Exist ence of Mult lvalue
A-Stable Methods of Order Greater than Two
by C. ¥. Gear

It is shown that the Dahlquist result limiting the order of
A-stable multistep methods also applies to multivalue methods.

UIUC-R-73-569 March 1973 7 pages

The Effect of Variable Mesh Size on the Stability of Multistep Methods
by C. W. Gear and K. W. Tu

The effects of two different techniques for implementing variable
mesh sizes in multistep formiiLas are investigated. It is proved that one
is more stable than the other for some cases, but that both are stable when
the step changes are small. The practical implications of these results
are discussed.

UIUC-R- 73-570 April 1973 35 pages

Stability and Convergence of Variable Order Multistep Methods
by C. W. Gear and D. S. Watanabe

The variable step Adam's method is shown to be stable for any
order changing scheme. The Nordsieck form of Adam's method, however, is
shown to be stable only if the step size and order are fixed for p steps
following a change to an r-step method, where p is r or r+1 depending on
the algorithm used to interpolate the necessary high derivatives. Finally,
general consistent and strongly stable multistep and multivalue methods are
shown to be stable if the method is fixed for a certain number of steps
following each method change and step size changes are small. This number
is independent of the differential equation and the step sizes.

UIUC-R-73-571 May 1973 31 pages

19

Solutions of a Differential Equation Arising in Chemical Reactor Processes
"by Seymour V. Parter

Consider the boundaiy value problem y" + — y' + Bf(y) = 0,

y'(0) = 0, y( x) = T where B >_ 0, t >_ 0. The function f(y) satisfies certain

properties which generalize the properties of '^^(j) = exp (- -i — r) . We are

concerned with the number of solutions in various regions of the t, 3 plane.

WIS-162 January 1973 5^ pages

Zxir numerischen Losimg von gewohnlichen Differentialgleichungen zweiter Ordnung
"by Manfred Heidt

In dieser Arbeit wird ein Verfahren zur numerischen Berechnving
einer Faherungslosving zusammen mit einer Fehlerabschatzung fiir das
An f an gswert problem

y"(x) = f(x,y(x),y'(x)), y(x^) = y^ , y'(x^) = y '^

einer gewohnlichen expliziten Differentialgleichung zweiter Ordnung
angegeben. Es handelt sich hierbei um ein Einschritt verfahren. Die
Differentialgleichung wird bei jedem Integrationsschritt lokal linearisiert ,
die linearisierte Differentialgleichung analytisch gelost , diese Losung mit
einem Storansatz abgespalten und nur noch eine relativ "harmlose" Rest-
differentialgleich-ung numerisch gelost. Mit Hilfe einer Defektabschatzung
werden anschliessend Fehlerschranken dieser Naherung berechnet.

Das Verfahren liefert fur eine KLasse linearer Differential-
gleichungen die exakte Losung. Das Phanomen der numerischen Instabilitat ,
wie es bei den meisten Faheriingsverfahren selbst bei stabilen Anfangswert-
problemen zu beobachten ist, tritt hierbei kaum mehr auf.

KARL 71/6 1971 122 pages

Investigation of One-Step Methods for Integro -Differential Equations
t»y Geneva G. Belford and Surender Kumar Kenue

One-step methods for solving integro-differential equations are
studied from the point of view of desiring that the method give good
accuracy when the true solution asymptotically goes to zero. A test equation
is proposed and absolute stability is investigated.

CAC No. 75 May 1973 11 pages

20

High Order Finite Difference Solution of Differential Equations
by Victor Pereyra

These seminar notes give a detailed treatment of finite difference
approximations to smooth nonlinear tvo-point "boiindary value problems for
second order differential equations. Consistency, stability, convergence,
and asymptotic expansions are discussed. Most results are stated in such a
way as to indicate extensions to more general problems. Successive extrapolations
and deferred corrections are described and their implementations are explored
thoroughly. A very general deferred correction generator is developed and it
is employed in the implementation of a variable order, variable (uniform) step
method. Complete FORTRAN programs and extensive numerical experiments and
comparisons are included together with a set of U8 references.

STAN-CS-T3-3^8 April 1973 86 pages Program Incl.

PARTIAL DIFFERENTIAL EQUATIONS

A Conjugate Gradient Approach to Nonlinear Elliptic Boundary Value Problems

in Irreg-ular Regions

by Richard Bart els and James W. Daniel

A version of the conjugate gradient method is proposed for solving
'discrete approximations to nonlinear elliptic boundary value problems over
irregular regions. The convergence rate is usually independent of the
discretization, but each step requires the solution of a Poisson equation on
the region; thus a fast Poisson solver yields a fast method for the general
problem. Details are given for the standard 5-point approximation to the
differential equation, with the Poisson equations being solved by the
Buneman algorithm after some preprocessing; numerical examples are given.

CNA-63

Niomerical Studies of Discrete Vibrating Strings
by A. B. Schubert and D. Greenspan

Discrete string vibrations are studied by means of a new two
dimensional model. Linear and nonlinear wave motions are constructed with
equal ease. Conditions and problem in which horizontal motion is
particularly noticeable are emphasized. A large variety of computer examples
are given.

WIS-158 November 1972 76 pages

21

FIMC TIONAL EQUATIONS

The Nimierical Solution of Boundary Value Problems for Second Order Functional
Differential Equations by Finite Differences
by Colin W. Cryer

In the present paper we consider numerical methods for computing
the solution of the boundaiy value problem

x(t) = g(t,x(t)) + (Fx)(t), 0 < t < 1,

x(0) = x(l) = 0,
where, F:C[0, l] ^ C[0, l], and g:R ^ R .
WIS-127 June 1971 57 pages Program Incl.

OPTIMIZATION

Least Squares Computations with Two Algorithms for the Two-Multiply,
Two-Add Givens Rotation
by R. J. Hanson

Two numerically stable algorithms for the implementation of the
two-multiply, two-add Givens transformation are discussed. An application
of the use of these algorithms is given for the problem of accumulating and
deleting rows of data from a least squares problem in a stable manner.

The construction of either transformation requires essentially
the same amount of work. The first method (which is not due to the author)
requires no square roots but may require rescaling to avoid underflow and
overflow. The second method requires one square root per transformation
but will need rescaling less than half as often as the first method.

WSU-73002 1973

Second and Higher Order Duality in Nonlinear Programming
by 0. L. Mangasarian

A d-ual problem associated with a primal nonlinear programming
problem is presented that involves second derivatives of the functions con-
stituting the primal problem. Duality results are derived for this pair
of problems. More general dual problems are also presented, and duality
results for these problems are also given.

WIS-159 October 1972 20 pages

22

Einschliepung des Minimalpunktes einer streng konvexen F-unktion auf elnem
n- dimensional en Quader
by Rainer Dussel

Gegeben sei eine Funktion <^: R -> R. Sie sei streng konvex in R
und es gelte (f)eC2(R^). Weiterhin sei ein n-dimensionaler achsenparalleler
Quader QOR^ gegeben durch Q := ( [a_ ,sr ], . . . , [a ,a" ]).

Gesucht ist derjenige Punkt xeQ, fur den gilt

(j)(x) = Min (t)(x) .
xeQ

Man nennt xeQ den Minimalpunkt von (f) bezuglich Q. Existenz und
Eindeutigkeit eines solchen Minimalpunktes sind unter den getroffenen
Voraussetzimgen trivial (siehe dazu Satz 3).

Anzugeben ist ein Verfahren zur numerischen Bestimmung von x und
damit von (j)(x). Da ein solches Verfahren in der Praxis nach endlich vielen
Schritten abgebrochen verden mu3 und da i. a. die Komponenten von x und die
Zaiil ^(x) in einem Computer nicht exakt darstellbar sind, stellt sich
■weiterhin die Frage nach Fehlerschranken fur eine mit diesem Verfahren
bestimmte Naheriing x zu x. Man kann damit das oben genannte Problem
umformulieren zu:

Gesucht ist ein numerischer Algorithmus zur Angabe eines "mog-
lichst kleinen" Quaders

[x] e I^(R) mit [x]CQ und xe:[x]

und eines "moglichst kleinen" Intervalls

$el(R) mit (|)(x)e$ .
KARL 72/2 July 1972 69 pages

Stability of the Solution of Definite Quadratic Programs
by James W. Daniel

This paper studies how the solution of the problem of minimizing
Q(x) = jx^Kx - k^x subject to Gx £ g and Dx = d behaves when K, k, G,^g, D,
and d are perturbed, say by terms~of size e, assioming that K is positive
definite. It is shown that in general the solution moves by roughly e if
G, g, D, and d are not perturbed; when G, g, D, and d are in fact perturbed,

23

much stronger hypotheses allow one to show that the solution moves "by
roughly e. Many of these results can be extended to more general, non-
quadratic, functionals.

CNA-58 September 1972

The Quadratic Assignment Problem
by George B. Purdy

In this report we discuss some seemingly reasonable approaches to
the quadratic assignment problem, and we give some evidence from automata
theoiy that the problem is insoluble.

CAC No. 71 February 1973 1^+ pages

Die Anwendung der Methode "Branch and Bound" auf ein verallgemeinertes
Knaps ackpr obi em
by Rudolf Krawczyk

Fur ein verallgemeinertes Knaps ackproblem mit gegebener Zielfunktion
und Restriktionen, dessen Lbsung durch boolesche Variable dargestellt werden
kann, wird eine Losungsmethode nach dem "Branch and Bound" — Prinzip angegeben.
Diese Methode wird mit Hilfe eines LSsungsbaumes veranschaulicht und an einem
Beispiel ausprobiert. Augerdem wird ein Algorithmus zu diesem Verfahren be-
schrieben und in der algorithmischen Sprache ALGOL programmiert .

KARL 71/1 January 1971 21 pages Program Incl.

21+

ROOT FINDING

Fehlerschranken zu Naherixngswerten von Polynomwurzeln
by Karl Nickel

Gegeben seien ein Polynom n-ten Grades und n komplexe Nahe-
runsverte zu den (unbekannten) Polynomwurzeln. Es vlrd ein Algorithmus
beschrieben, der zu jedem Naherungsvert' eine Fehlerabschatzung liefert.
Das Verfahren ist "konvergent" und besitzt eine gevisse (schwache)
Optimalitat. Es benbtigt keinerlei zus'atzliche Informationen uber die
exakten Nullstellen und versagt nie, auch night im Falle von mehrfachen
Nullstellen oder von Wurzelhaufen. Der Algorithmus wird durch ein Triplex-
ALGOL 60-Programm verwirklicht , vomit auch noch die unvermeidlichen
Runkungsfehler berucksichtigt "werden.

KARL 69/6 June 1969 22 pages Program Incl.

Abbruchkriterien und Numerishche Konvergenz
by K. Nickel and K. Ritter

Es sei X -> X eine von einem Verfahren erzeugte Folge zur

Approximation der reellen Zahl x. Es sei x (L) ein mit einer L-ziffrigen

Maschine gewonnener Naherungsvert zu x mit lim x (L) = x . Es wird em

" n , n n

L-x»

Abbrechkriterium N(L) angegeben derart, da3 es geniigt, bei fester Ziffer-

nanzahl L allein die Werte x (Lj, x-^ (L) , . . . ,31^/^ v (L) zu berechnen und

da6 unter sehr schvachen Voraussetzungen

L->o°
ist, d.h. da3 x^^/_s(L) "numerisch konvergiert ".

KARL 70/6 May 1970 11 pages

Abbrechkirterium fur Iterationsverfahren
tiy Rudolf Kravczyk

Die unendliche Folge x des allgemeinen Iterationsverfahrens zur
Losung einer Operatorgleichung x = Tx in einem metrischen Raum vird haufig
durch eine endliche Folge x approximiert, velche von der benutzten Rechen-
anlage abhangt. Es vird ein Abbrechkriterium angegeben, velches die
"numerische Konvergenz" im Sinne von [3] garantiert.

Dieses Abbrechkriteritim wird auf das NEWTONsche Verfahren zur
Los-ung einer Gleichung im Reellen und auf eine Lineare Integral gleichung
angevandt .

KARL 70/12 September 1970 11 pages

25

GRAPH ALGORITHMS

Two Upper Bounds for the Weighted Path Length of Binary Trees
"by Jean Louis Pradels

Rooted binary trees with weighted nodes are structures encountered
in many areas, such as coding theory, searching and sorting, information
storage and retrieval. The path length is a meaningful quantity which gives
indication about the expected time of a search or the length of a code for
example. In this paper, two sharp boimds for the total path length of
general weighted node trees are derived.

UIUC-R- 73-565 January 1973 1^ pages

An Efficient Implementation of Edmonds ' Maximum Matching Algorithm
by Harold Gabow

A matching in a graph is a collection of edges, no two of which
share a vertex. A maximum matching contains the greatest number of edges
possible. This paper presents an efficient implementation of Edmonds'
algorithm for finding maximum matchings. The computation time is proportional
to v3, where V is the number of vertices; previous algorithms have computation
time proportional to V^. The implementation avoids Edmonds' blossom reduction
by using pointers to encode the structure of alternating paths.

STAN-CS-72-328 June 1972 68 pages Program Incl.

Finding the Cliques of a Graph
by George B. Purdy

Auguston and Minker [l] presented a version of the Bierstone
algorithm for finding the set of cliques of a finite undirected graph.
(A clique is a maximal complete subgraph). However they gave no proof that
their algorithm worked, and indeed Mulligan and Cornell [2] pointed out that
it was wrong. Mulligan in [3] described his PL/I implementation of their
modified version of the algorithm, but it is referred to there as a
heuristic. For our algorithm we include a proof that it works.

This algorithm is clearly well suited for use on an array pro-
cessor, or an array of processors, which the other algorithms are not.

CAC m No. 5 December 1972 8 pages Program Inc.

26

MISCELLANEOUS

A Universal Random Number Generator

"by Michael A. Malcolm and Cleve B. Moler

A subroutine for generating uniformly-distrituted floating-point
numbers in the interval [O, l) is presented in ANSI standard Fortran.
The subroutine , URAND, is designed to be relatively machine independent.
URAND has undergone minimal testing on various machines and is thought to
work properly on any machine having binary integer number representation,
integer multiplication modulo m and integer addition either modulo m
or yielding at least £og (m) significant bits, where m is some integral
power of 2 .

Upon the first call of UMND, the value of m is automatically
determined and appropriate constants for a linear congruential generator are
computed following the suggestions of D. E. Knuth, Volume 2. URAND is
guaranteed to have a full-length cycle. Readers are invited to apply their
favorite statistical tests to URAND, using any binary machine, and report
the results to the authors.

STAN-CS-T3-33^ January 1973 Program Incl.

Computation of the Stationary Distribution of an Infinite Markov Matrix
by G. Golub and E. Seneta

An algorithm is presented for computing the -unique stationary
distribution of an infinite stochastic matrix possessing at least one
coliimn whose elements are bounded away from zero. Elementwise convergence
rate is discussed by means of two examples.

STAN-CS-73-335 Januaiy 1973

Calc\iIation of GFSR Pseudorandom Number Binary Starting Matrix
by W. H. Payne

The generalized feedback shift register pseudorandom niimber
algorithm produces the same floating-point sequence of pseudorandom numbers
on any computer. The algorithm requires a binary initialization matrix.
A matrix, given both in octal and hexadecimal, for primitive polynomial,
modulo 2, x98 + x27 + i is listed.

UIUC-R-73-567 March 1973 1^+ pages Program Incl.

27

The SAC-1 Modular Arithmetic System

by G. E. Collins, L. E. Heindel, E. Horowitz, M. T. McClellan and D. R. Musser

This is a reprinting of the original report of June I969, with
correction of a few minor errors. The SAC-1 Modular Arithmetic System is
the fifth of the ten SAC-1 subsystems which are now available. It provides
subprograms for the arithmetic operations in a prime finite field GF(p),
for any single-precision prime p, and for various operations on polynomials
in several variables with coefficients in GF(p). Besides the arithmetic
operations on such polynomials there are included subprograms for the
Chinese remainder theorem, evaluation and interpolation. For invariate
polynomials, subprograms are included for greatest common divisor calculation
and Berlekamp's factorization algorithm.

¥IS-l65 November 1972 50 pages Program Incl.

Gleichungen in halbgeordneten Raumen
"by R. Krawczyk

Im ersten Teil dieser Arbeit wird eine Operatorgleichung Tx = 9
in eine Operatorgleichung x = Sx transformiert . Darauf werden Fixpunksatze
angewendet und Fehlerabschatzungen fiir eine Losung durchgefuhrt . Das
allgemeine Iterationsverfahren entspricht bei variablem S dem WEWTONschen
Verfahren in normierten Raumen, ohne da3 eine Norm benotigt wird. Anstelle
der Frechet-Ableitung des Operators T tritt eine allgemeine Lips chit zbeding\mg
mit linearen Operatoren. Im zweiten Teil werden die abstrakten SStze des
ersten Teils auf einfache Beispiele: Gleichungen, nichtlineare
Gleichungssysteme, algebraische Eigenwertprobleme angewendet.

KARL TO/3 April 1970 16 pages

Das Prae-Euler'sche Limit ierungs verfahren
by Karl Nickel

Es sei {a } eine vollmonoton fallende Nullfolge. Es wird ein
n
Limit ierungs verfahren zur Kbnvergenzverbesserimg der alternierenden Reihe

I (-1) a angegeben und durch ein Triplex-ALGOL 60-Programm realisiert.

v=o

Es werden apriori-Fehlerschranken angegeben, die Stabilitat wird untersucht,
die Rundungsfehler fvor eine Klasse "idealer" Komputer werden abgeschatzt \md
es wird gezeigt, dass das Verfahren in dieser Klasse sogar "n-umerisch
konvergiert" . Beispiele zeigen die praktische Brauchbarkeit der Methode.

KARL 70/7 July 1970 ill pages Program Incl.

28

KEY TO REPORT SOURCES

ANL - Argonne National Laboratory
Argonne, Illinois 60^39

BTL - Bell Telephone Laboratories, Inc.
Murray Hill, New Jersey 079 71

CAC

Center for Advanced Computation

University of Illinois, Urbana, Illinois 618OI

CAL - Department of Mathematics

Statistics and Computing Science
University of Calgary, Calgary

Alberta, Canada

CMU

CNA

Carnegie-Mellon University
Computer Science Department
Pittsbiorgh, Pennsylvania 15213

Center for Numerical Analysis

University of Texas, Austin, Texas 78712

KARL - Inst i tut Fiir Informatik
Universitat Karlsruhe
Englerstrasse 2, Postfach 638O
D 75 Karlsriohe 1, Germany

MAC

MRC

Massachusetts Institute of Technology

Project MAC

Cambridge, Massachusetts 02139

Mathematics Research Center

University of Wisconsin, Madison, Wisconsin 53706

PRAK - Institut fur Praktische Mathematik
Universitat Karlsruhe
Englerstrasse 2, Postfach 638O
D 75 Karlsruhe 1, Germany

STAN - Computer Science Department

Stanford University, Stanford, California 9^305

TOR

Department of Computer Science
University of Toronto, Ontario, Canada

UAE - Department of Computing Science

University of Alberta, Edmonton, Alberta, Canada

UBC

Department of Computer Science

University of British Coliombia, Vancouver, B. C, Canada

29

UMINF -

UIUC -

WIS

Department of Information Processing
University of Umea, Umea, Sweden

Department of Computer Science
University of Illinois, Urbana, Illinois

Computer Sciences Department
The University of Wisconsin
1210 West Dayton Street
Madison, Wisconsin 53T06

61801

WSU - Computer Science Department
Washington State University
Pullman, Washington 99l63

YORK - T. J. Watson Research Center

Yorktown Heights, New York IO598

30

UNCLASSIFIED

SECURITY CL ASSinCATIOhi OF THIS PAGE (i*'hrn Data

Fnfer^d)

REPORT DOCUMENTATION PAGE

RliAD INSTRUCTIONS
BEFORE COMPLETING FORM

1. REPORT NUMQER

CAC Document No, 90

2. GOVT ACCESSION NO.

3. RECIPIENT'S CATALOG NUMBER

4. TITLE (end Subtllle)

Computational Mathematics Abstracts

5. TYPE OF REPORT & PERIOD COVERED

Bibliographical Abstracts

6. PERFORMING ORG. REPORT NUMBER

7. AUTHORCs;

Edited "by: Geneva Belford, Jonathan Lermit,
George Purdy, and Ahmed Sameh

8. CONTRACT OR GRANT NUMBER(-»;
DAHCOJ+-72-C-OOOI

9. PERFORMING ORGANIZATION NAME AND ADDRESS

Center for Advanced Computation
University of Illinois at Urhana-Champaign
Urhana, Illinois 618OI

10. PROGRAM ELEMENT. PROJECT, TASK
AREA 4 WORK UNIT NUMBERS

AEPA Order No. l899

»l. CONTROLLING OFFICE NAME AND ADDRESS

U.S. Army Research Office-Durham
Duke Station, Durham, North Carolina

12. REPORT DATE

October 1973

13. NUMBER OF PAGES

32

U. MONITORING AGENCY NAME A ADDRESSf// dlllerent from Controlling Oflice)

15. SECURITY CLASS, (oi thia report)

UNCLASSIFIED

15«. DECLASSIFICATION/ DOWNGRADING
SCHEDULE

16. DISTRIBUTION ST ATEM EN T Co/ <h<s Repor (;

Copies may be requested from the i\[ational Technical Information Service,
Springfield, Virginia 22151

17. DISTRIBUTION STATEMENT (ol the abstract entered In Block 20, II dlllerent Irom Report)

t8. SUPPLEMENTARY NOTES

19. KEY WORDS (Continue on reverse aide II necessary and Identlly by block number)

Numerical Analysis
Graph Theory
Mathematical Programming

20. ABSTRACT (Continue on reverse side II necessary and Idenlily by block number)

NONE

DD 1 JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE

UNCLASSIFIED

SECURITY CLASSIFICATION OF THIS PAGE fWTien Data Entered)

m