Subject: NA Digest, V. 93, # 19 NA Digest Sunday, May 9, 1993 Volume 93 : Issue 19 Today's Editor: Cleve Moler The MathWorks, Inc. moler@mathworks.com Today's Topics: Third Annual Large Dense Linear Algebra Survey C++ vs. FORTRAN Block Tridiagonal Solver Classic Papers in Numerical Analysis SIGOPT/OPT-NET: Call for Membership Parallel Optimization Book Last Call: Dundee 93 A. W. Tucker Prize Announcement IMACS Int'l. Conference on Computational Physics Symposium on High Perfomance Scientific Supercomputing Inverse Problems and Optimal Design in Industry Post Doc Position at the University of Oslo Submissions for NA Digest: Mail to na.digest@na-net.ornl.gov. Information about NA-NET: Mail to na.help@na-net.ornl.gov. ------------------------------------------------------- From: Alan Edelman Date: Sun, 2 May 93 22:53:40 PDT Subject: Third Annual Large Dense Linear Algebra Survey THE THIRD ANNUAL LARGE DENSE LINEAR ALGEBRA SURVEY Once again I wish to ask about the state of the art of large dense linear algebra applications. As usual, large means n > 10,000. I am expecting this year's survey to be low-key in that computing power has not increased significantly since a year ago, and I have not heard of any new applications areas that have opened up in the past year. (Am I misinformed?) Please send me your latest large dense matrix information. Previous surveys may be found in Survey #1 SIGNUM Newsletter, 26 (October 1991), 6--12. Survey #2 Inter. J. Supercomputing Appl., to appear this summer. or by anonymous ftp from math.berkeley.edu in pub/Alan_Edelman. ------------------------------ From: Walter Mascarenhas Date: Tue, 4 May 93 18:07:36 EST Subject: C++ vs. FORTRAN Hi, Two weeks ago I posted a note in the na-digest asking people's impressions about C++ for numerical analysis and how it compares with FORTRAN. Unfortunately, there was a problem with the mailing system here and I only got a couple of replies. Now my mail is back and I am getting several messages asking for the results of my survey. Therefore, I decided to post this note asking the people who tried to send me a message in that week and didn't get through to try it again. I also would like to hear more from people against C++. Sorry for having to post this again, Walter Mascarenhas. ------------------------------ From: Jie Shen Date: Wed, 5 May 93 10:59:37 -0400 Subject: Block Tridiagonal Solver I am looking for an efficient algorithm/software to solve the following symmetric positive definite block tridiagonal system: F X + D X + F X =G , i=1,2,...,n. i-1 i-1 i i i i+1 i where F and D are n-by-n symmetric tridiagonal matrices, F = F =0; i i 0 n X and G are vectors of order n. In addition, F and D are i i i j commutative (for all i,j). 2 It seems that the system can be solved in O(n log n) operations by 2 using a special cyclic reduction algorithm. Does anyone know a public domain software and/or other algorithm which can solve the system in 2 O(n log n) operations ? 2 Jie Shen ( shen_j@math.psu.edu) Department of Mathematics Penn State University ------------------------------ From: Nick Trefethen Date: Thu, 6 May 93 10:36:16 -0400 Subject: Classic Papers in Numerical Analysis "CLASSIC PAPERS IN NUMERICAL ANALYSIS" NA-Netters may be interested to hear of my experiences this spring teaching a seminar with the above title to a dozen Cornell graduate students (three of whom were actually post-docs or faculty). Comp. Sci. 722 met once a week for two hours, and in the course of the semester we read thirteen papers: 1. Cooley & Tukey (1965) the Fast Fourier Transform 2. Courant, Friedrichs & Lewy (1928) finite difference methods for PDE 3. Householder (1958) QR factorization of matrices 4. Curtiss & Hirschfelder (1952) stiffness of ODEs; BD formulas 5. de Boor (1972) calculations with B-splines 6. Courant (1943) finite element methods for PDE 7. Golub & Kahan (1965) the singular value decomposition 8. Brandt (1977) multigrid algorithms 9. Hestenes & Stiefel (1952) the conjugate gradient iteration 10. Fletcher & Powell (1963) optimization via quasi-Newton updates 11. Wanner, Hairer & Norsett (1978) order stars and applications to ODE 12. Karmarkar (1984) interior pt. methods for linear prog. 13. Greengard & Rokhlin (1987) multipole methods for particles Most weeks, one or two related readings were also assigned, typically from a recent textbook or survey article. For example, along with the Fletcher & Powell paper we read an extract from the 1983 text by Dennis & Schnabel. Our weekly meetings followed a regular format. First, this week's Historian distributed a handout containing information he/she had obtained about the historical context of the paper, including biographical information about the author(s) and a plot of citations as a function of time. Next, the Mathematician gave a presentation of some of the central ideas of the paper. Third and fourth, two Experimentalists reported the results of Matlab, C, or Fortran experiments conducted to illustrate some of the properties of the algorithm under discussion. Finally, the Professor added a few remarks. To me and at least some of the students, this course provided a satisfying vision of the broad scope of numerical analysis and a sense of excitement at what a diversity of beautiful and powerful ideas have been invented in this field. The thirteen papers were selected partly for their variety; they touch upon nearly all the main problems of numerical computation. We found that although they vary greatly in style, most are quite readable. Indeed it was a pleasure, week after week, to be in the hands of the masters. These authors are for the most part extraordinary people, including some about whom most numerical analysts know little (such as Hirschfelder, one of the leading American chemists of this century). We were struck by how young many of the authors were when they wrote these papers (average age: 34), and by how short an influential paper can be (Householder: 3.3 pages, Cooley & Tukey: 4.4). Our readings also uncovered a few surprises. For example, Curtiss and Hirschfelder inexplicably define stiffness in terms of exponentially diverging trajectories, not converging ones; nevertheless they invent the right cure for the problem in the shape of backward differentiation formulas. For another example, did you know that the classic SVD paper by Golub & Kahan makes no mention of the QR algorithm? Our thirteen papers fall into three categories: Finite algorithms for finite problems: papers 1,3,5 Infinite algorithms for infinite problems: papers 2,4,6,7,10,11 Infinite algorithms for finite problems: papers 8,9,12,13 (An infinite algorithm is one that depends on an iteration or discretization parameter; an infinite problem is one for which all exact algorithms must be infinite.) The third category is particularly interesting. Evidently four of the most exciting modern developments in numerical analysis -- multigrid iterations, conjugate gradient iterations, interior point methods, and multipole methods -- have in common that they depend on the approximate computation of quantities that might in principle be computed exactly. Most readers of this note will have thought of other classic authors and papers that should have been on the list. We agree! We are saving up ideas for the next run of CS 722 in a couple of years. Nick Trefethen Dept. of Computer Science Cornell University ------------------------------ From: Mike Dowling Date: Mon, 3 May 93 11:33 MET DST Subject: SIGOPT/OPT-NET: Call for Membership SPECIAL INTEREST GROUP IN OPTIMIZATION (Fachgruppe Optimierung der DMV) ANNOUNCING OPT-NET Call for Membership The Special Interest Group for OPTimization (SIGOPT) has been recently created under the auspices of the Deutsche Mathemiker Vereinigung (DMV) with the purpose of encouraging cooperation amongst its members, and of facilitating communication between them. It is primarily intended to meet the needs of all those interested in mathematical optimisation, both theory and practice. SIGOPT provides a forum for discussing actual and future developments in a broad variety of disciplines associated with optimisation, and actively supports interdisciplinary research and applications to industry. In particular, SIGOPT encourages students and younger scientists to join in research on optimisation. A yearly Mathematical Optimization Conference is organised by SIGOPT members, the first of which will be held at Vitte/Hiddensee in Germany in September this year. In the following two years, the conference will be part of larger conferences, in Berlin under the sponsorship of SVOR, and in Ulm under the sponsorship of DMV. The following year, the conference will be held under GAMM sponsorship. Further workshops shall be held on special aspects of mathematical optimization. The first service to be provided by SIGOPT for the optimisation community is OPT-NET, which has been implemented at the Konrad-Zuse-Zentrum fuer Datentechnik in Berlin (ZIB) under the vice presidency of Martin Groetschel. OPT-NET is an electronic forum similar to NA-Net, so that most NA-Net participants will already be familiar with the more important OPT-NET features. Like NA-Net, each OPT-NET user has a unique nickname that can be used for e-mail correspondence. If John has the nickname john, then Janet can send e-mail to John by sending mail to on.john@zib-berlin.de. Each week, there will be a moderated digest consisting of articles submitted by OPT-NET participants. The present moderator is Uwe Zimmermann from the Technical University of Braunschweig. The digest articles and other documents and programs will be stored in an archive at ZIB, where they can be retrieved using simple e-mail messages strongly reminiscent of the NETLIB procedure. There is also a dialogue service via eLib for perusing and retrieving data stored in the OPT-NET archive. Finally, anonymous FTP is can also be used to deposit and retrieve data. OPT-NET also supplies a WhitePage service similar to the WhitePages associated with NA-Net. Participants names, research interests, etc. are entered into a database which can be queried by other users. For example, in this way you can find the e-mail address of a colleague, or ask for a list of all those who are involved in research into combinatorial optimisation. There are nevertheless some important distinctions between OPT-NET and NA-Net. Perhaps the most important difference is that the WhitePages are closely associated with OPT-NET, so that, currently, the only means of registering with the WhitePages is to register first with OPT-NET. In fact, you will only have to register once, since the OPT-NET database is the same as the WhitePage database. The only difference is that, with a WhitePage registration, your data will be publicly accessible. You can indicate on your OPT-NET registration form that you want to publish your data. Only one registration is therefore necessary for to participate in both OPT-NET and the WhitePages. Similarly, changing your entry will update both your OPT-NET entry and your WhitePage entry. Each user is solely responsible for his or her own data. To guarantee this, your data will be protected with a password which you will have to use each time you change the data in your entry. The opt-net-request program will NEVER use your e-mail address that you enter with your registration. Rather, the e-mail address that the mailer extracts from the header of your registration e-mail will be used instead. In this way, we hope to avoid a number of problems that may otherwise occur when sending e-mail through obscure gateways. One more major distinction between OPT-NET and NA-Net is the influence of the German data security laws which require that written permission be obtained before personal data can be stored electronically. This has the unfortunate consequence that, after you have registered using e-mail, you will receive a letter by post containing a form and a request that you sign to indicate that you consent to ZIB storing your OPT-NET data. Failure to reply to this letter will mean that the ZIB administration will have no alternative but to delete your entry. Please do not feel disconcerted when you receive this letter. You are invited and encouraged to register with OPT-NET. You can obtain the help file simply by sending an empty e-mail message to: opt-net-request@zib-berlin.de This help file will provide you with all the details you will need in order to register with OPT-NET. SIGOPT is also canvassing for new members. You can apply for membership to SIGOPT simply by sending an e-mail message to opt-net-request@zib-berlin.de with the appropriate subject line and body. In fact, with a single additional line to your OPT-NET registration e-mail, your request will be forwarded automatically to the SIGOPT administration. How to do this and much more can be found in the help file. SIGOPT will be using the OPT-NET database as its membership list. In this way, you yourself can ensure that your address information used by SIGOPT is always up to date. SIGOPT members are therefore strongly advised to become OPT-NET participants. We are particularly indebted to Martin Groetschel. From the outset, it was clear that OPT-NET could never have got off the ground without his offer to provide both the facilities and the man power necessary for its implementation. It is thanks to him that OPT-NET could be implemented at ZIB by ZIB staff. In this connection, we wish extend our gratitude to the science director Joachem Luegger (on.luegger@zib-berlin.de) who was responsible for the organisation and technical concept of OPT-NET, and Wolfgang Dalitz (on.dalitz@zib-berlin.de), who was instrumental in the software implementation. We would especially like to thank Jack Dongarra and the NA-Net team whose concept has served as an invaluable guide for designing OPT-NET. Mike Dowling (opt-net-adm@zib-berlin.de) ------------------------------ From: P. M. Pardalos Date: Thu, 6 May 93 14:40:54 EDT Subject: Parallel Optimization Book Topics in Parallel Computing in Mathematical Programming (by P.M. Pardalos, A.T. Phillips and J.B. Rosen), Science Press (1992) ISBN 1-880132-11-7 Contents: Chapter 1: Introduction to parallel computing Chapter 2: Parallel methods for unconstrained optimization Chapter 3: Parallel methods for large-scale linear and nonlinear programming Chapter 4: Parallel methods for constrained global optimization Chapter 5: Parallel methods for discrete optimization The primary audience of this book is intended to be graduate students and scientists interested in the applications of parallel computers in solving mathematical programming problems. In addition, this book can be used as a complimentary text for any course in parallel computing. ------------------------------ From: D. F. Griffiths Date: Thu, 6 May 93 12:47:17 BST Subject: Last Call: Dundee 93 15th BIENNIAL CONFERENCE ON NUMERICAL ANALYSIS UNIVERSITY OF DUNDEE, SCOTLAND, UK 29th June - 2nd July 1993 Last Call for Papers Principal Speakers include J W Barrett I S Duff C M Elliott P Gill D J Higham N K Nichols M J D Powell 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. Abstracts should be submitted by May 21. Registration forms and full details of conference fees, etc.are available from: David F Griffiths Tel: (0382) 23181 EXT 4467 Dept of Maths & Computer Science FAX: (0382) 201 604 The University Dundee DD1 4HN email: dfg@uk.ac.dund.mcs Scotland, UK na.griffiths@na-net.ornl.gov ------------------------------ From: Thomas M. Liebling Date: Mon, 3 May 1993 18:29:41 +0200 Subject: A. W. Tucker Prize Announcement ANNOUNCEMENT BY THE MATHEMATICAL PROGRAMMING SOCIETY OF THE A.W. TUCKER PRIZE The Mathematical Programming Society invites nominations for the A.W. Tucker Prize for an outstanding paper authored by a student. The award will be presented at the International Symposium on Mathematical Programming in Ann Arbor (15-19 August 1994). All students, graduate and undergraduate, are eligible. Nominations of students who have not yet received the first university degree are especially welcome. In advance of the Symposium an award committee will screen the nominations and select at most three finalists. The finalists will be invited, but not required, to give oral presentations at a special session of the Symposium. The award committee will select the winner and present the award prior to the conclusion of the Symposium. The members of the committee for the 1994 A.W. Tucker Prize are : Thomas M. Liebling, Swiss Federal Institute of Technology, Lausanne; Andrew R. Conn, Thomas J. Watson Research Center, Yorktown Heights, William H. Cunningham, University of Waterloo, Clovis Gonzaga, COPPE, Federal University of Rio de Janeiro and Jean-Philippe Vial, University of Geneva. Eligibility The paper may concern any aspect of mathematical programming; it may be original research, an exposition or survey, a report on computer routines and computing experiments, or a presentation of a new and interesting application. The paper must be solely authored, and completed after January 1991. The paper and the work on which it is based should have been undertaken and completed in conjunction with a degree program. Nominations Nominations must be made in writing to the chairman of the award committee Thomas M. Liebling Swiss Federal Institute of Technology Department of Mathematics MA(Ecublens) CH-1015 Lausanne Switzerland by a faculty member at the institution where the nominee was studying for a degree when the paper was completed. Letters of nomination must be accompanied by four copies each of : the student's paper; a separate summary of the paper's contributions, written by the nominee, and no more than two pages in length; and a brief biographical sketch of the nominee. Deadline Nominations must be sent to the chairman no later than December 31, 1993. (Postmark on recommended letter). ------------------------------ From: Karen Hahn Date: Mon, 3 May 93 14:57:38 EDT Subject: IMACS Int'l. Conference on Computational Physics Call for Papers/Call for Sessions 2nd. IMACS International Conference on COMPUTATIONAL PHYSICS October 6-9, 1993 St. Louis, MO, USA Conference Chair: Prof. Jean Potvin - St. Louis University Topics to include: Computational Fluid Dynamics, Statistical mechanics, Condensed matter Physics, Non-linear Dynamics, Quantum Field Theory on the Lattice, Bio-Mechanics, Semi-Conductor Devices, Neural Networks, Applications of Super- and Parallel Computers. Proceedings will be produced, and selected papers of the conference will also appear as regular articles in the IMACS journals. (IMACS publishes MATHEMATICS AND COMPUTERS IN SIMULATION/North Holland; APPLIED NUMERICAL MATHEMATICS/North Holland; JOURNAL OF COMPUTATIONAL ACOUSTICS/World Scientific Pub. Co.) For more information, contact: imacs93@newton.slu.edu, imacs@cs.rutgers.edu, IMACS'93 Department of Science and Mathematics Parks College of Saint Louis University Cahokia, IL 62206, USA or IMACS Secretariat Department of Computer Science Rutgers University New Brunswick, NJ 08903, USA ------------------------------ From: Post Kennung FORTWIHR Date: Tue, 4 May 1993 07:37:17 +0200 Subject: Symposium on High Perfomance Scientific Supercomputing The Bavarian Consortium for High Performance Scientific Computing (FORTWIHR) announces a two-day Symposium on High Perfomance Scientific Supercomputing June, 17th and 18th, 1993 at BMW's Forschungs- und Ingenieur-Zentrum Knorrstr. 147, D-8000 Muenchen 40, Germany Topics will be perspectives, methods and applications of modern Supercomputing in Science and Technology. Invited Speakers: Chr. Zenger (TU Muenchen) N. Fiebiger (Bayerische Forschungsstiftung) R. Bulirsch (TU Muenchen) D. Kimbel (OECD) H.D Simon (NASA) F. Durst (FAU Erlangen-Nuernberg) A. Bode (TU Muenchen) H. Ryssel (FAU Erlangen-Nuernberg) H. Fischer (BMW AG) W. Hanke (Univ. Wuerzburg, FORSUPRA) G. Sachs (TU Muenchen) R. Callies (TU Muenchen) K.-H.Hoffmann (TU Muenchen) G. Mueller (FAU Erlangen-Nuernberg) E. Krause (RWTH Aachen) M. Schaefer (FAU Erlangen-Nuernberg) A. Gilg (Siemens AG) Conference languange will mainly be German. The number of participants is limited to about 400. Get application forms and further information from: Prof. Dr. Chr. Zenger, TU Muenchen, Institut fuer Informatik, Arcisstr. 21, D-8000 Muenchen 2, email: fortwihr@informatik.tu-muenchen.de About FORTWIHR: The Bavarian Consortium for High Performance Scientific Computing (FORTWIHR) was founded for a time limited to nine years in April, 1992. For a period of at least three years it will be financed by the State of Bavaria and the Bavarian Research Foundation. FORTWIHR is the fifth project financed by the Bavarian Research Foundation, which was founded in 1990. The plan for the future is to progressively increase the financial contributions of third agents. More than 40 scientists in the fields of engineering sciences, applied mathematics, and computer science of the Technical University of Munich and of the Friedrich-Alexander-University of Erlangen-Nuernberg are involved in the work of the Consortium. This inter-disciplinary concept is based on the recognition that the increasing significance of the yet young discipline High Performance Scientific Computing (HPSC) can be only given due consideration if the technical knowledge of the engineer, the numerical methods of the mathematician, and the up to date methods and computers of computer science are all applied equally. ------------------------------ From: Trini Flores Date: Wed, 05 May 93 13:22:45 EST Subject: Inverse Problems and Optimal Design in Industry Symposium on Inverse Problems and Optimal Design in Industry July 8-10, 1993 Wyndham Franklin Plaza Hotel Philadelphia, Pennsylvania A three-day Symposium to broaden the contacts between universities and industry on a world-wide scale. The Symposium precedes the July 12-16, SIAM Annual Meeting. A series of minisymposia at SIAM's annual meeting has been designed to complement the themes of the three-day Symposium. SIAM invites all attendees of the Symposium to attend the Annual Meeting. STUDENT AND POSTDOC TRAVEL SUPPORT SIAM has support from the Office of Naval Research to provide partial reimbursement of travel and lodging expenses of graduate students and postdocs who wish to attend the Symposium and the series of minisymposia at the Annual Meeting. To apply, students should ask their graduate advisor to send a letter of recommendation, (include a statement of current status and research interests) to: SIAM c/o Student/Postdoc Support IP93 3600 University City Science Center Philadelphia, PA 19104-2688. Postdocs should send a letter of application, including a statement of current status and research interests to the same address. The letter must be received at the above address by JUNE 15, 1993. ------------------------------ From: Aslak Tveito Date: Tue, 04 May 1993 13:55:55 +0200 Subject: Post Doc Position at the University of Oslo POST DOC POSITION IN COMPUTATIONAL MATHEMATICS UNIVERSITY OF OSLO, NORWAY At The Department of Informatics, University of Oslo we have a post doc position available for one year from approximately August 1-1993. The salary is about $3000 per month. In addition, travelling expences to and from Norway will be covered. We are, in particular, interested in a person who has a background in hyperbolic systems of conservation laws and who is interested in investigating such systems by numerical experiments. The systems we are interested in models different enhanced oil-recovery processes. For further information, please contact Ragnar Winther Deparment of Informatics University of Oslo P.O. Box 1080 Blindern 0316 Oslo Norway e-mail: ragnar@ifi.uio.no ------------------------------ End of NA Digest ************************** -------