Subject: NA Digest, V. 92, # 29 NA Digest Sunday, July 26, 1992 Volume 92 : Issue 29 Today's Editor: Cleve Moler The MathWorks, Inc. moler@mathworks.com Today's Topics: Again: C Programs for Linear Algebra Sparse Inverse Subspace Iteration Solver Netlib News: Searching for Files Contents: SIAM Control and Optimization Contents: SIAM Computing Submissions for NA Digest: Mail to na.digest@na-net.ornl.gov. Information about NA-NET: Mail to na.help@na-net.ornl.gov. ------------------------------------------------------- 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, J.G.Korvink Informatics in Engineering Applications, ETH-Zurich CH-8093 Zurich email: korvink@pfi.ethz.ch ------------------------------ From: Trott Michael 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 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 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 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 ************************** -------