krj@na.toronto.edu (Ken Jackson) (11/07/88)
NA Digest Sunday, November 6, 1988 Volume 88 : Issue 44
Today's Editor: Cleve Moler
Today's Topics:
Who is Working on Moving Boundary Problems?
Representation in Terms of Vertices
Stability of Block Toeplitz algorithms
Knuth's Spectral Test
Loss of Significance Register
Optimal Coefficient Lookup
Special Issue of LAA on Image Reconstruction
GAMM Meeting in Karlsruhe
Conference Announcement
IFIP WG 2.5 Conference Scheduled in 1991
-------------------------------------------------------
From: George Wilson <wilson@msr.EPM.ORNL.GOV>
Date: Tue, 1 Nov 88 11:58:55 EST
Subject: Who is Working on Moving Boundary Problems?
I have been asked by a student from Argentina if I knew of anyone in the
Boston, MA, area who does mathematical and computational work on moving
and/or free boundary problems (examples include: porous media problems,
dam problems, contact problems, phase change processes ...). She is
considering a post doc position at MIT working with an engineering faculty
member, but she is interested in also interacting with a more mathematically
oriented person. Are any of you interested in such problems? Do you know
someone in the (greater) Boston area who is? Incidentally, the student is
bright, energetic and speaks excellent English. George Wilson
bitnet: dgw@ornlstc arpanet: wilson@msr.epm.ornl.gov
------------------------------
From: Michael Todd <miketodd@gvax.cs.cornell.edu>
Date: Tue, 1 Nov 88 20:44:35 EST
Subject: Representation in Terms of Vertices
Last month there were a couple of questions about representing a point in a
polyhedron in terms of its vertices. An easy solution solves at most n+1 LP's.
Let the polyhedron be given by Ax >= b, and assume it is bounded (otherwise,
the claimed result is not necessarily true). Let x-bar be the given point,
and assume it satisfies the subsystem Bx >= c with equality. Now solve the
LP of minimizing d.x subject to Ax >= b, Bx = c, to get a vertex x-hat. Find
the point on the line through x-hat and x-bar that is on the boundary of the
face Ax >= b, Bx = c, say x-tilde. Now x-tilde satisfies at least one more
inequality at equality. If it is a vertex, you're done. Otherwise, use an
inductive argument to express x-tilde as a convex combination of vertices,
whence such a representation for x-bar can easily be found.
------------------------------
From: Kletsky Jeff <KLETSKY@GIZMO.SRI.COM>
Date: Thu 3 Nov 88 09:40:18-GMT
Subject: Stability of Block Toeplitz algorithms
We have been using the Block Toeplitz solver TGSLD from the Argonne
Toeplitz Package for some time now on a class of problems containing
128x128 blocks with a block size of 16x16. As our blocks are symmetric
indefinite, the LINPACK routines DSIFA and DSISL have been substituted
for the general routines DGEFA and DGESL.
Recently, we were tasked by an "informed" source to demonstrate
that double precision (VAX Fortran) was sufficient. (He could only
obtain results using quad precision with his own implementation of his
personal pet algorithm.) A quick edit of the Argonne and LINPACK codes
yielded quad precision versions. When we compared results on a case
with moderate conditioning, the solution vectors agreed exactly, save
for the least significant bit in one element.
However, when we examined closely related problem that was poorly
conditioned, although the solution obtained from the double precision
version of the code seemed to be stable and reasonable, the quad precision
version became unstable and yielded unreasonable results, beginning at the
38th block/iteration.
It seems strange to me that improving the numerical precision should
reduce the stability of such an algorithm. Any advice or experience that
others might have on this would be greatly appreciated.
Thanks,
Jeff Kletsky
kletsky@gizmo.sri.com
(415) 859-3948
------------------------------
From: Ajay <dukempd!ajay@cs.duke.edu>
Date: 2 Nov 88 16:30:21 GMT
Subject: Knuth's Spectral Test
I was wondering if anyone had a program (machine readable or
otherwise) in FORTRAN or C for Knuth's Spectral Test, as
described in his book "The Art of Computer Programming"
for testing Random Number Generators. I would be extremely
grateful if someone could help me out. If you can, please
send me e-mail(ajay@dukempd.cs.duke.edu).
Thanks. Ajay
Ajay 1-919-684-8236
Duke University Dept. of Physics ajay@dukempd.uucp
Durham, N.C. 27706 mcnc!duke!dukempd!ajay
------------------------------
From: Paul L Schauble <portal!cup.portal.com!PLS@uunet.uu.net>
Date: 5 Nov 88 03:51:25 GMT
Subject: Loss of Significance Register
Looking through some old paperwork brought back to mind a very old machine I
used to work on. This machine contained an interesting feature. It has a
register that stored the maximum postnormalizing shift performed. This was
updated for each floating point add or subtract. There was an instruction to
store and clear this register.
This seems like a useful feature. You could run a data item through an
algorithm, then store this register and see what precision was actually
maintained through the algorithm.
My question is that I haven't seen this feature or any equivalent in any
modern hardware. Why? Has experience shown it to be useless? Is there some
non-obvious problem with it?
-- Paul Schauble
The Portal System
------------------------------
From: Peter Mikes <under!pom@mordor.s1.gov>
Date: 2 Nov 88 18:38:22 GMT
Subject: Optimal Coefficient Lookup
I would like references and or pointers to any work which is addressing
the question described below as OCL (it already may have a name -
I just made the OCL up, not knowing any better)
It is a mundane problem, but it is quite ubiquious and general -
so it may deserve some name and optimalization study:
The OCL problem: I am writing an PDE solver ( PDE = Partial Differential
Equation) in which the coefficients c depend in various ways on the both
dependent and independent variables. Since these functions tend to be
evaluated over and over again, in the course of the solution and iterations,
they are often pre-calculated and stored in the look-up tables.
That is one extreme solution - taking lot of memory and memory lookup time.
On the other extreme, one may store nothing, but original few coefficients
and recalculate the value of the coefficient each time when it is neeeded.
The optimum seems to be somewhere in between - for example, one can
break the coeficient domain in the regions - and each region aproximate with
sufficient precision the coeficient i = c[i] with some simple function, e.g
with linear or polynomial or rational function with parameters a[...],
e.g.: c[i] = SUM.over.j a[i,j,l] *X[l]^j
where j (the powers ) range from j.min to j.max.
For example, one would have D(T) = a0 + a2 /T for a temperature
dependent Diffusion coeficient - and in this case j.min= -1,j.max=0 , etc
OCL problems asks:
what is the optimal j.min and j.max, given ..
well given all that affects the optimum : relative cost of CPUtime and
memory, memory latency (or latencies), number N of evaluations needed, etc
Extended OCL question deals with the fact that coefficients may
not be exactly known (the often are not) and so we a)only want to have
them aproximated with certain precision and b) we may want to know the
sensitivity of the solution (without repeating the whole solution with
the second set of values). Iin this case we have a range of coefficients
c[i] +/- delta c[i] and want to obtain the 'class of the solutions' which
corresponds to this range. The question again is : what is the numerically
'best' way for representing the functions c[i]( X[l] ), where X represents
physical space and fields (e.g. temperature) variables, so that MINIMAL TIME T
is spent in multiple (=N.times) evaluation of these functions?
The time T(N) represents essentially the CPU time - but we may include
the memory cost by adding a memory latency time T.mem as =cost of retrieving a
precalculated value...
So, in summary, the OCL problem asks:
Find J.min,Jmax (for given N) which will minimize T[J.min, J.max]
needed to aproximate (within epsilon) class of functions c[i](X[l]),
which are continuous (except at small number of the 'phase transition'
boundaries) and otherwise 'reasonable'.
Since N >>>1, the cost of computing the aproximation (preparation
of look-ups) is neglected and does not enter the T. the Time T however
includes the time Tc 'cost of checking whether we are crossing the
region boundary' N-times - to keep the number of regions reasonably small.
Any suggestions, references, pointers will be appreciated
and those e-mailed will be summarized.
Peter O. Mikes
Supercomputer R&D Project, LLNL
pom@under.s1.gov.
------------------------------
From: Hans Schneider <hans@pade.math.wisc.edu>
Date: Wed, 2 Nov 88 19:09:41 cst
Subject: Special Issue of LAA on Image Reconstruction
LINEAR ALGEBRA AND ITS APPLICATIONS
Special Issue on
LINEAR ALGEBRA IN IMAGE RECONSTRUCTION FROM PROJECTIONS
Reminder
This special special issue of LAA is still open for submissions. It
is intended to include papers in linear algebra and optimization
theory which are related to computerized tomography and other image
reconstruction techniques for medical and other purposes. See LAA,
Vol.99 (1988), for the full announcement of the issue and see
Censor's article in SIAM News, Vol.21 (#4, July 1988) pp.14-15, for
a general description of the area. The special editors wish to
encourage you to submit your paper for consideration.
Yair Censor, Haifa, Israel.
(e-mail: rsma403@haifauvm.bitnet).
Gabor T. Herman, Philadelphia, PA, USA
(e-mail: herman@cis.upenn.edu).
Tommy Elfving, Linkoping, Sweden
(e-mail: t-elfving%linnea.liu.se@uunet.uu.net).
------------------------------
From: Goetz Alefeld <AE02%DKAUNI48.BITNET@Forsythe.Stanford.EDU>
Date: 11/03/88 14:00:50 CET
Subject: GAMM Meeting in Karlsruhe
The Gesellschaft fuer Angewandte Mathematik und Mechanik
invites you to attend its Annual Scientific Conference
at Karlsruhe University
from March 28 to March 31, 1989
The regular General Assembly of GAMM will be held on Thursday,
March 30, 1989, at 12:00 a.m. in Gerthsen-Hoersaal.
Plenary Lectures
E.Hoerbst, Siemens AG Muenchen
Methoden des Halbleiterentwurfs - eine Aufgabe fuer den Mathematiker ?
G.C.Hsiao, University of Delaware, Newark
The Coupling of Boundary Element and Finite Element Methods
E.Krause, TH Aachen
Anwendungen numerischer Integrationsverfahren in der Stroemungsmechanik
P.C.Mueller, Universitaet Wuppertal
Parameteridentifikation in mechanischen Systemen
F.Obermeier, Max-Planck-Institut Goettingen
Ausbreitung schwacher Stosswellen - Stossfokussierung und
Stossreflexion
M.L.Overton, Courant Institute New York
Numerical Methods for Inverse and Extremal Eigenvalue Problems
S.B.Savage, McGill University Montreal
Dynamics of Avalanches of Granular Materials
J.W.Schmidt, TU Dresden
Monotonie und Einschliessung in der Numerik
H.R.Schwarz, Universitaet Zu
The Deutsche Gesellschaft fuer Luft und Raumfahrt, and the Gesellschaft
fuer Angewandte Mathematik und Mechanik invite you to the
32nd Ludwig Prandtl Memorial Lecture
Professor Dr.K.Gersten, Universitaet Bochum, will lecture on
"The Significance of Prandtl's Boundary Layer Theory after 85 years"
(in German).
Public Lecture
A public lecture titled
"High Tech = Math Tech"
will be held by Professor Dr.H.Neunzert, Universitaet Kaiserslautern.
This lecture will be given in Gerthsen-Hoersaal.
Additional Information
If you are interested in attending the conference send your mailing
address to the Organizing Committee (na.alefeld@na-net.stanford.edu)
We will send you the registration form and the necessary information.
G. Alefeld, Local Organizer
------------------------------
From: Claudio Canuto <MAT7%ITOPOLI.BITNET@Forsythe.Stanford.EDU>
Date: Sat, 5 Nov 88 11:34 N
Subject: Conference Announcement
I C O S A H O M '8 9
INTERNATIONAL CONFERENCE ON SPECTRAL AND HIGH ORDER METHODS
FOR PARTIAL DIFFERENTIAL EQUATIONS
Villa Olmo (Lake of Como, Italy) - June 26-29, 1989
TOPICS : Theory, algorithms, applications of Spectral Methods, h-p version
of Finite Element Methods, high-order Finite Difference Methods,
etc. Applications to Fluid Mechanics, Continuum Mechanics, Turbulence,
Combustion and Engineering Sciences in general.
The Conference will try to answer the following question: When,
why and to what extent it is preferable to use high-order methods
in the numerical approximation of differential problems.
SCIENTIFIC COMMITTEE : I.Babuska, C.Canuto, M.Deville, D.Gottlieb,
M.Y.Hussaini, Y.Maday, R.Peyret, A.Quarteroni.
LOCAL ORGANIZING COMMITTE : C.Canuto and A.Quarteroni
FORMAT : The Conference will host 45-minute invited lectures (approximately
16), and 20-minute contributed talks (up to about 30).
INVITED LECTURERS : I.Babuska (University of Maryland), M.Deville (Universite'
Catholique de Louvain), D.Gottlieb (Brown University), M.Y.Hussaini
(ICASE), N.F.Knight (NASA Langley), Y.Maday (Universite' de Paris VI), S.A.
Orszag (Princeton University), S.Osher (UCLA), A.Patera (MIT), R.Peyret
(Universite' de Nice), P.Sguazzero (IBM-ECSEC, Rome), B.A.Szabo (Washington
University), E.Tadmor (Tel Aviv University), L.N.Trefethen (MIT), T.A.Zang
(NASA Langley).
PROCEEDINGS : The proceedings of the Conference will be published by Elsevier-
North-Holland (Amsterdam).
LOCATION : The Conference center is in Villa Olmo, a beautiful neo-classic
building of the 18th century facing the lake, located in Como, a restful town
surrounded by green hills and mountains, close to Milan and the Swiss border.
Como is served by the European railways and motorways system, and by nearby
Milan and Zurich airports. Participants will find the right atmosphere of
calm and peacefulness necessary to ensure successful working.
REGISTRATION : People who wish to attend the Conference are requested to send
----------- IMMEDIATELY -------------
an e-mail message at the following address:
mat7@itopoli.bitnet
(att/n : Claudio Canuto)
in which they say whether they will just participate or also submit the
abstract of a contributed talk (see below).
The registration fee is Lit. 250,000 (Italian Lira) if paid before April 30,
1989, or Lit. 300,000 if paid later on. The fee include the scientific material
as well as daily buffet during the Conference. Graduate students will pay
half the fee.
CALL FOR PAPERS : Researchers in the areas of interest of the Conference are
invited to contribute by submitting an abstract of a possible talk. The
abstracts, not exceeding two typewritten pages, shoud be sent as soon as
possible to the following address:
The Organizers of ICOSAHOM'89
IAN-CNR, Corso Carlo Alberto,5
27100 PAVIA, Italy
Tel.: (39)-382-303740
e-Mail: cqa04@ipvian.bitnet
or : mat7@itopoli.bitnet
All the abstracts will be examined by the Scientific Committee by January
31, 1989, and authors will be promptly informed about acceptance of their
talk. Contributed papers, not exceeding 8 typewritten pages, should be sent
to the address above by April 30, 1989, and should conform to the typing
instructions which will accompany the acceptance notices.
------------------------------
From: Bo Einarsson <B_EINARS%SELIUC51.BITNET@Forsythe.Stanford.EDU>
Date: Mon, 31 Oct 88 14:21 N
Subject: IFIP WG 2.5 Conference Scheduled in 1991
INTERNATIONAL FEDERATION FOR INFORMATION PROCESSING
Working Group 2.5 on Numerical Software
Bo Einarsson, 31 October 1988
IFIP TC 2 WORKING CONFERENCE
PROGRAMMING ENVIRONMENTS FOR
HIGH LEVEL SCIENTIFIC PROBLEM SOLVING
First Announcement and Call for Interest
A working conference on Programming Environments for High Level
Scientific Problem Solving, will be arranged 23 - 27 September 1991 in
the Karlsruhe area, Federal Republic of Germany. This will be the
sixth working conference organized by the IFIP Working Group on
Numerical Software (WG 2.5) on behalf of the IFIP Technical Committee
on Programming (TC 2).
This letter is an invitation to you from the preliminary programme
committee to contribute your ideas for this conference. At present we
are very interested in suggestions regarding the scope of the
conference, who to invite to attend and who to invite as speakers, and
on which specific topics, and whether you are interested in
participating.
The conference will concentrate on the construction of high-level
scientific problem solving systems. We are particularly interested in
DESIGN OF USER INTERFACES
Techniques for problem description
Presentation and interpretation of results
Graphical, symbolic and numerical techniques
Multiple modes of I/O (digital, analog, graphical, audio,...)
TECHNIQUES FOR PROBLEM SOLVING
Dynamic selection of algorithms
Use of knowledge bases about problem solving
Integration of numerical, symbolic and graphical methods
User interaction and feedback
Accuracy control and estimation, self-validating systems
IMPLEMENTATION ISSUES
Mixed language programming
Declarative, dynamic and visual programming systems
Integration of libraries and multiple problem solving systems
Tools for integration and portability
Efficient utilization of computing resources, parallel and
distributed architectures, graphics engines
The programme committee will encourage speakers to put together
dynamic (live) talks, using the facilities being described. It is
also intended to complement the presentations with a hardware and
software exhibit, and to produce the proceedings not only as a book
(published by Elsevier) but perhaps also as a video cassette or disk.
The discussions will be recorded in the proceedings. All papers will
be refereed.
Previous working conferences arranged by WG 2.5 have focused on
performance evaluation of numerical software, numerical computation
and programming languages, software for partial differential
equations, problem solving environments, and aspects of computation on
asynchronous parallel processors. The number of participants will be
limited, in order to preserve informality and allow substantial time
for interaction.
The preliminary programme committee consists of Michel Bercovier
(Jerusalem, Israel), Jacques Calmet (Karlsruhe, Germany), Ifay Chang
(IBM, New York), Bo Einarsson (Linkoping, Sweden), Stuart Feldman
(Bell, New Jersey), Brian Ford (NAG, United Kingdom), Lloyd Fosdick
(Boulder, Colorado), Patrick Gaffney (IBM, Norway), Morven Gentleman
(Ottawa, Canada), Elias Houstis (Patras, Greece), Ulrich Kulisch
(Karlsruhe, Germany), John Rice (West Lafayette, Indiana) and Mladen
Vouk (Raleigh, North Carolina).
For further information you are invited to contact the programme
committee co-chairmen
Bo Einarsson, Mathematics Department, University of Linkoping,
S-581 83 Linkoping, SWEDEN.
Telephone +46 13 281432 (office) or 151896 (home).
Electronic mail BOGE@SELIUC51.BITNET or b-einarsson@linnea.liu.se
or na.einarsson@na-net.stanford.edu
Lloyd D. Fosdick, Department of Computer Science, Campus Box 430,
University of Colorado, Boulder, Colorado 80309, USA.
Telephone (303) 492 7507 (office) or 444 1065 (home).
Electronic mail lloyd@boulder.colorado.edu or na.fosdick@na-net.stanford.edu
We hope that you will join us in organizing a stimulating and
enjoyable Working Conference on a challenging and new topic.
Sincerely
Bo Einarsson and Lloyd D Fosdick
..............................................................................
Reply form (return to one of the above, either electronically or by
the conventional mail)
Name:
Mailing Address:
Telephone:
Electronic Mail:
Wishes to participate: Yes/No
Wishes to give a talk: Yes/No
Topic:
Wishes to suggest that the following individuals are contacted (please
give full mailing address and/or electronic mail address):
------------------------------
End of NA Digest
**************************
-------
Reposted by
--
Kenneth R. Jackson, krj@na.toronto.edu (on Internet, CSNet,
Computer Science Dept., ARPAnet, BITNET)
University of Toronto, krj@na.utoronto.ca (CDNnet and other
Toronto, Canada M5S 1A4 X.400 nets (Europe))
(416) 978-7075