NA Digest Saturday, January 17, 1998 Volume 98 : Issue 02

Today's Editor:
Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to

URL for the World Wide Web:

From: Gene Golub <>
Date: Sun, 11 Jan 1998 12:28:08 -0800
Subject: Richard Hamming

Richard Hamming, who made important contributions to communication theory
and computing, died in Monterey, Ca on Wed, Jan 7. He made the oft
quoted statement, " The purpose of computing is insight, not numbers".

An extended obituary is given in the NYTimes of Sunday, Jan 11.



From: Richard Franke <>
Date: Wed, 7 Jan 1998 22:32:56 -0800 (PST)
Subject: Richard Hamming

I am saddened to report that Dr. Richard Hamming died this
morning due to a massive heart attack.

Dr. Hamming spent some early years of his career at Los Alamos,
and was at Bell Laboratories from 1946-1976. He was also an
Adjunct Professor at Princeton University. In 1976 he retired
from Bell Laboratories and was appointed Adjunct Professor
(later Senior Lecturer) at the Naval Postgraduate School and
remained in that position until his death.

Dr. Hamming is well-known as the inventor of the Hamming filter,
the namesake of the IEEE Hamming prize (as well as its first
recipient), and many contributions to the numerical analysis
community. He will be long remembered for his keen insights
into many facets of science and computation. I'll also long
long remember him for his red plaid sport coat and his bad
jokes. A recent picture of him is available on his home page

I'm sure there will be many tributes in the coming months, all


From: James F Kaiser <>
Date: Wed, 14 Jan 1998 10:52:56 -0500 (EST)
Subject: Richard Hamming

On January 8, 1998 Richard W. Hamming died of a heart attack in Monterey,
California where he had taught at the Naval Postgraduate School for the
last 22 years. Prior to that Hamming had spent three decades at Bell
Laboratories in Murray Hill, NJ where he was a major factor in computerizing
the laboratories both in hardware and software. He is perhaps best known for
his pioneering work in error correcting codes that are now ubiquitous in
computer hardware, compact discs, hard drives, digital communication systems,
etc. He is also know for his work on integrating differential equations
and the spectral window which bears his name.

Richard Hamming had received a number of awards which included:
Fellow, IEEE, 1968; the ACM Turing Prize, 1968;
the IEEE Emanuel R. Piore Award, 1979; Member, National
Academy of Engineering, 1980; and the Harold Pender Award, U. Penn., 1981.
In 1987 a major IEEE award was named after him,
namely the Richard W. Hamming Medal, ``For exceptional contributions to
information sciences and systems''; fittingly, he was also the first
recipient of this award, 1988.
In 1996 in Munich he received the prestigious $130,000 Eduard Rheim Award
for Achievement in Technology for his work on error correcting codes.
He was both a Founder and Past President of ACM, and
a Vice Pres. of the AAAS Mathematics Section.

His extensive writing has included a number of important, pioneering, and
highly regarded books. These include:

"Numerical Methods for Scientists and Engineers", McGraw-Hill, 1962;
"Introduction to Applied Numerical Analysis", McGraw-Hill, 1971;
"Digital Filters", Prentice-Hall, 1977, 1983, 1989 and
translated into several European languages;
"Coding and Information Theory", Prentice-Hall, 1980, 1986;
"Methods of Mathematics Applied to Calculus, Probability and Statistics",
Prentice-Hall, 1985;
"The Art of Probability for Scientists and Engineers", Addison-Wesley, 1991;
and his last book,
"The Art of Doing Science and Engineering: Learning to Learn",
Gordon and Breach, 1997.

We will all miss his engaging mind and his penetrating insight into matters
scientific, engineering, and of everyday living.

He is survived by his wife Wanda of 55 years.

James F. Kaiser
Duke University


From: Arnold Neumaier <>
Date: Tue, 13 Jan 1998 10:08:45 +0100
Subject: Nabla

Does anyone know the history of using the symbol $\nabla$ for
the gradient, and the meaning of the symbol outside of mathematics?

Arnold Neumaier


From: Keith Briggs <>
Date: Thu, 8 Jan 1998 11:52:27 +0000 (GMT)
Subject: Doubledouble Floating Point Arithmetic

Dear Colleagues,

I have released version 2.2 of my C++ software package `doubledouble' which
implements doubled-double (approximately 30 decimal place) floating point
arithmetic on IEEE 754 floating-point hardware.

This version includes many improvements suggested by Stefan Bauberger, Roger
Schlafly, Wayne Hayes, Victor Shoup, Tony Dixon, and Alan Miller. These include
new functions, portability enhancements and improvements to many details.

This is a development of code formerly released as `Quad version 2.0'. The
name Quad has been dropped as the code does NOT implement the IEEE quadruple
precision format. The name `doubledouble' was chosen instead since it is
distinctive and reminds one that an unusual data type is being used, and it
describes the format of two adjacent doubles.

The code may be downloaded from

Except where otherwise indicated by comments in the code, this software is
covered by the GNU Public License, as described in the included COPYLEFT

Keith Briggs


From: Werner Krauth <>
Date: Thu, 8 Jan 1998 14:24:06 +0100 (CET)
Subject: Computing the Pfaffian

Dear colleagues..

I have an urgent question concerning the Pfaffian of an antihermitian
2 N x 2 N matrix Q

Pf(Q) proportional to

\sum_{\sigma} (-1)^\sigma Q^{\sigma_1 \sigma_2}...Q^{\sigma_{2 N-1} \sigma_2N}

...with sigma : Permutation of (1, 2, ... , 2 N}
which I need to compute efficiently for N \sim 80 .

A data base search has been as unsuccessful as all the other
bibliographic searches that I have undertaken...I only remember my
professor in the linear algebra 101 class tell us (18 years ago) that
this was next to impossible - but I don't have a reference for this.

The Pfaffian is an important concept in many fields of theoretical
physics, e. g. in some cases in which antisymmetric fermionic
wave functions are needed. Here I want to use it in a computational

Werner Krauth
Laboratoire de Physique Statistique, Ecole Normale Superieure
24, rue Lhomond, F-75231 Paris Cedex, France
Tel: 33 1 Fax: 33 1


From: G. W. Stewart <>
Date: Thu, 8 Jan 1998 12:31:34 -0500 (EST)
Subject: Computing the Adjoint

In a previous posting to na-digest Jim Gubernatis (

Does anyone know of an algortihm or of sofware that allows one to
compute the adjoint of a matrix that is singular? My matrices are
complex and of the order of 100.

This turned out to be a really interesting problem. I have prepared
a technical report "On the Adjoint Matrix", which may be obtained at

Briefly, not only is the adjoint of a matrix A defined when A
is singular, but its condition number is the ratio of the largest
singular value of A to the *second* smallest. Thus the adjoint
can be perfectly conditioned, even when A is ill-conditioned.

The surprising thing is that even when A is ill-conditioned
you can use the formula

adj(A) = det(A)*inv(A),

provided you implement it properly. For example, in the real case you
can computed the adjoint from the output of the Householder QR
decomposition provided by LAPACK or LINPACK. (The complex case
requires a little tweaking of the programs.) The details are
contained in the report.

Pete Stewart


From: Mahesh Joshi <>
Date: Fri, 9 Jan 1998 16:49:45 -0600 (CST)
Subject: Announcing PSPASES and WSSMP

Announcing PSPASES and WSSMP

PSPASES : A Scalable Parallel Direct Solver for
Sparse Symmetric Positive Definite Systems

Mahesh Joshi, George Karypis, Vipin Kumar
Department of Computer Science,
University of Minnesota, Mineapolis, MN.

Anshul Gupta
IBM Thomas J. Watson Research Center,
Yorktown Heights, NY.

We are glad to announce a beta release of PSPASES, a stand-alone MPI-based
parallel library for solving linear systems of equations involving sparse
symmetric positive definite matrices. The library efficiently implements
the scalable parallel algorithms developed by authors, for each of the four
phases of direct solution method; viz. ordering, symbolic factorization,
numerical Cholesky factorization, and solution of triangular systems.

PSPASES is highly scalable, mainly because it uses a highly scalable
parallel multifrontal algorithm in the most expensive computational phase
of numerical factorization. All the other phases are also scalable by

In our testing, PSPASES solved a system of around 1 million equations in
just 62 seconds on 64 processors and in 38 seconds on 128 processors of
Cray T3E. This time included times required for all the four phases of
the solver. The highest performance clocked by PSPASES is 21.2 GFLOPS for
the numerical factorization phase. This efficient and scalable behavior
is demonstrated while solving most of the systems appearing in practice.

PSPASES is implemented using standard MPI and BLAS, which makes it portable
to most of today's parallel computers and networks of workstations. We have
tested PSPASES extensively on IBM SP, network of IBM RS6000 workstations,
Cray T3E, SGI Origin 2000 and PowerChallenge architectures.

PSPASES uses ParMETIS and METIS as default libraries for computing fill-
reducing ordering, but it also accepts user supplied ordering. Different
functional interfaces are provided for each of the phases of the solver
and a simple interface is also provided for easy use. The user can use
these interfaces to solve multiple systems with same nonzero structures;
to solve same system for multiple right hand sides; and to get different
statistical information such as the memory requirements of the solver
and the quality of the ordering.

Visit the PSPASES web site at

to obtain the software, the manual, and related technical papers.

Any comments, questions or bugs regarding PSPASES can be reported to
Mahesh Joshi (

WSSMP: Watson Symmetric Sparse Matrix Package

Anshul Gupta
IBM Thomas J. Watson Research Center,
Yorktown Heights, NY.

Mahesh Joshi and Vipin Kumar
Department of Computer Science,
University of Minnesota, Mineapolis, MN.

A faster version of the solver with enhanced functionality is available
for IBM SP and RS6000 systems, as WSSMP. The WSSMP package contains
robust industrial strength code for serial and parallel solution of sparse
symmetric positive definite and indefinite systems. WSSMP has been
clocked at up to 450 MFLOPS on an RS6000/397 workstation and up to 24 GFLOPS
on a 64-processor SP with model-397 nodes. Documentation for WSSMP is
available at

Any questions pertaining to WSSMP may be directed to Anshul Gupta


From: Claude Brezinski <>
Date: Sun, 11 Jan 1998 09:27:26 +0100
Subject: New Book, Projection Methods for Systems of Equations

Projection Methods for Systems of Equations
North-Holland, Amsterdam, 1997
ISBN 0 444 82777 3


1. Preliminaries
2. Biorthogonality
3. Projection methods for linear systems
4. Lanczos-type methods
5. Hybrid procedures
6. Semi-iterative methods
7. Around Richardson's projection
8. Systems of nonlinear equations

The solution of systems of linear and nonlinear equations occurs in
many situations and, so, it is a question of major interest. The
advances in computer's technology now allow to consider systems of
several hundred thousands equations and even larger. Thus, there is
a crucial need for more and more efficient algorithms.

This book describes iterative methods, based on projections, for the
solution of this question.

These past few years, such methods have received much attention from
researchers in numerical linear and nonlinear algebra and they have
been applied to a wide range of problems.

This volume is intended to students and researchers in numerical analysis
(and many open questions are presented) and to practitionners and engineers
having to use the most recent methods for solving their particular problem.

Universite' des Sciences et Technologies de Lille
Laboratoire d'Analyse Numerique et d'Optimisation


From: Panos Pardalos <>
Date: Sun, 11 Jan 98 19:40:50 EST
Subject: New Book on Satisfiability

Satisfiability Problem: Theory and Applications
Edited by: Dingzhu Du, Jun Gu, and Panos M. Pardalos
American Mathematical Society,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science,
Volume 35 (1997), ISBN: 0-8218-0479-0
724 pages

The satisfiability (SAT) problem is central in mathematical
logic, computing theory, and many industrial applications. There
has been a strong relationship between the theory, the
algorithms, and the applications of the SAT problem. This book
aims to bring together work by the best theorists,
algorithmists, and practitioners working on the SAT problem and
on industrial applications, as well as to enhance the
interaction between the three research groups. The book features
the application of theoretical/algorithmic results to practical
problems and presents practical problems for
theoretical/algorithmic study.
Major topics covered in the book include practical and
industrial SAT problems and benchmarks, significant case studies
and applications of the SAT problem and SAT algorithms, new
algorithms and improved techniques for satisfiability testing,
specific data structures and implementation details of the SAT
algorithms, and the theoretical study of the SAT problem and SAT


Stephen A. Cook and David G. Mitchell -- Finding hard instances of
the satisfiability problem: A survey
Jun Gu, Paul W. Purdom, John Franco, and Benjamin Wah -- Algorithms
for the satisfiability (SAT) problem: A survey
Paul Walton Purdom and G. Neil Haven -- Backtracking and probing
J. Franco -- Relative size of certain polynomial time solvable subclasses
of satisfiability
Madhav V. Marathe, Harry B. Hunt, III, Richard E. Stearns, and Venkatesh
Radhakrishnan -- Complexity of hierarchically and 1-dimensional
periodically specified problems. I: Hardness results
Oliver Kullmann -- Worst-case analysis, 3-SAT decision, and lower bounds:
Approaches for improved SAT algorithms
Kazuo Iwama and Kazuya Takaki -- Satisfiability of 3CNF formulas with
small clause/variable-ratio
David A. Plaisted and Geoffrey D. Alexander -- Propositional search
efficiency and first-order theorem proving
Jinchang Wang -- Branching rules for propositional satisfiability test
Benjamin W. Wah and Yi Shang -- A discrete Lagrangian-based global-search
method for solving satisfiability problems
M. G. C. Resende, L. S. Pitsoulis, and P. M. Pardalos -- Approximate
solution of weighted MAX-SAT problems using GRASP
Jun Gu -- Multispace search for satisfiability and NP-hard problems
Steve Joy, John Mitchell, and Brian Borchers -- A branch and cut algorithm
for MAX-SAT and weighted MAX-SAT
Arne Lokketangen and Fred Glover -- Surrogate constraint analysis
--new heuristics and learning schemes for satisfiability problems
Henry Kautz, Bart Selman, and YueYen Jiang -- A general stochastic approach
to solving problems with hard and soft constraints
Jieh Hsiang and Guan Shieng Huang -- Some fundamental properties of
Boolean ring normal forms
Sandeep K. Shukla, Daniel J. Rosenkrantz, Harry B. Hunt, III, and Richard E.
Stearns -- The polynomial time decidability of simulation relations for
finite state processes: A HORNSAT based approach
Lefteris M. Kirousis, Evangelos Kranakis, and Danny Krizanc -- A better
upper bound for the unsatisfiability threshold
R. Battiti and M. Protasi -- Solving MAX-SAT with non-oblivious functions
and history-based heuristics
Ewald Speckenmeyer, Max B&ouml;hm, and Peter Heusch -- On the imbalance
of distributions of solutions of CNF-formulas and its impact on
satisfiability solvers
Hans van Maaren -- On the use of second order derivatives for the
satisfiability problem
Craig K. Rushforth and Wei Wang -- Local search for channel assignment in
cellular mobile networks
Shawki Areibi and Anthony Vannelli -- A GRASP clustering technique for
circuit partitioning

For orders with remittances:
American Mathematical Society
PO Box 5904, Boston, MA 02206-5904; (401) 455-4000


From: Margaret Maio <>
Date: Wed, 14 Jan 1998 20:05:00 -0500
Subject: New Book, Complexity and Real Computation

Complexity and Real Computation

LENORE BLUM, International Computer Science Institute, Berkeley, CA and
City University of Hong Kong
FELIPE CUCKER, City University of Hong Kong and Universitat Pompeu Fabra,
Barcelona, Spain
MICHAEL SHUB, IBM T.J. Watson Research Center, Yorktown Heights, NY and
STEVE SMALE, City University of Hong Kong

The classical theory of computation has its origins in the work of Godel,
Turing, Church, and Kleene and has been an extraordinarily successful
framework for theoretical computer science. The thesis of this book,
however, is that it provides an inadequate foundation for modern
scientific computation where most of the algorithms are real number

The goal of this book is to develop a formal theory of computation which
integrates major themes of the classical theory and which is more
directly applicable to problems in mathematics, numerical analysis, and
scientific computing. Along the way, the authors consider such
fundamental problems as:

 Is the Mandelbrot set decidable?  For simple quadratic maps, is the
Julia set a halting set?  What is the real complexity of Newton's
method?  Is there an algorithm for deciding the knapsack problem in a
polynomial number of steps?  Is the Hilbert Nullstellensatz intractable?
 Is the problem of locating a real zero of a degree four polynomial
intractable?  Is linear programming tractable over the reals?

Contents: Introduction. Definitions and First Properties of Computation.
Computation over a Ring. Decision Problems and Complexity over a Ring.
The Class NP and NP-complete Problems. Integer machines. Algebraic
Settings for the Problem "P=NP?". Newton's Method. Fundamental Theorem of
Algebra: Complexity Aspects. Bezout's Theorem. Condition numbers and the
loss of precision of linear equations. The Condition Number for
Non-Linear Problems. The condition Number in P(H(d)). Complexity and the
Condition Number. Linear Programming. Deterministic lower bounds.
Probabilistic machines. Parallel computations. Some Separations of
Complexity Classes. Weak machines. Additive machines. Non uniform
complexity classes. Descriptive Complexity.

1997/453 PP./HARDCOVER/$39.95/ISBN 0-387-98281-7

To order:
Call: 1-800-SPRINGER
Fax: (201)-348-4505
Write: Springer-Verlag New York, Inc., PO Box 2485, Secaucus, NJ


From: James Nagy <>
Date: Fri, 9 Jan 1998 14:34:41 -0600 (CST)
Subject: Conference for Bob Plemmons


a conference in honor of
Robert J. Plemmons
on the occasion of his 60th Birthday

Friday, January 8 -- Saturday, January 9, 1999
Wake Forest University
Winston-Salem, NC

In the past 30 years, Bob Plemmons has made several significant
contributions on a variety of problems in linear algebra, including:
nonnegative and structured matrices; large and sparse least squares
problems, including iterative methods and parallel computations;
signal processing and image processing applications.
The aim of this meeting is to bring together experts from these
diverse, yet related, areas to explore greater commonality.

There will be four invited long presentations (45 minutes),
one in each of the following areas:

* Large, sparse least squares problems / parallel algorithms.
* Signal processing applications.
* Matrix analysis / nonnegative matrices
* Image processing applications.

Associated with each of these long presentations there will
be up to five invited short presentations (25 minutes).
There will be no contributed papers, and no parallel sessions,
but we encourage contributed papers to be submitted for a
poster session.

On Saturday evening, there will be a banquet in Bob's honor.

Papers presented at the conference, including contributed posters,
can be submitted to a special issue of Linear Algebra and Its
Applications for possible publication. The papers will go through
the usual refereeing process.

Invited speakers will include:

Abraham Berman (Technion) Franklin Luk (RPI)
Michael Berry (Tennessee) Carl Meyer (NC State)
Ake Bjorck (Linkoping) Michael Neumann (Connecticut)
Raymond Chan (CUHK, Hong Kong) Esmond Ng (Oak Ridge)
Robert Funderlic (NC State) Michael Ng (HCU, Hong Kong)
Kyle Gallivan (Florida State) Ching-Tsuan Pan (Northern Illinois)
Gene Golub (Stanford) Nikos Pitsianis (BOPS, Inc.)
Martin Hanke (Karlsruhe) Ahmed Sameh (Purdue)
William Harrod (Cray Research) Daniel Szyld (Temple)
Misha Kilmer (Northeastern) Curt Vogel (Montana State)

A future announcement will include information on submission
guidelines for poster presentations, as well as a www address
containing detailed information about the meeting. Any questions
can be sent to:

Organizing Committee:

Michele Benzi (Los Alamos) Pau'l Pauca (Duke)
Richard Carmichael (Wake Forest) Xiaobai Sun (Duke)
William Ferng (Taiwan) Todd Torgersen (Wake Forest)
James Nagy (Southern Methodist)


From: Chenm <>
Date: Sat, 10 Jan 1998 23:48:51 -0500 (EST)
Subject: SIAM Southeastern-Atlantic Section

The Second SIAM Student Conference and
The 22nd Annual Meeting of SIAM's Southeastern-Atlantic Section

Florida State University, Tallahassee
March 19-21, 1998

The conference will be held at the Turnbull Center for Professional
Development on the campus of Florida State University. The Student
Conference will run for two days, and will begin at 1:00 p.m. on Thursday,
March 19. It is intended primarily for graduate students, although
undergraduates are welcome as well. Like the First SIAM Student Conference
at Clemson in 1996, the conference at FSU will also be held in conjunction
with the annual meeting of SIAM's Southeastern-Atlantic Section; students
from the southeastern U.S. - and beyond - are invited to attend.

The conference program will focus on applications of mathematics
in a wide variety of areas, and include presentations from some recent
mathematics graduates working in industry. A select group of students
will be invited to give talks, and all students are encouraged
to present contributed papers. The meeting will feature distinguished
invited speakers, and special sessions in areas of current interest.
Hans Schneider Muntau, Deputy Director of the National High Magnetic
Field Lab., will be the speaker at the banquet on the evening of Thursday,
March 19. The invited plenary speakers are:

"The Dynamics of Neurons"
- John Guckenheimer, Cornell University
"Use of Scale-Up and Parallel Reservoir Simulation Technologies for
Practical Large-Scale Problems"
- Hamdi Tchelepi, Chevron Petroleum Technology Company
"Statistical and Computational Aspects of Biological Database Searches"
- Michael Waterman, University of Southern California
"Domain Decomposition Methods for Modeling Subsurface and Surface Flow
- Mary Wheeler, University of Texas at Austin

and there will be special sessions on:

"Computational Genomics," - organized by De Witt Sumners
"Higher Order Methods for Multi-Domain Decomposition," - organized by
Gordon Erlebacher (FSU,
"Imaging," - organized by Dave Wilson (University of Florida,
"Recent Mathematics Graduates Working in Industry," organized by SIAM

Students are encouraged to stay on when the conference merges with
the Southeastern Section meeting on the afternoon of Friday, March 20.
The emphasis on students will continue at the Section meeting, where
papers contributed by students will be given priority in the scheduling.
The meeting will end by 1:00 p.m. on Saturday, March 21, but interested
participants who can, or must, extend their stay through the afternoon
can tour the National High Magnetic Field Lab.

Dr. Chris Hunter (, chair of FSU's Mathematics Department,
is the host and chair of the Local Organizing Committee (LOC). Questions about
the conference should be directed to


From: Jens Burmeister <>
Date: Sun, 11 Jan 1998 11:00:18 +0100 (MET)
Subject: GAMM-Seminar Kiel on Concepts of Numerical Software

Dear na-netters,

the webpages concerning the

14th GAMM-Seminar Kiel on
Concepts of Numerical Software
January 23rd to 25th, 1998,
University Kiel, Germany

are available via the URL

You will find information about the timetable and a collection
of abstracts. Please use our registration form if you would like
to participate.

Greetings from Northern Germany
Jens Burmeister


From: Karsten Decker <>
Date: Mon, 12 Jan 1998 17:23:23 +0100
Subject: 23rd SPEEDUP Workshop

23rd SPEEDUP Workshop on
Process Engineering
jointly organized by
Swiss Center for Scientific Computing (CSCS/SCSC)
Leonhard Euler Research Center
Competence Center For CFD
to be held at
ETH Zurich
March 19-20, 1998

Physical modeling and numerical simulation of today's industrial
processes is extremely demanding. In general, multi-disciplinary
physical phenomena need to be be treated, requiring the expertise of
specialists in the fields of structural, solid and fluid mechanics,
thermodynamics, electrodynamics, control theory, material science, as
well as mathematics and computer science.

The 23rd SPEEDUP Workshop is intended to bring together members of
academic institutions and business enterprises which have an active
interest in process engineering, both, from the perspectives of model
development and applications. The workshop will focus on topics of
growing importance in process engineering which highlight today's and
future challenges of process simulation, process optimization and the
development of process control equipment.

The topics include but are not limited to

-- Separation technology and transport phenomena
-- Reaction engineering and catalysis
-- Process design, operation, integration and development
-- Dynamic simulation and process optimization
-- Design of process control strategies

Confirmed speakers in the workshop program include

-- M. Campagna, A. Steiner, ABB Switzerland
-- M. Casey, E. Lang, M. Wehrli, Sulzer Innotec
-- J. Murphy, British Aerospace
-- V. Ranade, National Chemical Laboratory, India
-- W. Schmidt, Daimler Benz AG

The proceedings of the workshop will be published in the first 1998
issue of the SPEEDUP Journal, to appear in May 1998.

For the latest information on the program the interested reader is
referred to

Further information on the SPEEDUP Society can be obtained from


From: Erik Elmroth <>
Date: Fri, 16 Jan 1998 15:42:56 +0100 (MET)
Subject: PARA98, Workshop on Applied Parallel Computing

PARA98 - International Workshop on Applied Parallel Computing,
Large Scale Scientific and Industrial Problems,
June 14-17, 1998, Umea University, Sweden

(see updated

Second Call for Papers
Participation and Registration

High Performance Computing Center North (see
is hosting the fourth International Workshop on Applied Parallel
Computing (PARA98) in June 14-17, 1998 at Umea University, Sweden.

The general theme for PARA98 is Large Scale Scientific and
Industrial Problems focusing on:
o High-performance computing applications in academia and industry,
o Tools, languages and environments for high-performance computing,
o Scientific visualization and virtual reality applications in
academia and industry,
o Future directions in high-performance computing and networking.

Deadlines, Abstracts and Papers:
o February 15, 1998: Extended Abstracts
o April 15, 1998: Notification to authors
o July 31, 1998: Papers (between 5 and 10 pages)
Deadline early registration:
o May 1, 1998

The PARA98 meeting is aimed to be an international forum for
idea and competence exchange for specialists in parallel computing,
visualization, etc and scientists from industry and academia
solving large scale computational problems.
Another important aim of the PARA meetings is to strengthen the ties
between HPC centers, academia, and industry in the Nordic countries
as well as worldwide.

The meeting starts with a one day tutorial followed by a three day
workshop. There will be several invited one-hour lectures as well as
contributed 20-30 minutes talks. The conference proceedings will be
published by Springer Verlag in their LNCS series.

So far the following invited speakers have accepted our invitation
(there are pending invitations):
- Prof Jack Dongarra, University of Tennessee, Knoxville, USA
- Prof Iain Duff, Rutherford Appleton Lab., UK, and CERFACS, France
- Prof Dennis Gannon, University of Illinois, Urbana-Champaigne, USA
- Prof Gene Golub, Stanford University, USA
- Dr Fred Gustavsson, IBM Yorktown Heights, USA
- Prof Chris Johnson, University of Utah, Salt Lake City, USA
- Dr Richard Lehoucq, Sandia National Laboratories, New Mexico, USA
- Prof Cherry Pancake, Oregon State University, USA
- Prof Hans Zima, University of Vienna, Austria

The PARA Steering Committee:
- Petter Bjorstad, University of Bergen (Norway)
- Jack Dongarra, University of Tennessee and Oak Ridge National Lab (USA)
- Bjorn Engquist, PDC, Royal Institute of Technology, Stockholm (Sweden)>
- Kristjan Jonasson, University of Iceland, Reykjavik (Iceland)
- Bo Kagstrom, Umea University and HPC2N (Sweden), PARA98 Chairman
- Risto Nieminen, Helsinki University of Technology, Espoo (Finland)
- Karstein Sorli, SINTEF, Dept of Industrial Mathematics, Trondheim (Norway)
- Olle Teleman, Center for Scientific Computing (CSC), Espoo (Finland)
- Jerzy Wasniewski, Danish Computing Centre for Research and Education
(UNI-C), Lyngby (Denmark), PARA94-96 Chairman

Questions regarding PARA98 should be addressed to


From: Fred Hickernell <>
Date: Thu, 08 Jan 1998 10:21:53 +0800
Subject: Position at Hong Kong Baptist University

Hong Kong Baptist University
Department of Mathematics

The Department of Mathematics invites applications for an Assistant,
Associate, or Full Professor position with specialty in scientific computing or
statistics commencing September 1, 1998. Applicants should have a PhD in
mathematics, statistics or a related discipline and a demonstrated teaching and
research ability. Applicants for appointment at a senior rank should have
academic leadership experience. The Department of Mathematics has fourteen
faculty members and offers BSc, MPhil and PhD degrees in Mathematics and an MSc
in Scientific Computing. Several faculty members are members of the
University's Statistical Research and Consultancy Centre. The annual salary is
HK$522,780 and above depending on qualifications and experience. Benefits
include annual leave, medical, education allowance and housing. To apply send
your CV and three confidential letters of reference to the Personnel Office,
Hong Kong Baptist University, Kowloon Tong, Hong Kong, Fax: (852) 2339 5001.
Applications received by April 1, 1998 will receive full consideration. To
find out more about our department and this position visit our web page at Specific inquiries may be made to Fred J.
Hickernell, Head of Mathematics, E-mail:


From: Andreas Brieden <>
Date: Mon, 12 Jan 1998 02:04:25 +0100
Subject: Postdoctoral Position at University of Technology, Munich.

Beginning March 1, 1998 and Juli 1, 1998 there will be available a
Postdoc-Position and a position for a Ph.D-student (Assistent) at the
Center for Mathematical Sciences, University of Technology, Munich.

The candidate for the post-doc position will be joining a project
supported by the German Research Foundation dealing with the
algorithmic analysis of finite metric spaces
that is motivated by demands from computer linguistics to develop
operational models for natural languages.

The candidate for the second position will be given the opportunity
to work towards a Ph.D. in an active research project in
applied algorithmic mathematics.

Applicants should have a strong background in at least one of the
following areas: discrete mathematics, combinatorial or convex geometry,
combinatorial optimization, or stochastic programming.
However, for the second position, particularly strong candidates
with other majors are also invited to apply.

Applications should be sent to

Professor Dr. Peter Gritzmann
Zentrum Mathematik
Technische Universitaet Muenchen
Gabelsbergerstr. 43
D-80233 Muenchen

no later than February 1, 1998 for the first and May 1,1998 for the second

For further information contact:

Dipl. Math. oec. Andreas Brieden
(0) 89 289 28 289


From: Ray Tuminaro <>
Date: Mon, 12 Jan 98 12:12:35 MST
Subject: Postdoctoral Positions at Sandia National Laboratories

Two Fellowships at Sandia National Laboratories

The Computational Sciences and Mathematics Center at Sandia National
Laboratories (Albuquerque/NM and Livermore/CA) is seeking qualified
candidates for two post-doctoral fellowship positions. These positions
offers an exceptional opportunity for innovative research in scientific
computing. The successful candidates will hold a Ph.D. in a scientific
computing discipline and have significant experience in iterative linear
equation solvers, high performance computing, and numerical algorithms.

The Center maintains strong research programs in a variety of areas, including
numerical mathematics, discrete algorithms, computational physics/engineering,
and advanced systems software and tools. A unique computing environment is
supported which includes a 4500-node Intel TFlops computer, a 1800-processor
Intel Paragon, a 192-processor SGI Origin system, an 84-processor DEC-8400
system, and experimental heterogeneous computer platforms.

The position includes a competitive salary, moving expenses, and a professional
travel allowance.

Interested persons should submit a complete resume with names and
addresses of three references to:

Ray S. Tuminaro
Sandia National Laboratories
Department 9222 / MS 9214
P.O. Box 969
Livermore, CA 94551-0969
(510) 294-2564

Applications will be accepted through March or until the position
is awarded.

Sandia National Labs is a U.S. Department of Energy multiprogram
laboratory, operated by Sandia Corporation, a wholly owned subsidiary
Lockheed Martin Corporation, with locations in Albuquerque, NM and
Livermore, CA.

Equal Opportunity Employer. Drug-free workplace. U.S. Citizenship is
normally required.


From: Peter Knabner <>
Date: Fri, 16 Jan 1998 14:35:07 +0100
Subject: Assistenten-Position in Erlangen

Am Lehrstuhl fuer Angewandte Mathematik I der Friedrich-Alexander-Unversitaet
Erlangen-Nuernberg ist voraussichtlich zum 1.5.1998 die Stelle eines

Wissenschaftlichen Assistenten (C1)

zu besetzen. Bewerber/Bewerberinnen sollten vorzugsweise promoviert sein und
einen Studienabschluss in Mathematik, Physik oder Informatik aufweisen.
Kenntnisse in Numerischer Mathematik und/oder Analysis von partiellen
Differentialgleichungen werden erwartet. Zu den Aufgaben gehoeren Betreuung
von Uebungen fuer Ingenieur-Studenten und Teilnahme an Forschungsprojekten aus
dem Gebiet Numerik von partiellen Differentialgleichungen

Bewerbungen werden bis zum 28.2.1998 erbeten an

Prof. Dr. Peter Knabner
Institut fuer Angewandte Mathematik Tel. +9131 857015 or 857016
Martensstrasse 3 Fax +9131 857670
D 91058 Erlangen E-mail


From: Barry Smith <>
Date: Wed, 14 Jan 1998 16:54:39 -0600 (CST)
Subject: Summer Graduate Student Positions at Argonne

1998 Summer Research Positions
Givens Associates
Argonne National Laboratory
Mathematics and Computer Science Division

The Mathematics and Computer Science (MCS) Division at Argonne National
Laboratory is developing innovative techniques in numerical computing
and computational mathematics. Givens Associates will work actively with
Argonne scientists designing, analyzing, and implementing numerical and
visualization methods using the new framework. Associates will have
access to some of the most powerful computers in the world.

The MCS Division has strong programs in software tools and in numerical
methods for automatic differentiation, optimization, partial
differential equations, and linear algebra. The Givens Associate
positions are intended to encourage graduate students who are beginning
careers in numerical analysis or computational mathematics. Candidates
must be in an accredited Ph.D. program in mathematics, applied
mathematics, computer science, or a related field.

Internationally recognized for innovative research in high-performance
computing, the MCS Division is expanding its activities in conjunction
with the newly established Center for Computational Science and
Technology. At the core of the center are scalable parallel computers, a
distributed supercomputing laboratory, and a virtual environments
laboratory. For further information, see or
contact Jan Griffin at

During the appointment period, participants receive a stipend of $580 to
$600 per week (depending on experience level) and a housing allowance.*
Transportation expenses are reimbursed for one round-trip between the
Laboratory and the participant's home or university for round-trip
distances greater than 100 miles. If travel is via personal auto,
reimbursement is at a rate of 31-1/2 cents per mile, with the total not
to exceed coach-class airfare.

The first step in the application procedure is to send or E-MAIL a
current resume and the names and addresses of three persons willing to
write letters of reference to Ms. Lisa Reed, Division of Educational
Programs, Argonne National Laboratory, 9700 S. Cass Avenue, Argonne, IL
60439, (630-252-3366; This material must be received
at Argonne by February 6, 1998. Approximately six appointments will be
made for 10 to 12 summer weeks and may be renewed for a second summer.

* Stipends and housing allowance are considered taxable income by the
IRS. The Laboratory is required by law to withhold tax on this income.


From: Technical Group <>
Date: Fri, 9 Jan 1998 15:20:27 +0300 (MSK)
Subject: Contents, East-West Journal of Numerical Mathematics

Vol.5, No.4, 231-311 (December 1997)

Explicit extension operators on heirarchical grids
G.Haase and S.V.Nepomnyaschikh

Streamline diffusion least-squares mixed finite element
methods for convection-diffusion problems
R.D.Lazarov, L.Tobiska, and P.S.Vassilevski

Hybrid finite element - spectral element approximation
of wave propagation problems
D.J.P.Lahaye, F.Maggio, and A.Quarteroni

Stabilized mixed finite volume methods
for convection-diffusion problems
R.Sacco and F.Saleri


From: Corry Magrijn <>
Date: Fri, 9 Jan 1998 15:27:39 +-100
Subject: Contents, Mathematics of Control, Signals, and Systems

Mathematics of Control, Signals, and Systems (MCSS)
Volume 10, Number 3

B.R. Barmish and C.M. Lagoa,
The uniform distribution: A rigorous justification
for its use in robustness analysis,

A. Fischer,
Stability radii of infinite-dimensional positive systems,

M. Cohen de Lara,
Characterization of a subclass of finite-dimensional
estimation algebras with maximal rank. Application to

P. Kunkel and V. Mehrmann,
The linear quadratic optimal control problem for linear
descriptor systems with variable coefficients,

N. Cohen and I. Lewkowicz,
Convex invertible cones of state space systems,

Volume 10, Number 4

M. Weiss and G. Weiss,
Optimal control of stable weakly regular linear systems,

K.L. Blackmore, R.C. Williamson, I.M.Y. Mareels,
and W.A. Sethares,
Online learning via congregational gradient descent,

L. Farina and L. Benvenuti,
Polyhedral reachable set with positive controls,

J.N. Tsitsiklis and V.D. Blondel,
Lyapunov exponents of pairs of matrices, a correction,


From: Deidre Wunderlich <>
Date: Wed, 14 Jan 98 09:00:08 -0500
Subject: Contents, SIAM Journal on Matrix Analysis and Applications

SIAM Journal on Matrix Analysis and Applications
Volume 19, Number 1, JANUARY 1998

On the Least Squares Approximation of Symmetric-Definite Pencils
Subject to Generalized Spectral Constraints
Moody T. Chu and Quanlin Guo

Regularization of Singular Systems by Derivative and Proportional
Output Feedback
D. L. Chu, H. C. Chan, and D. W. C. Ho

Perturbation Theory for Algebraic Riccati Equations
Ji-Guang Sun

Inequalities for the Hadamard Product of Matrices
B. Mond and J. E. Pecaric

Primitivity of Positive Matrix Pairs: Algebraic Characterization,
Graph Theoretic Description, and 2D Systems Interpretation
Ettore Fornasini and Maria Elena Valcher

Bruhat Decomposition and Numerical Stability
O. H. Odeh, D. D. Olesky, and P. van den Driessche

Generalizations of Ky Fan's Dominance Theorem
Chi-Kwong Li and Roy Mathias

A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz
Systems of Linear Equations
S. Chandrasekaran and Ali H. Sayed

Generalized Reflexive Matrices: Special Properties and Applications
Hsin-Chu Chen

Efficient Solution of Constrained Least Squares Problems with
Kronecker Product Structure
Anders Barrlund

Computing a Factor of a Polynomial by Means of Multishift LR
Luca Gemignani

Eigenvector Slicing of the Nonnegative Matrices
D. J. Hartfiel

Euclidean Norm Minimization of the SOR Operators
Apostolos Hadjidimos and Michael Neumann

Using the Matrix Sign Function to Compute Invariant Subspaces
Zhaojun Bai and James Demmel

The M-Matrix Group Generalized Inverse Problem for Weighted Trees
Stephen J. Kirkland and Michael Neumann

Parameter Estimation in the Presence of Bounded Data Uncertainties
S. Chandrasekaran, G. H. Golub, M. Gu, and A. H. Sayed

A Generalized Hilbert Matrix Problem and Confluent
Chebyshev-Vandermonde Systems
Hao Lu

Note On "Further Study and Generalization of Kahan's Matrix Extension
Dao-Sheng Zheng


From: Deborah Poulson <>
Date: Wed, 14 Jan 98 15:35:43 -0500
Subject: Contents, SIAM Journal on Scientific Computing

SIAM Journal on Scientific Computing
Volume 19, Number 2, MARCH 1998

Solution of Two-Dimensional Riemann Problem of Gas Dynamics by
Positive Schemes
Peter D. Lax and Xu-Dong Liu

ADI Methods for Cubic Spline Collocation Discretizations of Elliptic
P. Tsompanopoulou and E. Vavalis

Geometric Separators for Finite-Element Meshes
Gary L. Miller, Shang-Hua Teng, William Thurston, and Stephen A.

A 3D Rectangular Mixed Finite Element Method to Solve the Stationary
Semiconductor Equations
Guido E. Sartoris

Enhanced Cell-Centered Finite Differences for Elliptic Equations on
General Geometry
Todd Arbogast, Clint N. Dawson, Philip T. Keenan, Mary F. Wheeler, and
Ivan Yotov

Stochastic Integration Rules for Infinite Regions
Alan Genz and John Monahan

Exploiting Invariants in the Numerical Solution of Multipoint Boundary
Value Problems for DAEs
Volker H. Schulz, Hans Georg Bock, and Marc C. Steinbach

Multilevel Evaluation of Integral Transforms with Asymptotically
Smooth Kernels
A. Brandt and C. H. Venner

The Number of Coarse-Grid Iterations Every Cycle for the Two-Grid
Lars Ferm

Multigrid Algorithms for Nonconforming and Mixed Methods for
Nonsymmetric and Indefinite Problems
Zhangxin Chen, Do Y. Kwak, and Yoon J. Yon

Multigrid Method for Ill-Conditioned Symmetric Toeplitz Systems
Raymond H. Chan, Qian-Shun Chang, and Hai-Wei Sun

An Ineration for Indefinite Systems and Its Application to the
Navier-Stokes Equations
Gene H. Golub and Andres J. Wathen

An Optimal Preconditioner for a Class of Saddle Point Problems with a
Penalty Term
Axel Klawonn

Using a Massively Parallel Processor to Solve Large Sparse Linear
Programs by an Interior-Point Method
Joseph Czyzyk, Robert Fourer, and Sanjay Mehrotra

Statistical Condition Estimation for Linear Systems
C. S. Kenney, A. J. Laub, and M. S. Reese

Data-Parallel Sparse LU Factorization
John M. Conroy, Steven G. Kratzer, Robert F. Lucas, and Aaron E.

Sparse Approximate-Inverse Preconditioners Using Norm-Minimization
Nicholas I. M. Gould and Jennifer A. Scott

Using Level 3 BLAS in Rotation-Based Algorithms
Bruno Lang

Provably Good Partitioning and Load Balancing Algorithms for Parallel
Adaptive N-Body Simulation
Shang-Hua Teng

Accelerated Inexact Newton Schemes for Large Systems of Nonlinear
Diederik R. Fokkema, Gerard L. G. Sleijpen, and Henk A. Van der Vorst

Computing Maximum Likelihood Estimators of Convex Density Functions
T. Terlaky and J.-Ph. Vial

Timely Communication

Error Analysis of Krylov Methods in a Nutshell
Marlis Hochbruck and Christian Lubich


From: Lisa Dougherty <>
Date: Thu, 15 Jan 98 08:54:21 -0500
Subject: Contents, SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics
Volume 11, Number 1, FEBRUARY 1998

The Ring Loading Problem
Alexander Schrijver, Paul Seymour, and Peter Winkler

Interference-Minimizing Colorings of Regular Graphs
P. C. Fishburn, J. H. Kim, J. C. Lagarias, and P. E. Wright

Combinatorial Properties and Constructions of
Traceability Schemes and Frameproof Codes
D. R. Stinson and R. Wei

The Number of Independent Sets in a Grid Graph
Neil J. Calkin and Herbert S. Wilf

A Randomness-Rounds Tradeoff in Private Computation
Eyal Kushilevitz and Adi Rosen

Sometimes Travelling Is Easy: The Master Tour Problem
Vladimir G. Deineko, Rudiger Rudolf, and Gerhard J. Woeginger

Analysis of Algorithms for Listing Equivalence Classes of
k-ary Strings
Andrzej Proskurowski, Frank Ruskey, and Malcolm Smith

An Ordering on the Even Discrete Torus
Oliver Riordan

Competition Graphs of Hamiltonian Digraphs
David R. Guichard

The Number of Intersection Points Made by the Diagonals of
a Regular Polygon
Bjorn Poonen and Michael Rubinstein

Geometry and Diameter Bounds of Directed Cayley Graphs of
Abelian Groups
Charles M. Fiduccia, Rodney W. Forcade, and Jennifer S. Zito

Rankings of Graphs
Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen,
Ton Kloks, Dieter Kratsch, Haiko Muller, and Zsolt Tuza


End of NA Digest