E1AR0002@SMUVM1.BITNET (06/12/86)
==================================================
NUMERICAL ANALYSIS TITLES -- Volume 4, Number 2
June 1986
==================================================
---------------
As in the last volume, we are using troff/refer format:
%A Author's name (this field is repeated for each author)
%T Title of report
%R Report number (optional)
%I Issuer (optional)
%C Address (optional)
%D Date of publication
%P Number of pages or range of page numbers (optional)
%X Abstract (optional)
---------------
##### Aachen #####
---------------
The following report(s) may be obtained from:
Frau Ch. Jarausch
Institute for Geometry and Practical
Mathematics
RWTH-Aachen
Templergraben 55
D-5100 Aachen, Fed. Rep. Germany
or by sending an electronic message to
NA.Jeltsch at SU-Score.arpa
(Submitted by Rolf Jeltsch.)
---------------
%A Bernd Einfeldt
%T Higher-Order Godunov-Type Schemes
%R Report 34
%I Institut for Geometrie and Practical Mathematics
%C RWTH-Aachen
%D October 1985
%A Helmut Jarausch
%A Wolfgang Mackens
%T Computing Bifurcation Diagrams for Large Nonlinear Variational Problems
%R Report 35
%I Institut for Geometry and Practical Mathematics
%C RWTH-Aachen
%D October 1985
##### Alabama #####
---------------
Submitted by: Bruce Suter
Obtainable from: Prof. Bruce Suter
Dept. of Computer and Information Science
University of Alabama at Birmingham
University Station
Birmingham, AL 35294
<suter@UAB.CSNet>
---------------
%A Bruce W. Suter
%T A Parallel Algorithm for the Discrete Radon Transform
%I Proceedings of IEEE Computer Society Workshop on Computer Architecture for
Pattern Analysis and Image Database Management
%D November 18-20, 1985
%P 394-398
%X A new discrete Radon transform algorithm designed for parallel processing
is presented. A special case of the discrete Radon transform is the Hough
transform, an algorithm for the detection of straight line segments. One
deficiency of the Hough transform is a distortion in the shape and location
of peaks in parameter space. This difficulty can be avoided when using the
discrete Radon transform. The basic structure of the discrete Radon t
transform is a series of linearly weighted summations. Each term is the
product of the intensity associated with a given pixel and the line length
through the pixel.
%A Bruce W. Suter and Stanley R. Deans
%T A Hankel Transform Algorithm for Uniformly Sampled Data
%I Proceedings of IEEE International Conference on Acoustics, Speech, and
Signal Processing
%D March 26-29, 1985
%P 1542-1545
%X A new Hankel transform algorithm designed for uniformly sampled data is
presented. Although data of this type occur frequently, previous algorithms
require interpolations and/or numerical evaluations of Bessel functions.
These difficulties can be avoided by using a Tchebycheff transform followed
by a Fourier transform. The basic structure and performance of any Hankel
transform derived from this two-step process depends on the combined results
from the numerical methods used to compute the Tchebycheff and Fourier
transforms. The algorithm presented here is the most elementary of several
algorithms derived from this procedure. Examples are presented and errors
associated with the results are discussed.
##### Bell Labs #####
---------------
Submitted by: Linda Kaufman
Obtainable from: Linda Kaufman
Room 2c-461, Bell Labs
600 Mountain Ave.
Murray Hill, N.J. 07974
<lck%piggot@btl.csnet>
---------------
%A Linda Kaufman
%T The Generalized Householder Transformation and Sparse Matrices
%R Numerical Analysis Manuscript 85-9
%I AT&T Bell Laboratories
%C Rm. 2c-461, 600 Mountain Ave., Murray Hill, N.J. 07974
%D August 1985
%X
Many algorithms for solving eigenvalue, least squares and
nonlinear programming problems require the determination of an
orthogonal matrix Q such that for a given matrix C ,
Q transforms C into an upper triangular matrix, Q C .
Usually Q is a product of Householder transformations. Each
transformation is a rank 1 modification of the identity matrix
designed to annihilate elements in one vector. Several years ago
Bronlund and Johnson proposed a generalization of the Householder
transformation that is a rank k modification of the identity
matrix designed to annihilate elements in k vectors
simultaneously. In this paper their generalized Householder
transformation will be discussed in the context of sparse
problems.
%A Linda Kaufman
%T Implementing and accelerating the EM algorithm
for Positron Emission Tomography
%R Numerical Analysis Manuscript 85-15
%I AT&T Bell Laboratories
%C Rm. 2c-461, 600 Mountain Ave., Murray Hill, N.J. 07974
%D Dec. 1985
%X Since the publication of Shepp and Vardi's[3] maximum likelihood
reconstruction algorithm for emission tomography(ET), many
medical research centers engaged in ET have made an effort to
change their reconstruction algorithms to this new approach.
Some have succeeded while others claim they could not adopt this
new approach primarily because of limited computing power. In
this paper we discuss techniques for reducing the computational
requirements of the reconstruction algorithm. Specifically the
paper discusses the data structures one might use and ways of
taking advantage of the geometry of the physical system. The
paper also treats some of the numerical aspects of the
EM(Expectation Maximization) algorithm, and ways of speeding up
the numerical algorithm using some of the traditional techniques
of numerical analysis.
##### Boulder & NBS #####
---------------
Submitted by: Richard H. Byrd
Obtainable from: Richard H. Byrd
Dept. of Computer Science
Campus Box 430
University of Colorado
Boulder, Colorado 80309
<richard@BOULDER.CSNet>
---------------
%A Paul T. Boggs
%A Richard H. Byrd
%A Robert B. Schnabel
%T A stable and efficient algorithm for nonlinear orthogonal distance regression
%R Report CU-CS-317-85
%I Dept. of Computer Science, Univ. of Colorado
%C Boulder, Colorado 80309
%D December 1985
%X Abstract
In data fitting problems where significant observation errors exist in all
data variables the ordinary least squares approach, where all errors are
attributed to a single variable, is often inappropriate.
An alternative approach, which has been suggested by several researchers,
involves minimizing the sum of squared distances between each data point and
the curve described by the model equation. In this paper we describe a method
for solving this problem, which refer to as the orthogonal distance fitting
problem, that is a direct analog of the Levenberg-Marquardt algorithm.
In spite of the size of the optimization problem, with as many unknowns
as there are data points, this algorithm exploits sparsity so that the
computational effort per step is of the same order as required for ordinary
least squares. We prove the algorithm to be globally and locally convergent,
and perform some computational tests on some examples that illustrate
the differences between the two approaches.
##### Cornell #####
---------------
Submitted by: Franklin Luk
Obtainable from: Franklin Luk
School of Electrical Engineering
Cornell University
Ithaca, NY 14853
<luk%tesla.ee@cornellcsnet>
---------------
%A Franklin T. Luk and David E. Schimmel
%T A New Systolic Array for the Singular Value Decomposition
%R EE-CEG-85-7
%I School of Electrical Engineering
%C Cornell University, Ithaca, NY 14853
%D December 1985
%X A new systolic processor system is proposed for computing the
singular value decomposition of an m-by-n matrix. This approach
uses only orthogonal interconnections and simple multiply and
accumulate processors in the array. The square root computations
are all performed by one boundary processor. The architectute
requires O(n) processors and O(mnS) time.
%A Franklin Luk
%T Architectures for Computing Eigenvalues and SVDs
%R EE-CEG-86-1
%I School of Electrical Engineering
%C Cornell University, Ithaca, NY 14853
%D February 1986
%X Systolic architectures for eigenvalues and singular values are discussed.
One "triangular" processor and associated algorithms for computing the
QR decomposition, the singular value decomposition, the generalized
singular value decomposition and the CS decomposition are described
in detail.
%A Franklin Luk and Haesun Park
%T Fault-tolerant Matrix Triangularizations on Systolic Arrays
%R EE-CEG-86-2
%I School of Electrical Engineering
%C Cornell University, Ithaca, NY 14853
%D February 1986
%X We examine the checksum methods of Abraham et al. for LU decomposition
on multiprocessor arrays.
Their methods are efficient for detecting a transient error,
but expensive for correcting it
due to the need for a computation rollback.
We show how to avoid the rollback by using matrix updating techniques,
and we introduce new checksum methods for
Gaussian elimination with pairwise pivoting and for QR decomposition
on systolic arrays.
##### Duke #####
---------------
Submitted by: Craig C. Douglas <ccd@DUKE.CSNet>
This work is available as Research Report RC 11742 (#52722)
on request from:
IBM T. J. Watson Research Center
Distribution Services F-11 Stormytown
P. O. Box 218
Yorktown Heights, NY 10598
---------------
%A Craig C. Douglas
%A Willard L. Miranker
%T Constructive Interference in Parallel Algorithms
%I Mathematical Sciences Department, IBM T. J. Watson Research Center
%C P. O. Box 218, Yorktown Heights, NY 10598
%R RC 11742 (#52722)
%X Parallel algorithms are developed in the setting of iterative
multilevel methods. The constituent parts of the algorithms are dependent
rather than independent as in conventional parallel algorithms. We develop
cases and conditions wherein this dependence generates a constructive
interference in the computation. The resulting parallel algorithms can then
be more efficient than serial counterparts.
##### Delft #####
---------------
Submitttted by: Henk van der Vorst
Obtainable from:
H.A.van der Vorst
Department of Mathematics and Informatics
Delft University of Technology
P.O.Box 356
2600 AJ DELFT, Netherlands
---------------
%A A.van der Sluis & H.A.van der Vorst
%T The rate of convergence of conjugate gradients
%R nr. 354
%D November 1984
%P 29
%X It has been observed that the rate of convergence of Conjugate
Gradients increases when one or more of the extreme Ritz values have
sufficiently converged to the corresponding eigenvalues (the 'super-
linear convergence' of CG). In this paper this will be proved and
made quantitative. It will be shown that a very modest degree of
convergence of an extreme Ritz value already suffices for an increased
rate of convergence to occur.
%A Henk A.van der Vorst
%T Analysis of a parallel solution method for tridiagonal systems
%R REPORT 86-06
%D MAY 1986
%P 14
%X We analyse an alternative decomposition for a tridiagonal matrix, which has
the property that the decomposition as well as the subsequent solution
process can be done in two parallel parts. This decomposition is equiva-
lent to a parallel variant of Gaussian elimination that has been proposed
Joubert and Cloete. The computational complexity of this alternative
decomposition is the same as for the standard decomposition and a remar-
kable aspect is that it often leads to slightly more accurate solutions
than the standard process does. The algorithm can be combined with recur-
sive doubling or cyclic reduction in order to increase the degree of
parallelism and vectorizability.
%A A.van der Sluis & H.A. van der Vorst
%T The convergence behaviour of Ritz values in the presence of close
eigenvalues
%R REPORT 86-08
%D MAY 1986
%P 52
%X In this paper a number of results for Ritz values are presented. These
are used to study the local effects in the convergence behaviour of Ritz
values corresponding to a pair of close eigenvalues in the spectrum.
The local effects that are typical for such a situation are illustrated
by numerical examples.
##### NAG #####
---------------
The following NAG reports may be obtained from:
Stephen Hurley
Numerical Algorithms Group
256 Banbury Road
Oxford, OX2 7DE
England
(nagkvf%vax2.ox@ucl-cs.arpa or na.hurley@su-score.arpa)
---------------
%A Stephen Hurley
%T Computation of the Singular Value Decomposition using Systolic Arrays
%R NAG TR1/86
%D March 1986
%X We present an overview of the computation of the singular value
decomposition of a general m X n(m>=n) real matrix, using systolic
array type architectures.
A brief description of systolic arrays is also presented.
%A K.V. Fernando
%T VLSI Computation of the SVD of Real Matrices via the Method of
Kogbetliantz.
Part 1: Algorithms for Diagonalisation of 2 X 2 Real Matrices
%R NAG TR2/86
%D March 1986
%X Algorithms for diagonalisation of 2 X 2 real matrices using orthonormal
transformations are developed which are paramount in VLSI computation
of the singular value decomposition based on the method of Kogbetliantz.
----------------
And the following NAG reports may be obtained from:
Sven Hammarling
NAG Central Office
256 Banbury Road
Oxford OX2 7DE
U.K.
----------------
%A Sven Hammarling
%T The numerical solution of the Kalman filtering problem
%R NAG Technical Report TR1/85
%D October 1985
%P 11
%X The report presents a short historical perspective of the numerical
solution of the Kalman filtering problem covering 25 years from the
Kalman paper of 1960.
%A Sven Hammarling
%T The numerical solution of the general Gauss-Markov linear model
%R NAG Technical Report TR2/85
%D October 1985
%P 13
%X The report presents an overview of the numerical solution of the
linear least squares problem associated with the general Gauss-Markov
linear model
y = Xb + e, e - N( 0, W ),
where W is a symmetric non-negative definite variance-covariance
matrix.
%A K V Fernando
%T Conditions for internal stability of 2D systems
%R NAG Technical Report TR3/85
%D October 1985
%P 6
%X The numerical range (the field value) of a matrix is generalised for
two matrices and via this extension new stability conditions for 2D
systems are derived.
##### Oak Ridge #####
--------------------
Obtainable from: D. C. Human
Mathematical Sciences
P. O. Box Y, Bldg. 9207A
Oak Ridge National Laboratory
Oak Ridge, Tennessee 37831
--------------------
%A L. J. Gray
%A T. Kaplan
%T Analytic Continuation and Green's Function Calculations
%R ORNL-6191
%I Oak Ridge National Laboratory
%C Oak Ridge, Tennessee
%D November 1985
%X Hass, Velicky, and Ehrenreich have shown that Green's function values
can be obtained appreciably faster by performing the calculation at
complex energies with large imaginary parts and then coming back to real
energies by an analytic continuation algorithm. However, analytic
continuation is numerically unstable and thus an error analysis is
essential if one is to have confidence in the results of the
continuation. In this paper, error estimates are obtained for the power
series method of Hass et al. and also for a method based upon Cauchy's
Theorem introduced herein. These estimates can be used to select
appropriate values for the parameters of the continuation algorithms
and also to determine which of the two methods is most appropriate for
a given calculation.
%A A. George
%A M. T. Heath
%A J. Liu
%A E. Ng
%T Sparse Cholesky Factorization on a Local-Memory Multiprocessor
%R ORNL/TM-9962
%I Oak Ridge National Laboratory
%C Oak Ridge, Tennessee
%D March 1986
%X This article deals with the problem of factoring a large sparse
positive definite matrix on a multiprocessor system. The processors
are assumed to have substantial local memory but no globally shared
memory. They communicate among themselves and with a host processor
through message passing. Our primary interest is in designing an
algorithm which exploits parallelism, rather than in exploiting
features of the underlying topology of the hardware. However, part of
our study is aimed at determining, for certain sparse matrix problems,
whether hardware based on the binary hypercube topology adequately
supports the communication requirements for such problems. Numerical
results from experiments running on a multiprocessor simulator
are included.
%A S. Thompson
%T Software for Rootfinding and Interpolation with Runge-Kutta-Sarafyan Methods
%R ORNL-6151
%I Oak Ridge National Laboratory
%C Oak Ridge, Tennessee
%D September 1985
%X Mathematical software is described which implements Runge-Kutta methods of
Sarafyan. Due to the embedded nature of the methods, it is possible to
perform both rootfinding the interpolation in a very natural manner. The
software described contains provisions for both rootfinding and
interpolation. The ability to do rootfinding makes it possible to
efficiently handle discontinuities and special events as well as other
rootfinding tasks. The ability to do interpolation without negatively
impacting the integration stepsize selection process makes it possible to
handle the question of dense output in an efficient manner. Examples are
presented to illustrate the types of problems which may be solved and to
demonstrate the typical performance of the software.
%A A. D. Solomon
%T A Numerical Study of the Performance of Latent Heat Storage for Solar Dynamic
Power Systems
%R ORNL-6218
%I Oak Ridge National Laboratory
%C Oak Ridge, Tennessee
%D January 1986
%X A conceptual design of a space station power system based on a Brayton cycle
and solar powered has been developed. A key component of such a system is
the thermal energy storage module, which is of crucial importance during
periods of darkness. We have developed a computer program, FPAK1.F,
simulating one possible storage design. We describe the code and, using it,
raise some questions about the system under study.
%A G. A. Geist
%A R. F. Wood
%T Modeling of Complex Melting and Solidification Behavior in Laser-Irradiated M
aterials
%R ORNL-6242
%I Oak Ridge National Laboratory
%C Oak Ridge, Tennessee
%D November 1985
%X The conceptual foundation of a computational model and a computer program
based on it have been developed for treating various aspects of the complex
melting and solidification behavior observed in pulsed laser-irradiated
materials. A particularly important feature of the modeling is the
capability of allowing melting and solidification to occur at temperatures
other than the thermodynamic phase change temperatures. As a result,
interfacial undercooling and overheating can be introduced and various
types of nucleation events can be simulated. Calculations on silicon with
the model have shown a wide variety of behavior, including the formation
and propagation of multiple phase fronts. Although originally developed
as a tool for studying certain problems arising in the field of laser
annealing of semiconductors, the program should be useful in treating
many types of systems in which phase changes and nucleation phenomena play
important roles.
This report describes the underlying physical and mathematical ideas and
the basic relations used in LASER8. It also provides enough specific and
detailed information on the program to serve as a guide for its use; a
listing of one version of the programis given as an appendix.
##### Penn State #####
---------------
submitted by: Alex Pothen
obtainable from: Alex Pothen
Computer Science
Whitmore Lab
The Pennsylvania State University
University Park, PA, 16802
---------------
%A Thomas F. Coleman and Alex Pothen
%T The Null Space Problem II: Algorithms
%R CS-86-09
%I Computer Science Department, The Pennsylvania State University
%C Whitmore Lab, University Park, PA, 16802
%D April 1986
%P 31 pages
%X The Null Space Problem is that of finding a sparsest
basis for the null space ( null basis )
of a $t times n $ matrix of rank $t$.
This problem was shown to be NP-hard in Coleman and Pothen (1985).
In this paper we develop heuristic algorithms
to find sparse null bases. These algorithms have
two phases: In the first combinatorial phase,
a minimal dependent set of columns is
identified by finding a matching in the bipartite graph of the matrix.
In the second numerical phase, a null vector is
computed from this dependent set.
We describe an implementation of our algorithms and
provide computational results on several large sparse constraint matrices
from linear programs.
One of our algorithms compares favorably with previously reported
algorithms in sparsity of computed null bases and in running times.
Unlike the latter, our algorithm does not require
any intermediate dense matrix storage.
This advantage should make our algorithm an attractive
candidate for large sparse null basis computations.
A matching based algorithm is designed
to find
orthogonal null bases, but we present some
theoretical evidence that such bases are unlikely
to be sparse. Finally, we show how sparsest
orthogonal null bases may be found for an $n$-vector and
a $ t times n$ dense matrix by a divide and conquer
strategy. The algorithm for a dense matrix is suited for
implementation on a parallel machine architecture.
---------------
Submitted by: Panos M. Pardalos
Obtainable from: Panos M. Pardalos
Computer Science Department
Whitmore Laboratory
The Pennsylvania State University
University Park, PA 16802
<pardalos@PENN-STATE>
---------------
%A P. M. Pardalos
%T On generating test problems for global optimization algorithms
%R CS-86-01
%D January 1986
%A P. M. Pardalos and J.B. Rosen
%T Bounds for the solution set of linear complementarity problems
%R CS-85-30
%D November 1985
%A P. M. Pardalos, J.H. Glick and J.B. Rosen
%T Global minimization of indefinite quadratic problems
%R CS-85-31
%D November 1985
%A P. M. Pardalos and J.B. Rosen
%T Constrained Global Optimization: References
%R CS-86-02
%D January 1986
%A P. M. Pardalos and S. Gupta
%T On some classes of linear complementarity problems
%R CS-86-08
%D January 1986
##### Pitt #####
--------------
Submitted by : Rami Melhem
Obtainable from : Rami Melhem
Department of Mathematics and Statistics
The University of Pittsburgh
Pittsburgh, PA 15260 (melhem@pitt)
---------------
%A Rami Melhem
%T Parallel Solution of Linear systems With Striped Matrices.
PART 1: VLSI networks for striped matrices
%R ICMA-86-91
%I The University of Pittsburgh
%D Jan. 1986
%X The multiplication of a matrix by a vector and the solution of
triangular linear systems are the most demanding operations in
the majority of iterative techniques for the solution of linear
systems.
Data-driven VLSI networks that perform these two operations, efficiently,
for sparse matrices are introduced.
In order to avoid computations that involve zero operands,
the non-zero elements in a sparse matrix are organized in the
form of non intersecting stripes, and only the elements within
the stripe structure of the matrix are manipulated.
Detailed analysis of the networks proves that both operations
may be completed in n global cycles with minimal communication
overhead, where n is the order of the linear system.
The number of cells in each network as well as the communication
overhead are determined by the stripe structure of the matrix.
A companion paper examines this structure for the class
of sparse matrices generated in Finite Element Analysis.
%A Rami Melhem
%T Parallel Solution of Linear Systems with Striped Sparse Matrices.
Part 2: STIFFNESS MATRICES; A CASE STUDY
%R ICMA-86-92
%I The University of Pittsburgh
%D Jan. 1986
%X The stripe structures of stiffness matrices resulting from irregular domains
covered by regular grids are analysed.
It is proved that the non-zero elements in these matrices may be
covered by very few stripes, and that these stripes may be non-overlapping,
if the nodes of the grids are numbered appropriatly.
The exact number of stripes, which is independent of the size of the problem,
is derived for different types of grids, and
different numbering schemes.
The stripe structures of some irregular grids are also examined.
##### RPI #####
---------------
Obtainable from:
Robert Schreiber
Computer Science Department
Rensselaer Polytechnic Institute
Troy, NY 12181
<schreibr@RPICS.CSNet>
---------------
%A Robert Schreiber
%T Bidiagonalization and symmetric tridiagonalization by systolic array.
%X Systolic arrays for bidiagonalization of an N X N matrix and tridiagonalizati
on of a symmetric N X N matrix in O(N log N) time are described.
##### Simon Fraser, et. al. #####
---------------
Submitted by: John Paine
Obtainable by
-- but wait, let's let John tell this in his own words --
Dear Richard,
Here are some abstracts which you might like to add to your
quarterly issue of T+A. All, except the first and last papers, can be obtained
from me via the nanet ( na.jpaine@su-score). The first one can be ordered
through Bob Russell at SFU (though don't tell him that I said that!), and the
last can be requested direct from Alan -- though I'm quite willing
to pass on any email requests.
Thanks
John Paine
---------------
%A Chris Godsil
%A John Paine
%T Summing slowly converging series
%R Research Report #85-06
%I Simon Fraser University
%C Burnaby, Vancouver, B.C., Canada, V5A 1S6
%D June, 1985
%X The use of standard series summation techniques for evaluating
functions defined by series (e.g power series, Fourier series, etc.)
is usually not feasible due to the slow convergence of the series in
question. When the functions in the series have a known generating
function (e.g. the monomials have the generating function 1/(1-xt))
the series can be reexpressed as an integral of the generating function
in which the measure is defined as the solution of the moment problem
associated with the coefficients of the series. This alternative
expression for the series provides useful analytic information, and also
allows for efficient evaluation of the series via Gaussian quadrature
techniques. The main deficiency of this approach is that process of
generating the quadrature rule from the coefficients is unstable, however
examples are given which show that the method is of practical use.
%A R. S. Anderssen
%A John Paine
%T EFFICIENT COMPUTATION OF GEOPHYSICAL EIGENVALUES
%I CTAC-85 (to appear)
%C Department of Geology and Geophysics, University of Adelaide, SA 5001
%X A classical method for computing Sturm_Liouville eigenvalues
is the shooting method, for which a large body of theoretical and practical
knowledge has been developed. More recently Rayleigh--Ritz methods have also
been applied with some success. The appeal of this technique is that the
original differential eigenvalue problem is replaced by an algebraic eigenvalue
problem, and there are a number of good algorithms available for computing
matrix eigenvalues.
In this paper we recast the algebraic problem obtained from the
Rayleigh--Ritz method so that it's structure closely resembles the
shooting formulation. This recasting allows the error squaring
property of the Rayleigh quotient to be exploited in much the same way
as has been done for shooting. The resulting algorithm is very efficient
and appears to be competitive with the most efficient algebraic
methods currently available.
%A John Paine
%T A Comparison of methods for approximating the vertical gradient of
%T one--dimensional magnetic field data.
%I GEOPHYSICS (to appear)
%C Department of Geology and Geophysics, University of Adelaide, SA 5001
%X The vertical gradient of a one--dimensional magnetic field is known to be a
useful aid in the interpretation of magnetic data. When the vertical gradient
is required but has not been measured in the survey, it is necessary to
approximate it using the available total field data. This is possible because
a relationship between the total field and the vertical gradient can be
established using Fourier analysis. After reviewing the theoretical basis of
this relationship, a number of methods for approximating the vertical gradient
are derived. These methods fall into two broad categories; those based on the
discrete Fourier transform, and those based on discrete convolution filters.
There are a number of choices to be made in designing such methods, each of
which will affect the accuracy of the computed values in differing, and
sometimes conflicting, ways. A comparison of the spatial and spectral accuracy
of the methods derived here shows that it is possible to construct a filter
which maintains a reasonable balance between the various components of the total
error. Further, the structure of this filter is such that it is also
computationally more efficient than methods based on fast Fourier transform
techniques.
%A Alan L. Andrew
%A John Paine
%T CORRECTION OF FINITE ELEMENT ESTIMATES FOR STURM--LIOUVILLE EIGENVALUES
%C Department of Geology and Geophysics, University of Adelaide, SA 5001
%X It is shown that a simple asymptotic correction technique of Paine, de Hoog
and Anderssen reduces the error in the estimate of the k'th eigenvalue
of a regular Sturm--Liouville problem obtained by the finite element method,
with linear hat functions and mesh length h, from O(k^4 h^2) to
O(k h^2). The result still holds when the matrix elements are evaluated by
Simpson's rule, but if the trapezoidal rule is used the error is O(k^2 h^2).
Numerical results demonstrate the usefulness of the correction
even for low values of k.
%A Alan L. Andrew
%T The accuracy of Numerov's method for eigenvalues
%I BIT (to appear)
%C Mathematics Department,La Trobe University,Bundoora,Victoria 3083,Australia
%X A simpler proof is given of a slightly stronger version of a
convergence result of Chawla and Katti.
##### USC #####
---------------
Sumbitted by: W. Proskurowski
Obtainable from:
Computer Research Institute
University of Southern California
sal-110
Los Angeles, CA 90089-0781
---------------
%A Max Dryja
%A Wlodek Proskurowski
%T Iterative methods in subspaces for solving elliptic problems
using domain decomposition
%R cri-86-10
%I Computer Research Institute
%C University of Southern California, Los Angeles, CA 90089-0781
%D May, 1986
%P 32
%X Two substructures of the region when it is divided into strips and
boxes, and the corresponding two preconditions are studied.
numerical experiments are reported.
%A Max Dryja
%A Wlodek Proskurowski
%T Domain Decomposition Seminar Notes
%R cri-86-12
%I Computer Research Institute
%C University of Southern California, Los Angeles, CA 90089-0781
%D May, 1986
%P 82
%X The notes contain ten lectures from a graduate seminar.
The preliminary material includes cg iterations, fast elliptic
solvers and fem approximation. Then follow the capacitance matrix
technique and domain decomposition methods with preconditioners on
separators and on subregions.
##### Waterloo #####
---------------
Submitted by: Richard Bartels
Obtainable from:
Technical Reports Librarian
Computer Science Department
University of Waterloo
Waterloo, Ontario N2L 3G1
CANADA
---------------
%A Richard Bartels
%A Nezam Mahdavi-Amiri
%T Constrained Nonlinear Least Squares:
An Exact Penalty Approach with Structured Quasi-Newton Updates
%R Research Report CS-86-10
%I Department of Computer Science, University of Waterloo
%C Waterloo, Ontario, Canada N2L 3G1
%D March, 1986
%X This paper is concerned with the development, numerical
implementation, and testing of an algorithm for solving
finite-dimensional, generally-constrained, nonlinear,
least-squares (CNLLS) problems. The algorithm is an
adaptation to the CNLLS problem of an exact penalty method
for solving nonlinearly constrained optimization problems
due to Coleman and Conn. The adaptation draws heavily on
the methods of Dennis, Gay, and Welsch for handling the
unconstrained, nonlinear, least-squares problem and upon
the work of Murray and Overton for performing line searches.
This method has been tested on a selection of CNLLS problems
listed in the collection of Schittkowski and Hock.