E1AR0002@SMUVM1.BITNET (03/20/86)
From rhbartels%watcgl@WATERLOO Thu Mar 20 00:11:04 1986
Received: by csevax.smu (4.12/4.7)
id AA09032; Thu, 20 Mar 86 00:09:58 cst
Received: from waterloo by csnet-relay.csnet id ad28657; 19 Mar 86 13:32 EST
Received: from watcgl.UUCP by watmath; Wed, 19 Mar 86 09:44:05 est
Received: by watcgl.UUCP (4.12/4.7)
id AA01980; Wed, 19 Mar 86 09:41:59 est
Date: Wed, 19 Mar 86 09:41:59 est
From: Richard Bartels <rhbartels%watcgl@WATERLOO>
Message-Id: <8603191441.AA01980@watcgl.UUCP>
To: leff
Subject: Numerical Analysis
Received: from CSNet-Relay by smu; 19 Mar 86 23:47:46-CST (Wed)
Status: R
==================================================
NUMERICAL ANALYSIS TITLES -- Volume 4, Number 1
Month March 1986
==================================================
##### Argonne #####
---------------
The following Argonne report(s) may be obtained from:
Jack Dongarra (dongarra@anl-mcs.arpa)
Argonne National Laboratory
Mathematics and Computer Science Division
Argonne National Laboratory
Argonne, IL 60515
---------------
%A Jack J. Dongarra
%A Tom Hewitt
%T Implementing Dense Linear Algebra Algorithms Using Multitasking
on the CRAY X-MP-4 (or Approaching the Gigaflop)
%R MCSD-TM-55
%I Argonne National Laboratory
%C Argonne, IL 60515
%D August, 1985
%X This note describes some experiments on simple dense
linear algebra algorithms. These experiments show that
the CRAY X-MP is capable of small grain multitasking
arising for standard implementations of LU and Cholesky decomposition.
The implementation described here provides the "fastest"
execution rate for LU decomposition, 718 MFLOPS for a matrix of order 1000.
%A J.J. Dongarra
%A D. C. Sorensen
%T A Fast Algorithm for the Symmetric Eigenvalue Problem
%I Proceedings of the IEEE ARITH7 Conference at the University of Illinois
%C Urbana, IL
%D June, 1985
%P 338-342
%X The symmetric eigenvalue problem is one of the most fundamental problems
of computational mathematics. It arises in many applications, and therefore
represents an important area for algorithmic research. It is also one of the
first eigenvalue problems for which reliable methods have been obtained.
It would be surprising therefore, if a new method were to be found that would
offer a significant improvement in execution time
over the fundamental algorithms available in
standard software packages such as EISPACK. However, it is reasonable to
expect that eigenvalue calculations might be accelerated through the use
of parallel algorithms for parallel computers that are emerging.
We shall present such an algorithm in this paper. The algorithm is able to
exploit parallelism at all levels of the computation and is well suited to
a variety of architectures. However, a pleasant bonus of this research is that
the parallel algorithm, even when run in serial mode, is significantly
faster than the best sequential
algorithm on large problems, and is effective on moderate size (order > 30)
problems when run in serial mode.
%A Jack J. Dongarra
%A Alan Hinds
%T Comparison of the CRAY X-MP-4, Fujitsu VP-200, and Hitachi S-810/20:
An Argonne Perspective
%I Argonne National Laboratory
%R ANL-85-19
%D October, 1985
%X A set of programs, gathered from major Argonne computer users, was run on
the current generation of supercomputers: the CRAY X-MP-4, Fujitsu VP-200
and, Hitachi S-810/20. The results show that the Fujitsu and Hitachi offer
a particularly attractive opportunity to sites that use IBM-compatible
computers. For our set of benchmarks, a single processor of a CRAY X-MP-4
compares favorably to the Fujitsu VP-200.
%A Jack J. Dongarra
%A Iain S. Duff
%T Advanced Architecture Computers
%I Argonne National Laboratory
%R MCSD-TM-57
%D October, 1985
%X We describe the characteristics of several recent computers that
employ vectorization or parallelism to achieve high performance
in floating-point calculations.
We consider both top-of-the-range supercomputers and computers
based on readily available and cheap basic units.
In each case we discuss the architectural base, novel features,
performance, and cost. It is intended that this report will be
continually updated, and to this end the authors welcome comment.
---------------
The following Argonne report(s) may be obtained from:
Jorge More' (more@anl-mcs.arpa)
Argonne National Laboratory
Mathematics and Computer Science Division
Argonne National Laboratory
Argonne, IL 60515
---------------
%A James Burke
%T Algorithms for solving finite dimensional systems
of nonlinear inequalities that have both global
and quadratic convergence properties
%R ANL/MCS-TM-54
%I Argonne National Laboratory, Mathematics and Computer Science Division
%D August, 1985
%X Methods for solving systems of inequalities and equalities
are developed. The problem is formulated as finding a vector
x such that g(x) belongs to an appropriate cone K.
The techniques used are Gauss-Newton type algorithms
for the minimization of the function
dist ( g(x) ; -K )
Under the assumption of a constraint qualification, the
algorithms are shown to be quadratically convergent.
##### Birkhauser-Boston Publishers #####
---------------
The following was submitted by:
Jane Cullum
IBM Research Center
P. O. Box 218
Yorktown Heights,
N. Y. 10598
914-945-2227
They are available from the publisher.
---------------
%A Jane Cullum
%A Ralph A. Willoughby
%T Lanczos Algorithms for Large Symmetric Eigenvalue Computations,
Volume 1: Theory and Volume 2: Programs.
%I Birkhauser-Boston
%D January, 1985
%X Volume 1 focuses on the background material
and analysis of Lanczos procedures which do not use
any reorthogonalization of the Lanczos vectors.
The authors' Block Lanczos procedure is also discussed
in detail. A brief summary of various Lanczos
algorithms which have been proposed in the literature
is also included.
Volume 2 contains FORTRAN implementations of all
of the 'symmetric' Lanczos algorithms developed by the
authors, together with the associated documentation
and auxiliary subroutines.
##### University of British Columbia #####
---------------
The following UBC report(s) may be obtained from:
Uri Ascher (ascher@ubc.csnet)
Department of Computer Science,
University of British Columbia,
Vancouver, British Columbia, Canada V6T 1W5 .
---------------
%A G. Bader
%A U. Ascher
%T A NEW BASIS IMPLEMENTATION FOR A MIXED
ORDER BOUNDARY VALUE ODE SOLVER
%R Technical Report 85-11
%X The numerical approximation of mixed order systems of multipoint
value ordinary differential equations by collocation requires
appropriate representation of the piecewise polynomial solutions.
B-splines were originally implemented in the general purpose code COLSYS, but
better alternatives exist. One promising alternative was proposed
by Osborne and discussed by Ascher, Pruess and Russell.
In this paper we analyze the performance of the latter solution
representation for cases not previously covered,
where the mesh is not necessarily dense. This analysis
and other considerations have led us to
implement a basis replacement in COLSYS, and we
discuss some implementation details.
Numerical results are given
which demonstrate the improvement in performance of the code.
##### University of Technology at Delft #####
---------------
The following Delft report(s) may be obtained from:
Henk A. van der Vorst (na.vandervorst@su-score.arpa)
Department of Mathematics
University of Technology at Delft
Julianalaan 132
Delft, the Netherlands
---------------
%A C.Cuvelier
%A J.M.Driessen
%T Thermocapillary free boundaries in crystal growth
%R Report 85-17
%I University of Technology at Delft
%C Julianalaan 132, 2628 BL DELFT, The Netherlands
%X In this paper a two-dimensional free boundary arising from the steady
therom-capillary flow in a viscous incompressible fluid is studied
from the numerical point of view. The problem is considered in the
context of the open boat crystal growth technique. The motion of the
fluid is governed by the Navier-Stokes equations coupled with the heat
equation.
The problem is solved numerically by a finite element method
discretization. Three iterative methods are introduced for the
computation of the free boundary. The non-dimensional form of the problem
gives rise to six characteristic parameters (Reynolds, Grashof, Prandtl,
Marangoni, Bond, Ohnesorge number). The influence of these parameters
on the flow field, the temparature distribution and the shape of the
free boundary is studied.
%A Henk A. van der Vorst
%T Using the Conjugate Gradients Information from Ax=b
when Solving Related Linear Sparse Systems
%I Department of Mathematics, University of Technology at Delft
%C Julianalaan 132, Delft, The Netherlands
%X The conjugate gradients method generates successive
approximations for the solution of the linear system Ax=b,
where A is symmetric positive definite and usually sparse.
Since the residual vectors form an orthogonal basis for the
Krylov subspace (which contains the approximated solution),
one may seek to use that information in order to solve
approximately some related linear systems. We will show
that this may lead to an efficient way of solving systems
with different right-hand sides and for systems like AAx=b,
or more generally, f(A)x=b, where the matrix f(A) is nonsingular.
%A R.Kettler
%A P.Wesseling
%T Aspects of multigrid methods for problems in three dimensions
%I Department of Mathematics, University of Technology at Delft
%C Julianalaan 132, 2628 BL DELFT, The Netherlands
%X Smoothing methods are analyzed for use in multigrid methods
applied to flow problems in three dimensions. A three-dimensional
version of incomplete block factorisation is described. The
anisotropic diffusion and convection-diffusion equations are used as model
problems. Unlike the two-dimensional case, none of the smoothing
methods considered is suitable for all relevant values of the physical
parameters.
##### Weidlinger Associates #####
---------------
The following report(s) may be obtained from:
Victor Pereyra (pereyra@su-score.arpa)
620 Hansen Way, Suite 100
Palo Alto, CA 94304
---------------
%A V. Pereyra
%T Modeling with Ray-tracing in 2-D curved homogeneous media
%I Weidlinger Associates
%D October, 1985
%X Algorithms for ray-tracing in a piecewise homogeneous medium with curved
layer interfaces are described. Normal incidence and non-zero offset two-
point and shooting are considered. Travel time and amplitude calculations
are used in the generation of synthetic seismograms. Also, time-to-depth
migration of seismic sections, an inverse problem, is described. The whole
package has been implemented in a microcomputer, and it is integrated into
a complete modeling system to aid the interpreter of seismic reflection
surveys.
(To appear in Proceedings of Workshop on Microcomputer applications, held
at Univ. of Delaware, May 20-22,1985. Siam Publications (Editor, A. Wouk)).
##### Los Alamos National Laboratory #####
---------------
The following report(s) may be obtained from:
David L. Brown (ARPA: dlb@lanl.arpa or na.dbrown@su-score.arpa)
Center for Nonlinear Studies and Computing Division
Los Alamos National Laboratory MS-B265
Los Alamos, NM 87544 USA
---------------
%A David L. Brown
%T A Numerical Method for Singular Perturbation Problems with Turning Points
%I California Institute of Technology
%D January, 1985
%X This paper considers the numerical solution of stiff systems of
linear first order ODEs with turning points. The main feature of
the method discussed is a constructive procedure for determining an
a priori scaling of the independent variable so that rapid
variations such as boundary and internal layers are resolved. From
a numerical point of view, this translates into a procedure for
constructing an appropriate numerical mesh for the problem. A
byproduct of the mesh construction procedure is that the dependent
variables corresponding to rapidly growing, rapidly decaying and
smooth modes in the problem are determined, and thus one-sided
difference approximations can be used.
This method has been extended to solving nonlinear problems by the
technique of quasilinearization. While for some problems the
quasilinearization technique works well given an appropriate
initial guess and using continuation, it has been observed that
there is a class of problems with internal layers for which
convergence is difficult to obtain. An analysis of the problems
where this occurs leads to an explanation for the difficulty, and
also leads to a remedy. Examples are presented and the new
procedure is discussed.
%A David L. Brown and Jens Lorenz
%Title A High-Order Method for Stiff-Boundary Value Problems with
Turning Points.
%R Rept. No. LA-UR 85-4406
%I Los Alamos National Laboratory
%D December, 1985
%X This paper describes some high-order collocation-like methods for
the numerical solution of stiff boundary-value problems
with turning points. The presentation concentrates on the
implementation of these methods in conjunction with the
implementation of the a priori mesh construction algorithm
introduced by Kreiss, Nichols and Brown (SIAM J. Num.
Anal., 1986) for such problems. Numerical examples are
given showing the high accuracy which can be obtained in
solving the boundary value problem for singularly perturbed
ordinary differential equations with turning points.
##### ICASE #####
---------------
Here are the latest ICASE abstracts. Barbara Kraft, ICASE, M/S 132C, NASA
Langley Research Center, Hampton, VA 23665 may be contacted for these
reports, or a message may be sent to emily%icase@csnet-relay.
---------------
%A I. G. Rosen
%T Approximation methods for inverse problems involving the
vibration of beams with tip bodies.
%R ICASE Report No. 84-51
%D September 26, 1984
%P 10
%X We outline two cubic spline based approximation schemes for the
estimation of structural parameters associated with the transverse vibration
of flexible beams with tip appendages. The identification problem is
formulated as a least squares fit to data subject to the system dynamics which
are given by a hybrid system of coupled ordinary and partial differential
equations. The first approximation scheme is based upon an abstract semigroup
formulation of the state equation while a weak/variational form is the basis
for the second. Cubic spline based subspaces together with a Rayleigh-Ritz-
Galerkin approach was used to construct sequences of easily solved finite
dimensional approximating identification problems. Convergence results are
briefly discussed and a numerical example demonstrating the feasibility of the
schemes and exhibiting their relative performance for purposes of comparison
is provided.
%A C. Canuto
%T Boundary Conditions in Chebyshev and Legendre Methods.
%R ICASE Report No. 84-52
%D October 1, 1984
%P 38
%X We discuss two different ways of treating non-Dirichlet boundary
conditions in Chebyshev and Legendre collocation methods for second order
differential problems.
An error analysis is provided. The effect of preconditioning the
corresponding spectral operators by finite difference matrices is also
investigated.
%A P. L. Roe
%T Generalized formulation of TVD Lax-Wendroff schemes.
%R ICASE Report No. 84-53
%D October 23, 1984
%P 14
%X The work of Davis [1] which imports the concept of total-variation-
diminution (TVD) into non-upwinded, Lax-Wendroff type schemes is reformulated
in a way which is easier to analyze. The analysis reveals a class of TVD
schemes not observed by Davis.
%A Shahid H. Bokhari
%T Shuffle-exchanges on augmented meshes.
%R ICASE Report No. 84-54
%D October 24, 1984
%P 12
%X Prior research has shown how a mesh connected array of size N = 2**K an
integer, can be augmented by adding at most one edge per node such that it can
perform a shuffle-exchange of size N/2 in constant time.
We now show how to perform a shuffle-exchange of size N on this augmented
array in constant time. This is done by combining the available perfect
shuffle of size N/2 with the existing nearest neighbor connections of the
mesh. By carefully scheduling the different permutations that are composed in
order to achieve the shuffle, the time required is reduced to 5 steps, which
is shown to be optimal for this network.
%A Jonathan B. Goodman
%A Randall J. LeVeque
%T A geometric approach to high resolution TVD schemes.
%R ICASE Report No. 84-55
%D October 29, 1984
%P 35
%X We use a geometric approach, similar to Van Leer's MUSCL schemes, to
construct a second-order accurate generalization of Godunov's method for
solving scalar conservation laws. By making suitable approximations we obtain
a scheme which is easy to implement and total variation diminishing. We also
investigate the entropy condition from the standpoint of the spreading of
rarefaction waves. For Godunov's method we obtain quantitative information on
the rate of spreading which explain the kinks in rarefaction waves often
observed at the sonic point.
%A Tin-Chee Wong
%A C. H. Liu
%A James Geer
%T Comparison of uniform perturbation solutions and numerical solutions
for some potential flows past slender bodies
%R ICASE Report No. 84-56
%D October 29, 1984
%P 32
%X Approximate solutions for potential flow past an axisymmetric slender
body and past a thin airfoil are calculated using a uniform perturbation
method and then compared with either the exact analytical solution or the
solution obtained using a purely numerical method. The perturbation method is
based upon a representation of the disturbance flow as the superposition of
singularities distributed entirely within the body, while the numerical
(panel) method is based upon a distribution of singularities on the surface of
the body. It is found that the perturbation method provides very good results
for small values of the slenderness ratio and for small angles of attack.
Moreover, for comparable accuracy, the perturbation method is simpler to
implement, requires less computer memory, and generally uses less computation
time than the panel method. In particular, the uniform perturbation method
yields good resolution near the regions of the leading and trailing edges
where other methods fail or require special attention.
%A M. D. Salas
%A S. Abarbanel
%A D. Gottlieb
%T Multiple steady states for characteristic initial value problems
%R ICASE Report No. 84-57
%D November 1, 1984
%P 43
%X The time dependent, isentropic, quasi-one-dimensional equations of gas
dynamics and other model equations are considered under the constraint of
characteristic boundary conditions. Analysis of the time evolution shows how
different initial data may lead to different steady states and how seemingly
anamolous behavior of the solution may be resolved. Numerical experimentation
using time consistent explicit algorithms verifies the conclusions of the
analysis. The use of implicit schemes with very large time steps leads to
erroneous results.
%A Milton E. Rose
%T A compact finite element method for elastic bodies
%R ICASE Report No. 84-58
%D November 7, 1984
%P 38
%X A nonconforming finite element method is described for treating linear
equilibrium problems, and a convergence proof showing second order accuracy is
given. The close relationship to a related compact finite difference scheme
due to Phillips and Rose is examined. A condensation technique is shown
to preserve the compactness property and suggests an approach to a certain
type of homogenization.
%A Liviu Lustman
%T A review of spectral methods
%R ICASE Report No. 84-59
%D November 19, 1984
%P 25
%X This paper presents a brief outline of spectral methods for partial
differential equations. The basic ideas, together with simple proofs are
discussed. An application to potential transonic flow is also reviewed.
%A M. Y. Hussaini
%A W. D. Lakin
%T Existence and non-uniqueness of similarity solutions
of a boundary layer problem
%R ICASE Report No. 84-60
%D November 21, 1984
%P 17
%X This work considers a Blasius boundary value problem with inhomogeneous
lower boundary conditions f(0) = 0 and f'(0) = - L with L strictly
positive. The Crocco variable formulation of this problem has a key term
which changes sign in the interval of interest. It is shown that solutions of
the boundary value problem do not exist for values of L larger than a positive
critical value LC. The existence of solutions is proved for 0 < L _ LC by
considering an equivalent initial value problem. However, for 0 < L < LC,
solutions of the boundary value problem are found to be nonunique.
Physically, this non-uniqueness is related to multiple values of the skin
friction.
%A Alvin Bayliss
%A Lucio Maestrello
%A Eli Turkel
%T On the interaction of a sound pulse with the shear layer of an
axisymmetric jet, III Nonlinear effects
%R ICASE Report No. 84-61
%D November 23, 1984
%P 22
%X The fluctuating field of a jet excited by transient mass injection is
simulated numerically. The model is developed by expanding the state vector
as a mean state plus a fluctuating state. Nonlinear terms are not neglected,
and the effect of nonlinearity is studied. A high order numerical method is
used to compute the solution. The results show a significant spectral
broadening in the flow field due to the nonlinearity. In addition, large
scale structures are broken down into smaller scales.
%A R. C. Swanson
%A Eli Turkel
%T A multistage time-stepping scheme for the Navier-Stokes equations
%R ICASE Report No. 84-62
%D November 23, 1984
%P 28
%X A class of explicit multistage time-stepping schemes is used to construct
an algorithm for solving the compressible Navier-Stokes equations. Flexibility
in treating arbitrary geometries is obtained with a finite-volume formulation.
Numerical efficiency is achieved by employing techniques for accelerating
convergence to steady state. Computer processing is enhanced through
vectorization of the algorithm. The scheme is evaluated by solving laminar
and turbulent flows over a flat plate and an NACA 0012 airfoil. Numerical
results are compared with theoretical solutions or other numerical solutions
and/or experimental data.
%A Yann Brenier
%A Stanley Osher
%T Approximate Riemann solvers and numerical flux functions
%R ICASE Report No. 84-63
%D December 5, 1984
%P 33
%X Given a monotone function z(x) which connects two constant states,
uL < uR, (uL > uR), we find the unique (up to a constant) convex (concave)
flux function, F(u) such that z(x/t) is the physically correct solution to
the associated Riemann problem. For z(x/t), an approximate Riemann solver to
a given conservation law, we derive simple necessary and sufficient conditions
for it to be consistent with any entropy inequality. Associated with any
member of a general class of consistent numerical fluxes, hf(uR,uL), we have
an approximate Riemann solver defined through z(Z) = (-d/dZ)hfZ(uR,uL), where
fZ(u) = f(u) - Zu. We obtain the corresponding F(u) via a Legendre
transform and show that it is consistent with all entropy inequalities iff
hfZ(uR,uL) is an E flux for each relevant Z. Examples involving commonly
used two point numerical fluxes are given, as are comparisons with related
work.
%A Philip Hall
%A Mujeeb R. Malik
%T On the instability of a three-dimensional attachment line boundary layer:
Weakly nonlinear theory and a numerical approach
%R ICASE Report No. 84-64
%D December 6, 1984
%P 65
%X The instability of a three-dimensional attachment line boundary layer is
considered in the nonlinear regime. Using weakly nonlinear theory, it is
found that, apart from a small interval near the (linear) critical Reynolds
number, finite amplitude solutions bifurcate subcritically from the upper
branch of the neutral curve. The time-dependent Navier-Stokes equations for
the attachment line flow have been solved using a Fourier-Chebyshev spectral
method and the subcritical instability is found at wavenumbers that correspond
to the upper branch. Both the theory and the numerical calculations show the
existence of supercritical finite amplitude (equilibrium) states near the
lower branch which explains why the observed flow exhibits a preference for
the lower branch modes. The effect of blowing and suction on nonlinear
stability of the attachment line boundary layer is also investigated.
%A George J. Fix
%A Manil Suri
%T Three-dimensional mass conserving elements for compressible flows
%R ICASE Report No. 84-65
%D December 13, 1984
%P 27
%X A variety of finite element schemes has been used in the numerical
approximation of compressible flows particularly in underwater acoustics. In
many instances instabilities have been generated due to the lack of mass
conservation. In this paper we develop new two- and three-dimensional
elements which avoid these problems.
%A H. Thomas Banks
%A James M. Crowley
%T Estimation of material parameters in elastic systems
%R ICASE Report No. 84-66
%D December 28, 1984
%P 45
%X In this paper we present theoretical and numerical results for inverse
problems involving estimation of spatially varying parameters such as
stiffness and damping in distributed models for elastic structures such as
Euler-Bernoulli beams. An outline of algorithms we have used and a summary of
some of our computational experiences are presented.
%A Kazufumi Ito
%A Robert K. Powers
%T Chansrasekhar equations for infinite dimensional systems
%R ICASE Report No. 84-67
%D December 31, 1984
%P 36
%X In this paper we derive the Chandrasekhar equations for linear time
invariant systems defined on Hilbert spaces using a functional analytic
technique. An important consequence of this is that the solution to the
evolutional Riccati equation is strongly differentiable in time and one can
define a 'strong' solution of the Riccati differential equation. A detailed
discussion on the linear quadratic optimal control problem for hereditary
differential systems is also included.
%A James M. Ortega
%A Robert G. Voigt
%T Solution of partial differential equations on vector and
parallel computers
%R ICASE Report No. 85-1
%D January 2, 1985
%P 173
%X In this paper we review the present status of numerical methods for
partial differential equations on vector and parallel computers. A discussion
of the relevant aspects of these computers and a brief review of their
development is included, with particular attention paid to those
characteristics that influence algorithm selection. Both direct and iterative
methods are given for elliptic equations as well as explicit and implicit
methods for initial-boundary value problems. The intent is to point out
attractive methods as well as areas where this class of computer architecture
cannot be fully utilized because of either hardware restrictions or the lack
of adequate algorithms. A brief discussion of application areas utilizing
these computers is included.
%A Robert G. Voigt
%T Where are the parallel algorithms?
%R ICASE Report No. 85-2
%D January 16, 1985
%P 14
%X Four paradigms that can be useful in developing parallel algorithms are
discussed. These include computational complexity analysis, changing the
order of computation, asynchronous computation, and divide and conquer. Each
is illustrated with an example from scientific computation, and it is shown
that computational complexity must be used with great care or an inefficient
algorithm may be selected.
%A D. Gottlieb
%A E. Tadmor
%T Recovering pointwise values of discontinuous data within spectral accuracy
%R ICASE Report No. 85-3
%D January 31, 1985
%P 20
%X We show how pointwise values of a function, f(x), can be accurately
recovered either from its spectral or pseudospectral approximations, so that
the accuracy solely depends on the local smoothness of f in the neighborhood
of the point x. Most notably, given the equidistant function grid values,
its intermediate point values are recovered within spectral accuracy, despite
the possible presence of discontinuities scattered in the domain. (Recall
that the usual spectral convergence rate decelerates otherwise to first order,
throughout).
To this end we employ a highly oscillatory smoothing kernel, in contrast
to the more standard positive unit-mass mollifiers.
In particular, post-processing of a stable Fourier method applied to
hyperbolic equations with discontinuous data, recovers the exact solution
modulo a spectrally small error. Numerical examples are presented.
%A R. E. Noonan
%T An algorithm for generating abstract syntax trees
%R ICASE Report No. 85-4
%D January 31, 1985
%P 18
%X In this paper, we discuss the notion of an abstract syntax. An algorithm
is presented for automatically deriving an abstract syntax directly from a BNF
grammar. The implementation of this algorithm and its application to the
grammar for Modula are discussed.
%A W. D. Lakin
%T Differentiating Matrices for Arbitrarily Spaced Grid Points
%R ICASE Report No. 85-5
%D January 31, 1985
%P 23
%X Differentiating matrices allow the numerical differentiation of functions
defined at points of a discrete grid. The present work considers a type of
differentiating matrix based on local approximation on a sequence of sliding
subgrids. Previous derivations of this type of matrix have been restricted to
grids with uniformly spaced points, and the resulting derivative
approximations have lacked precision, especially at endpoints. The new
formulation allows grids which have arbitrarily spaced points. It is shown
that high accuracy can be achieved through use of differentiating matrices on
non-uniform grids which include "near-boundary" points. Use of the
differentiating matrix as an operator to solve eigenvalue problems involving
ordinary differential equations is also considered.
%A Peter J. Fleming
%T SUBOPT - A CAD program for suboptimal linear regulators.
%R ICASE Report No. 85-6
%D February 4, 1985
%P 16
%X This interactive software package provides design solutions for both
standard linear quadratic regulator (LQR) and suboptimal linear regulator
problems. Intended for time-invariant continuous systems the package is
easily modified to include sampled-data systems. LQR designs are obtained by
established techniques while the large class of suboptimal problems containing
controller and/or performance index options is solved using a robust gradient
minimization technique. Numerical examples demonstrate features of the
package and recent developments are described.
%A H. Thomas Banks
%A I. Gary Rosen
%T A Galerkin method for the estimation of parameters in hybrid
systems governing the vibration of flexible beams with tip bodies
%R ICASE Report No. 85-7
%D February 5, 1985
%P 44
%X In this report we develop an approximation scheme for the identification
of hybrid systems describing the transverse vibrations of flexible beams with
attached tip bodies. In particular, problems involving the estimation of
functional parameters (spatially varying stiffness and/or linear mass density,
temporally and/or spatially varying loads, etc.) are considered. The
identification problem is formulated as a least squares fit to data subject to
the coupled system of partial and ordinary differential equations describing
the transverse displacement of the beam and the motion of the tip bodies
respectively. A cubic spline-based Galerkin method applied to the state
equations in weak form and the discretization of the admissible parameter
space yield a sequence of approximting finite dimensional identification
problems. We demonstrate that each of the approximating problems admits a
solution and that from the resulting sequence of optimal solutions a
convergent subsequence can be extracted, the limit of which is a solution to
the original identification problem. The approximating identification
problems can be solved using standard techniques and readily available
software. Numerical results for a variety of examples are provided.
%A Hillel Tal-Ezer
%T The eigenvalues of the pseudospectral Fourier approximation
to the operator sin(2x) (d/dx)
%R ICASE Report No. 85-8
%D February 7, 1985
%P 10
%X In this note we show that the eigenvalues of the pseudospectral Fourier
approximation to the operator sin(2x) (d/dx) have real parts either equal to
zero or equal to plus or minus one.
Whereas this does not prove stability for the Fourier method, applied to the
hyperbolic equation
dU/dt = sin[2x)(dU/dx) - Pi < x < - Pi;
it indicates that the growth in time of the numerical solution is essentially
the same as that of the solution to the differential equation.
%A Hillel Tal-Ezer
%T Spectral methods in time for parabolic problems
%R ICASE Report No. 85-9
%D February 8, 1985
%P 19
%X A pseudospectral explicit scheme for solving linear, periodic, parabolic
problems is described. It has infinite accuracy both in time and in space.
The high accuracy is achieved while the time resolution parameter M (M =
0(1/(delta t)) for time marching algorithm) and the space resolution parameter
N (N = 0(1/(delta t)) have to satisfy M = 0(N**(1 + ep)) ep > 0, compared to
the common stability condition M = 0(N**2) which has to be satisfied in any
explicit finite order time algorthm.
%A Eitan Tadmor
%T Complex symmetric matrices with strongly stable iterates
%R ICASE Report No. 85-10
%D February 14, 1985
%P 22
%X We study complex-valued symmetric matrices. A simple expression for the
spectral norm of such matrices is obtained, by utilizing a unitarily congruent
invariant form. Consequently, we provide a sharp criterion for identifying
those symmetric matrices whose spectral norm is not exceeding one: such
strongly stable matrices are usually sought in connection with convergent
difference approximations to partial differential equations. As an example,
we apply the derived criterion to conclude the strong stability of a Lax-
Wendroff scheme.
%A Eli Turkel
%T Algorithms for the Euler and Navier-Stokes equations for supercomputers
%R ICASE Report No. 85-11
%D February 14, 1985
%P 27
%X We consider the steady state Euler and Navier-Stokes equations for both
compressible and incompressible flow. Methods are found for accelerating the
convergence to a steady state. This acceleration is based on preconditioning
the system so that it is no longer time consistent. In order that the
acceleration technique be scheme independent this preconditioning is done at
the differential equation level. Applications are presented for very slow
flows and also for the incompressible equations.
%A Terrence W. Pratt
%T PISCES: An environment for parallel scientific computation
%R ICASE Report No. 85-12
%D February 15, 1985
%P 30
%X PISCES (Parallel Implementation of Scientific Computing EnvironmentS) is
a project to provide high-level programming environments for parallel MIMD
computers. Pisces 1, the first of these environments, is a Fortran 77 based
environment which runs under the UNIX operating system. The Pisces 1 user
programs in Pisces Fortran, an extension of Fortran 77 for parallel
processing. The major emphasis in the Pisces 1 design is in providing a
carefully specified "virtual machine" that defines the run-time environment
within which Pisces Fortran programs are executed. Each implementation then
provides the same virtual machine, regardless of differences in the underlying
architecture. The design is intended to be portable to a variety of
architectures. Currently Pisces 1 is implemented on a network of Apollo
workstations and on a DEC VAX uniprocessor via simulation of the task level
parallelism. An implementation for the Flexible Computing Corp. FLEX/32 is
under construction. This paper provides an introduction to the Pisces 1
virtual computer and the Fortran 77 extensions. An example of an algorithm
for the iterative solution of a system of equations is given. The most
notable features of the design are the provision for several different
"granularities" of parallelism in programs and the provision of a "window"
mechanism for distributed access to large arrays of data.
%A Eduard Harabetian
%T A convergent series expansion for hyperbolic systems of
conservation laws
%R ICASE Report No. 85-13
%D February 20, 1985
%P 88
%X We consider the discontinuous piecewise analytic initial value problem
for a wide class of conservation laws that includes the full three-dimensional
Euler equations. The initial interaction at an arbitrary curved surface is
resolved in time by a convergent series. Among other features the solution
exhibits shock, contact, and expansion waves as well as sound waves
propagating on characteristic surfaces. The expansion waves correspond to the
one-dimensional rarefactions but have a more complicated structure. The sound
waves are generated in place of zero strength shocks, and they are caused by
mismatches in derivatives.
%A Saul Abarbanel
%A David Gottlieb
%T Information content in spectral calculations
%R ICASE Report No. 85-14
%D February 21, 1985
%P 13
%X Spectral solutions of hyperbolic partial differential equations induce a
Gibbs phenomenon near local discontinuities or strong gradients.
A procedure is presented for extracting the piecewise smooth behavior of
the solution out of the oscillatory numerical solution data. The procedure is
developed from the theory of linear partial differential equations. Its
application to a non-linear system (the two-dimensional Euler equations of gas
dynamics) is shown to be efficacious for the particular situation.
%A Christopher L. Cox
%A George J. Fix
%T On the accuracy of least squares methods in the presence
of corner singularities
%R ICASE Report No. 85-15
%D February 21, 1985
%P 24
%X This paper treats elliptic problems with corner singularities. Finite
element approximations based on variational principles of the least squares
type tend to display poor convergence properties in such contexts. Moreover,
mesh refinement or the use of special singular elements do not appreciably
improve matters. Here we show that if the least squares formulation is done
in appropriately weighted space, then optimal convergence results in
unweighted spaces like L two.
%A Robert E. Noonan
%A W. Robert Collins
%T Construction of a menu-based system
%R ICASE Report No. 85-16
%D February 26, 1985
%P 11
%X In this paper we discuss the development of the user interface to a
software code management system. The user interface was specified using a
grammar and implemented using a LR parser generator. This was found to be an
effective method for the rapid prototyping of a menu-based system.
%A Yvon Maday
%T Analysis of spectral operators in one-dimensional domains
%R ICASE Report No. 85-17
%D February 28, 1985
%P 26
%X We prove results concerning certain projection operators on the space of
all polynomials of degree less than or equal to N with respect to a class of
one-dimensional weighted Sobolev spaces. These results are useful in the
theory of the approximation of partial differential equations with spectral
methods.
%A Philip L. Roe
%T Discrete models for the numerical analysis of time-dependent
multidimensional gas dynamics
%R ICASE Report No. 85-18
%D March 1, 1985
%P 36
%X This paper explores a possible technique for extending to
multidimensional flows some of the upwind-differencing methods that have
proved highly successful in the one-dimensional case. Attention here is
concentrated on the two-dimensional case, and the flow domain is supposed to
be divided into polygonal computational elements. Inside each element the
flow is represented by a local superposition of elementary solutions
consisting of plane waves not necessarily aligned with the element boundaries.
##### AT&T Bell Laboratories #####
---------------
The following report(s) may be obtained from:
David M. Gay
Numerical Analysis Manuscript 85-10
AT&T Bell Laboratories
600 Mountain Avenue
Murray Hill, NJ 07974
---------------
%A David M. Gay
%T A Variant of Karmarkar's Linear Programming Algorithm
for Problems in Standard Form
%R Numerical Analysis Manuscript 85-10
%I AT&T Bell Laboratories
%C 600 Mountain Avenue, Murray Hill, NJ 07974
%X This paper presents a variant of Karmarkar's linear programming algorithm
that works directly with problems expressed in standard form
and requires no a priori knowledge of the optimal objective function value.
Rather, it uses a variation on Todd and Burrell's approach to compute ever
better bounds on the optimal value, and it can be run as a primal-dual
algorithm that produces sequences of primal and dual feasible
solutions whose objective function values converge to this value.
The only restrictive assumption is that the feasible region is bounded
with a nonempty interior.
##### New York University #####
---------------
The following report(s) may be obtained from:
Mary Conway (conway@NYU.arpa)
Department of Computer Science
New York University
251 Mercer Street
New York, NY 10012
(212)460-7226
---------------
%A Raymond Chan
%T Iterative Methods for Overflow Queueing Models
%R Technical Report #171
%I New York University
%D August, 1985
%X Markovian queueing networks having overflow capacity are discussed.
The Kolmogorov balance equations result in a linear homogeneous system,
where the right null-vector is the steady-state probability
distribution for the network. The dimension of the system is equal to the
total number of states in the networks which is of the same order of
magnitude as the product of all the queue sizes. Thus it is not
uncommon that the order of the matrix exceeds 10,000. Preconditioned
conjugate gradient methods are employed to find the null-vector.
The preconditioner is a singular matrix of the same order which
can be handled by separation of variables. The resulting preconditioned
system is nonsingular. Since the states remaining are
precisely those at which interactions between the queues take place,
the dimension of this preconditioned system can usually be reduced by an
order n, where n is the individual queue size. Numerical results show
that the number of iterations required for convergence is roughly
constant when n increases. Analytic results are given to explain this
fast convergence.
%A James Demmel
%T Constrained Total Least Squares Problems and the Smallest Perturbation
of a Submatrix Which Lowers the Rank
%R Technical Report #174
%I New York University
%D September, 1985
%X Let T = < A B ; C D > be a partitioned rectangular matrix. We exhibit
perturbations of D of smallest norm which lower the rank of T. We
apply this result to generalize the total lest squares problems
Sx=b when only a rectangular subset of the data [S,b] is considered
uncertain.
%A S. Friedland
%A J. Nocedal
%A M. Overton
%T The Formulation and Analysis of Numerical Methods for Inverse
Eigenvalue Problems
%R Technical Report #179
%I New York University
%D September, 1985
%X We consider the formulation and local analysis of various
quadratically convergent methods for solving the symmetric matrix
inverse eigenvalue problem. One of these methods is new. We study
the case where multiple eigenvalues are given: we show how to state
the problem so that it si not overdetermined, and describe how to modify the
numerical methods to retain quadratic convergence on the modified problem.
We give a general convergence analysis which covers both the distinct
and the multiple eigenvalue cases. We also present numerical
experiments which illustrate our results.
%A Christoph Borgers
%T A Lagrangian Fractional Step Method for the Incompressible
Navier-Stokes Equations
%R Technical Report #183
%I New York University
%D October, 1985
%X We develop a modification of Peskin's Lagrangian fractional step
method for the incompressible Navier-Stokes equations. This new method is
substantially more efficient than the one originally proposed by Peskin.
On a grid with N points, the work per time step is proportional to
NlogN. This gain in efficiency is accomplished by modifying the
splitting and by using a multigrid method for the solution of the
resulting systems of equations.
The method uses finite difference operators constructed with the aid
of Voronoi diagrams. We have implemented it on a periodic domain in
the plane. We describe an efficient algorithm for the numerical
construction of periodic Voronoi diagrams in the plane. We believe that
this algorithm can easily be generalized to high space dimensions.
We report on numerical experiments with our method. We solve test problems
with known solutions, and we compute a flow evolving from an initial vortex
blob. Our results indicate that the method is convergent of first order.
As an application of our method, we present a fully Lagrangian variant of
Peskin's algorithm for the treatment of elastic boundaries immersed in the
fluid, and we report on numerical results obtained with this algorithm.
%A James Demmel
%T Three Methods for Refining Estimates of Invariant Subspaces
%R Technical Report #185
%I New York University
%D October, 1985
%X We compare three methods for refining estimates of invariant
subspaces, due to Chatelin, Dongarra/Moler/Wilkinson and Stewart. Even
though these methods all apparently solve different equations, we show
by changing variables that they all solve the same equation, the Riccati
equation. The benefit of this point of view is threefold. First, the
same convergence theory applies to all three methods, yielding a single
criterion under which the last two methods converge linearly, and a
slightly stronger criterion under which the first algorithm converges
quadratically. Second, it suggests a hybrid algorithm combining
advantages of all three. Third, it leads to algorithms (and convergence
criteria) for the generalized eigenvalue problem. These techniques are
compared to techniques used in the control systems community.
##### Yale #####
---------------
The following report(s) may be obtained from:
Judy Terrell
Dept of Computer Science
Yale University
P.O. Box 2158 Yale Station
New Haven, CT 06520
---------------
%A Jean-Marc Delosme
%A Ilse C.F. Ipsen
%T Parallel Solution of Symmetric Positive Definite Systems with
Hyperbolic Rotations
%R Yale Research Report 341
%I Department of Computer Science, Yale University
%D September 1985 (revised)
%X An algorithm based on hyperbolic rotations is presented for the
solution of linear systems of equations, Ax=b, with symmetric positive
definite coefficient matrix A. Forward elimination and
backsubstitution are replaced by matrix vector multiplications,
rendering the method amenable to implementation on a variety of
parallel and vector machines. The method can be simplified and
formulated without square-roots if A is also Toeplitz; a systolic
(VLSI) architecture implementing the resulting recurrence equations is
more efficient than previously proposed pipelined Toeplitz system
solvers. The hardware count becomes independent of the matrix size if
its inverse is banded.
%A Jean-Marc Delosme
%A Ilse C.F. Ipsen
%T Efficient Systolic Arrays for the Solution of Toeplitz Systems : An
Illustration of a Methodology for the Construction of Systolic
Architectures in VLSI
%R Yale Research Report 370
%I Department of Computer Science, Yale University
%D June 1985
%X A methodology is proposed that automates the mapping of recurrence
equations to processor arrays. Two aspects distinguish our
methodology from extant work : (1) complex coupled systems of
recurrence equations can be systematically treated and (2) the
resulting systolic systems are optimal. The methodology takes as
input recurrence equations describing the algorithm, along with
certain desirable hardware features. A sophisticated optimization
procedure is then applied to generate the description of optimal
arrays that implement the algorithm. If there is no satisfactory
implementation, the algorithm will have to be revised, in order to
improve pipelinability, without sacrificing numerical stability.
Several classes of applications will significantly benefit from this
approach : fast analysis of parallel algorithms, efficient
partitioning of algorithms, and determination of optimal architectures
for the implementation of multiple algorithms.
##### University of Colorado at Boulder #####
---------------
The following report(s) may be obtained from:
Richard Byrd (richard@boulder.csnet)
Department of Computer Science
University of Colorado
Boulder, Colorado 80309
---------------
%A R.H. Byrd
%A R.B. Schnabel
%A G.A. Shultz
%T A Trust Region Algorithm for Nonlinearly Constrained Optimization
%I University of Colorado Department of Computer Science
%R Report CU-CS-313-85
%D October, 1985
%X We present a trust region-based method for the nonlinearly constrained
optimization problem that works by iteratively minimizing a quadratic
model of the Lagrangian subject to a possibly relaxed linearization
of the problem constraints and a trust region constraint.
We show that this method is globally convergent even if singular or
indefinite Hessian approximations are made.
Use of a second order correction step allows us to guarantee
that the limit satisfies the second order necessary conditions for
constrained optimization.
Without this correction, a situation similar to the Maratos effect may
occur where the iteration is unable to move away from a saddle point.
##### Stanford #####
---------------
The following report(s) may be obtained from:
Gerard Meurant
Centre d'Etudes de Limeil-Valenton
BP 27
94190 Villeneuve St Georges, FRANCE
---------------
%A Gerard Meurant
%T Multitasking the conjugate gradient on the Cray X-MP/48
%R NA-85-33
%I Numerical Analysis Project, Stanford University
%D August, 1985
%X We show how to efficiently implement the preconditioned
conjugate gradient method on a four processor computer CRAY X-MP/48.
We solve block tridiagonal systems using block preconditioners well
suited to parallel computation.
Numerical results are presented that exhibit nearly optimal speed
up and high Mflops rates.
---------------
The following report(s) may be obtained from:
Gene Golub
Computer Science Department
Stanford University
Stanford CA 94305
---------------
%A Gene Golub
%T ERROR BOUNDS FOR ITERATIVE METHODS
%I Numerical Analysis Project, Stanford University
%X We descibe procedures for determining the upper and lower bounds for
the error in the approximate solution of linear equations when the
matrix is symmetric and positive definite. The error bounds are
optimal but are given for a norm dependent on the matrix of
coefficients. New results concerning the Chebyshev semi-iterative
method are given.
##### University of Durham #####
---------------
The following report(s) may be obtained with the help of:
John P. Coleman (John_Coleman%durham.mailnet@MIT-MULTICS.ARPA)
Dept. of Mathematical Sciences
University of Durham
South Road
Durham DH1 3LE
England.
---------------
%A John P. Coleman
%T Polynomial approximation in the complex plane
%I University of Durham, Dept. of Mathematical Sciences
%D September, 1985
%X Good polynomial approximations for analytic functions are
potentially useful but are in short supply. A new approach introduced
here involves the Lanczos tau-method, with perturbations proportional
to Faber or Chebyshev polynomials for specific regions of the complex
plane. The results show that suitable forms of the tau-method, which
are easy to use, can produce near-minimax polynomial approximations for
functions which satisfy linear differential equations with polynomial
coefficients. In particular, some accurate approximations of low
degree for Bessel functions are presented. An appendix describes a
simple algorithm which generates polynomial approximations for the
Bessel function of the first kind of any given order.
%A D. M. Greig
%T The solution of Moser's optimisation problem
%I University of Durham, Dept. of Mathematical Sciences
%D October, 1985
%X A nonlinear nonconvex programming problem with multiple optima arises
from the requirement of weighting an N-sided dice so that the frequency
of the most commonly occurring sum when two dice are thrown is as small
as possible.The performance of different algorithms is compared on this
problem,solutions are found for N up to 14, and theoretical bounds are
given for large N.
%A Alan Craig
%T On the convergence of iterative methods for finite dimensional
variational problems
%R Report No. C/R/522/85
%I Institute for Numerical Methods for Engineering, Swansea
%D July, 1985
%X In this paper a general technique is constructed with which
one may study the convergence of iterative methods. The technique
is applicable, not only to standard methods (such as Jacobi or
successive overrelaxation), but also to generalised forms of
multigrid methods. In addition to showing the convergence of
standard multigrid methods it will be applied to the study of
nonnested multigrid methods, where each grid bears no relation
to any of the others, and to unstructured multigrid methods,
where we do not apply a strict 'cycling' amongst the grids.
It is shown that both of these iterative techniques are
convergent under certain mild, and easily verifiable conditions.
%A O.C.Zienkiewicz
%A Alan Craig
%T Adaptive refinement, error estimates, multigrid solution and hierarchic
finite element concepts
%R REPORT NO. : C/P/514/85
%I Institute for Numerical Methods in Engineering, Swansea.
%D April, 1985
%A John P. Coleman
%A Russell A. Smith
%T The Faber polynomials for circular sectors
%I University of Durham, Dept. of Mathematical Sciences
%D January, 1986
%X The Faber polynomials for a region of the complex plane,
which are of interest as a basis for polynomial approximation
of analytic functions, are determined by a conformal mapping
of the complement of that region to the complement of the
unit disc. We derive this conformal mapping for a sector
of the unit disc, symmetric about the real axis, and discuss
the computation of the coefficients of the Faber polynomials
of degree 1 to 15, which are tabulated here for sectors of
half-angle 5, 10, 15, 30, 45, and 90 degrees. Explicit
expressions are given for the polynomials of degree 1 to 3.
The norms of Faber polynomials are tabulated and are compared
with those of the Chebyshev polynomials for the same regions.
##### Chalmers University of Technology #####
---------------
The following report(s) may be obtained from:
Axel Ruhe (ruhe@chalmers.csnet)
Department of Computer Science
Chalmers University of Technology
S-41296 Goteborg
Telephone int-46-31810100 ext. 1015
---------------
%A Kenneth Holmstrom
%A Axel Ruhe
%T Complex formation constants - a challenging data fitting problem
from Solution Chemistry
%R Report GNA-1
%D November, 1985
%X The computation of chemical equilibrium is studied mathematically
and numerically, specializing to the case of complex formation in a solution.
It is shown that the complex formation constants occur as Taylor coefficients
when the total osmotic concentration is expanded as a function of the
free concentrations of the elements. Computing these formation constants
from observations from a titration experiment, is a constrained nonlinear
least squares problem, whose Lagrange multipliers give information on which
complexes that are actually formed.
Numerical tests from chemical experiments are reported.
%A Yong Feng Zhou
%A Axel Ruhe
%T Numerical Path Following and Eigenvalue Criteria for Branch switching
%R Report GNA-2
%D November, 1985
%X Methods for numerical path following for nonlinear
eigenvalue problems are studied. Euler Newton continuation along
curves parameterized by a semi arc length is described. Criteria
for localizing singular points (turning points or bifurcations)
by means of a linear eigenproblem are introduced. It is found that
a technique, which for the linear symmetric case is the same as
spectral transformation, gives a surprisingly accurate prediction
of the position of a singular point and the direction of bifurcating
branches.
Practical applications are discussed and numerical examples are reported.
##### Penn State #####
---------------
The following report(s) may be obtained from:
Jesse L. Barlow
Computer Science Department
The Pennsylvania State University
University Park, PA 16802
(814) 863-1705
barlow@psuvax1.bitnet
allegra!psuvax1!barlow@BERKELEY.ARPA
na.barlow@SU-SCORE.ARPA
---------------
%A J.L. Barlow
%A S.L. Handy
%T On Downweighting Methods for the Solution of Sparse Equality
Constrained Least Squares Problems
$R Report CS-85-16
%D November, 1985
%X The downweighting approach to the solution of sparse equality
constrained linear least squares problems is considered.
A method is proposed which uses downweighting, but does not require
complete row and column pivoting as have downweighting methods in
the past. It is shown that reasonable freedom in row permutations
and a modified minimum degree strategy for column permutations
are possible for this downweighting strategy. This makes it a
feasable method for large, sparse problems. An error analysis is
given which shows that the method is as stable as standard
downweighting with complete row and column pivoting.
Empirical tests are given which show that this new strategy
allows one to preserve much more of the sparsity in the constraint matrix
than standard downweighting.
The residual correction scheme of Van Loan is also examined.
The convergence of this iteration with an approximate factorization
of the downweighted problem is analyzed. It is shown that for this
iteration to converge on the full range of problems possible, it is
necessary that a pivoting strategy such as that given in this paper
be used.
%A J.L. Barlow
%T On the Smallest Positive Singular Value of a Singular M-matrix with
applications to ergodic Markov chains
%R CS-85-11
%D July, 1985
%X Let A be a singular M-matrix of dimension n and rank n-1. Let
B be a nonsingular submatrix of A of dimension n-1 that results from
deleting one row and column from A. An open question disucssed
Harrod and Plemmons [Siam J. Sci. Stat. Computing 5(1984) pp.453-459])
is whether there is a choice of row and column to delete from A (to
obtain B) such that the smallest singular value of B is approximately
the same as the smallest positive singular value of A. In this paper,
we resolve this conjecture by showing that there is always such a
choice.
This conjecture is important when finding the stationary distribution
of an ergodic Markov chain. This can be posed as the problem of
finding the n-vector p such that Ap = 0 and TRANS(e)*p = 1
where e = (1, ... , 1). Here A = I - TRANS(Q) where
Q is a row stochastic matrix, p is the stationary distribution,
and TRANS denotes transpose. This problem can be reduced to the
problem of solving a system of linear equations with coefficient
matrix B. Since the smallest singular value of B is approximately
the same as the smallest positive singular value of A, this system
is about as well conditioned as the original problem.
%A Richard J. Zaccone
%A Jesse L. Barlow
%T Improved Normalization Results for Digit Online Arithmetic
%R CS-84-16
%D October, 1984
%X In digit online arithmetic, operands are introduced a digit at a time.
After the first few operand digits have been introduced, the result
begins to appear a digit at a time. This feature of digit online
arithmetic allows a significant amount of overlapping of arithmetic
operations.
Digit online arithmetic can sometimes produce unnormalized results.
This can present a problem for the divide and square root algorithms.
If the divisor and radicand are highly unnormalized, these algorithms
will not produce the correct results. Two advances in overcoming this
problem are presented. First, several techniques for producing results
that are closer to being normalized are developed. Second, it is shown
that normalized results are not necessary for divide and square root
to work properly. Combining these results yields algorithms that will
always give the correct results.