NA Digest Sunday, December 19, 1993 Volume 93 : Issue 47

Today's Editor:

Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: James F. Epperson <>
Date: Tue, 14 Dec 93 15:27:00 CST
Subject: Penalty Methods Question

For a new problem I am studying, I need to do a penalized least
squares type of computation (excuse the pidgin notation; I don't
speak TeX):

min{ |b-Au|^2 + a|Ku|^2 }

where A and K are square matrices, b is a known vector, u is the unknown
vector, and a is the penalty coefficient. The |.| notation denotes
the standard 2-norm.

I can do the usual manipulations to get the normal equations for this
problem, and hence get a solution, but I am not sufficiently familiar
with this area to know if there is a different or better way. In
particular, I would like to know if there are algorithms based on a
QR or SVD factorization of the matrices A and K.

Thanks in advance for any replies.

Jim Epperson


From: Bruno Besace <>
Date: Thu, 16 Dec 1993 01:58:04 +0000
Subject: Searching for C code for MemSys Algorithm

I'm looking for C code about MemSys algorithm (Maximum Entropy algorithm).

Any and all advice welcome.

Thanks in advance for your responses.
You may reply to me personally.

Bruno Besace. (


From: Nick Higham <>
Date: Fri, 17 Dec 93 10:16:49 GMT
Subject: Test Matrix Toolbox for Matlab 4

I am pleased to announce the release of version 2.0 of
The Test Matrix Toolbox for Matlab. This is a major new
release of the toolbox first released in July 1989 and published as

Algorithm 694: A collection of test matrices in MATLAB.
ACM Trans. Math. Soft., 17(3):289-305, September 1991.

The toolbox is distributed as a Unix shar file, available by
anonymous ftp from The MathWorks at Internet address (
in directory pub/contrib/linalg as files - the M-files (shar file: `sh' to unshar.
A directory testmatrix will be created
containing the M-files in the toolbox.
Try the demonstration file tmtdemo.m.) - the 76-page documentation (PostScript file)

Note: The MathWorks ftp server has a special feature which enables you to
type, for example, `get'; the server will then compress the
file before sending it (make sure you set binary mode first).

The Test Matrix Toolbox for Matlab 4 contains a collection of test
matrices, routines for visualizing matrices, and miscellaneous
routines that provide useful additions to Matlab's existing set of
There are 58 parametrized test matrices, which are mostly
square, dense, nonrandom, and of arbitrary dimension.
The test matrices include ones with known inverses or known
eigenvalues; ill-conditioned or rank deficient matrices; and
symmetric, positive definite, orthogonal, defective, involutary, and
totally positive matrices.
The visualization routines display surface plots of a matrix and its
(pseudo-) inverse, the field of values, Gershgorin disks, and two- and
three-dimensional views of pseudospectra.

Nick Higham
Department of Mathematics
University of Manchester


From: Stefano Foresti <>
Date: Tue, 14 Dec 1993 18:16:24 -0700
Subject: BibTex Database on Netlib

I was thinking that it would be very nice to have a Nanet or Netlib
bibliography database in BibTex, similar to what Craig Douglas has
coordinated on MGNet. Such a service would allow to:

- Find all references of a Nanet subscriber, as it is currently possible
to find out information with the "WHO" command on Xnetlib.
- Find references with a certain keyword.
- Retrieve reference entries, that are complete and updated.

There are two possible kinds of bibliography databases I can think of:

1) Each Nanetter submits a file containing the publications in Bibtex format
of which he/she is (co-)author (i.e. his/her list of publication).
This option would just require that each Nanetter be responsible for
formatting his list and submit an update once new papers are published.

2) Each Nanetter submits a Bibtex database, and these references are added
in the database by a coordinator. This requires that the entries be
sorted, checked for multiplicity and so on. However, I have the impression
that this kind of a database would require a lot of coordinating work.

One of the issues to consider is the definition of a standard entry format.
For instance, Craig Douglas has defined a standard format of the Bibtex entry
label (to enforce unicity) as follows:
> <InitialsLastname_morenames_YearLetter>
> For example, my dissertation's key from 1982 is
> CCDouglas_1982a
> The key for a book by Braess, Hackbusch, and Trottenberg from 1984 is
> DBraess_WHackbusch_UTrottenberg_1984a

Stefano Foresti
Utah Supercomputing Institute
85 SSB
University of Utah
Salt Lake City, Utah 84112, USA
Ph: (801)581-3173 Fax: (801)585-5366


From: John Pryce <>
Date: Mon, 13 Dec 93 17:46 +0100 (BST)
Subject: Numerical Solution of Sturm-Liouville Problems

This news item is to announce the forthcoming publication of my book

"Numerical Solution of Sturm-Liouville Problems"
by John D Pryce, FIMA
Lecturer, Software Engineering Group,
Royal Military College of Science, Shrivenham, Swindon SN6 8LA, UK

In the series "Monographs on Numerical Analysis", Oxford University Press,
Dec 1993, 330 pages, line illustrations, Hardback 37.50 pounds sterling

Sturm-Liouville Problems (SLPs) belong to an elegant area of mathematics,
the spectral theory of differential operators, which motivated much of the
development of analysis and linear algebra by Hilbert, Weyl, Titchmarsh et
al. in the early 20th century. Since the early 19th century SLPs have been
ubiquitous in applied mathematics, arising naturally from modelling in such
fields as acoustics, waveguide theory, hydrodynamic stability, MHD, and
neutron transport. They are also of vital interest to physicists since
Schrodinger's equation in one dimension is of Sturm-Liouville form. The
variety of interesting SL-related computations reflects this triple

The range of numerical methods is correspondingly vast: since the 1920s,
quantum physicists found Schrodinger eigenvalues by methods often angled to
a particular problem, based on asymptotics and thus of limited accuracy;
since the 1950s numerical analysis journals contain SLP algorithms, often
accurate and efficient on a class of (usually regular) problem but hard to
automate. General ODE boundary-value software solves SLPs, but
inefficiently. Typically none of these approaches handle singular endpoints
in a way that corresponds to the mathematical theory. It is worth
developing methods to exploit SLPs' special features and to cope
systematically with the variety of behaviour singular SLPs display.

The book will help the scientist/engineer who wants simple methods for
simple SLPs but needs to know their limitations and be pointed to the best
current library software for harder problems. It is also for the numerical
software specialist who wants a reference on good SLP algorithms, their
theory, their implementation in the library codes and the resulting
performance. The basic mathematical theory as it relates to algorithms is
covered in some detail. A chapter on Further Topics sketches problems or
methods lying just beyond the book's main theme. There are numerous
problems. An appendix presents a standard list of Test Problems, and a
Benchmark for software validation.

Introductory background; Elementary theory of the classical SLP;
Simple matrix methods; Variational methods; Shooting and the scaled Prufer
method; Pruess methods; Singular SLPs (theory); Singular SLPs (numerical
treatment); Computing and manipulating eigenfunctions; Computation of
resonances; Further topics; Conclusion. A: Eigenvalues 0-50 of two problems
of Paine; B: Test problems and benchmark; C: Available SL software.


From: Jinchao Xu <>
Date: Sun, 12 Dec 1993 23:04:32 -0500
Subject: Conference on Domain Decomposition

The Eighth International Conference on Domain Decomposition Methods
will be held in Beijing, China during May 15-19, 1995. For further
information, please contact:

Prof. Zhong-Ci SHI
Computing Center
Academia Sinica
PO Box 2719
Beijing 100080, CHINA


From: Yuefan Deng <>
Date: Tue, 14 Dec 93 10:14:34 EST
Subject: Stochastic Modeling Workshop at Stony Brook

A Joint Cornell/MSI -- Stony Brook Workshop
January 19 -- 20, 1994

This workshop will emphasize applications of stochastic modeling.
Stochasticity represents the unknown, uncertain, not understood,
or excessively detailed fine scale aspects of a system.
Most real systems of interest to technology have
stochastic features. In many cases stochasticity is a central feature,
essential for even the simplest accurate description of the system.
Usually there are deterministic, non-random features as well,
and there are also deterministic laws to govern the dynamic evolution
of randomness. The resulting interaction between
randomness and determinism leads to stochastic modeling, stochastic
partial differential equations and stochastic signal processing.
The purpose of this workshop is to bring together a representative
sampling of the many (and highly diverse) applications, or instances
in which stochastic modeling has an important role to play.
An intended outcome is to identify points of interaction between
theory and applications for stochastic modeling.

Topics and Speakers (more to invite and to expect):

1. Stochastic Fluids: Turbulent Mixing ---- J. Glimm
2. Stochastic Fluids: Anomalous Dispersion and Geostatistics ---- Q. Zhang
3. Interacting Particle System ---- C. Mueller
4. Percolation or Dynamic Ising Models ---- H. Kesten
5. Monte Carlo Simulation ---- M. Mascagni
6. Speech Recognition and Signal Processing ---- D. Sun
7. Stochastic Models in Manufacturing ---- M. Sobel
8. Stochastic Systems Models ---- TBD
9. Application of Stochastic Modeling to Finance ----D. Weiss (To be confirmed)
10. Stochastic methods in image processing ---- TBD

For information, call
Ms. Terry Mills
Department of Applied Mathematics and Statistics
Center for Scientific Computing
State University of New York at Stony Brook
Stony Brook, NY 11794


From: H.J.J. te Riele <>
Date: Thu, 16 Dec 1993 18:39:34 +0100
Subject: Massively Parallel Computing and Applications



In 1993 - 1994, CWI (Centre for Mathematics and Computer Science Amsterdam)
and RUU (University of Utrecht) are organising a series of Symposia on
Massively Parallel Computing and Applications.

As far as the computing part is concerned, we are interested in
contributions on the optimization and analysis of generic numerical
algorithms on massively parallel computers. In particular, we think of
iterative methods for solving large sparse linear systems of equations
and for finding eigenvalues and eigenvectors of large sparse linear systems,
multigrid methods for various types of PDEs, parallel methods for the solution
of ordinary differential equation, software tools for parallelization, etc.

On the applications side, we seek contributions in fields where optimization
and analysis of numeric and nonnumeric algorithms for massively parallel
computers are instrumental for real progress. In particular, we think of
environmental problems, number theory and cryptography, multiple-particle
systems, chemical reactions, computational fluid dynamics, seismic problems etc.

The following advisory board will assist in the selection of the
Symposium programs:

P. Aerts, Dutch National Computing Facilities Foundation NCF
O. Axelsson, Catholic University Nijmegen
L.O. Hertzberger, University of Amsterdam
P.A.J. Hilbers, Royal Shell Laboratory Amsterdam
P.J. van der Houwen, CWI and University of Amsterdam
W. Loeve, National Aerospace Laboratory NLR
N. Petkov, University of Groningen
M. Rem, Technical University Eindhoven
J.G. Verwer, CWI
H. Wijshoff, University of Leiden
P. De Wilde, Technical University Delft

We intend to organise bi-monthly one-day meetings each of which will
be centred around a class of numerical algorithms or around a coherent
applications field.
The first three meetings took place in 1993 and were devoted to:

"Topics in environmental mathematics" (June 4, 1993),
"Parallel numerical algorithms" (Sept. 24, 1993),
"Computational number theory and cryptography" (Nov. 26, 1993).

The next three meetings are scheduled in the first half of 1994, namely,

Febr. 4, 1994,
March 25, 1994,
June 3, 1994.

Refereed proceedings will be published.

Abstracts of possible contributions are solicited now. Please send an
abstract to Herman J.J. te Riele, CWI, Kruislaan 413, 1098 SJ Amsterdam,
The Netherlands (email: and indicate your preference,
if any, for one of the above three dates.
The deadline for submission of abstracts is Jan. 14, 1994.
Notification of acceptance of the abstracts for the first meeting
will be sent by Jan. 21, 1994. and for the two subsequent meetings
by Febr. 25, 1994.
A limited budget is available for contributors from abroad to partially
cover travel and lodging expenses.

The organisers:
H.J.J. te Riele (CWI)
H.A. v.d. Vorst (RUU and CWI)


From: Dirk Roose <>
Date: Fri, 17 Dec 1993 15:02:23 +0100 (MET)
Subject: Course on Iterative Methods in Leuven

Course on
Recent Advances in Iterative Methods
for Solving Algebraic Systems and Eigenvalue Problems
Leuven, Belgium

The lectures will be given in February - March 1994, in three sessions of two
days each, starting on Thursday at 10 a.m. and ending on Friday at 4 p.m.
All lectures will take place in the Auditorium of the Arenberg Castle,
Kardinaal Mercierlaan, B-3001 Leuven-Heverlee.

Participants from Belgian academic institutions are requested to pay a regis-
tration fee of 4000 BF. For other participants the registration fee is 15000 BF.

Registration forms can be obtained via anonymous ftp from
in directory pub/NumAnal-ApplMath/Announce , files course.ascii or course.tex .

The organisers,

Dirk Roose, K.U.Leuven Roland Keunings, U.C.L., Louvain-la-Neuve


Thursday and Friday 24 - 25 February 1994

H. Van der Vorst (Universiteit Utrecht, the Netherlands) (3h)
Survey on iterative methods for solving linear systems and their implementa-
tion on modern computer architectures
R.W. Freund (AT&T Bell Laboratories, Murray Hill, USA) (3h)
I. The Lanczos Process for Large-Scale Nonsymmetric Matrix Computations
II. Quasi-Minimal Residual Iterations for Non-Hermitian Linear Systems and
K. Vuik (T.U.Delft, the Netherlands) (1.5h)
Krylov subspace methods applied to the incompressible Navier-Stokes eqs.
G. Degrez (Von Karman Institute for Fluid Dynamics, Belgium) (1h)
Acceleration of multiblock solvers for the compressible Euler and
Navier-Stokes equations by Krylov subspace methods

Thursday and Friday 10 - 11 March 1994

O. Axelsson and M. Neytcheva (Universiteit Nijmegen, the Netherlands) (3h)
I. Block diagonal and Schur complement preconditioners
II. The algebraic multilevel iteration method
III. Approximate inverses and their use in preconditioning methods
R. Beauwens (Universite Libre de Bruxelles, Belgium) (1h)
Conditioning analysis
F.X. Roux (Onera, Chatillon, France) (3h)
A survey of domain decomposition methods
R. Keunings (U.C.L., Louvain-la-Neuve, Belgium) (1h)
Domain decomposition methods for nonlinear finite element analysis

Thursday and Friday 24 - 25 March 1994

Y. Saad (University of Minnesota, USA) (3h)
The use of Krylov subspace methods in scientific computing
I. Linear systems; II. Eigenvalue problems;
III. Nonlinear equations and other applications
Ch. Farhat (University of Colorado at Boulder, USA) (3h)
Domain decomposition methods for time-dependent problems:
I. Construction of coarse grid problems for unstructured meshes;
II. Scalable solution of coarse grid problems and efficient solution of
repeated systems;
III. Application to fluid/structure coupled problems
M. Geradin (Universite de Liege, Belgium) (1h)
Application of domain decomposition methods to flexible multibody dynamics
F. Dupret (U.C.L., Louvain-la-Neuve, Belgium) (1h)
Numerical stability analysis of stratified coating flow by Lanczos method
K. Meerbergen (K.U.Leuven, Belgium) (1h)
Preconditioners for computing eigenvalues with largest real part


From: Piyush Mehrotra <>
Date: Tue, 14 Dec 1993 13:11:56 -0500
Subject: Research Positions at ICASE

Research Positions at ICASE

The Institute for Computer Applications in Science and
Engineering (ICASE) is seeking fresh PhDs for staff scientist
positions in the following areas:

a) systems software for parallel computers,
b) performance and reliability analysis, and
c) parallel numerical algorithms.

The principal focus of the software research effort at ICASE is
development of tools and environments for porting large scale
scientific applications to parallel and distributed systems. The focus
of the performance and reliability analysis research is development of
algorithms and tools for the study and optimization of performance of
complex computer systems, especially parallel and distributed systems.
The focus in parallel numerical algorithms is the development and
experimental investigation of scalable methods for computational fluid
dynamics applications.

In the software area we are looking for PhDs interested in
collaborative research on runtime support systems, on compiler design
and enhancements, on tools for distribution, mapping, and load
balancing, and on tools for performance monitoring and prediction. In
the performance and reliability analysis area we seek PhDs interested
in tools and algorithms for high performance simulation, and for
parallel mathematical performance and relability analysis. Current
topics of interest in the algorithms area are multilevel iterative
methods, domain decomposition iterative methods, problem decomposition
and parallel mapping in the presence of adaptivity, and
multidisciplinary optimization.

Staff scientists appointments are usually made for two years,
with the possibility of a third-year extension. ICASE is a non-profit
research organization located at the NASA Langley Research Center in
Hampton, Virginia. The institute offers excellent opportunities to
computer science researchers for collaboration on complex and
computationally intensive problems of interest to NASA. ICASE staff
scientists have access to Langley's 66 processor Intel PARAGON, a Cray
Y/MP, and internet access to many other parallel architectures.

US citizens/permanent residents will be given *strong* preference.

Please send resumes to:

NASA Langley Research Center
Hampton VA 23681

or by e-mail to


From: Lois Mansfield <>
Date: Wed, 15 Dec 93 15:21:12 EST
Subject: Chair Position at University of Virginia


The University of Virginia invites applications and nominations for
the position of Chair, Department of Applied Mathematics. The
Department, which is in the School of Engineering and Applied Science,
has a full-time faculty of eleven, and has numerous active research
programs grouped in three major areas: continuum mechanics, control theory,
and numerical analysis/scientific computing. The Department offers B.S., M.S., and Ph.D. degrees in Applied Mathematics and is responsible for all
undergraduate and graduate education in Applied Mathematics within the
School of Engineering and Applied Science.

Candidates for the position must have a Ph.D. degree and an outstanding
record of research and scholarship in Applied Mathematics. Also, they
must have a firm knowledge of the best programs in Applied Mathematics
nationally and internationally. A clear commitment to academic
leadership, teaching, and administration within an environment dedicated to
engineering and applied science is expected. Women and ethnic minority
candidates are encouraged to apply. Priority will be given to applications
received by March 1, 1994.

Applications should be sent to:

Professor Paul Allaire
Chair, Search Committee
c/o Department of Applied Mathematics
Thornton Hall
University of Virginia
Charlottesville, VA 22903-2422

The University of Virginia is an equal opportunity/affirmative action employer.


From: Elbridge Gerry Puckett <>
Date: Thu, 16 Dec 93 14:33:24 PST
Subject: PostDoctoral Position at U. C. Davis


Applications are invited for a Visiting Research Assistant Professorship
in computational mathematics / numerical analysis at the University of
California, Davis effective July 1, 1994. The appointment is for one year and
is renewable up to two times for a total of three years. The salary will be
commensurate with the successful applicant's qualifications. Applicants must
have received a PhD by the date of the appointment and no earlier than three
years prior to the appointment, and have an outstanding record
or show great promise in teaching and research. Duties include undergraduate
and graduate teaching and research. The teaching load is five quarter courses
per year and may include an advanced course in the candidate's field.
Applications will only be considered from individuals who have a strong
background in numerical analysis and computational mathematics.

The U. C. Davis Department of Mathematics includes faculty in both pure and
applied mathematics engaged in numerous areas of mathematical and
interdisciplinary research. The department offers a full range of academic
programs leading to the BA, BS, MA and PhD degrees in Mathematics. In addition
the department is home to the Graduate Group in Applied Mathematics which
consists of faculty from the Department of Mathematics and other disciplines
and which offers the MS and PhD degrees in Applied Mathematics.
U. C. Davis is the third largest of the nine University of California campuses.
It is conveniently located within 1-2 hours drive of the San Francisco
Bay Area, the Northern California coast and the Sierra Nevada mountains.

We will begin considering applications on February 15, 1994 and expect to make
an offer no later than March 1, 1994. Applicants should send a curriculum
vitae, a list of publications, and at least three letters of reference to:

VRAP Search Committee Chair
Department of Mathematics
University of California
Davis, California 95616-8633

It is essential that these documents contain evidence of the applicant's
abilities and experience in teaching as well as research.
The University of California is an equal opportunity / affirmative action
employer with a strong institutional commitment to the achievement of
diversity among its faculty and staff. In that spirit, we are particularly
interested in receiving applications from persons of underrepresented groups
including women, ethnic minorities, disabled veterans and handicapped persons.



From: John Belward <>
Date: Tue, 14 Dec 93 10:05:58 EST
Subject: Positions at The University of Queensland


Centre for Industrial and Applied Mathematics and Parallel Computing (CIAMP)
High Performance Computing Unit (HPCU)


Professor Kevin Burrage and A/Professor John Belward have been awarded a
3 year ARC Collaborative Research Grant to work on the development of an
integrated software environment on a supercomputer platform for land
management systems in conjunction with the Queensland Department of
Primary Industries.

Post Doctoral applicants should have a strong background in scientific
computing and have experience with vector and/or MIMD parallel programming.
A working knowledge of GIS software and Database systems would also be useful.

The appointment will be for a period of 3 years.
Salary: \$36,285 per annum
Closing date: 15 February 1994

CIAMP and the HPCU have entered into a substantial collaborative
agreement with the Queensland Department of Primary Industries (QDPI) to
develop and implement parallel computational algorithms with spatial
modelling and environmental applications.

Ph. D. Scholarships are available from CIAMP as top ups for 1994--1996 for
two students with new APAs. These scholarships will each be in excess of
\$5,000 for each of the three years. Applicants should have a strong
background in Mathematics and Computer Science.

These appointments will provide opportunity for close collaboration with
a prestigious Government establishment (QDPI) on problems of national
importance; access to state of the art hardware including an advanced
computational lab of SUN workstations, a Silicon Graphics INDIGO, a DEC alpha
workstation and colour printer; network access to a Cray YMP-2D and 4096
processor MasPar MP1 sited at the University of Queensland; a stimulating
research environment of approximately 12 Ph.D students and two research
fellows working on various aspects of scientific computing.

Further details may be obtained from:

Professor K. Burrage: phone (07) 365 3487, email address
Dr J. Belward: phone (07) 365 3257, email address

Please forward applications and resume to the Head, Department of
Mathematics, The University of Queensland, Qld 4072, fax (07)8702272.


From: Memphis State <>
Date: 17 Dec 93 15:48:11 CDT
Subject: Position at Memphis State

To whom may be concerned.

The department of Mathematical sciences of Memphis State University
wants to fill a tenure track position at the assistant professor level
in Probability theory. This is meant as a Mathematics position.
Interested applicants should apply not later than February 1, 1994.
Minorities are encouraged to apply.


From: Michel Cosnard <>
Date: Mon, 13 Dec 93 09:55:46 -0500
Subject: Contents: Parallel Processing Letters



Information can be obtained form the Editor in Chief, Professor Michel Cosnard
The content of the previous issues is available via anonymous ftp on in directory pub/LIP/users/btouranc/PPLcontents.

CONTENTS - Volume 2 - Number 4 - December 1992

Editorial Note
M. Cosnard 299

Constructing An Exact Parity Base is in $RNC^{2}$
G. Galbiati, F. Maffioli 301

Parallel Constructions of Heaps and Min-Max Heaps
S. Carlsson, J. Chen 311

Computation List Evaluation and Its Applications
EA. Albacea 321

Data Parallel Computation of Euclidean Distance Transforms
T. Bossomaier, N. Isidoro, A. Loeff 331

Two Selection Algorithms on A Mesh-Connected Computer
BS. Chlebus 341

Channel Classes: A New Concept for Deadlock Avoidance in
Wormhole Networks
J. Duato 347

Broadcasting Time in Sparse Networks with Faulty Transmissions
A. Pelc 355

A Low Overhead Schedule for A 3D-Grid Graph
E. Bampis, JC Konig, D. Trystram 363

Multi-Rate Arrays and Affine Recurrence Equations
PM. Lenders 373

Simulation of Genetic Algorithms on MIMD Multicomputers
I. De Falco, R. Del Balio, E. Tarantino, R. Vaccaro 381

Parallel Buddy Memory Management
T. Johnson, TA. Davis 391

Author Index - Volume 2 (1992) 399


End of NA Digest