### Today's Editor:

- Cleve Moler
- The MathWorks, Inc.
- moler@mathworks.com

- Again: C Programs for Linear Algebra
- Sparse Inverse Subspace Iteration Solver
- Netlib News: Searching for Files
- Contents: SIAM Control and Optimization
- Contents: SIAM Computing

-------------------------------------------------------

From: Jan Korvink <jan@pfi.ethz.ch>

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,

J.G.Korvink

Informatics in Engineering Applications,

ETH-Zurich

CH-8093 Zurich

email: korvink@pfi.ethz.ch

------------------------------

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

nanostructures.

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?

Thanks

Michael Trott

trott@physik.th-ilmenau.de

------------------------------

From: Eric Grosse <ehg@research.att.com>

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

syntax.

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

mail netlib@research.att.com

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

path user@campus.edu

(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

c++/idioms.

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.

Ramamurti.

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

netlib@research.att.com

netlib@ornl.gov

netlib@nac.no

netlib@draci.cs.uow.edu.au

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

collection.

This column was written June 7, 1992.

------------------------------

From: SIAM <helfrich@siam.org>

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

Spaces

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

Functions

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 <norris@siam.org>

Date: Mon, 20 Jul 92 09:19:40 EST

**Subject: Contents: SIAM Computing**

SIAM J. COMPUT.

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

Specifications

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

**************************

-------