NA Digest Sunday, July 26, 1992 Volume 92 : Issue 29

Today's Editor:

Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: Jan Korvink <>
Date: Mon, 20 Jul 92 09:08:49 +0200
Subject: Again: C Programs for Linear Algebra

Could someone answer Dr. Jaroslav Kautsky's question
for all of the C community:

"Are C-versions of LINPACK or LAPACK available in public domain?"

Thank you,

Informatics in Engineering Applications,
CH-8093 Zurich


From: Trott Michael <trott@Bibliothek.TH-Ilmenau.DE>
Date: Mon, 20 Jul 92 18:44:29 MESZ
Subject: Sparse Inverse Subspace Iteration Solver

Dear reader,
I am a theoretical solid state physicist and I am beginning to do
electronic structure calculations of semiconductor micro- and
This means to solve the Kohn-Sham equations, a Helmholtz like
eigenvalue problem and a Poissoneqation in a self consistent manner.
In the moment I do this with FEM in two dimensions.
and my interest is in a FORTRAN inverse subspace iteration solver
for the eigenvalue problem for sparse matrices. I favour inverse sub-
space iteration techniques because I need a good accuracy and because
I have same information on the eigenvalues and vectors and I will use it.
Can somebody supply such a solver?

Michael Trott

From: Eric Grosse <>
Date: Sun, 19 Jul 92 22:51 EDT
Subject: Netlib News: Searching for Files

In the last column (see SIAM News, November 1991), we saw that netlib had
adapted to the growing size of program files by 1) providing access via ftp
and xnetlib, 2) better mail splitting, and 3) user-specified mail limits.
(Ftp is the Internet file transfer protocol and xnetlib is an X-windows
program from Jack Dongarra's group using sockets for file transfer.)

This time, we look at how netlib is adapting to the growing number of files.

Recall that the organization of netlib is one of libraries and sublibraries,
each described briefly in an ``index'' file. In the early days of netlib, you
could download the dozen or so index files in areas of potential interest and
keep the information at hand or in your head.

By 1987 this was becoming more burdensome, so Greg Astfalk kindly prepared a
keyword list. An email or xnetlib command like ``find bessel'' could quickly
search for all related files in the collection.

Keeping they keyword list up to date, however, quickly proved to be beyond our
modest administrative resources. As time went by, the keyword list became
less useful as it fell out of sync with the explosive growth in material.

Since the index files are reliably updated, we've decided to keep the keyword
information there. Moreover, to allow automatic searching, we've switched
from the somewhat haphazard writing style formerly used to a more systematic

Each file that you might want to request is now supposed to have a paragraph
in the appropriate index file. Here's an example.

file a/dloess
for smoothing multivariate scattered data
by Cleveland and Grosse
ref Statistics and Computation 1:1
prec double
lang Fortran77
gams L8h
# The method is based on a moving
# least squares fit by a quadratic,
# accelerated by k-d trees and blending
# functions. (To get the univariate
# code, "send lowess from go".)

The first line tells you how to get the file; say
send a/dloess
or equivalently,
send dloess from a.
The next line provides a few keywords, and succeeding lines give more details
about the program such as authors, literature reference, precision, language,
and GAMS classification code. For a description of the complete scheme, ask
netlib to
send thesaurus gams from bib.

So, as of June 1992, keyword searching again provides a comprehensive view of
the collection. We are well aware that some searches don't lend themselves to
a keyword approach, and we're exploring hierarchical classification (as in
Boisvert et al. GAMS and in my approximation catalog). Other approaches are
also being tried under the aegis of the HPCC (High Performance Computing and
Communications) Software Sharing Initiative. We intend that the new index
files will provide a sound database for these new user interface efforts.

Turning now to another topic, it dismays me to report that some e-mail systems
in the world still have trouble generating correct return addresses. The rule
is that the program shipping mail to the outside world should be sure that
there is a From: line in the header with a valid Internet address, not
merely an abbreviation sufficient for the local campus. Sometimes, by
carefully puzzling over other information in the header, a human can guess how
to fix the address on failed mail. But netlib doesn't try to work miracles.
If all else fails, you can resort to including in the main message text
(before requests) the command
(after substituting your own address).

By the way, I have received several email messages of the sort ``why doesn't
this silly netlib program ever respond to my mail?'', signed something like
mystery-vax!joe. Unfortunately, if netlib can't get through to him, neither
can I!

Recent additions

Quite a lot of material has been added since the last column. The big
announcement, of course, is lapack, a successor to linpack and eispack. That
has been covered elsewhere in the SIAM News and need not be dwelt on here.
Similarly, there is a great deal of interesting material in the matlab
libraries in netlib, but presumably matlab users will see descriptions in
other newsletters.

Traditionally all scientific computation was done in Fortran, but we're seeing
more requests for library code in other languages, particularly C and C++.
There are technical reasons (e.g. function pointers) and portability reasons
behind this trend. For the most part, our community's approach has been to
call from C main programs to Fortran library routines, or to apply the f2c
Fortran-to-C translator. But native C libraries are appearing.

One specific but outstanding example is David Gay's contribution, fp/dtoa.c.
This contains C functions for perfect binary/decimal conversion. I use this
for all my scientific computing input/output.

A broader example is David E. Stewart's C library for matrix computations,
meschach (pronounced ``me shark''). This provides the common operations on
dense and sparse matrices, though of course is much smaller in scope than
lapack. Readers interested in learning about the effect of dynamic memory
allocation on library design might find this package illuminating.

The operator overloading provided by C++ is attractive for matrix libraries,
if implicit loop fusion is implemented cleverly. Various commercial efforts
along these lines are contending; if someone cares to contribute a good,
public-domain version to netlib, that would be welcome.

Newcomers to C++ may be interested in James Coplien's Advanced C++ Programming
Styles and Idioms, published by Addison-Wesley. For code, send index for

Algorithms from the new journal Numerical Algorithms are being archived in the
numeralgo library. The first two entries are: ``na1'' (avoiding breakdown
and near-breakdown in Lanczos type algorithms by Brezinski, Sadok, and Zaglia)
and ``na2'' (B-nets of box splines on three- and four-directional meshes by
M.-J. Lai)

The library lp/generators contains transportation networks, assignment, and
generalized network flow problems, from Darwin Klingman, Fred Glover, and M.

svdpack by Mike Berry computes singular values and singular vectors of large
sparse matrices.

misc/sparsdyn is a prototype sparse matrix algorithm development tool for Sun
workstations. (T. A. Davis, and P.-C. Yew)

misc/lalqmr is a package implementing the Freund, Gutknecht, and Nachtigal
version of the look-ahead Lanczos algorithm. It includes driver code to
compute eigenvalues of matrices, as well as a linear systems solver using the
quasi-minimal residual method.

misc/gemmw is a portable Level 3 BLAS implementation by Craig Douglas of
Winograd's variant of Strassen's matrix multiply.

The misc/mglab library provides a tutorial univariate multigrid program. The
user may choose various multigrid cycles, transfer operators, smoothing
methods, and nested iteration end defect correction. An Introduction to
Multigrid Methods, Wiley, Chichester, 1992 by P. Wesseling.

After a lapse, we're back on the toms (ACM Trans. on Math. Software)
distribution, now complete through Collected Algorithm 702. See the journal
for complete descriptions; a quick summary is:
687: decision tree for initial value ode
688: epdcol: a more efficient pdecol code
689: nonlinear volterra integral equations of the second kind
690: chebyshev polynomial software for elliptic-parabolic systems of pdes
691: improving quadpack automatic integration routines
692: model implementation and test package for the sparse blas
693: floating point multiple precision arithmetic
694: test matrices
695: modified cholesky factorization
696: inverse rayleigh iteration for complex band matrices
697: univariate interpolation
698: adaptive multidimensional integration for a vector of integrals
699: Patterson's quadrature formulae
700: Sturm-Liouville problems
701: exact analysis of rectangular rank-deficient sparse rational linear systems
702: truncated Newton

Subroutines for maximum likelihood and quasi-likelihood estimation of
parameters in nonlinear regression models by David Bunch, David Gay, and Roy
Welsch have been submitted to TOMS. send index for opt/nlr for details.

The libraries odrpack (orthogonal distance regression) and pppack (de Boor's
Practical Guide to Splines) have been updated, and small changes made to
napack, paranoia, picl, pltmg, pvm and others.

If you're new to netlib, send e-mail containing the line ``help'' to one of
the Internet addresses
or uucp address uunet!research!netlib. A few minutes later, assuming you have
speedy mail connections, you will receive information on how to use netlib and
an overview of the many mathematical software libraries and databases in the

This column was written June 7, 1992.


From: SIAM <>
Date: Mon, 20 Jul 92 09:19:39 EST
Subject: Contents: SIAM Control and Optimization

Table of Contents
SIAM Journal on Control and Optimization
Vol. 30, No. 6, November 1992

On the Time-Varying Riccati Difference Equation of Optimal Filtering
Giuseppe De Nicolao

Verification of the Self-Stabilization Mechanism in Robust Stochastic Adaptive
Control Using Lyapunov Function Arguements
Miloje Radenkovic and Anthony N. Michel

Global Time-Varying Linearization up to Output Injection
H. Hammouri and J. P. Gauthier

Constrained Controllability of Linear Discrete Nonstationary Systems in Banach
Vu Ngoc Phat and Trinh Cong Dieu

Extended Quadratic Controller Normal Form and Dynamic State Feedback
Linearization of Nonlinear Systems
Wei Kang and Arthur J. Krener

On the Exponential Stability of Singularly Perturbed Systems
Martin Corless and Luigi Glielmo

Variants of the Kuhn--Tucker Sufficient Conditions in Cones of Nonnegative
J. C. Dunn and T. Tian

Extreme Points for Linear Optimal Control Problems with Diagonal Structure
Edward J. Anderson and Andrew J. Philpott

A Finite Fuel Stochastic Problem on a Finite Time Horizon
A. P. N. Weerasinghe

Sensitivity Analysis of Parametrized Programs Under Cone Constraints
A. Shapiro and J. F. Bonnans

Tracking and Restrictability in Discrete Event Dynamic Systems
Cuneyt M. Ozveren and Alan S. Willsky

Information Structures, Causality, and Nonsequential Stochastic Control I:
Design Independent Properties
Mark S. Andersland and Demosthenis Teneketzis

Stochastic Approximations and Adaptive Control of a Discrete-Time Single-Server
Network with Random Routing
Armand M. Makowski and Adam Shwartz


From: SIAM <>
Date: Mon, 20 Jul 92 09:19:40 EST
Subject: Contents: SIAM Computing


October 1992 Volume 21, Number 5

Increasing the Size of a Network by a Constant Factor Can Increase
Performance by More Than a Constant Factor
Richard Koch

Representability of Design Objects by Ancestor-Controlled Hierarchical
Lin Yu and Daniel J. Rosenkrantz

A Lower Bound for Parallel String Matching
Dany Breslauer and Zvi Galil

Searching for a Mobile Intruder in a Polygonal Region
Ichiro Suzuki and Masafumi Yamashita

Determinism vs. Nondeterminism in Multiparty Communication Complexity
Danny Dolev and Tomas Feder

On Threshold Circuits and Polynomial Computation
John H. Reif and Stephen R. Tate

Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions
Bettina Just

Laying Out Graphs Using Queues
Lenwood S. Heath and Arnold L. Rosenberg

Optimal On-Line Simulations of Tree Machines by Random Access Machines*
Michael C. Loui and David R. Luginbuhl

New Results on Dynamic Planar Point Location*
Siu Wing Cheng and Ravi Janardan


End of NA Digest