krj@na.toronto.edu (Ken Jackson) (09/11/89)
NA Digest Sunday, September 10, 1989 Volume 89 : Issue 35
Today's Editor: Cleve Moler
Today's Topics:
Positions at North Carolina State
Homer Walker Visiting Yale
Examples of Applications of Elementary Mathematics
J. Barkley Rosser
Expert Systems for Numerical Computing
An Open Problem in FFT/Convolution Theory
Golub and Van Loan, Matrix Computations, 2nd Edition
Chair of CS at SUNY Buffalo
A Scaled Matrix Sum Problem
Bart De Moor Returns to Belgium
ICS-90
-------------------------------------------------------
From: Michael Shearer <shearer@matagh.ncsu.edu>
Date: Wed, 6 Sep 89 12:51:31 EDT
Subject: Positions at North Carolina State
DEPARTMENT OF MATHEMATICS
NORTH CAROLINA STATE UNIVERSITY
Applications are invited for one or two tenure track positions in
partial differential equations, beginning July 1, 1990.
Applicants must have a Ph.D. in Mathematics and a strong record or
potential in research and instruction. Research interests should include
applications, and may emphasize
numerical or analytic treatment of pde's. Specialists in hyperbolic equations
are especially encouraged to apply. Send a resume, reprints and three letters
of recommendation to Professor M. Shearer, Search Committee Chairman,
Department of Mathematics, Box 8205, North Carolina State University,
Raleigh, NC 27695-8205. Applications received before December 1st will
receive priority. Later applications should be complete by January 15th, 1990.
N.C. State University is an Affirmative Action and Equal Opportunity
Employer.
------------------------------
From: Homer Walker <walker@math.usu.edu>
Date: Thu, 7 Sep 89 09:09:53 MDT
Subject: Homer Walker Visiting Yale
Dear colleagues:
I will be visiting Computer Science at Yale for the fall semester.
Until the end of December, (regular) mail to me should be send to
the Department of Computer Science, Yale University, New Haven,
CT 06520. E-mail can continue to be sent to na.walker@na-net.stanford.edu
or more directly to walker-homer@cs.yale.edu. My phone number is
(203) 432-1209.
Homer Walker
------------------------------
From: D G Wilson <wilson@MSR.EPM.ORNL.GOV>
Date: Thu, 7 Sep 89 11:14:13 EDT
Subject: Examples of Applications of Elementary Mathematics
The mathematics department at the University of Tennessee is interested
in real live examples of the use of relatively elementary mathematics
(calculus, ordinary differential equations, vectors, elementary linear
algebra, etc.) in science and engineering. They want to use these
examples in the classroom to motivate concepts being taught. They
would appreciate hearing about any examples that you would be willing
to share. The coordinator of this project is Harvey Carruth. His
e-mail address is pa78448@utkvm1.bitnet, and his paper mail address is
Professor J. H. Carruth, Mathematics Department, Ayres Hall, University
of Tennessee, Knoxville, TN, 37996-1300.
------------------------------
From: Lou Rall <rall@math.wisc.edu>
Date: Thu, 7 Sep 89 15:19:11 cdt
Subject: J. Barkley Rosser
Professor J. Barkley Rosser passed away in his sleep on Tuesday, September 5,
1989. He was 81 years old.
------------------------------
From: John R. Rice <jrr@cs.purdue.edu>
Date: Thu, 7 Sep 89 16:45:17 EST
Subject: Expert Systems for Numerical Computing
Announcement and Call for Papers
THE SECOND INTERNATIONAL
CONFERENCE ON EXPERT SYSTEMS FOR NUMERICAL COMPUTING
* April 24-26, 1990 *
Computing About Physical Objects Laboratory
Purdue University
Conference Rationale:
Many diverse groups have started work on projects to aid in the use
of complex software systems, and to guide nonspecialists in the many
choices that have to be made when they want to use computers for
scientific applications. This international conference will bring
together active researchers to exchange ideas, viewpoints, and
techniques.
Topics of Interest: These include, but are not limited to:
* Artificial intelligence and expert systems for numerical computing
(e.g. for the numerical solution of ordinary or partial differential
equations, integral equations, linear systems. . .)
* Knowledge-based systems for scientific applications
* Expert systems for mapping applications to parallel architectures
and to support parallel processing
* Advisory expert systems for general-purpose scientific software
libraries
* Tools and methods for knowledge acquisition about numerical computing
* Sophisticated user interfaces for scientific/engineering systems
* Natural language for scientific interfaces
Submission of Papers:
The conference will include invited and contributed papers.
Authors should submit three copies of an extended abstract (two or three
typewritten pages) by * December 15, 1989 * Contributors will be notified
regarding acceptance by * February 15, 1990 * Deadline for final manuscripts
is * May 1, 1990 * Abstracts and inquiries should be sent to the conference
coordinator:
Dr. Elias Houstis
Department of Computer Sciences, Purdue University
West Lafayette, Indiana 47907
(317) 494-6181, Internet: enh@cs.purdue.edu
Publications:
Preprints consisting of a collection of the abstracts will be available
to the attendees at the conference. The best papers presented will be
published as a special issue of Transactions of Mathematical Software
(TOMS). A conference proceedings book is also planned.
* Organizing Committee *
John Rice, Purdue University, USA, Co-Chairman
Robert Vichnevetsky, Rutgers University, USA, Co-Chairman
Elias Houstis, Purdue University, USA/Greece, Conference Coordinator
------------------------------
From: David Bailey <dbailey@ew11.nas.nasa.gov>
Date: Thu, 7 Sep 89 16:49:30 -0700
Subject: An Open Problem in FFT/Convolution Theory
A great many (perhaps 80%) of the practical applications of FFTs
utilize the FFT to compute linear discrete convolutions, i.e.
c(k) = sum a(i) b(j) (1)
i+j=k
Naive application of the FFT, i.e. by computing
d(k) = F^{-1} [F(a) F(b)], (2)
where F() denotes the results of a FFT, actually produces what is
known as the circular discrete convolution:
d(k) = sum a(i) b(j) (3)
i+j=k
or i+j-n=k
In order to produce the desired linear discrete convolution, computer
programs typically pad the n-long input vectors a and b with n zeroes,
and then perform 2n-long FFTs using the formula (2).
In virtually every other instance where only half of the input data to
a FFT is numerically significant (such as the case of computing the
FFT of purely real data), transformations are known that can reduce
the number of floating-point operations by approximately half. Thus
many in the field believe that it might be possible to compute such
"half-length" FFTs in only half the time of the usual method.
This question can be precisely posed as follows: Is it possible to
compute the 2n-point DFT of an input real sequence the second n of
whose values are zero in significantly fewer than 5 n log2 n
floating-point operations? or double this number for an input complex
sequence? Assume power-of-two length inputs.
Unfortunately, no such algorithm is currently known, as far as I have
been able to determine. Such an algorithm would have enormous impact
on a wide variety of computational applications. Even a negative
answer would be of great significance, not to mention the practical
benefit that persons such as myself could stop losing sleep over the
problem!
It should be noted that even if the above problem is insoluble, the
following weaker form would still be of enormous value: Is it possible
to compute the 2n-point linear discrete convolution of two input
n-long real sequences in significantly fewer than 15 n log2 n
floating-point operations? or double this number for input complex
sequences?
I am aware of a partial solution to this second problem, known as the
"three halves rule". This rule states that by padding the two n-long
input sequences by n/2 zeroes, performing 3n/2-long FFTs in the
convolution formula (2), and ignoring the first n/2 values of the
result, one exactly obtains the center n values of the 2n-long linear
convolution. Since a number of applications only require the center n
values, this rule is of some value. Its computational requirement is
only 75% of the usual method. For many other applications, however,
it is of no help, since either the first n words, or all 2n words of
the linear convolution are required.
If anyone is aware of any results in this area, please let me know.
Solutions with asympototically negligible speedups (such as noting
that the first iteration of the FFT can be done faster on zero data)
are of no interest.
David H. Bailey
NASA Ames Research Center
Mail Stop T045-1
Moffett Field, CA 94035
415-694-4410
dbailey@ew11.nas.nasa.gov
------------------------------
From: Charles Van Loan <cv@gvax.cs.cornell.edu>
Date: Fri, 8 Sep 89 09:01:58 -0400
Subject: Golub and Van Loan, Matrix Computations, 2nd Edition
A list of errata for the recently published ``Matrix Computations,
2nd Edition'' by Gene Golub and myself is available from me at
cv@gvax.cs.cornell.edu
Charlie Van Loan
------------------------------
From: William Rapaport <rapaport@cs.Buffalo.EDU>
Date: Tue, 5 Sep 89 15:30:16 -0400
Subject: Chair of CS at SUNY Buffalo
SUNY AT BUFFALO
Department of Computer Science
Chair
Nominations and applications are invited for the position of Professor
and Chair of the Department of Computer Science, to begin Fall 1990.
We seek a distinguished scientist with a prominent research record
to lead an expanding department. Candidates should be committed to
excellence in research and teaching, be conversant in trends and issues
in computer science, and be willing and able to pursue opportunities for
strengthening the department. Salary will be extremely competitive,
with a flexible research budget.
SUNY-Buffalo is the largest and most comprehensive public univer-
sity in New York and New England. The department currently has 14
tenured/tenure-track faculty (with plans to increase this number) and 3
lecturers. There are approximately 130 Ph.D. and M.S. students and 200
selectively admitted B.A./B.S. majors. The department is scheduled to
move into a new building in Fall 1991. All faculty are actively engaged
in research, principally in: AI, parallel algorithms, software quality,
systems, and theory, and in interdisciplinary research programs in
Advanced Scientific Computing, Cognitive Science, Vision, and with the
National Center for Geographic Information and Analysis.
A complete resume, with names of four references, and a description
of current research should be sent to:
Dr. William J. Rapaport
Computer Science Search Committee
Department of Computer Science
SUNY-Buffalo
Buffalo, NY 14260
(rapaport@cs.buffalo.edu).
Application closing date: 1 January 1990 or until position is filled.
SUNY-Buffalo is an EO/AA employer.
------------------------------
From: Jean-Yves Herve' <herve@cvl.umd.edu>
Date: 9 Sep 89 05:00:34 GMT
Subject: A Scaled Matrix Sum Problem
I am currently blocked by a matrix problem and would appreciate any help
(references would be particulary welcome).
Here is the problem:
We are given n mx3 matrices A A ..... A (the A have no special property)
1 2 3 k
* can I find a 3x1 column matrix V such that
k=n
__ T T
B = \ A * V * V * A is regular?
/__ k k
k=1
(maybe I'd better ask first "does such a vector V exist ?")
* Since my goal is to solve a linear equation B * X = C
can I pick a vector V such that B is most likely to behave well
(no zero or small pivot for example) in a numerical resolution of the
equation ?
* looking back at the last question, I am wondering: should I adopt a
probabilistic approach to the whole problem (do I need to say that B is
obtained by least squares minimisation?) ?
Again, I would much appreciate pointers to the litterature.
have a nice day,
Jean-Yves.
Jean-Yves Herve'
Center for Automation Research herve@cvl.umd.edu
University of Maryland
------------------------------
From: Bart De Moor <kulcs!kulesat!demoor@prlb.philips.be>
Date: Fri, 8 Sep 89 19:14:03 GMT
Subject: Bart De Moor Returns to Belgium
Here is my new address as of September 1, 1989:
Bart De Moor
E(lectronics), S(ystems), A(utomation), T(echnology)
Katholieke Universiteit Leuven
Kardinaal Mercierlaan 94
B-3030 Leuven (Heverlee)
Belgium
tel: 32/16/220931 (int:1715)
fax: 32/16/221855
email: na.demoor@na-net.stanford.edu
or demoor@esat.kuleuven.ac.be
My private address is: Brusselsestraat 128 (5de verd.)
B-3000 Leuven
Belgium
According to Belgian rules, it will take some time before we get
a phone there. Nevertheless, anyone who is in the neighbourhood,
is welcome!
Hilde and I would like to thank everybody, in particular Gene Golub
and Thomas Kailath, for the opportunity they gave us to spend a
wonderful year at Stanford University.
------------------------------
From: Dennis Gannon <gannon@iuvax.cs.indiana.edu>
Date: Sun, 10 Sep 89 22:06:02 -0500
Subject: ICS-90
Call for Papers
ICS-90: 1990 International Conference on Supercomputing
June 11-15, Amsterdam, the Netherlands
( Vrije Universiteit and Centrum voor Wiskunde en Informatica)
Sponsored by ACM SIGARCH
in association with ACM-SIGNUM, AICA, BCS-PPG, CTI, CSRD,
CWI, GI, INRIA, IPSJ, SBMAC and SIAM-SIAGS
Conference Co-Chairmen
Ahmed Sameh, Univ of Illinois, USA
and
Henk van der Vorst, Delft Univ of Technology & CWI, the Netherlands
Program Committee Organizers
J. R. Gurd, Manchester Chairman Europe and Africa
Y. Muraoka, Waseda Chairman Japan and Far East
E. Gallopoulos, Illinois Chairman North and South America
J. R. Sopka, DEC Director
Local Arrangements: H. TeRiele, CWI, Amsterdam, the Netherlands
The fourth International Conference on Supercomputing is now soliciting
papers on significant new research results in the development and use of
supercomputing systems. Contributions should emphasize the novel aspects
of the work being reported and should discuss their implications for future
supercomputing development. Papers are solicited in the following areas:
Architectural Design of Supercomputer Systems:
Heterogeneous use of MIMD, SIMD and Data Flow Systems Designs,
Memory System Organization (Distributed, Shared or Hierarchical),
Bus, Network and Communication Systems,
Instruction Architecture (RISC, CISC, etc.) and Performance Studies.
Software Systems Support for Supercomputing:
Operating Systems Support Features,
Programming Languages, Compilers and Analysis Tools,
Performance Evaluation Tools, Methods and Modeling,
Programming Environments and High Level Problem Solving Systems.
Applications of Supercomputing:
Numerical and Non-Numerical Algorithms,
Structural Mechanics,Computational Fluid Dynamics,
Circuit and Semiconductor Device Simulation,
Computational Chemistry,
Artificial Intelligence and Symbolic Computation,
Graphics and Visualization,
Other new or nontraditional applications.
Conference proceedings, published by Springer-Verlag in 1987 and ACM in
1988 and 1989, will again be published by ACM in 1990.
Authors should send five (5) copies of the manuscript to the program chairman
of their region. The deadline for submissions is January 10, 1990.
Authors will be notified of acceptance by March 10.
Final versions of accepted submissions will be due by 15 April.
The addresses for submissions are:
Europe and Africa: North and South America: Japan and Far East:
Dr. John R. Gurd Dr. E. Gallopoulos Dr. Y. Muraoka
Dept Computer Science CSRD Univ of Illinois Dept. of Elect. Eng.
Univ of Manchester 305 Talbot Laboratory Waseda University
Oxford Road 104 South Wright St 3-4-1 Okubo, Shinjuku-ku
Manchester M13 9PL Urbana, IL61801-2932 Tokyo
UNITED KINGDOM USA JAPAN
********************* ************************** **********************
jgurd@uk.ac.man.cs.ux stratis@uicsrd.csrd.uiuc.edu muraoka@jpnwasoo
------------------------------
End of NA Digest
**************************
-------
Reposted by
Prof. Kenneth R. Jackson, krj@na.toronto.edu (on Internet, CSNet,
Computer Science Dept., ARPAnet, BITNET)
University of Toronto, krj@na.utoronto.ca (on CDNnet and other
Toronto, Ontario, X.400 nets (Europe))
Canada M5S 1A4 ...!{uunet,pyramid,watmath,ubc-cs}!utai!krj
(Phone: 416-978-7075) (on UUCP)
(FAX: 416-978-4765)