NA Digest Sunday, June 11, 1989 Volume 89 : Issue 23
Today's Editor: Cleve Moler
Today's Topics:
-------------------------------------------------------
From: Cleve Moler and Gene Golub <na@na-net.stanford.edu>
Date: Sun Jun 11 22:55:09 PDT 1989
Subject: NA Net Digest Policy
We would like to cut back on really long pieces in the
NA Net Digest. Many of these long pieces are detailed
programs and registration forms for forthcoming meetings.
After today's Digest, we will limit such announcements to
brief summaries (a few hundred words). The program itself
can then be sent to anyone who requests it, either from
the originator, or perhaps from netlib. (How about it,
Jack and Eric?)
-- Cleve and Gene
------------------------------
From: Chris Kuszmaul <armada!fyodor@decwrl.dec.com>
Date: 5 Jun 89 21:29:59 GMT
Subject: Sparse Convolution
I am trying to find a fast algorithm for evaluating
the discrete convolution of two functions.
There is a complication that makes the obvious answer (FFT)
incomplete (maybe):
Let g and h be the functions to be convolved. I know
g is 'usually' zero, so I have a list of ordered
pairs of locations, and values defining g such as:
((0 1) (100 2) (200 1) (1000 1))
Let the length of the list here be N. (in the e.g. N = 4)
Let the maximum value in the domain of g where g is not zero be M.
(in the e.g. M = 1000)
In reality, N may be about 1000, and M may be about 100,000.
h is NOT sparse, but it is anti-symmetric.
So g*h is not sparse. However,
I only want to evaluate g*h at the N points where g is not 0.
Now, I could use the FFT to evaluate g*h at M points in time
MlogM, but I have a hunch there is a way to either tweak
the FFT (some kind of symbolic FFT maybe???) or some
way to tweak g (if g was uniformly distributed then the
problem goes away) either using a conformal mapping (???!)
or by using the fact that h is anti-symmetric so I can
rearrainge g by splitting selected data points and halving their
maginitudes.
Thanks.
Chris Kuszmaul
MassPar Inc., Santa Clara, CA
------------------------------
From: Bill Baringer <pasteur!navajo.berkeley.edu!bilbo@ucbvax.Berkeley.EDU>
Date: 6 Jun 89 04:53:15 GMT
Subject: Dynamical Systems Simulation Package Available
I thought I'd pass this on, in hopes that it would be of general interest.
-- Bill
INSITE is a collection of easy-to-use programs for the simulation and
characterization of dynamical systems, with an emphasis on chaotic systems.
INSITE runs on the X11 graphics package under UNIX and on the MetaGraphics
graphics package under PC-DOS. There is a short write-up on it in the
August 1987 issue of the Proceedings of the IEEE. It contains graphically
based, interactive programs that:
calculate and plot trajectories and orbits,
calculate and plot bifurcation diagrams of continuous- or
discrete-time systems,
calculate Lyapunov exponents (via simulation),
calculate correlation dimension of attractors (from a data file
obtained via experiment or simulation),
calculate and plot one-dimensional invariant manifolds of a
(Poincare) map,
calculate and plot periodic solution of continuous- or
discrete-time systems, and
calculate and plot phase portraits of two-dimensional
continuous-time systems.
The software is now available for distribution. The complete source code
is included. Ordering information on the software can be obtained by writing
INSITE
P.O. Box 9662
Berkeley, CA, 94709-9662
------------------------------
From: Peter Alfeld <ALFELD@SCIENCE.UTAH.EDU>
Date: Tue 6 Jun 89 07:48:10-MDT
Subject: Computer Operations Position at University of Utah
The Center for Scientific Computing of the Department of
Mathematics, University of Utah, invites applications for the position
of Manager of Computer Operations. The successful candidate will have
at least a Bachelor's degree (or equivalent) in Computer Science or a
related field, and experience in the administration of complex
computer networks. Knowledge of the Unix operating system and
networking hardware and software are essential. Knowledge of the VMS
and TOPS 20 operating systems are desirable. Specific skills required
include: planning and organizing, keeping of accurate records, and
getting tasks completed in a timely and efficient manner. Also
desired is experience in the keeping of financial accounts.
The Systems Manager is responsible for the smooth administration of
the departmental computing resources (a network comprising one Vax
8600, one Dec-20, and numerous Sun workstations and Macintoshes) and
the rendering of computing services to the faculty and students of the
Department of Mathematics. The incumbent reports to the Director of
Computing (a faculty member in the Mathematics Department) and
oversees a staff of one software specialist, one systems programmer,
one secretary, and several part time operators. An immediate task
will be the detailed planning (in cooperation with the Director of
Computing and other Mathematics faculty) of the phaseout of the
DEC-20, and its replacement with suitable hardware and software.
The position is available immediately. Salary will be based on
qualifications and experience, and is negotiable. Benefits are
competitive.
Inquiries should be directed to Peter Alfeld, Department of
Mathematics, University of Utah, Salt Lake City, Utah 84112,
801-581-6842 or 801-581-6851, alfeld@science.utah.edu.
The University of Utah and the Department of Mathematics are
Affirmative Action/Equal Opportunity Employers.
------------------------------
From: Jim Davis <OP.DAVIS@SCIENCE.UTAH.EDU>
Date: Tue 6 Jun 89 09:47:27-MDT
Subject: Supercomputing Positions at University of Utah
UNIVERSITY OF UTAH SUPERCOMPUTING INSTITUTE
The University of Utah Supercomputing Institute invites applications for
three staff positions in the areas of (i) graphics, visualization and
animation, (ii) scientific computing, and (iii) development and
implementation of parallel algorithms. Preference will be given to
applicants with a Ph.D. in Applied Mathematics or Computer Science, but
applicants with a degree in other areas of science or engineering will
be considered.
These positions are in a newly-created supercomputing institute at the
University of Utah. The objectives of the institute are to pursue
research and development in the above areas and to provide services in
these areas to faculty and students at the University via consulting,
seminars, workshops and courses. Staff members will be expected to
pursue research in their area of expertise and adjunct appointments in
academic departments will be considered.
To apply send a curriculum vita and make arrangements to have three
letters of recommendation sent to Professor Hans G. Othmer, Director of
Academic Supercomputing, Department of Mathematics, University of Utah,
Salt Lake City, UT 84112. Tel:(801) 581-3901; Email:
othmer@science.utah.edu. The University of Utah is an equal opportunity
/affirmative action employer.
------------------------------
From: Brian Coomes <coomes%csfsa.cs.umn.edu@umn-cs.cs.umn.edu>
Date: Wed, 7 Jun 89 18:06:57 cdt
To: Global Error Bound from ODE Solver
Does anyone know of an ODE solver that gives a bound on global error?
Here is what I would like to do: Given an initial value problem
dy/dt = V(y), y(a)=x
on an interval [a,b], I want to be able to specify a ball containing
y(b). Please send replies (or reasons why I won't be able to do
this) to
coomes%csfsa.cs.umn.edu@umn-cs.cs.umn.edu
Brian Coomes
------------------------------
From: Margareta Heilmann <HEILMANN%DHDIBM1.BITNET@Forsythe.Stanford.EDU>
Date: Fri, 09 Jun 89 10:07:59 ESZ
Subject: Multivariate Polynomial Interpolation
I would like to get some hints for literature about multivariate
interpolation by polynomials.
Especially I am interested in conditions for (unique) solutions of
interpolation problems.
Thank you very much for your help in advance.
Margareta Heilmann
------------------------------
From: Kamal Abdali <kabdali@nsf.gov>
Date: Wed, 07 Jun 89 14:59:55 -0400
Subject: ISSAC 89 Program
ACM - SIGSAM
1989 International Symposium on Symbolic and Algebraic Computation
ISSAC-89
Portland, Oregon July 17-19, 1989
Conference Chair
Kamal Abdali (NSF)
Program Chair
Gaston Gonnet (Univ of Waterloo)
Local Arrangements Chair
Bruce Jensen (Portland State Univ)
Exhibition Chair
Dennis Arnon (Xerox PARC)
Tutorials Chair
Keith Geddes (Univ of Waterloo)
Publicity Chair
Benton Leong (Univ of Waterloo)
Program Committee
Manuel Bronstein (IBM)
Bob Caviness (University of Delaware)
Patrizia Gianni (University of Pisa)
Gaston Gonnet (University of Waterloo)
Anthony Hearn (RAND Corp.)
Tetsuo Ida (University of Tsukuba)
Daniel Lazard (Universite Paris)
Teo Mora (Universita di Genova)
Franz Winkler (Johannes Kepler Universitaet)
The 1989 International Symposium on Symbolic and Algebraic Computation
will be held in Portland, Oregon on July 17-19, 1989. The conference
will feature original research contributions, tutorials, demonstra-
tions of hardware and software and invited lectures. The conference
includes six technical paper sessions, four tutorial sessions, and an
exhibition of hardware and software systems.
Program
Sunday 7:45 AM - 8:00 PM
Mt. St. Helens Bus Tour
Sunday 9:00 AM - 5:00 PM
Tutorials
Tutorial 1: 9:00 AM - 12:00
Handling Algebraic Numbers in Computer Algebra
D. Duval (Universite de Limoges)
Tutorial 2: 2:00 PM - 5:00 PM
Parallel Algebraic Algorithm Design
E. Kaltofen (Rensselaer Polytechnic Institute)
Tutorial 3: 9:00 AM - 12:00
Systems Tutorial I
Reduce, Macsyma, Mathematica, Macauley
Tutorial 4: 2:00 PM - 5:00 PM
Systems Tutorial II
DOE Macsyma, Maple, Scratchpad, Derive
Sunday 7:00 PM - 10:00 PM
Conference Reception
Monday 8:00 - 12:00
Session Chair: B. Caviness (Univ of Delaware)
A Survey of Formal Solutions of Differential Equations
Michael Singer (North Carolina State Univ)
On the Reduction of Linear Systems of Difference Equations
M.A. Barkatou (INPG)
A Differential-Equations Approach to Functional Equivalence
J. Shackell (Univ of Kent at Canterbury)
Series Solutions of Algebraic and Differential Equations: A Com-
parison of Linear and Quadratic Algebraic Convergence
R.J. Fateman (Univ of California)
A Factorization Algorithm for Linear Ordinary Differential Equations
F. Schwarz (GMD)
An Improved Las Vegas Primality Test
E. Kaltofen (RPI), T. Valente (RPI) & N. Yui (Queen's Univ)
On Some Computations with Dense Structured Matrices
V. Pan (City Univ of New York)
Inversibility of Rational Mappings and Structural Identifiability in
Automatics
F. Ollivier (Ecole Polytechnique)
Knuth-Bendix Procedure and Buchberger Algorithm - A Synthesis
F. Winkler (Johannes Kepler Universitaet)
Monday 1:00 - 5:40
Session Chair: G. Gonnet (Univ of Waterloo)
Symbolic Algebra in Mathematics: Dreams and Reality
Andrew M. Odlyzko (AT&T Bell Labs)
Lookup Tables, Recurrences and Complexity
R.J. Fateman (Univ of California)
Labeled Trees and the Efficient Computations of Derivations
R. Grossman & R.G. Larson (Univ of Illinois at Chicago)
Absolute Factorization of Bivariate Polynomials
C. Bajaj (Purdue), J. Canny (UC Berkeley), T. Garrity (Rice) & J.
Warren (Rice)
A New Modular Algorithm for Computation of Algebraic Number Polynomial
GCDs
T.J. Smedley (Univ of Waterloo)
A Fast, Reliable Algorithm for Calculating Pade-Hermite Forms
S. Cabay (Univ of Alberta) & G. Labahn (Univ of Waterloo)
Computing With Algebraic Series
M.E. Alonso, Teo Mora & M. Raimondo (Universita di Genova)
Recovery of Algebraic Numbers from Their p-adic Approximations
J. Abbott (Rensselaer Polytechnic Institute)
Solving Systems of Non-Linear Equations Faster
J. Canny (UC Berkeley), E. Kaltofen (RPI) & L. Yagati (RPI)
Some Results on the Defect
R. Bradford (Univ of Bath)
Sturm-Habicht Sequence
L. Gonzalez, H. Lombardi, T. Recio & M-F. Roy (Universidad de Canta-
bria)
Monday 8:00 PM
Sigsam Business Meeting
ISSAC Business Meeting
Tuesday 8:00 - 12:00
Session Chair: A.C. Hearn (RAND Corp.)
Designing a Software Environment for Studying Algebraic
Structures
John Cannon (Univ of Sydney)
MINION: An Environment to Organize Mathematical Problem Solving
J.M. Purtilo (Univ of Maryland)
How Can REDUCE be Run in Parallel?
J. Fitch (Univ of Bath)
A Code Optimization Package for REDUCE
J.A. van Hulzen (Twente), B.J.A. Hulshof (Philips), B.L. Gates (RAND)
& M.C. van Heerwaarden (Twente)
IRENA - An Integrated Symbolic and Numerical Computation Environment
M.C. Dewar (Univ of Bath)
A MACSYMA Package for the Generation and Manipulation of Chebyshev
Series
T.H. Einwohner (Lawrence Livermore) & R.J. Fateman (UC Berkeley)
GENCRAY: A Portable Code Generator for Cray Fortran
S. Weerawarana & P.S. Wang (Kent State Univ)
Experimenting the Groebner Basis Algorithm With the AlPI System
C. Traverso (Universita di Pisa)
A Program Generator for Efficient Evaluation
B.R. Miller (NIST)
Tuesday 1:00 - 4:20
Session Chair: D. Lazard (Universite Paris)
Computing with Algebraic Numbers - An Example of Dynamic
Evaluation
Dominique Duval (Universite de Limoges)
Simplification of Real Elementary Functions
M. Bronstein (IBM)
On the Risch-Norman Algorithm and Its Implementation in MAPLE
K.O. Geddes & L.Y. Stefanus (Univ of Waterloo)
Unleashing Computer Algebra on the Mathematics Curriculum
J.S. Devitt (Univ of Saskatchewan)
Symbolic Summation with Generating Functions
R.A. Ravenscroft (Brown) & E.A. Lamagna (Univ of Rhode Island)
Automatic Reasoning About Numerical Stability of Rational Expressions
B.W. Char (Univ of Tennessee)
Computing the Normal Forms of Matrices Depending on Parameters
G. Chen (INPG)
Tuesday 5:30 - 10:00
Conference Banquet
Scenic Bus Tour of Portland
Conference Banquet
Symbolic Computation: Directions for Future Research
A.C. Hearn (RAND Corp.), Moderator
Wednesday 8:00 - 12:00
Session Chair: M. Bronstein (IBM)
Computer Algebra - the Method of Averaging and Elliptic
Functions
Richard Rand (Cornell Univ)
On the Castelnuovo Regularity for Curves
M. Giusti (Ecole Polytechnique)
Careful Algebraic Translations of Geometry Theorems
B. Kutzler (Johannes Kepler Univ)
Quantifier Elimination and the Sign Variation Method for Real Root
Isolation
G.E. Collins & J.R. Johnson (The Ohio State Univ)
On the Computer Solution of Symmetric Homogeneous Triangle Inequali-
ties
S. Rabinowitz
Dense Representation of Affine Coordinate Rings of Curves with One
Point at Infinity
S.C. Porter (Boise State Univ)
A Parallel Implementation of the Cylindrical Algebraic Decomposition
Algorithm
B.D. Saunders (Delaware), H.R. Lee (Delaware) & S.K. Abdali (NSF)
Massively Parallel Symbolic Manipulations
A. Deprit (NIST) & E. Deprit (US Naval Research Lab)
Parallel Algorithms for Hermite Normal Form of an Integer Matrix
F. Siebert-Roch (INPG-CNRS)
Wednesday 1:00 - 5:00
Session Chair: T. Mora (Universita di Genova)
Decomposition of Polynomial Equation Systems by Groebner
Type Methods
Herbert Melenk (Konrad-Zuse-Zentrum fuer Informationstechnik)
Using Rewriting Techniques to Solve the Generalized Word Problem in
Polycyclic Groups
J. Avenhaus & D. Wissmann (Universitaet Kaiserslautern)
A Method for Enumerating Cosets of a Group Presented by a Canonical
System
N. Kuhn & K. Madlener (Universitaet Kaiserslautern)
Reduction of Group Constructions to Point Stabilizers
G. Cooperman (Northeastern), L. Finkelstein (Northeastern) & E. Luks
(Oregon)
Strong Normalizability for the Combined System of the Pure Typed
Lambda Calculus and an Arbitrary Convergent Term Rewrite System
M. Okada (Concordia Univ)
A Note on Theorem Proving Strategies for Resolution Counterparts of
Non-Classical Logics
P. O'Hearn (Queen's Univ) & Z. Stachniak (York Univ)
Employing Path Dissolution To Shorten Tableaux Proofs
N.V. Murray (SUNY Albany) & E. Rosenthal (Univ of New Haven)
Constrained Equational Reasoning
C. Kirchner & H. Kirchner (LORIA)
Resolvantes et Fonctions Symetriques
A. Valibouze (Universite Paris)
General Information
Location All technical sessions, exhibits, and tutorials will held
at the Portland Hilton in downtown Portland.
Transportation The Portland International Airport is served by most
major airlines. The Portland Hilton provides a limo service to and
from the airport. In addition, the RAZ bus provides transportation
between the airport and major Portland hotels for $5 each way.
Climate Portland's weather is mild. Rain, if any, is likely to be
light to intermittent. The average daytime high is 79 degrees and the
average nighttime low is 56 degrees.
Locale The Coastal Range to the west and the snow capped Cascades
to the east, the majestic Columbia River Gorge and the serene Wil-
lamette River, recollections of a pioneer heritage, fountains,
forests, sculpture, carousels, galleries, and roses - every view of
Portland is the right one. You'll find the ISSAC-89 conference is
right in the city - within walking distance of fine restaurants,
shops, and theaters - but it is also on the riverbank as well as near
parks, esplanades, and jogging paths.
Conference Events In addition to the technical program, tutorials,
and exhibits, there will be a reception on Sunday evening, business
meetings on Monday evening, a banquet at the World Forestry Center
and a post-prandial panel discussion on Tuesday evening. Also, there
will be a bus excursion to Mt. St. Helens Volcanic National Park
(site of the 1980 volcanic eruption) and the Columbia Gorge scenic
area on Sunday. The all-day excursion includes a box lunch. The cost
of the tour is $23.50 and is contingent upon receiving a sufficient
number of pre-paid reservations.
Registration Fee The regular registration fee includes the recep-
tion on Sunday evening, the banquet on Tuesday evening, all coffee
breaks, and a copy of the proceedings. Student registration includes
everything except the banquet.
Student Accomodations There are a limited number of rooms at the
Portland State University available to accomodate students during the
conference. These accomodations are within 20 minutes walking dis-
tance to the conference hotel and local buses run between the hotel
and the university frequently. The charge for a room is $18 per night
and includes breakfast.
Advance Registration
Please use this form or a facsimile to preregister. Advance registra-
tion forms must be received by June 28 to qualify for the early
registration rates. Please mail registration forms with a check drawn
on a U. S. bank or with an international money order in U.S. funds
payable to ACM ISSAC 89 to:
ACM ISSAC 89 Conference
c/o Dr. Bruce Jensen
Department of Mathematics
Portland State University
P.O. Box 751
Portland, Oregon 97201
Registration form
ACM ISSAC 89
Name (last, first) _________________________________________
Affiliation ________________________________________________
Address ____________________________________________________
City _______________ State _________________________________
Zip/Postal Code _____ Country ______________________________
Phone number _______________________________________________
Electronic mail address ____________________________________
Please circle appropriate fees.
Pre-reg. Late reg.
ACM and Sigsam member $200 $250
ACM or Sigsam member $210 $260
Non-member $220 $270
Student $80 $80
Additional banquet tickets ___ x @$40ea
Mount St. Helens Excursion ___ x @$23.50ea
Student housing nights: ___ @$18/night
Tutorial Sessions (member) ___ x @$40ea
Tutorial Sessions (non-member) ___ x @$50ea
Circle Tutorial Numbers: 1 2 3 4
Total enclosed: $ _____
Hotel Registration
A block of rooms has been reserved for conference participants. If
you wish to reserve one of these rooms at the conference rates,
please complete this form and return it by mail or fax (503-220-2565)
by June 18:
Portland Hilton
921 SW Sixth Avenue
Portland, Oregon 97204
Attention: Reservations
If you call the hotel (503-226-1611), please mention that you are
attending the ACM Sigsam ISSAC 89 conference to qualify for the rates
below.
Accommodations should be confirmed for at least the first night with
either a check or a major credit card (see list of acceptable credit
cards below).
The conference rate at the Portland Hilton is $72 per night for a room
with either single or double occupancy. Triple and quadruple occu-
pancy may be added for $10 per extra person. The conference rate
will be honored for up to three days before the start of the confer-
ence and up to three days after the conference (subject to room avai-
lability).
Hotel Reservation Form
ACM Sigsam ISSAC 89 Conference
July 17-19, 1989
Name (last, first)
Affiliation
Address
City
Zip/Postal Code
Country
Phone number
Arrival Date
Departure Date
Number of persons
Deposit enclosed
Credit card number
Expiration date
Signature
Credit cards accepted for confirmation of accomodations include AC
Enroute, Air Canada, Air Plus, American Express, BankAmericard, Carte
Blanc, Choice, Diners Club, Discover, Eurocard, Hilton Charge, Inter-
Bank, JAL Credit, JCB International, MasterCard, Optima, Preferential,
Shell Signature and Visa.
------------------------------
End of NA Digest
**************************
-------