NA Digest Sunday, June 4, 1989 Volume 89 : Issue 22

Today's Editor: Cleve Moler

Today's Topics:


From: Rodrigo Fontecilla <>
Date: Tue, 30 May 89 16:12:19 EDT
Subject: Code for Graph Algorithms Sought

I am looking for a robust source code for finding the
shortest path in a network. Also I need a Branch and Bound
algorithm. Either Fortran or C will be ok.
Any information related to these topics will be appreciated.
My e-mail address;

Rodrigo Fontecilla


From: E115N06%AWITUW01.BITNET@Forsythe.Stanford.EDU
Date: 01 JUN 89 16:33:38
Subject: Vienna Conference

Conference on Scientific Computation
Vienna, Austria, 14 - 16 June, 1990

On the occasion of the 60th birthday of Professor Hans J. Stetter, a
Conference on Scientific Computation will be held in the spring of 1990
at the Technical University of Vienna.

The following three areas will be emphasized: numerical methods for
differential equations (ODEs and PDEs), numerical software and validated
computation; contributions from other areas of scientific computation
are also welcome.

The scientific program will consist of contributed talks only
(approximate length: 25 minutes). The social program will include a
conference dinner and a half day excursion.
The conference fee will cover the participation in the social

There will be no proceedings of the conference but a special issue of the
journal 'Computing' will be published on the occasion of Professor
Stetter's 60th birthday. Those who wish to dedicate a paper to Professor
Stetter and have it included in this issue should send the manuscript
(conforming with the usual requirements of 'Computing') either to

Professor Rudolf Albrecht
Institut fuer Informatik, Universitaet Innsbruck
Innrain 52
A-6020 Innsbruck

or to

Professor Hansjoerg Wacker
Institut fuer Mathematik, Universitaet Linz
A-4045 Linz

before October 1st, 1989. The papers will be refereed. They need not be
connected with a contribution at the conference.

If you consider to participate in this conference you should complete the
slip below and mail it to

You will then receive more detailed information on the conference very early
in 1990.

We are looking forward to have you in Vienna for an interesting conference
and a cheerful celebration of Professor Stetter's birthday.

Sincerely yours

Christoph W. Ueberhuber, Richard Weiss

Institut fuer Angewandte und Numerische Mathematik
Technische Universitaet Wien
Wiedner Hauptstrasse 8-10/115
A-1040 Wien

Conference on Scientific Computation
Vienna, Austria 14-16 June, 1990

I will / may / will not participate.

I will / may / will not give a talk.
Topic: ODEs / PDEs / /
validated coputation / other


From: Gene Golub <>
Date: Thu, 1 Jun 1989 18:26:43 PDT
Subject: New Reports from Stanford

Here is a list of new reports from Stanford. We will be pleased to send them
as long as copies are available. Be sure to send me your postal mail address.


Report: NA-89-03

The Restricted Singular Value Decomposition:
Properties and Applications

Bart L.R. De Moor and Gene H. Golub

The restricted singular value decomposition (RSVD) is the
factorization of a given matrix, relative to two other given
matrices. It can be interpreted as the ordinary singular value
decomposition with different inner products in row and column
spaces. Its properties and structure are investigated in detail as
well as its connection to generalized eigenvalue problems, canonical
correlation analysis and other generalizations of the singular
value decomposition.

Applications that are discussed include the analysis of the
extended shorted operator, unitarily invariant norm minimization
with rank constraints, rank minimization in matrix balls, the
analysis and solution of linear matrix equations, rank minimization
of a partitioned matrix and the connection with generalized Schur
complements, constrained linear and total linear least squares
problems, with mixed exact and noisy data, including a generalized
Gauss-Markov estimation scheme.
Two constructive proofs of the RSVD in terms of other generalizations
of the ordinary singular value decomposition are provided as well.

Report: NA-89-04


Sylvan Elhay, Gene Golub, Jerry Kautsky

We derive and assess new methods for updating and downdating least
squares polynomial fits to discrete data using polynomials orthogonal
on all the data points being used. Rather than fixing on one basis
throughout, the methods adaptively update and downdate both the least
squares fit and the polynomial basis. This is achieved by performing
similarity transformations on the tridiagonal Jacobi matrices
representing the basis. Although downdating is potentially unstable,
experimental results show that the methods give satisfactory results
for low degree fits. We give details of new algorithms implementing
the methods, the most economical of which needs 14n + O(1) flops and
2n square roots to update a fit of order n.

Report: NA-89-05

Generalized Singular Value Decompositions:
A proposal for a standardized nomenclature.

Bart L.R. De Moor and Gene H. Golub

A mnemonic system of names for several matrix decompositions related
to the singular value decomposition is proposed:
the O SVD: Ordinary Singular Value Decomposition
P SVD: Product Singular Value Decomposition
Q SVD: Quotient Singular Value Decomposition
R SVD: Restricted Singular Value Decomposition
S SV: Structured Singular Value
T SVD: Takagi Singular Value Decomposition
The main purpose of this article is to propose a standardization of
the nomenclature and the structure of these matrix decompositions.

Report: NA-89-06

On the structure and geometry of
the product singular value decomposition

Bart De Moor

The product singular value decomposition is a factorization of
two matrices, which can be considered as a generalization of the
ordinary singular value decomposition, at the same level of
generality as the quotient (generalized) singular value

A constructive proof of the product singular value decomposition is
provided, which exploits the close relation with a symmetric
eigenvalue problem. Several interesting properties are established.
The structure and the non-uniqueness properties of the so called
contragredient transformation, which appears as one of the factors
in the product singular value decomposition, are investigated in detail.
Finally, a geometrical interpretation of the structure is provided
in terms of principal angles between subspaces.

Report: NA-89-07

Iterative Methods for Cyclically Reduced
Non-Self-Adjoint Linear Systems II

Howard Elman and Gene Golub

We perform an analytic and experimental study of line iterative
methods for solving linear systems arising from finite difference
discretizations of non-self-adjoint elliptic partial differential
equations on two-dimensional domains. The methods consist of
performing one step of cyclic reduction, followed by solution of the
resulting reduced system by line relaxation. We augment previous
analyses of one-line methods, and we derive a new convergence analysis
for two-line methods, showing that both classes of methods are highly
effective for solving the convection-diffusion equation. In addition,
we compare the experimental performance of several variants of these
methods, and we show that the methods can be implemented efficiently
on parallel architectures.


From: Jacques Calmet <mcvax!unido!iraun1!iraun2!iraul1!>
Date: 1 Jun 89 07:56:15 GMT
Subject: New Journal on Applicable Algebra

Journal Announcement

Applicable Algebra in Engineering, Communication and Computer Science

Arrangements have been finalized with Springer-Verlag to publish a new journal
entitled "Applicable Algebra in Engineering, Communication and Computer Science"
The first issue of this quarterly journal will appear in the beginning of 1990.

Authors are encouraged to submit papers. This is a good opportunity for good
papers to be quickly published!

This journal aims to cover all aspects of applicable algebra in the fields of
Communication, Engineering, Artificial Intelligence and Computer Science. This
includes, but is not limited to, domains such as:
(i) Engineering: Vision, robotics, system design, VLSI, signal processing,
fault tolerance and dependability of systems ....
(ii) Communication: Signal theory, coding, error control techniques,
cryptography, protocol specification ....
(iii) Computer science and Artificial intelligence: arithmetics, algorithm
engineering, complexity, algebraic algorithms, computer algebra, logic
and functional programming, programming languages, term rewriting systems
algebraic specification, theorem proving, graphics, modeling, knowledge
engineering, expert systems, artificial intelligence methodology ....

The scope of the journal is best illustrated by the two key-words in its title:
"Applicable Algebra". This implies that it does not cover domains which are not
linked to algebra such as applicable analysis or analytical methods to mention
two obvious ones.
Purely theoretical papers will not primarily be sought for even when they belong
to "algebraic" domains such as combinatorics, finite geometry, computer algebra
or cryptography for instance. But, papers dealing with problems in domains such
as commutative or non-commutative algebra, group theory, field theory, real or
algebraic geometry for instance, which are of interest for applications in the
previously mentioned fields are relevant for this journal.
On the opposite, technology and know-how transfer papers from engineering which
either stimulate or illustrate research in Applicable Algebra do fit the scope
of this journal.

The editorial board consists of:
Th. Beth(Univ. of Karlsruhe), W. Buettner (Siemens, Munich),
J. Calmet (Univ. of Karlsruhe - Managing Editor), P. Camion (INRIA, Paris),
J. Cannon (Univ. of Sydney), J. Heintz (Inst. of Math., Buenos Aires),
C.M. Hoffmann (Purdue Univ.), H. Imai( Yokohama National Univ.),
D. Jungnickel (Justus-Liebig Univ. Giessen), E. Kaltofen (Rensselaer Poly-
technic Inst., Troy), D. Kapur (SUNY at Albany), P. Lescanne (CRIN, Nancy),
H. Lueneburg (Univ. of Kaiserslautern), H.F. Mattson (Syracuse Univ.),
T. Mora (Univ. of Genoa), J. Mundy ( GE Co., Schenectady),
H. Niederreiter (Austrian Academy of Sciences, Vienna), A. Poli (Univ. Sabatier,
Toulouse), S.A. Vanstone ( Univ. of Waterloo).

Submissions are to be sent to:

Calmet Jacques
e-mail : (csnet) calmet@DKAUNI0I.BITNET (bitnet)
Universitaet Karslruhe - Institut fuer Algorithmen und Kognitive Systeme
Postfach 6980 - D-7500 Karlsruhe 1 - BRD - tel.: (49) 721 6084043


Date: Sun, 04 Jun 89 15:10:10 GMT
Subject: Dundee Conference Program

Program starts: 9.15am, Tuesday 27 June
ends: 5.50pm, Friday 30 June
We shall continue to accept registrations up to the time of the conference.
Enquiries to na.griffiths

Registration will take place in West Park Hall on Monday afternoon/evening
and in the University Tower Building thereafter.

There will be 16 invited talks.

There will be 96 submitted talks. These have been allotted 20 minutes and
will be presented in three parallel sessions each morning and four parallel
sessions during the afternoons.
Invited Talks:
Title to be announced.
T. Coleman, Cornell University, USA.

The hunting of the SNARK, or Why the trapezoidal rule is algebraically stable
K. Burrage, University of Aukland, New Zealand.

Parallel multilevel preconditioners.
J. Bramble, J. Pasciak and J. Xu, Cornell University, USA.

Submitted Talks:
Discretisation and Asymptotic Behaviour of Dissipative Dynamical Systems.
C. M. Elliott, University of Sussex, U.K.

An Interval Step Control for Continuation Methods.
R. B. Kearfott, University of Southwestern Louisiana, U.S.A.

Polynomial higher order predictors in numerical path following schemes.
K. Ulrich, University of Hannover.

Invited Talks:
Moving Finite Elements.
M. J. Baines, University of Reading, U.K.

Rapid Generation of Weights in Finite Difference Formulas.
B. Fornberg, Exxon Research and Engineering Co., USA.

Submitted Talks:
Constrained Moving Finite Elements Using Piecewise Cubics In 2-d.
P. Jimack, University of Bristol.

A Moving-Grid Interface for Systems of One-Dimensional Time-Dependent
Partial Differential Equations.
P. A. Zegeling, and J. G. Blom, CWI, The Netherlands.

Accurate Fourier pseudospectral solution of the RLW equation
D. M. Sloan, University of Strathclyde, UK.

On Optimally High Order in Time Approximations for the Korteweg - de Vries
O. Karakashian, and W. McKinney, University of Tennessee, U.S.A.

Finite Element Approximation of a Free Boundary Problem Arising in the
Theory of Liquid Drops and Plasma Physics.
J. W. Barrett, and C. M. Elliott, Imperial College and University of Sussex.

The Numerical Solution of Parabolic Free Boundary Problems Arising
>From Thin Film Flows.
R. Hunt, University of Strathclyde, U.K.

Using Divergent Iterations in High Speed, High Accuracy Computations.
P. Pedersen, Technical University of Denmark.

Parallel Evaluation of Some Recurrence Relations by Recursive Doubling
A. Kiper and D. J. Evans.
Middle East Technical University, Turkey and Loughborough University.

Estimation of convergence orders in repeated Richardson extrapolation.
E. Christiansen, Odense University, Denmark.

Some Preconditioners for Multi-Vector Processing of Nonsymmetric Systems.
S. Doi, INRIA, France.

Solution of Elliptic Systems of P.D.E.'s by Cell Discretization.
J. Greenstadt, University of Cambridge, U.K.

New families of convergence acceleration methods: The P-algorithms.
K. J. Overholt, University of Bergen, Norway.

Fast, Reliable Numerical Algorithms for Sturm-Liouville Computations.
M. Marletta, and J. D. Pryce, RMCS Shrivenham, U.K.

Reliable Computation of Weyl's $m( lambda )$ Function.
J. D. Pryce, M. Brown and V. Kirby, RMCS and U.C. Cardiff.

Solving Large ODE Problems Using the Iterative Matrix Solver WATSIT
W. L. Seward, University of Waterloo, Canada.

The Numerical Solution of Large Scale Systems of Differential Equations
G. D. Byrne, Exxon Research and Engineering Company, USA.

Invited Talks:
The Updating of Matrices of Conjugate Directions in Optimisation Algorithms.
M. J. D. Powell, University of Cambridge, U.K.

Towards Reliable Linear Programming.
R. Fletcher and J. A. J. Hall, University of Dundee.

Submitted Talks:
Conjugate Basis Matrices and Local Convergence for the Algorithm REQP
for Constrained Minimisation.
M. C. Bartholomew-Biggs, and T. T. Nguyen, Hatfield Polytechnic, U.K.

Preconditioned Conjugate Gradient Methods for Equality Constrained Least
Squares Problems.
N. K. Nichols, University of Reading, U.K.

The relationship between theorems of the alternative, least square problems,
and steepest descent directions.
A. Dax, Hydrological Service, Israel.

Parallel Hopscotch Solutions of the Ginzberg-Landau Equation.
D.B. Duncan, Heriot-Watt University, Edinburgh.

Hopscotch for Parabolic PDEs.
A. S. Wood, University of Bradford, U.K.

Unconditional Convergence of some Crank-Nicholson LOD Schemes.
W. Hundsdorfer, Centre for Mathematics and Computer Science, The Netherlands.

Error Estimation in Automatic Quadrature Routines.
J. Berntsen, and T. O. Espelid, University of Bergen, Norway.

Software for Adaptive Multidimensional Integration.
T. O. Espelid, University of Bergen, Norway.

Validated Anti-Derivatives.
G. F. Corliss, Marquette University, USA.

Invited Talks:
Finite Element Methods for Compressible Flow.
C. Johnson, Chalmers University of Technology, Sweden.

Title to be announced
A. Spence, University of Bath, U.K.

Submitted Talks:
Optimal Grids and Solutions for Compressible Flows in Nozzles.
J. Wixcey, University of Reading, U.K.

Stability of wide-angle absorbing boundary conditions for the wave equation.
R. A. Renaut, Arizona State University, USA.

Existence and Linear Stability of Period 2 Solutions of Discrete
Reaction-Diffusion Models with Various Types of Nonlinear Diffusion.
S. W. Schoombie, University of the Orange Free State, South Africa.

Spurious Dynamics in Numerical Simulations of Differential Equations.
A. Stuart, University of Bath, U.K.

Embedded Runge-Kutta Methods on Parallel Computers.
P. J. van der Houwen, CWI, Amsterdam.

Block Runge-Kutta Methods on Parallel Computers.
B. P. Sommeijer, CWI, Amsterdam.

Towards a Parallel, Commercial Oil Reservoir Simulator.
C. A. Addison, University of Liverpool, U.K.

Optimisation of Heavy Oil Recovery.
R. L. Brown, University of Reading, U.K.

Equilibria of Runge-Kutta Methods.
A. Iserles, and J. M. Sanz-Serna, University of Cambridge and University of
Valladolid, Spain.

Highly Continuous Runge-Kutta Interpolants.
D. J. Higham, University of Toronto, Canada.

Stability of Approximations from Radial Basis Function Spaces.
M. D. Buhmann and M. J. D. Powell,
University of Cambridge, U.K.

Faber polynomials on circular sectors.
G. Opfer, University of Hamburg, F. R. Germany.

Galerkin and Petrov-Galerkin Methods for the Semiconductor Problems.
T. Murdoch, University of Oxford, U.K.

Finite Element Approximation of a Model Reaction - Diffusion Problem with a
Non - Lipschitz Nonlinearity.
R. M. Shanahan, and J. W. Barrett, Imperial College, London.

The Global Error Estimate of Exponential Splitting.
Q. Sheng, University of Cambridge, U.K.

L inf Errors in Finite Volume Approximations.
R. Jones, University of Oxford, U.K.

Invited Talks:
Uniqueness Theorems for Stiff ODE Initial Value Problems.
P. Deuflhard, Konrad-Zuse-Zentrum fur Informationstechnik, Berlin, F.R. Germany.

Eulerian-Lagrangian Localized Adjoint Methods
for Advection-Dominated Problems.
T. F. Russell, University of Colorado at Denver, USA.

Submitted Talks:
An option for implicit Runge-Kutta methods.
J. C. Butcher, University of Auckland, New Zealand.

Starting Methods for the Iteration of IRK's.
J. Sand, University of Copenhagen, Denmark.

The Finite-element Method with Nodes Moving along the Characteristics
for Convection-Diffusion Equations.
Y. Tourigny, and E. Suli, University of Oxford, U.K.

Multi-Grid Techniques with Non-Standard Coarsening and Group Relaxation Methods.
A. Danaee, International Centre for Theoretical Physics, Trieste, Italy.

FFT solution of the Robbins problem
W. M. Pickering and P. J. Harley, University of Sheffield.

A Quadratically Convergent Parallel Jacobi-like Eigenvalue Algorithm.
M. H. C. Paardekooper, Tilburg University, The Netherlands.

A Parallel Algorithm for Banded Linear Systems.
S. J. Wright, Argonne National Laboratory, U.S.A.

High order explicit Runge-Kutta pairs.
P. W. Sharp, and E. Smart, University of Toronto, Canada.

Trajectory Optimisation Applications using the Program STOMP for
Generating Cost Function and Gradient Evaluations.
K. Horn, Messerschmitt-Boelkow-Blohm, Germany.

Invited Talks:
Knot Removal and Condition Numbers for B-Splines.
T. Lyche, University of Oslo, Norway.

Computing the structured singular value, and some related problems
G. A. Watson, University of Dundee, Scotland.

Submitted Talks:
Optimal Distribution of Knots in Tensor-Product Splines Approximation.
N. Dyn and I. Yad-Shalom, Tel-Aviv University, Israel.

The Difference Interpolation Method for Splines.
W. Volk, Berlin, F.R. Germany.

On a Certain Approximation problem for Matrices.
W. Light, University of Lancaster, U.K.

The Solution of Semi-infinite Programming Problems by Discretization Methods.
R. Reemtsen, Technical University of Berlin, F.R. Germany.

Some Observations on the Streamline Upwind Petrov Galerkin Method for
Convection-Diffusion Problems.
S. Sigurdsson, University of Iceland.

Spectral Transport-diffusion Algorithm for Convection-diffusion Problems.
E. Suli and A. Ware, University of Oxford, U.K.

On Positive Shock Capturing Schemes.
B. Einfeldt, Cranfield Institute of Technology, U.K.

Comparison of Roe's Scheme and a Directional Difference Scheme for Gas
Network Flows.
S. Emmerson, University of Reading, U.K.

Optimal Lattice rules in Dimension 2 and 3.
T. Sorevik and J. N. Lyness, University of Bergen and Argonne National

Sub-lattices of Integration Lattices.
P Keast, J. N. Lyness and T. Sorevik,
Dalhousie University, Argonne National Laboratory and University of Bergen.

Multistep Methods for Ordinary Differential Equations based on Algebraic and
First Order Trigonometric Polynomials.
G. Vanden Berghe, Rijksuniversiteit Gent, Belgium.

Multistep Methods based on Continued Fractions for solving Initial Value
D. Eyre, and S. Abelman, Potchefstroom University and University of the

Order results for R-K methods applied to Differential Algebraic Equations.
M. Roche, Universite de Geneve, Switzerland.

A Regularization-Technique for the Numerical Solution
of Index-2 - Differential - Algebraic Equations
M. Knorrenschild, Lawrence Livermore National Laboratory, USA.

A note on the construction of continuous quadric patches.
M. L. Baart, Potchefstroom University, South Africa.

A shape preserving curve interpolation scheme using parametric
rational cubic splines.
K. Unsworth, and T.N.T. Goodman

Invited Talks:
How Accurate is Gaussian Elimination?
N. J. Higham, Cornell University and University of Manchester.

Some numerical aspects of Divide and Conquer Methods for Eigenvalue
D.C. Sorensen, Argonne National Laboratory, USA.

Submitted Talks:
Stable solvers for singular linear systems and application to block
linear systems.
W. Govaerts, University of Gent, Belgium.

The Use of the Basic Linear Algebra Subprograms (BLAS) in improving
supercomputer speeds.
Jerzy Wasniewski, The Danish Computer Centre for Research and Education.

Computing Accurate Eigensystems of Scaled Diagonally Dominant Matrices.
J. Barlow and J. Demmel, Pennsylvania State University and Courant Institute.

Conjugate Gradient Algorithms for Stabilised Mixed Finite Element Methods.
D. J. Silvester and N. Kechkar, UMIST, U.K.

Finite Element Computation on Multiprocessor computer
R. Wait and C. J. Willis, University of Liverpool, U.K.

Galerkin Methods for Nonlinear Elliptic PDES.
C. Budd, and T. Murdoch, Oxford University Computing Laboratory, U.K.

Generalised Pade approximations to the exponential function.
F. H. Chipman and J. C. Butcher, Acadia University, Canada and University of
Auckland, New Zealand.

Numerical solution of retarded ode-systems.
P. G. Thomsen, Technical University of Denmark.

The Construction of Cubature Formulae using Software from Bifurcation Theory.
R. Cools, Catholic University, Belgium.

Invited Talks:
Boundary Integral Methods for Laplace's Equation.
I. Graham, University of Bath, U.K.

Submitted Talks:
Ill - posedness and singular integrals in the boundary integral method.
J. Steinberg, Technion - Israel Institute of Technology.

Solution of exterior Helmholtz problems by improved boundary element
S. M. Kirkup, Brighton Polytechnic, U.K.

Chebyshev Polynomial Solutions of First Kind Integral Equations for
Numerical Conformal Mapping.
J. Levesley, D. M. Hough and S. N. Chandler-Wilde, Coventry Polytechnic, U.K.

A Cahn-Hilliard Type Model for Phase Separation.
J. F. Blowey, University of Sussex, U.K.

Numerical Simulation of the Cahn-Hilliard Equation.
M. I. M. Copetti, and C. M. Elliott. University of Sussex, U.K.

The Effect of Filtering on the Pseudospectral Solution of Evolutionary
Partial Differential Equations.
L. S. Mulholland, University of Strathclyde, U.K.

A Tool for Analysing Ill-conditioned Equations.
W. M. Connolley, and J. S. Rollett, Oxford University Computing Laboratory, U.K.

Thin Plate Spline Approximants,
P. Gonzalez-Casanova, University of Oxford, U.K.

Some New Ideas on Conjugate Gradient Methods.
Y. F. Hu and C. Storey, Loughborough University of Technology, U.K.

Least Squares Data Smoothing by Non-Negative Second Divided Differences.
I. C. Demetriou, Greece.

A deficient spline function approximation to third order O.D.E.
T. Fawzy, Suez-Canal University, Egypt.

On Approximate Solutions of Integral Equations of the Mixed Type
Lechoslaw Hacia, Poznan University, Poland.

Differential and integro-differential equations as population growth models
with applications in Agriculture.
A. Makroglou, Agricultural University of Athens, Greece.

New Stopping Criterions for Some Iterative Methods for a Class of
Unsymmetric Linear Systems.
C. Li and D. J. Evans, Loughborough University of Technology, U.K.

The Whittaker-Henderson graduation method
A. J. Macleod, Paisley College, Glasgow.

A Criterion Test for Self-scaling Variable Metric Algorithms.
M. Al-Baali, University of Damascus, Syria.

Implementation of a Multigrid Method on a Transputer Network.
G. J. Shaw and A. Stewart, University of Oxford and Queen's University, Belfast.

Title to be announced.
K. Zietak, Poland.