NA Digest Sunday, November 1, 1992 Volume 92 : Issue 41

Today's Editor:

Cleve Moler
The MathWorks, Inc.

Submissions for NA Digest:

Mail to

Information about NA-NET:

Mail to


From: Bert Pohl <>
Date: Tue, 27 Oct 92 10:10:11 EST
Subject: Change of Address for Bert Pohl

My new address is:

Bert Pohl
Department of Mathematics
University of Queensland
St. Lucia
Brisbane, 4072

Tel.: ++61 - 7 - 365 3487
Fax.: ++61 - 7 - 870 2272


From: Atul Chhabra <>
Date: Sat, 31 Oct 92 14:47:05 EST
Subject: Direct Poisson Solvers / Rapid Elliptic Solvers

In 1975, Bank and Rose [1] proposed an O(N*N) method for solving Poisson or
Helmholtz equations on a two dimensional square grid. They showed that this
mathod was unstable with respect to round off errors and therefore it could
not be used in practice. The well known Poisson sovlers that work are the
O(N log N) cyclic reduction method of Buneman [2], the O(N log N) cyclic
reduction or Fourier analysis methods of Buzbee, Golub, and Nielson [3] and
the O(N log log N) Fourier analysis and cylic reduction method of Swarztrauber
[4]. These methods are also applicable to separable second order linear
elliptic partial differential equations.

I have two questions:

1. Has more work been done since 1975 on the O(N*N) direct Poisson solver [1]
to make it numerically stable? Or have other O(N*N) methods been proposed

2. Concus and Golub [5], in 1973, proposed using the direct solvers for
iteratively solving nonseparable elliptic equations. However, in order to
converge rapidly, this method required the coefficient to vary smoothly
and to satisfy

coeff_max - coeff_min
----------------------------------------------- << 1.
2 * PoissonEigenval_min + coeff_max + coeff_min

I have an application where coeff_max is of the order of 10^4, coeff_min
is zero, and the minimum eigenvalue of the discrete Poisson operator is
close to zero. Therefore, using the Concus and Golub method [5] results in
very very slow convergence.

Has this kind of problem been addressed by direct solvers? Has there been
any recent work on solving nonseparable elliptic equations using direct
Poisson/Helmholtz solvers? Of course, I know of multigrid methods,
conjugate gradient methods, and Chebyshev acceleration? I am looking for
direct or almost direct methods for nonseparable equations.

[1] R.E. Bank and D.J. Rose, "An O(N*N) method for solving constant coefficient
boundary value problems in two dimensions," SIAM Journal of Numerical
Analysis, 12:529-540, 1975.

[2] O. Buneman, "A compact non-iterative poisson solver," Technical Report 294,
Stanford University Institute for Plasma Research, Stanford, CA, 1969.

[3] B.L. Buzbee, G.H. Golub, and C.W. Nielson, "On direct methods for solving
Poission's equation," SIAM Journal of Numerical Analysis, 7(4):627-656,

[4] P.A. Swarztrauber, "The methods of cyclic reduction, Fourier analysis and
the FACR algorithm for the discrete solution of Poisson's equation on a
rectangle," SIAM Review, 19(3):490-501, 1977.

[5] P. Concus and G.H. Golub, "Use of fast direct methods for the efficient
numerical solution of nonseparable elliptic equations," SIAM Journal of
Numerical Analysis, 10(6):1103-1120, 1973.

Thanks in advance for any help.


Atul K. Chhabra Phone: (914)644-2786
Member of Technical Staff Fax: (914)644-2404
NYNEX Science & Technology Internet:
500 Westchester Avenue
White Plains, NY 10604


From: Dan Sorensen <>
Date: Mon, 26 Oct 92 13:15:22 CST
Subject: New Computational Science & Engineering Degree at Rice University


Rice University announces the Computational Science And Engineering (CSE)
Graduate Degree Program, designed to provide interdisciplinary research and
education in the area of scientific computing.

The intent of the master's degree program is to graduate professional
experts in scientific computing who will be able to work as technical
specialists within an interdisciplinary research team. Degree candidates
will be offered: training in the use of state-of-the-art numerical methods,
high performance computer architectures, and software development tools for
parallel and vector computers; application of these techniques to at least
one scientific or engineering area; a curriculum consisting of topics from
computer science, computational and applied mathematics, and a selected
application area; and hands-on experience with leading-edge parallel

The Ph.D. degree program offers the same interdisciplinary approach as the
master's degree program but with greater specialization. An original thesis,
in addition to the completion of either an advanced schedule of
courses or a computational project in an application area other than
computer science or computational and applied mathematics, are required for
the Ph.D. in this program.

Biochemistry and Cell Biology (expected)
Chemical Engineering
Computational and Applied Mathematics
Computer Science
Electrical and Computer Engineering
Statistics (expected)

Students must be admitted into one of the academic departments listed above
to be considered for participation in the CSE graduate degree program. The
student participates as a graduate student within that department in every
way except that the curriculum and examination requirements will be set by
guidelines for the CSE graduate degree program. All applications must be
received by January 15th.

First-year funding for Ph.D. candidates is provided by fellowships from the
Center for Research on Parallel Computation, a National Science Foundation
Science and Technology Center at Rice. After the first year, support for
Ph.D. students is provided by research fellowships.

Students participating in the CSE graduate degree program will have access
to several advanced computational resources: Intel Paragon, Delta, and
iPSC/860; Cray machines; and Thinking Machines CM-2 and CM-5.

To request information and application materials for the new CSE Graduate
Degree Program, please contact:

Theresa Chatman
Computational Science and Engineering Graduate Degree Program
Center for Research on Parallel Computation
Rice University
6100 South Main Street
Houston, TX 77005
Theresa Chatman

Phone: 713-285-5180

Electronic mail:


From: E.C. Gartland <>
Date: Mon, 26 Oct 92 11:33:33 EST
Subject: Computational Problems in Liquid Crystals

A Conference on
November 13-14, 1992
Kent State University
Kent, Ohio

Preliminary Schedule

Friday (Nov 13):

AM: Invited Talks - Dan Frenkel (Inst. for Atomic & Mol. Phys.)
Mitch Luskin (Univ. of Minnesota)
Solicited Talks - Robert Cohen (Univ. of North Carolina)
Robert Guenette (Univ. of Laval)
Tim Sluckin (Univ. of Southampton)
PM: Invited Talks - Frank Leslie (Univ. of Strathclyde)
Richard Varga (Kent State Univ.)
Solicited Talks - Carme Calderer (Penn State Univ.)
Epifanio Virga (Univ. di Pisa)
Axel Kilian (Tech. Univ. Berlin)
Saturday (Nov 14):

AM: Invited Talks - Ole Mouritsen (Tech. Univ. of Denmark)
David Kinderlehrer (Carnegie Mellon Univ.)
Solicited Talks - Claudio Zannoni (Univ. di Bologna)
Phil Taylor (Case Western Reserve Univ.)
Chuck Gartland (Kent State Univ.)
PM: Invited Talks - Greg Ryskin (Northwestern Univ.)
Maurice Kleman (Univ. de Paris-Sud)
Solicited Talks - Slobodan Zumer (Univ. of Ljubljana)
Dwight Berreman (AT&T Bell Labs (retired))
Tom Lubensky (Univ. of Pennsylvania)
Birger Bergersen (Univ. of British Columbia)

The Conference is interdisciplinary in nature, bringing together
computational and theoretical physicists, chemists and engineers, and
applied and numerical analysts, to explore some of the many challenging
computational problems in the area of liquid crystals. In addition to
the talks above, there will be a session of contributed posters.

The Conference is being co-sponsored by the Department of Mathematics
and Computer Science and the Liquid Crystal Institute at Kent State
University. Sources of primary support are the Institute for
Mathematics and its Applications (IMA) at the University of Minnesota
and the NSF Science and Technology Center for ``Advanced Liquid
Crystalline Optical Materials'' (ALCOM), a consortium of Kent State
University, Case Western Reserve Univerity, and the University of Akron.
The Conference is being organized in cooperation with the Society for
Industrial and Applied Mathematics (SIAM).

For further information, contact the Conference Secretary:

Brenda L. Buck Phone: 216-672-2654
Liquid Crystal Institute FAX: 216-672-2796
Kent State University e-mail:
Kent, OH 44242

Organizing Committee

E.C. Gartland, Jr (Co-chair) M.B. Luskin P. Palffy-Muhoray (Co-chair)
Dept of Math & CS School of Math Liq Cryst Inst & Dept of Phys
Kent State Univ Univ of Minn Kent State Univ


From: Francois Cellier <>
Date: Mon, 26 Oct 1992 13:34:19 -0700 (MST)
Subject: ICBGM'93: International Conference on Bond Graph Modeling

Part of the 1993 Western Simulation Multiconference
Sponsored by the SCS
January 18-20, 1993
Hyatt Regency, La Jolla, California, USA

The International Conference on Bond Graph Modeling (ICBGM) is a new forum for
knowledge exchange among Bond Graphers and for promoting the Bond Graph
methodology to the modeling world through its Proceedings. We are very proud
of the enthusiastic response received to our Call for Papers. We are happy
that a large majority of today's Bond Graph experts have agreed to support this
conference either by serving on its Program Committee or by sending
contributions. We are particularly proud that the spiritual father of the
Bond Graph methodology, Hank Paynter, agreed to speak to us, and also to write
a preface to the Proceedings of this conference.

Bond Graphs, as a methodology for modeling lumped continuous-time physical
processes, have been around for more than 30 years. Bond Graphs describe the
power flow through a physical system. They preserve the topological structure
of the processes they describe, i.e., they are object-oriented, yet allow to
quickly examine the computational structure as well through the introduction of
so-called causality strokes.

Bond graphs, as an educational tool for teaching students how to make good
models, have been very successful. As teachers, we have been able to observe
that students grasp the concepts behind Bond Graph modeling quickly, and they
love it. Students who use Bond Graphs as a tool for designing their models are
much more likely to come up with correct answers than students who don't.

Bond graphs, as a research tool in the principles of modeling, have been
fashionable all along. Hundreds, maybe thousands, of archival research papers
on various aspects of Bond Graph modeling have been published over the years.
Bond Graphs have been understood not only as a tool for deriving simulation
models, but also as a means to concisely and unambiguously describe physical
phenomena. In our view, Bond Graph modelers are simply better physicists.

Bond graphs, as an engineering tool for modeling real-life physical processes
were however slow in coming. Most of the early Bond Graph software tools did
not allow to model nonlinear phenomena at all, others did not lend themselves
to a convenient description of such phenomena; and yet, our real world is
utterly nonlinear indeed. Few of the software tools available did allow the
user to describe subsystems in a modular fashion, enabling him to hierarchically
structure his models; and yet, it is quite unrealistic to assume that engineers
will be willing to describe complex processes monolithically at a single
modeling layer. Such models would be extremely difficult to debug and maintain.
However, Bond Graph software has meanwhile matured to a state where complex
engineering processes can indeed be described elegantly and efficiently as
demonstrated by many of the application-oriented papers presented at this

If you wish to received an E_Mail copy of the Preliminary Program of this
conference, please, send a request via E_Mail to:

or: na.Cellier@na-net.ORNL.Gov

General Chairman Program Chairman

Jose J. Granda Francois E. Cellier
Department of Mechanical Engineering Dept. of Electr. and Computer Engr.
California State University, Sacramento University of Arizona
Sacramento, Calif. 95819 Tucson, Ariz. 85721

Phone: (916) 278-5711 Phone: (602) 621-6192
FAX: (916) 278-5949 FAX: (602) 621-8076
EMail: GrandaJJ@ECS.CSUS.Edu EMail: Cellier@ECE.Arizona.Edu

International Program Committee

Jan Broenink Tech. University of Twente Netherlands
Peter Breedveld Tech. University of Twente Netherlands
Marisol Delgado Universidad Simon Bolivar, Caracas Venezuela
Hallvard Engja Norwegian Institute of Technology, Trondheim Norway
Peter Gawthrop University of Glasgow, Scottland United Kingdom
Dean Karnopp University of California, Davis U.S.A.
Lennart Ljung Linkoping University Sweden
Francis Lorenz Lorenz Consulting, Liege Belgium
Donald Margolis University of California, Davis U.S.A.
Fernando Mejia Universidad Nacional de Colombia, Bogota Colombia
Henry Paynter formerly at M.I.T. U.S.A.
Jean Thoma Thoma Consulting, Zug Switzerland
Tong Zhou California State University, Sacramento U.S.A.


From: Bill Hager <>
Date: Thu, 29 Oct 92 16:34:08 EST
Subject: Conference on Large Scale Optimization

Conference on Large Scale Optimization
University of Florida, Gainesville, Florida
February 15-17, 1993

The conference will bring together researchers who are
working on many different aspects of large scale optimiza-
tion: algorithms, applications and software. Currently, the
list of invited speakers includes the following people:

Dimitri Bertsekas John Birge Christian Bischof Andrew Conn
Jann Cook Thomas Coleman George Dantzig Renato DeLeone
Joseph Dunn Chris Floudas Anders Forsgren Masao Fukushima
David Gay Philip Gill Jean-Louis Goffin Donald Goldfarb
Masao Iri Narendra Karmarkar C.T. Kelley Hiroshi Konno
Leon Lasdon S. Lawphongpanich P. O. Lindberg Robert Meyer
Jorge More' Walter Murray Anna Nagurney George Nemhauser
James Orlin Michael Overton P. Panagiotopoulos Jong-Shi Pang
Roman Polyak Aubrey Poore Mauricio Rescende K. Ramakrishnan
J. B. Rosen Ekkehard Sachs Michael Saunders Robert Schnabel
David Shanno Richard Tapia Andre Tits Philippe Toint
Yinyu Ye Stavros Zenios

Although only invited talks will be presented at the confer-
ence, everyone is welcome to attend the conference. More-
over, it is anticipated that some funds will be available
for the support of graduate students, and to support the
participation of women, minorities, and persons with disa-
bilities; please contact the organizers. To obtain the
latest information concerning the conference, send an email
message to "" and in the body of the email
message, put the phrase "send meeting". The contact people
for the conference are Bill Hager (fax: 904-392-6254), Don
Hearn (email:, and Panos Pardalos (phone:


From: D. F. Griffiths <>
Date: Sat, 31 Oct 92 12:26:50 GMT
Subject: Dundee Biennial Conference 1993


29th June - 2nd July 1993

The A R Mitchell lecture will this year be given by

M J D Powell (Cambridge).

Other Principal Speakers will include

J W Barrett I S Duff C M Elliott
P Gill D J Higham N K Nichols
P Townsend J M Sanz-Serna M N Spijker
G W Stewart A M Stuart R Temam
M J Todd

A limited number of submitted papers will be presented. Full details
of submission dates, conference fees, etc. will be available towards
the end of 1992 and may be obtained by writing to either
Dr D F Griffiths or Professor G A Watson:
The Organizing Secretaries
Biennial Conference on Numerical Analysis
Department of Mathematics and Computer Science
The University
Dundee, DD1 4HN
Scotland, UK
Tel: (0382) 23181 ext 4467/4474
FAX: (0382) 201 604


David F Griffiths Tel: (0382) 23181 EXT 4467
Dept of Maths & Computer Science FAX: (0382) 201 604
The University
Dundee DD1 4HN email:
Scotland, UK


From: Richard Sincovec <sincovec@sirius.EPM.ORNL.GOV>
Date: Fri, 30 Oct 92 14:37:27 -0500
Subject: Householder Fellowship at ORNL

Mathematical Sciences Section
Oak Ridge National Laboratory

The Mathematical Sciences Section of Oak Ridge National Laboratory invites
outstanding candidates to apply for the 1993 Alston S. Householder
Fellowship in Scientific Computing.

Alston S. Householder was the organizer and founding Director of the
Mathematics Division (precursor of the current Mathematical Sciences
Section) at Oak Ridge National Laboratory (ORNL). In recognition of the
seminal research contributions of Dr. Householder to the fields of
numerical analysis and scientific computing, a distinguished postdoctoral
fellowship program has been established at ORNL and named in his honor.
The Householder Fellowship is supported by the Applied Mathematical
Sciences Subprogram of the U.S. Department of Energy.

The purposes of the Householder Fellowship are to promote innovative
research in scientific computing on advanced computer architectures and to
facilitate technology transfer from the laboratory research environment to
industry and academia through advanced training of new computational
scientists. The Householder Fellowship is normally for a term of two
years. Benefits of the Fellowship include a competitive salary, fringe
benefits, travel opportunities, access to state-of-the-art computational
facilities (including both parallel architectures and high-performance
personal workstations), and collaborative research opportunities in a very
active research program in advanced scientific computing. Competition for
the appointment is open to U.S. citizens and permanent residents.
Applicants should have completed a doctoral degree in computer science,
mathematics, or statistics within three years prior to the appointment and
have a strong background and research interest in large-scale scientific

ORNL's Mathematical Sciences Section has research programs in
Computational Mathematics, Computer Performance Characterization, Applied
Analysis, Global Climate Modeling, and Computational Statistics. The
precise research emphasis of the Householder Fellow would necessarily
depend to a great degree on the research interests of the selected Fellow.
Areas of particular interest at ORNL, and in which applicants would be
especially encouraged, include: computational linear algebra,
parallel algorithms for partial differential equations including fluid
flow through porous media, tools for the development and analysis of
parallel algorithms, computational statistics, scientific visualization,
and "grand challenges" in computational science.

Applicants should send a resume, statement of research goals, and three
letters of recommendation to Carl Ludemann, PhD Employment, Oak Ridge
National Laboratory, P.O. Box 2008, Oak Ridge, TN 37831-6216, marked
"ATTN: Householder Fellowship." The deadline for applying is
January 13, 1993. Finalists will be invited to visit ORNL in
February 1993, and the selection committee's decision on the winning
candidate will be announced in March 1993. The fellowship will
commence in 1993.

For further information, contact Richard F. Sincovec by phone at
615-574-3125 or by electronic mail at


From: John Grove <>
Date: Mon, 26 Oct 92 07:56:15 EST
Subject: Postdoctoral Position at SUNY Stony Brook

Department of Applied Mathematics and Statistics

The Department of Applied Mathematics and Statistics at the University
at Stony Brook expects to have one or more postdoctoral positions
available for the academic year of 1993/94. We are seeking qualified
applicants in any of the following fields; computational fluid
dynamics, parallel computing, hyperbolic conservation laws, flows in
elastic and plastic media, or flows in porous media. We are
particularly interested in candidates who will pursue manufacturing and
industrial applications of these areas.

A vita, a brief description of research interests, and at least three
letters of recommendation and any supporting materials should be sent to

Prof. James Glimm
Chair, Department of Applied Mathematics and Statistics
University at Stony Brook
Stony Brook, NY 11794-3600.

Applications in the form of plain TeX or LaTeX files can be sent via
electronic mail to

Hiring decisions are expected in January or February of 1993, although
all applications received before the position is filled will be
considered. The University at Stony Brook is an Equal Opportunity
Employer. We especially solicit applications by women and minorities.


From: Wei Pai Tang <>
Date: Mon, 26 Oct 1992 10:15:37 -0400
Subject: Position at University of Waterloo

Department of Computer Science

The University of Waterloo invites applications for a one-year
definite term lecturing position in Computer Science with possi-
bility of renewal. The Department is looking for candidates in
numerical analysis who will participate in teaching courses
related to scientific computation at the intermediate and
advanced undergraduate level. Evidence of teaching skills is
required, and a Ph.D. in Computer Science or equivalent is an
asset. Candidates can expect to be appointed at the rank of lec-
turer or assistant professor, depending on qualifications.
Effective date of appointment: January or May 1993.

The Department of Computer Science comprises over 40 full-time
faculty members engaged in research and teaching covering a broad
spectrum. The Department and its research laboratories are
housed in the new 300,000 sq. ft. William G. Davis Computer
Research Centre. The Department is a key participant in ITRC:
Information Technology Research Centre (a Centre of Excellence
funded by the government of the Province of Ontario) that sup-
ports basic and applied research in information technology.

Applications should include a curriculum vitae and the names of
three references and should be directed to the chair: Professor
Frank Tompa, Department of Computer Science, University of
Waterloo, Waterloo, Ontario, Canada N2L 3G1;

In accordance with Canadian Immigration requirements, this adver-
tisement is directed to Canadian Citizens and Permanent
Residents. The University of Waterloo encourages applications
from qualified women and men, members of visible minorities,
native peoples, and persons with disabilities.

This appointment is subject to the availability of funds.

October 1992


From: Ian Christie <U0ACB@WVNVM.WVNET.EDU>
Date: Wednesday, 28 Oct 1992 15:17:52 EST
Subject: Chairperson Position at West Virginia

Department of Mathematics
West Virginia University

Applications and nominations are invited for the position of
Chairperson. The position requires a Ph.D. in mathematics or its equivalent,
administrative experience, and research credentials sufficient to justify a
tenured appointment at the Associate Professor or Professor level. It is
expected that the successful applicant will continue his/her research
program while serving as chairperson. The Department is searching for a
person with a desire for administrative responsibility who will continue to
strengthen the Department's research program while maintaining a substantial
commitment to quality teaching.

The Department consists of 32 faculty, 5 support staff, and 25 graduate
teaching assistants, and offers the B.A., M.S., and a newly established
Ph.D. degree. The Department is located in newly refurbished facilities that
include its own departmental research library, a mathematics learning center
with CAI capacity, and fully integrated computer offices, classrooms, and
computer laboratories. Faculty have direct access to the University's
mainframe computer facilities and to Internet. The Department has faculty
active in various areas of pure and applied mathematics and in mathematics
education. West Virginia University has an enrollment of 22,500. Morgantown
is a culturally diverse college community with a population of about 40,000,
and is located on the Monongahela River, 70 miles south of Pittsburgh and
200 miles west of Washington D.C.

Applicants should provide a vita and the names of five references.
Applications and inquiries should be sent to Dr. Bernard Cooper, Benedum
Professor of Physics, Chair of the Search Committee, 201 Woodburn Hall, West
Virginia University, PO BOX 6286, MORGANTOWN WV 26506-6286. Screening of
applicants will begin on January 15, 1993 and will continue until a
successful candidate is chosen.

WVU is an equal opportunity/affirmative action/Title IX employer.


From: SIAM <>
Date: Mon, 26 Oct 92 15:29:04 EST
Subject: Contents: SIAM Computing

SIAM Journal on Computing
February 1993 Volume 22, Number 1

Implicit O(1) Probe Search
Amos Fiat and Moni Naor

Maintaining the 3-Edg

On the Boundedness of Constant-Time-Maintainable Database
Hctor J. Hern ndez and Ke Wang

Tight Worst-Case Performance Bounds for Next-k-Fit Bin
Weizhen Mao

A Note on the Complexity of a Simple Transportation
Greg N. Frederickson

A Lower Bound on the Size of Shellsort Sorting Networks
Robert Cypher

A Note on Poset Geometries
Joel Friedman

An O(n) Algorithm for Determining the Subregion-Tree
Representation of a Rectangular Dissection
Sukhamay Kundu

Tally Versions of the Savitch and Immerman--Szelepcsenyi
Theorems for Sublogarithmic Space
Viliam Geffert

NV-Sequentiality: A Decidable Condition for Call-by-Need
Computations in Term-Rewriting Systems
Michio Oyamaguchi

ASPACE(o(log log n)) Is Regular
Kazuo Iwama

The Complexity of Malign Measures
Peter Bro Miltersen

Scan-First Search and Sparse Certificates: An Improved
Parallel Algorithm for k-Vertex Connectivity
Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna

Decomposing Finite-Valued Transducers and Deciding Their
Andreas Weber

One More Occurrence of Variables Makes Satisfiability
Jump from Trivial to NP-Complete
Jan Kratochv!l, Petr Savicky, and Zsolt Tuza

Rounds in Communication Complexity Revisited
Noam Nisan and Avi Wigderson


End of NA Digest