Subject: NA Digest, V. 93, # 32
NA Digest Sunday, August 29, 1993 Volume 93 : Issue 32
Today's Editor:
Cleve Moler
The MathWorks, Inc.
moler@mathworks.com
Today's Topics:
SIAM Classics Series
Kang Feng
Multivariate Numerical Integration in MATLAB?
Permanent Calculation
Solver for Parabolic/Elliptic Systems.
SISTA Publications Available via FTP
Report on Claremont Modeling Workshops
Structure of Conferences
SIAG/LA meetings
California Matrix Theory Meeting
First International Meeting on Vector and Parallel Processing
Two New Books
Contents: Applied Numerical Mathematics
Contents: SIAM Scientific and Statistical 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: Gene Golub
Date: Sat, 28 Aug 93 11:55:11 PDT
Subject: SIAM Classics Series
I will be editing the SIAM Classics Series; Richard Brualdi, Avner Friedman,
Herb Keller, Ingram Olkin and Bob O'Malley will also be associated with the
series. If you have any suggstions of books that are out of print and should
be reprinted, please let me know.
Gene Golub
------------------------------
From: Meiqing Zhang
Date: Wed, 25 Aug 93 21:13:25 -0500
Subject: Kang Feng
Those who work on finite element methods or symplectic algorithms will
be sad to hear that Kang Feng, one of the pioneers in these fields,
passed away on August 17 at the age of 72. His memory will remain with us.
Meiqing Zhang
Dept. of Computer Science
University of Illinois at Urbana-Champaign
e-mail Zhang@lisboa.ks.uiuc.edu
------------------------------
From: David Brainard
Date: Mon, 23 Aug 93 08:28:13 PDT
Subject: Multivariate Numerical Integration in MATLAB?
Does anyone know of a package for performing multivariate
numerical integration in MATLAB? I am open-minded about
algorithms, although my own application is for problems
where the dimension is between 10 and 20.
I will compile responses sent to:
brainard@psych.ucsb.edu
and return them to the digest.
David Brainard
Department of Psychology
UC Santa Barbara
Santa Barbara, CA 93106
brainard@psych.ucsb.edu
(805) 893-2011
------------------------------
From: Xianzhou (Joe) Zhu
Date: Mon, 23 Aug 1993 17:14:36 -0700 (PDT)
Subject: Permanent Calculation
Hi,
I would like some help in evaluating the permanent of NxN matrice.
The following is a typical 7x7 matrix I am interested in
1 9.96651e-31 0.693521 8.39639e-36 6.03125e-24 5.45151e-31 1.47348e-37
9.96651e-31 1 1.3468e-31 0.000317621 5.04988e-25 0.0527272 5.16714e-05
0.693521 1.3468e-31 1 7.27441e-36 6.31672e-23 3.42605e-31 5.7238e-38
8.39639e-36 0.000317621 7.27441e-36 1 2.23242e-14 4.59726e-06 0.411012
6.03125e-24 5.04988e-25 6.31672e-23 2.23242e-14 1 8.18067e-28 2.03174e-14
5.45151e-31 0.0527272 3.42605e-31 4.59726e-06 8.18067e-28 1 3.80986e-08
1.47348e-37 5.16714e-05 5.7238e-38 0.411012 2.03174e-14 3.80986e-08 1
The diagonal matrix elements are all 1, the off-diagonal maxtrix elements
are in the range of 0-1, but are mostly very small.
The definition of the permanent is as follows
per(A)=sum A_{1,sigma(1)} A_{2,sigma(2)} ... A_{N,sigma(N)}
where sigma is the permutation and sigma(i) is the ith element in
the permutation. The sum is over all permutations.
Currently I am using the Ryser-Nijenhuis-Wilf algorithm to evaluate the
permanent. It is OK for N<20. For N>20, this method becomes slow.
Probably we can take advantage of the special structure of our matrix
and devise a method for the efficient evaluation of the permanent.
For example, if we can pick out terms in the sum, and pick the largest
one first, then the second largest, ..., the sum should converge very quickly
to the permanent. With an error estimate, we can establish the accuracy
of the calculation as well.
The goal is to evaluate permanent of 1000x1000 matrix of the above
stated properties.
If you have some bright idea or know somebody who have thought about this,
please let me know. Please send your response directly to me because I
do not receive nadigest.
My contact info is as follows:
Joe Zhu
zhu@npl.npl.washington.edu
206-543-4080(office)
206-528-0424(home)
regards
Joe
------------------------------
From: Silvia Veronese
Date: Wed, 25 Aug 1993 11:41:09 -0600
Subject: Solver for Parabolic/Elliptic Systems.
One of the models for the study of the excitation process
in the cardiac tissue leads to the solution of a reaction
diffusion system composed of a nonlinear parabolic equation
and a linear elliptic equation in u and v of the following form:
1) v_ +f(v)-div M(x)grad v = div M(x)grad u +g(x,t)
t
2) div B(x)grad u = -div M(x)grad v
with boundary conditions:
t
n B(x)grad u = 0
t
n M(x)grad v = 0
Investigating the solution of the system we expect a traveling wave-front
solution v(x,t) presenting an upstroke of approximately 1 msec, that is
a step-like function where the "jump" is 1 mm thick and lasts for 1 msec.
The main drawback of the numerical simulation of the RD system is the
large amount of computational time required to achieve a sufficient
accuracy. For example, for a simulation covering 30 ms we need to solve
600-3000 stationary elliptic problems with approx. 50^3-10^6 nodes.
Given the characteristic shape of the solution, it seems that adaptive methods
could be succesfully used for this problem.
I would be very happy to receive any information regarding fast iterative
techniques (and available codes) for the solution of the above problem.
I am interested in particular in highly parallelizable codes, adaptive
techniques and domain decomposition.
Thanks,
Silvia Veronese
Utah Supercomputing Institute
University of Utah
Salt Lake City, UT 84112
e-mail: silvia@osiris.usi.utah.edu
PS. Does anyone know if PLTMG code for the solution of systems is
available somewhere?
------------------------------
From: Geert Schelfhout
Date: Thu, 26 Aug 1993 10:36:48 +0200
Subject: SISTA Publications Available via FTP
The publication list of the research group SISTA is now made available
by anonymous ftp.
SISTA (Signals, Identification, System Theory and Automation) is the Control
and Signal Processing group of the division ESAT (Electronics, Systems,
Automation, Technology) of the department of Electrical Engineering
of the Katholieke Universiteit Leuven, Belgium.
The list can be obtained from gate.esat.kuleuven.ac.be (134.58.56.20).
Please type your email address at the password prompt.
It is stored in a directory pub/SISTA/publications, both in (compressed)
Postscript (publist.ps.Z) and in (compressed) ASCII format (publist.def.Z).
Many recent SISTA publications are available at this ftp site as well.
------------------------------
From: David Cohen
Date: Fri, 27 Aug 93 16:05:00 -0700
Subject: Report on Claremont Modeling Workshops
August 13 to August 21, 1993, Claremont Colleges, Claremont,
California, hosted a two-part workshop centered around the process of
mathematical modeling. Thirty-five graduate students from universities
all across the United States attended the workshop.
The first part of the workshop encompassed the truly hands-on portion of
the week. On the first day six academics and researchers presented talks
to the entire group on the nature of the problems they wished the
participants to model. The presenters included John Collura (NSA),
Chuck Gartland (Kent State), Alistair Fitt (Univ. of Southhampton),
Mark Matthews (MIT), Jerry Purcell (Momentum Data Systems, Newport
Beach, California), and Eric Varley (Lehigh). The topics covered such
varied subjects as twisted nematic cells in liquid crystal displays
(LCD's), plate tectonics, and efficient oil pumping. That afternoon
the workshop participants broke into six subgroups each trying to
develop a model for one of the topics presented earlier.
The participants by and large were placed in groups whose topic was
not closely related to their specialization or focus back at school.
This tactic insured that the groups were considering the problem from
its foundation mathematically rather than worrying about a small
specialized part of the problem.
The groups worked from the initial presentation to develop a working
model. As a specific example of one of the problems posed, one group was
presented a set of data representing the relative displacements of points
at the surface along a certain section of the San Andreas Fault.
The group then modeled motion locally along the fault below the
surface to show where the tectonic plates might be locking or to
calculate how much energy might be building up along the faults.
Their final model gave results that did approximate what one would expect
to be happening based on other knowledge of that fault section.
After five days of work, all the subgroups gave thirty minute
presentations of their models to the rest of the workshop. The models are
now in the process of being collected into a technical report
including all six subgroups' work.
For the last two days, people representing eight different companies
came to present current problems in environmental modeling.
The vast majority of the presentations focused on groundwater modeling
and contamination detection as the preeminent problem today. During
the first afternoon of this part, the participants broke into
working groups based on the morning's talks and discussed the modeling
problems with the presenters themselves. The results of the working
session were reported back briefly to the entire group on the second afternoon.
Ellis Cummerbatch at Claremont organized the entire event. The National
Security Agency sponsored the week's activities. SIAM gave each participant
the choice of up to $75 worth of books from its current publications.
[Comment from Gene Golub:
These meetings seem like an excellent idea. There is a real need for education
of this nature. Congratulations Ellis for organizing such a stimulating
workshop. -- Gene]
------------------------------
From: Robert I McLachlan
Date: Mon, 23 Aug 93 10:57:20 -0600
Subject: Structure of Conferences
I am writing to wholeheartedly agree with the points made by Gene Golub in
the most recent NA-Digest. I expect the Digest will be deluged with similar
letters. I have been to so many bad conferences and a very few good ones
that something really has to be done.
Here is what I would recommend for a special topic conference, e.g. one
on numerical linear algebra, multigrid, or suchlike.
1) The maximum seminar load should be 3 50-minute talks in the morning
(ONE session only) and a maximum of two parallel sessions in the
afternoon. The afternoon talks could be 30 or 50 minutes. The crucial
thing is to get a big audience with everyone alert and involved.
2) One very successful workshop I attended was at the Geometry Center in
Minneapolis. They had a large open area next to the seminar room,
with computers in it, and people would mingle there for hours. Joint
projects started spontaneously and were completed during the workshop!
The crucial factors seemed to be a friendly area (not crowded with
people shouting over their mini croissants), in a place where people
went naturally (often 'research rooms' are out of the way and no one
goes there). The computers helped attract people because they could
check their email and demo their computer graphics programs.
3) In order of preference,
(1) no proceedings to be published except for photocopies of
1-2 page abstracts, handed out _during_ the conference
(2) full, _original_ conference papers published, but in a special
issue of a journal, _not_ in a book which appears after three
years and nobody can ever find ever again
(3) a motley collection of minuscule "survey" papers which are
really a rehash of the author's previous three papers and
have been published five times already
You can guess which one I think is most prevalent today.
In case (2), the papers could be solicited and refereed up to six months
before the conference, i.e. at the time when people first plan to attend.
The the proceedings will appear in a reasonable amount of time after the
conference, with the post-refereed versions submitted immediately after
the conference.
4) Some kind of informal game to get everyone relaxed, e.g. everyone could
contribute $2 to a sweepstakes for the best seminar, to be awarded by
popular vote. Speakers running over time are disqualified.
5) Another thing for organizers to aim at is to have the seminars,
accomodations, and restaurants absolutely as close together as possible.
You have to plan to throw people together or it won't work.
The ultimate would be to have all three in the same building, e.g. at
some country retreat. This would be no more expensive than the usual
system and is what I am going to try for in my next conference.
Robert McLachlan
------------------------------
From: John Lewis
Date: Fri, 27 Aug 93 11:07:54 PDT
Subject: SIAG/LA meetings
In the last na-digest, Gene Golub raised several concerns about the
Third SIAM Conference on Linear Algebra Signals, Systems and Control
and, by implication, SIAM conferences in general.
The LASSC conferences support a primary goal of the SIAM Activity
Group on Linear Algebra (SIAG/LA): to bring together people for whom
linear algebra is a necessity and those for whom linear algebra is a
livelihood. They have been quite successful by bodycount, but also by
the more important measures of relevance and scientific interchange.
Some repetition in material from specialized linear algebra meetings
may be a necessary cost in promoting interchange. These meetings have
been relevant to many of the attendees, as indicated to us by the
large number of positive comments, particularly from our colleagues
outside of linear algebra.
SIAM's meetings are not perfect. They evolve, not always as smoothly
or as speedily as they might, to try to serve their attendees better.
The structure and pace of SIAM meetings has traditionally included a
high degree of parallelism and long working days (SIAM is often
rendered as "Session Is At Midnight"). SIAG/LA will be experimenting
with one alternative at our next major meeting, the 1994 SIAM Applied
Linear Algebra Conference. As we announced here (na-digest, V93,#21):
An article describing the new format in detail appears in the current
SIAG/LA newsletter, and is also available by anonymous ftp from the
machine AE.SIAM.ORG (IP number 192.108.225.1) as PUB/LA-NET/FORMAT.PS
(postscript) or FORMAT.TEXT (plain text). We encourage interested
parties to retrieve this article and comment on it.
This experiment is in response to past comments by many people. Our
experimental format reduces the number of sessions and provides more
focus to the minisymposia. It will proceed at a somewhat slower pace.
It is an experiment. We invite Gene and you to send us ideas and
comments regarding our format. We have already surveyed the SIAG/LA
membership regarding our 1994 format. Full details of these results
will be published in this fall's SIAG/LA newsletter. We hope that our
plan and these responses can add to the discussion of these and other
issues of SIAM meetings.
Change will only occur if we collectively turn our discomfort into
constructive measures and better meetings. SIAG/LA is grateful to
Biswa Datta for doing just that, for having the energy and foresight
to establish and maintain a forum for interaction between linear
algebra and several important areas where it is used. This is one of
the most important functions of the SIAM Activity Group on Linear
Algebra. To this and the other activities of SIAG/LA we always
welcome the contributions of our members.
-- John Lewis, Chairman, SIAG/LA
-- John Gilbert, Program Director, SIAG/LA
------------------------------
From: Jane Day
Date: Tue, 24 Aug 93 10:54:02 +0100
Subject: First International Meeting on Vector and Parallel Processing
LAST ANNOUNCEMENT AND GENERAL INFORMATION
FIRST INTERNATIONAL MEETING ON VECTOR AND PARALLEL PROCESSING
Centro de Informatica "Prof. Correia de Araujo" (CICA)
Faculdade de Engenharia da Universidade do Porto (FEUP)
Porto, Portugal
1993, 29 September - 1 October
ATTENTION: ALTERATION ON THE DEADLINE FOR EARLY REGISTRATION: JULY 31
ABOUT THE MEETING
The Meeting is interdisciplinary in nature, bringing together people from
Science, Engineering and Industry to explore some of the many challenges and
promises of vector and parallel processing. The event aims at disseminating
state-of-the art knowledge on the topic and at providing a forum for
presentation and discussion of basic research and applications in this area.
Industrial applications will be emphasized.
The Meeting is organized by the Computer Center (CICA) of the University of
Porto Engineering Faculty (FEUP) with the support of several other entities.
FORMAT AND TOPICS
The Meeting will feature invited lectures and selected contributed papers.
Topics of the Meeting include architecture concepts, enabling technologies,
operating systems, languages, environments and software tools, software and
hardware performance, numerical algorithms, applications in Science and
Engineering, Industrial systems and applications.
INVITED SPEAKERS
L. Almeida (Convex, Portugal)
M. Dayde (CERFACS-ENSEEIHT, France)
J. Dongarra (Univ. Tennessee, USA)
I. Duff (CERFACS, France)
V. Hernandez (Univ. Polit. Valencia, Spain)
J. Kreatsoulas (Digital Equip. Corp., Brussels)
F. Moura (Univ. Minho, Portugal)
J. Omnes (EEC, Brussels, Belgium)
H. Pina (FCCN, Portugal)
A. Proenca (Univ. Minho, Portugal)
L. Tassakos (Parsytec, Germany)
M. Vitaletti (IBM, Italy)
LOCAL ORGANIZING COMMITTEE
Organizing Committee Chairperson
Ligia M. Ribeiro
Filomena Dias D' Almeida
Joao Falcao e Cunha
Joao Pecas Lopes
Jose Laginha Palma
ADDITIONAL INFORMATION
The full announcements and registration form are available via anonymous ftp
from garfield.fe.up.pt (192.82.214.12) in directory pub/mvpp. Get files
mvpp-anX.ascii and mvpp-rg.ascii (or .ps for Postscript format).
General information can be found in the file mvpp-general.ascii (or .ps).
For more details please write to the Chairman of the Organizing Committee at
the contact address below (email:lmr@fe.up.pt).
CONTACT ADDRESS
FEUP-CICA email: mvpp@fe.up.pt
Meeting VEC/PAR Proc. fax: 351-2-318787
Rua dos Bragas phone: 351-2-2082071
4099 Porto Codex
Portugal
------------------------------
From: P.M. Pardalos
Date: Tue, 24 Aug 93 10:27:57 EDT
Subject: Two New Books
"NETWORK OPTIMIZATION PROBLEMS: ALGORITHMS, APPLICATIONS AND
COMPLEXITY" (Editors: D.-Z. Du and P.M. Pardalos)
World Scientific (1993), 401 pages
ISBN -981-02-1277-1
The field of networks is a lively one, both in terms of theoretical
developments and in terms of the diversity of its
applications. Many problems of design and analysis of large systems
can be formulated and solved using techniques of network theory.
Such problems include communication systems, electrical networks,
computer networks, transportation, scheduling of industrial processes,
facility location, and modeling of combinatorial optimization problems.
Network theory originated many years ago, before our information age.
In the eighteenth century, Euler solved the famous K\"{o}nigsberg Bridge problem
and later Kirchoff initiated the theory of electrical networks.
But it was not until late last century, when Bell invented the telephone,
that many areas of network theory were stimulated.
After the appearance of the first graph theory book (by D. K\"{o}nig)
in 1936, there was tremendous development regarding the theory and
applications of networks. Hitchcock proposed the first complete
algorithm for the transportation problem in 1941, Dantzig proposed
the simplex algorithm for linear programming in 1947, and algorithms
for the minimum spanning tree (Kruskal, 1956) and shortest path
problems were proposed (Prim, 1957). During the same period, the
first commercial computers became available. As it happened with
many other areas of research, the fields of computer science and
networks influenced each other in many respects. In 1962 the book
by Ford and Fulkerson on "Flows in Networks" appeared. With the
development of new data structure techniques and the theory of
computational complexity we entered a new era of algorithmic
developments in networks.
During the second half of our century we saw major
technological developments in all areas of human endeavor and
particularly in information processing. Computer networks
play a vital role in providing fast, reliable, cost-effective
means of communication and information sharing.
In addition, network techniques and computer technology enable
us to solve large-scale network models that appear in applications
such as transportation and telecommunications.
It is clear that the theory and applications of networks is so
great that this book could not give a full account and systematic
treatment of the subject in its entirety. It is our intention to
introduce a number of special topics in order to show the spectrum
of recent research activities and the richness of ideas in the
development of algorithms and the applications of networks.
While we were able to provide only a glimpse of this expansive
field, we felt that this glimpse would allow the reader to sense
the breadth and the depth of the field.
"COMPLEXITY IN NUMERICAL OPTIMIZATION" (Editor: P.M. Pardalos)
World Scientific (1993), 511 pages
ISBN 981-02-1415-4
Computational complexity, originated from the interactions
between computer science and numerical optimization, is one
of the major theories that have revolutionized the approach
to solving optimization problems and to analyzing their
intrinsic difficulty.
The main focus of complexity is the study of whether existing
algorithms are efficient for the solution of problems, and
which problems are likely to be tractable. The quest for
developing efficient algorithms leads also to elegant general
approaches for solving optimization problems, and reveals
surprising connections among problems and their solutions.
This book is a collection of articles on recent complexity
developments in numerical optimization. The topics covered include,
complexity of approximation algorithms, new polynomial time
algorithms for convex quadratic minimization, interior point
algorithms, complexity issues regarding test generation of NP-hard
problems, complexity of scheduling problems, min-max, fractional
combinatorial optimization, fixed point computations, and network
flow problems.
The collection of articles provide a broad spectrum of the
direction in which research is going and help to elucidate the
nature of computational complexity in optimization. The book will
be a valuable source of information to faculty, students and
researchers in numerical optimization and related areas.
------------------------------
From: Serge Petiton
Date: Wed, 25 Aug 93 18:27:58 +0200
Subject: Contents: Applied Numerical Mathematics
APPLIED NUMERICAL MATHEMATICS, North Holland
Vol. 12, Issue 5, 1993
Special Issue
Parallel Scientific Computing: From Solvers to Application
Editors :
Pierre LECA, ONERA and Univ. PARIS VI.
Serge PETITON, ETCA and YALE Univ.
M.T. JONES and M.L. PATRICK
The Lanczos Algorithm for the Generalized
Symmetric Eigenproblem on Shared-Memory Architectures
B. PHILIPPE and B. VITAL
Parallel Implementations for Solving
Generalized Eigenvalue Problems with Symetric Sparse Matrices
E.R. JESSUP
A Case Against a Divide and Conquer Approach to the
Nonsymmetric Eigenvalue Problem
D.C. MARINESCU, J.R. RICE and E.A VAVALIS
Performance of Iterative Methods for Distributed Memory Machines
H. SIMON and L. DAGUM
Experience in Using SIMD and MIMD Parallelism
for Computational Fluid Dynamics
C. FARHAT and M. LESOINE
Mesh Partitioning Algorithms for the
Parallel Solution of Partial Differential Equations
Y.-H. De ROECK
Non-Linear Elasticity Solved by a Domain-Decomposition
Method on a Hypercube
A. de La BOURDONNAYE
Numerical Treatment of Integral Equation on iPSC
------------------------------
From: SIAM
Date: Fri, 27 Aug 93 14:10:18 EST
Subject: Contents: SIAM Scientific and Statistical Computing
TABLE OF CONTENTS
SIAM Scientific and Statistical Computing
Vol. 14-6, November 1993
Block-Cyclic Dense Linear Algebra
Woody Lichtenstein and S. Lennart Johnsson
Computing the Exact Least Median of Squares Estimate and Stability Diagnostics
in Multiple Linear Regression
Arnold J. Stromberg
Numerical and Asymptotic Solutions for Peristaltic Motion of Nonlinear
Viscous Flows with Elastic Free Boundaries
Dalin Tang and Samuel Rankin
A Parallel Algorithm for Reducing Symmetric Banded Matrices to Tridiagonal Form
Bruno Lang
Computing Periodic Gravity Waves on Water by Using Moving Composite
Overlapping Grids
N. Anders Petersson
A Modified Broyden Update with Interpolation
Miguel F. Anjos
Fast Fourier Transforms for Nonequispaced Data
A. Dutt and V. Rokhlin
Numerical Solution of the Riemann Problem for Two-Dimensional Gas Dynamics
Carsten W. Schulz-Rinne, James P. Collins, and Harland M. Glaz
Construction of K-Dimensional Delaunay Triangulations Using Local
Transformations
Barry Joe
A Method for Devising Efficient Multigrid Smoothers for Complicated PDE Systems
Irad Yavneh
Computing the Generalized Singular Value Decomposition
Zhaojun Bai and James W. Demmel
The Use of the L-Curve in the Regularization of Discrete Ill-Posed Problems
Per Christian Hansen and Dianne Prost O'Leary
------------------------------
End of NA Digest
**************************
-------