NA Digest Sunday, August 4, 1991 Volume 91 : Issue 31

Today's Editor: Cleve Moler

Today's Topics:

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: Liz Jessup <jessup@gus.EPM.ORNL.GOV>
Date: Mon, 29 Jul 91 11:15:25 -0400
Subject: Restoration of Address for Liz Jessup

Effective August 5, my address will once again be

Elizabeth R. Jessup
Department of Computer Science
University of Colorado
Boulder, CO 80309-0430

phone: (303)492-0211


From: David Watkins <>
Date: Mon, 29 Jul 91 11:57:18 -0700
Subject: David Watkins is on the Road

For most of the coming academic year (until August, 1992), I will be at
the Applied Mathematics Department, University of Washington, Seattle, WA.
However, in October and November I will visit the Faculty of Mathematics
at the University of Bielefeld, and from about mid February to mid April,
1992 I will be at the IMA in Minneapolis. To contact me by email, use

Best wishes to all of you,
David Watkins


From: Steve Murray <>
Date: 1 Aug 91 16:06:00 PDT
Subject: Problems for Networks with Gains and Losses

I am developing a method to solve network flow problems in which the
arcs have gains and losses. This type of network is often refered to
as a generalized network. I am primarily interested in problems with
general costs (Minimum Cost Flow problems), but would also appreciate
those with costs only on arcs associated with one node (Maximum Flow
problems). Problems of any size would be helpful. I am willing to
adapt to any (readable) input format for the problems. Codes which
generate problems would also be welcome.

Steve Murray

Department of Operations Research
Stanford University
Stanford, CA 94305-4022 USA
email: or
phone: (415) 723-1900 or (415) 961-7125


From: John D. McCalpin <>
Date: Fri, 2 Aug 91 10:42:48 EDT
Subject: Discrete Sine Transforms

Is there any way to calculate Discrete Sine Transforms (DST) using a
fast [ O(NlnN) ] algorithm without packing everything into a standard
complex FFT?

The reason I ask is that I have an application in which I need to
calculate some 10^6 2-D DST's on datasets ranging from 180x140 to
720x560, and the CPU time estimates are getting into the weeks on my
IBM RS/6000-320.

The "standard" way of doing DST's is to pack everything into complex
arrays of 1/4 the size and then doing the standard FFT. This is
inefficient on heavily pipelined machines because the data motion is
more expensive than FP arithmetic on the data. Since the Sine
transform has most of the symmetries of the complex FFT, it seems like
a direct fast algorithm should exist....

John D. McCalpin
Assistant Professor
College of Marine Studies, U. Del. J.MCCALPIN/OMNET


From: Richard P. Beyer, Jr. <>
Date: Fri, 2 Aug 91, 08:25 PDT
Subject: Fractal Dimension Code Request

Does anyone have a program for determining the fractal
dimension of 1-d, 2-d, or 3-d objects they would
send me? Either box counting or fixed mass algorithms
are ok. Any language is ok, preferably C or fortran.

Thanks much,

Dick Beyer Department of Applied Mathematics, FS-20 University of Washington, Seattle, WA 98195
Telephone: (206) 543-5077 FAX: (206) 684-1440


From: Tim Davis <>
Date: Wed, 31 Jul 91 13:01:54 -0400
Subject: Looking for a Research Assistant

I have a research assistant position available in the Computer and
Information Sciences Dept. at the U. of Florida. The research is in a
parallel sparse LU factorization method that uses dense matrix kernels
(the BLAS), yet does not make the symmetric-pattern assumption that the
multifrontal method makes [1]. This work is in collaboration with Iain
Duff and is supported by the NSF.

It's probably too late to apply to UF for this fall, but if I find an
excellent candidate who is interested in this area, I could hold the
position open until the spring 1992 semester.

Tim Davis
301 CSE
Univ. of Florida
Gainesville, FL 32611-2024
phone (904) 392-1481
fax (904) 392-1220

[1] I. S. Duff and J. K. Reid, "The multifrontal solution of
unsymmetric sets of linear equations," SIAM J. Sci. Statis.
Comput., 5 (1984), pp. 633-641.


From: Andy Wathen <>
Date: Fri, 2 Aug 91 17:02:42 PDT
Subject: Report on Dundee Numerical Analysis Conference

The Dundee Biennial Numerical Analysis Conference attracted over 200
Numerical Analysts from 25 countries to the sun and showers of Scotland
for a most stimulating four days in June. This was the 14th such meeting,
and it was appropriately dedicated to Ron Mitchell (who instigated this
regular series) on the occasion of his 70th birthday.
After a high quality symposium for the Leslie Fox Prize the previous
day (see Iain Duff's article: NA-digest vol 91, number 28), the conference
began with the first "A.R. Mitchell Lecture" which was delivered by Gene Golub
of Stanford University. Golub preceded his masterful talk on 'Matrices,
Moments and Quadrature' by expressing his pleasure at once again being
in Dundee, and his gratitude to the organisers for the honour of the
invitation to deliver the highlighted lecture. He acknowledged Ron Mitchell's
contribution to the subject of Numerical Analysis, singling out his
encouragement of young people coming into the subject. His sentiments were
echoed by many speakers throughout the meeting.
Jack Dongarra (University of Tennessee) - at his first Dundee meeting -
talked on a parallel algorithm for the non-symmetric eigenvalue problem and
Jim Demmel (University of California, Berkeley) gave a high speed talk on
design considerations for numerical software (such as LAPACK) for advanced
parallel machines. Ian Sloan (University of New South Wales) introduced the
1/8 3/4 1/8 quadrature formula (c.f. Simpsons 1/6 2/3 1/6) which surprised
the audience until he showed how it came out of the 'Qualocation' (quadrature/
collocation) boundary integral method he had developed. Vidar Thomee (Chalmers
University, Gothenburg) gave a clear and stylish talk on a numerical approach
to hyperbolic integro-differential equations (which showed us that such
problems are not quite so intractable as we had thought!).
The second day featured invited talks on optimisation and partial differ-
ential equations. Mike Powell (University of Cambridge) gave a talk in his usual
enthusiastic and direct style on the complexity of Karmarkar's Algorithm. His
challenge of the audience for a three line proof of one of his lemmas solicited
the required result by the end of the day! Large scale nonlinear programming
and the design and analysis of the methodology for the LANCELOT project were
the subject of Nick Gould's (Rutherford Labs, UK) talk. Ron Mitchell chaired
the Wednesday afternoon session in which Bill Morton (University of Oxford)
and Jens Lorenz (University of New Mexico) spoke on pde's. Unflinched by a
dimensionally spiked introduction, Morton reposted in kind and gave some new
results on upwinded (Petrov-Galerkin) Finite Element (/Volume) methods.
Lorenz gave a varied talk which touched on a large number of mathematical and
numerical fields, but didn't quite reach his announced title on slightly
compressible Navier-Stokes equations. (Some people set themselves high
John Gregory (Brunel University, UK) introduced his talk on subdivision
algorithms for Computer Aided Geometric Design by showing a CAGD saguaro cactus
and an examination question from the year 2001! He then proceded to describe
how to compute the first and answer the second. Hubert Schwetlick (Martin Luther
University, Germany) apologised that his English was not as fast as his German,
but he still left many lagging behind in his generous survey of 'Nonlinear
Parameter Estimation, Models, Criteria and Algorithms'. A packed and expectant
audience were not disapointed by Nick Trefethen's (Cornell University) lecture
on non-normal matrices and pseudospectra. Using theory and many examples, his
message was that we should be interested in pseudo-eigenvalues and not eigen-
values of non-symmetric matrices. This controversial suggestion engendered much
discussion amongst the participants. Trefethen advertised his forthcoming book
on the subject and promised not to talk on pseudo-eigenvalues ever again!
Ake Bjorck (Linkoping University, Sweden) gave a classical numerical analysis
lecture on pivoting and stability in the Augmented System method for
constrained least squares problems.
The conference dinner was the epitomical occasion to sense the friendliness
and conviviality which seem the hallmark of these meetings. Plied with plenty
of wine and appropriately Scottish fare, the after dinner speeches provided
the ideal opportunity for firstly Alistair Watson and principly Jack Lambert
to recount some characteristic moments in the life of their colleague
Ron (Hacker) Mitchell. When we could laugh no more, we headed for the bar.
Most attendees made the excellent Friday morning talk of Jan Verwer (CWI,
Amsterdam) on an adaptive finite difference method for time-dependent pde's.
Chus Sanz-Serna (University of Valladolid, Spain) talked on symplectic
integrators for ode's and showed some results he considered surprisingly
poor when a popular variable step size method rather than constant steps were
used. John Butcher (University of Auckland) suggested that criteria for step
size selection with a symplectic integrator might be rather different than
those which through considerable development have come to be used for standard
integrators. Arieh Iserles (University of Cambridge) gave the final invited
talk of the meeting on functional equations with a variable delay. Unlike most
speakers who had limited their acknowledgement of Ron Mitchell to the first
few moments of their presentations, Iserles devoted his first 8 transparencies
to his paradigm of the search for new results in Numerical Analysis - the
punch line was: Beware, Ron Mitchell has almost certainly been there before
The popularity of the conference had lead the organisers to schedule the
contributed talks in four parallel sessions. One of the rooms was a little small
(perhaps they didn't expect so many attendees), but all were fortunately in the
same building and we only had to dodge the showers in heading for morning coffee
and afternoon tea.
All, of course, was not work. Some headed to the golf links in nearby
St Andrews and others to the Scottish highlands. Swimming, squash, tennis, or
just a walk on the banks of the Tay were other options.
The organisers, Alistair Watson and David Griffiths, were always on hand
and should be rightly pleased in the success of their conference. If there
are any Numerical Analysts out there who have never been to a Dundee conference,
I thoroughly recommend you to try the 15th one - summer 1993.

Andy Wathen (with thanks to David Silvester and Gene Golub)


From: Tom Manteuffel <>
Date: Tue, 30 Jul 91 11:31:59 PDT
Subject: Copper Mountain Conference on Iterative Methods

Copper Mountain Conference
Iterative Methods

April 9 -16, 1992
Copper Mountain, Colorado

Sponsors: DOE and NSF (pending). In Cooperation with
SIAM Special Activity Group on Linear Algebra

Topics of Emphasis:

Nonsymmetric Linear Systems, Equivalent Preconditionings,
Nonlinear Systems, Applications on Advanced Architectures.

Special Features:

Tutorial on Polynomial Iterative Methods April 7-8, Denver Co.
Student Paper Competition
Preliminary Proceedings
Special Journal Issues in SISSC and SIMAX


Abstracts Jan 1, 1992
Student Papers Jan 1, 1992
Papers for Premliminary Proceedings Feb 15, 1992
Early Registration March 1, 1992

Chairmen: Tom Manteufffel and Steve McCormick

Program Committee: Seymour Parter(Chair), Steve Ashby, Howard Elman,
Roland Freund, Ann Greenbaum, Ahmed Sameh, Paul Saylor, David Young,
Homer Walker, Olof Widlund

This is a preliminary announcement. A formal call for papers will be sent to
the SIAM mailing list in September. A more detailed na-net announcement will
also be sent at that time. Inquiries to


From: Sven Hammarling <>
Date: Thu, 1 Aug 91 10:54 GMT
Subject: IMA Conference on Parallel Computation


18th - 20th September, 1991 University of Oxford

Keynote speakers will lead sessions on Software and Hardware Overviews, Tools,
Algorithms, Architectures, and Applications. The emphasis of the conference is
on the application of parallel computing to practical problems. Recent
developments and future directions in parallel computation will be covered.
Panel and poster sessions provide opportunities for discussing ideas generated
by the presentations.

It is intended that the proceedings of this conference will be published by
Oxford University Press after the conference.


Wednesday 18th (9am start)

Architectural Overview of Developments in Parallel Architectures and
Future Prospects - Paul Messina, California Institute of Technology, USA

Architectural Overview for General Purpose Parallel Computers - David May,
INMOS Limited, Bristol, UK

Overview of Available Software and its Performance - Jack Dongarra,
University of Tennessee and Oak Ridge National Laboratory, USA

Development of Numerical Software Libraries for Vector and Parallel Machines -
Sven Hammarling, NAG Limited, Oxford, UK

Algorithmic and Language Issues for General Purpose Parallel Machines -
Bill McColl, Oxford University Computing Laboratory, Oxford, UK

Tools for Parallel Computing - William Jalby, IRISA, University of Rennes,

Optimising Air Pollution Models on Parallel Machines - Jerzy Wasniewski,
Danish Computer Centre for Research and Education

Calculation of Radiative Heat Transfer Through a Grey Gas on Parallel Computer
Architectures - Hussein Al-Bahadili, Queen Mary and Westfield College,
London, UK

Panel Session - The Future of Parallel Computing

Introduction to Poster Session

Thursday 19th

Exploitation of Parallelism in Direct and Semi-direct Solution of
Large Sparse Systems - Iain Duff, Rutherford Appleton Laboratory,
Chilton, UK

Parallel Aspects of Iterative Methods - Henk van der Vorst,
Department of Mathematics, University of Utrecht, The Netherlands

Some Challenges in Parallel Methods for Optimization Problems -
Robert Schnabel, Department of Computer Science, University of Colorado
at Boulder, USA

Large Scale Mathematical Programming on Parallel Computers - Stavros Zenios,
The Wharton School, University of Pennsylvania, US

Evolution of Parallel Algorithms in Dense Linear Algebra - Jeremy Du Croz,
NAG Limited, Oxford, UK

Parallel Iterative Solution of Sparse Linear Systems on a Transputer Network -
Rob Bisseling, Koninklijke/Shell-Laboratorium, Amsterdam, The Netherlands

Concurrent LU Factorization on Workstation Networks - Maria Loredana Sales,
IBM ECSEC, Rome, Italy

Implementation of ICCG Algorithm with Different Orderings on
Local Memory Microprocessors - Pierre Manneback, Faculte' Polytechnique
de Mons, Belgium

Optimisation of a 532-City Symmetric Travelling Salesman Problem with
a Parallel Genetic Algorithm - Terence Fogarty, The Transputer Centre,
Bristol Polytechnic, UK

Prize for the Best Poster

Friday 20th

Scientific Applications and Parallel Computing - Tony Hey,
Department of Electronics and Computer Science, University of Southampton, UK

Lattice Gas Techniques for PDE's - Gary Doolen, Centre for Non-Linear Studies,
Los Alamos National Laboratory, USA

PDE Solution on Highly Parallel Computers - Oliver McBryan,
Department of Computer Science, University of Colorado at Boulder, USA

The Need for Parallelism in Engineering Applications - Michael Brady,
Department of Engineering Science, University of Oxford, UK

12.30 Lunch and finish

17th September, 1991, University of Oxford

Co-sponsored by the Institute of Mathematics and Thames Polytechnic

Objectives of the Workshop:

1) To provide an overview introduction to current practical hardware, software
environments and some basic tools available to assist in parallelisation; 2) To
discuss how numerical algorithms, relevant to the solution of pde's and ode's
can be mapped onto parallel architectures; 3) To descibe some experiences of
mapping large scale numerical codes onto transputer and i860 based systems.

To register, contact:

Miss Pamela Irving, Conference Officer, the IMA, 16, Nelson Street,
Southend-on-Sea, Essex, SS1 1EF.
Tel 0702 354020 Fax: 0702 354111


From: Anne C. Elster <>
Date: Wed, 31 Jul 91 12:01:13 -0400
Subject: CRA Committee on the Status of Women in Computer Science

I have been given permission to distribute the following announcement
from Nancy Leveson. Thought it might be of interest to our community.

Anne C. Elster

CRA Committee on the Status of Women in Computer Science

The CRA's new Committee on the Status of Women had its first meeting on
June 14 where we laid the foundation for an ambitious set of projects on
which to focus during the coming year.

Our overall goal is to maintain and increase the number and status
of women participating in computer science research and education
at all levels. The underlying principle of the committee is to be
action-based, undertaking projects that will result in significant
progress toward eliminating the barriers to full participation by
women in computer science research, including barriers in the
pre-college pipeline, in higher education, and in professional
advancement. Because there is a limit to how much each of us can
personally do, we are focusing on activities that will help others
to get involved. The emphasis will be on providing information about
successful current programs, writing proposals for funding agencies
to set up and support programs, and disseminating information.

The initial membership of the committee is:

Prof. Maria Klawe, University of British Columbia
Prof. Nancy Leveson, University of California, Irvine
Prof. Ruzena Bajcsy, University of Pennsylvania
Dr. Sandra Baylor, IBM Research Lab
Prof. Fran Berman, University of California, San Diego
Prof. Thelma Estrin, UCLA
Dr. Joan Feigenbaum, AT&T Bell Labs
Prof. Michael Fischer, Yale University
Prof. Barbara Grosz, Harvard University
Prof. Marilyn Livingston, Southern Illinois University
Prof. Nancy Lynch, MIT
Dr. Jill Mesirov, Thinking Machines
Prof. Richard Tapia, Rice University
Prof. Elaine Weyuker, NYU

Prof. Weyuker is also a member of a similar committee recently formed
by the ACM and will help to coordinate activities in order to eliminate
duplication of effort.

The rest of this (long) message describes the CRA (Computing Research
Association), the goals of the committee, and our current activities.


The Computing Research Association (CRA) was organized in 1972 as the
Computer Science Board. From 1972 until 1985, the CRB operated as an
informal organization that represented the interests of computer science
researchers. Computer engineering was added in 1985. In June, 1988, the
Computer Research Board was incorporated as a non-profit corporation
and the name was changed to the Computing Research Association.

The CRA is an association of academic departments of Computer Science
and Computer Engineering (currently over 160 universities are members),
industrial laboratories that engage in basic computing research, and
affiliated professional societies with a primary interest in computing
(the ACM is a member).

The mission of the CRA is twofold. First, it helps strengthen research
and education in the computing fields through publications, conferences,
surveys, and other such professional activities. Second, through
various communications programs, it seeks to improve the understanding
by the public and policy makers in government and industry of the important
role in our society played by computing and computing research.


-- To increase the number of women in all types of research and in the
faculty-ranks at universities including both the research universities
and the 4-year teaching colleges.

-- To increase the degree of success experienced by women researchers
as measured, for example, in terms of:

Obtaining appropriate professional positions
Advancing appropriately
Research recognition (awards, lectureships, invited presentations)
Professional respect
Research support
Consulting opportunities
Editorships, program committee memberships and chairships,
advisory boards
Department chairships and other leadership positions.

-- To provide a forum for addressing problems that are of concern
to women (and men) such as career-family conflicts, maternity,
child care, two-body problems, discrimination, and harassment.


The members of the committee will serve as coordinators of the various
activities, but much help will be needed from others (both women and men).
We hope you will be willing to join us in this effort. We have planned
some initial activities with more long-term activities after we get these
started. The addresses of the coordinators are given below; those of you
who would like to participate are encouraged to contact the appropriate

Databases and Lists: Joan Feigenbaum (
This project will collect and disseminate names and other
information about women researchers and graduate students
in CS and CE. It will also monitor the level of participation
by women in various types of professional activity within
computer science research. Examples of such activities include
editorial boards, program committees, membership in prestigious
organizations, positions within professional societies, etc.

Women's Speaker's List: Marilyn Livingston (
This will be coordinated with the database project and will
involve making a list of women speakers and topics on which
they are willing to give invited talks.

Surveys: Nancy Leveson (
In order to plan further activities, it is important to
understand where we are. This project will collect information
from students and faculty in the form of scientific surveys to
learn more about the dimensions of the problems we face.

CRA Newsletter: Fran Berman (
The Editor-in-Chief of the CRA Newsjournal has agreed to have a
column from our committee in each issue. The newsjournal comes
out six times a year. Columns will also be available and
distributed electronically. Periodically, the columns will be
compiled as technical reports to provide a more permanent collection
of information and will be available upon request.

Enhanced Communication: Michael Fischer (
There are several ideas for communication being considered
including a newsletter (perhaps electronic) or a moderated
mailing list that provides more focused dissemination of information
and opinions than systers and is open to everyone.

Mentoring Activities: Maria Klawe (
This is a broad activity encompassing mentoring programs at
all levels from K-12, undergraduate education, graduate education,
and faculty. Our goal is to provide information about successful
programs that already exist and possibly to initiate new programs
such as a Distributed Mentoring Project to match up female
researchers and undergraduates for summer research experiences
at different universities.

Career Booklet: Thelma Estrin (
This project will develop a career booklet to describe careers
in computer science, highlighting successful women.

Student Awards: Jill Mesirov (
The Association of Women in Mathematics has recently established
a very successful award for female undergraduates in mathematics.
The aim of this project is to create analogous awards at the
undergraduate and graduate levels in computer science.

Regional Workshops: Nancy Leveson (
This project will provide information on how to hold a regional
workshop and information about previous successful ones. The
workshops may be research oriented (having women speaking on
their research) or informational (e.g., career opportunities,
how to be a successful graduate student, tips for writing
research funding proposals).

Graduate School workshops: Maria Klawe (
This involves bringing together the top male and female third
year CS students from many different departments and universities
in an area for a weekend to encourage them to attend graduate
school in computer science.

Possible Future Activities:

The committee also discussed a broad range of other activities that might
be considered for the future. These ranged from projects involving
interaction with grades K-12 (preparation of materials for enhancing the
curriculum, review of curriculum materials for gender-bias, teacher education,
summer and after school programs for high school students) to lobbying
companies and foundations to establish chairs for female faculty in computer
science, and educating funding agencies about the special difficulties of
female and minority researchers.

There is much to be done, and whatever we accomplish in the next few months
is only a first step. Still, with everyone's help we can make a difference.
Please join us.

Nancy Leveson


End of NA Digest