Subject: NA Digest, V. 93, # 42 NA Digest Saturday, November 13, 1993 Volume 93 : Issue 42 Today's Editor: Jack Dongarra University of Tennessee / Oak Ridge National Labs dongarra@cs.utk.edu Stan Green University of Tennessee sgreen@cs.utk.edu (Cleve's away on travel.) Today's Topics: GAMM-SIAM Conference on "Inverse Problems in Diffusion Processes" ICRM parallelization Position at the Department of Computer Science at Purdue University LAA policy on publication of research FTP at UTIA Available Release 1.1 of CUTE is now available SIMAX 15-1 Table of Contents New book: Numerical Methods for Advection-Diffusion Problems, etc, Vol 45 Announcing 1994 SIAM Annual Meeting Algorithm analysis and efficiency Upstate Numerical Analysis Day -- Cornell University 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: Heinz W. Engl Date: Mon, 08 Nov 1993 12:07:55 EST Subject: GAMM-SIAM Conference on "Inverse Problems in Diffusion Processes" GAMM-SIAM Conference on "Inverse Problems in Diffusion Processes" St.Wolfgang, Austria June 27 - July 1, 1994 First Announcement This conference is the first one in a series of conferences on different application fields of inverse problems. The organizing committee for this series consists of David Colton (Newark, DE, USA), Heinz W. Engl (Linz, Austria), Alfred Louis (Saarbr|cken, Germany), and William Rundell (College Station, TX, USA). In addition, there is an advisory committee consisting of M.Bertero, G.Chavent, M.Cheney, R.Ewing, A.Friedman, R.Kre_, K.Kunisch, P.Sabatier, and W.Symes. The first conference is organized locally by Heinz W. Engl and focusses on inverse problems as they appear in the mathematical formulation of diffusion processes, both transient (parabolic pde's) and steady-state (elliptic pde's). This includes parameter identification problems and problems involving side conditions that render them ill-posed. Besides questions of uniqueness and stability, numerical algorithms and applications in science and technology are of special interest. The following invited speakers have so far confirmed their presence at least tentatively: A.Bakushinskii, J.Beck, G.Crosta, L.Elden, A.Friedman, Hong-Ming Yin, V.Isakov, K.Kunisch, A.Lorenzi, D.Ross, T.Seidman, G.Vainikko, S.Vessella, and K.Zeman. In addition to invited talks, there will also be the possibility of some contributed talks of 30 minutes (including discussion) fitting into the scope of the meeting. Participants who wish to give a talk should indicate below and include an abstract. Since we want to avoid parallel sessions, we also encourage participation at this conference just by being there and taking part in the discussions! The meeting will be held in a conference center on Lake St.Wolfgang in one of the most picturesque parts of the Austrian Alps. Because of space limitations, the meeting will be open to up to 120 participants. Therefore, we suggest early registration! The most convenient airport (and train station) is Salzburg, Austria. Salzburg has good flight connections to major gateway airports in central Europe and good train connections to Munich and Vienna. Since June/July is high tourist season, early flight bookings are advised. However, please do not make a firm booking before you hear from us! Detailed travel information from Salzburg onwards will be sent in a second announcement. Participants should arrive at the conference center on June 26 and leave on July 2. The total price for accomodation and full board for this period is currently 4000 Schilling (minor changes possible; currently, 7.15 Schilling = 1 DM, 11 Schilling = 1 US$). Accomodation for accompanying persons is very limited in the conference center, but double rooms in hotels can be booked if we know early enough (at different prices depending on the category). There will be a conference fee of up to 1400 Schilling. This also includes an excursion on Wednesday afternoon (price for accompanying persons: 250 Schilling). If our funding applications are successful, this conference fee might be substantially smaller. The exact amount will not be known until a few weeks before the meeting. In addition to this possible reduction of the conference fee, financial support for participants other than invited speakers is not available. If you want to receive the registration material, please contact me by e-mail at engl@indmath.uni-linz.ac.at or by Fax at +43-732-246810, attn.Prof.Engl or by mail at Prof.Dr.Heinz W.Engl Kepler-Universitdt A-4040 Linz, Austria. Those who have already replied to an earlier preliminary announcement need not reply again, they will receive the registration material soon. ------------------------------ From: Lorie Liebrock Date: Mon, 8 Nov 93 09:07:35 CST Subject: ICRM parallelization I am working on algorithms for automating the distribution of ICRM (Irregularly Coupled Regular Mesh) problems across parallel processors in Fortran D. Other names for ICRM problems are composite grid and multi-block. ICRM problems typically involve the simulation of material dynamics in or around complex topology bodies. For example, one of the areas I am interested in is aerodynamics simulations where each mesh represents some component (e.g., body, wing, pylon, etc.) and the couplings represent the seams or connections between the parts. In the aerodynamics case the flow of air over the components may be the phenomenon of interest. I am interested in any and all applications with such connected components. My work is also intended to support ICRM problems for which the grids have been generated automatically. I am looking for a few test problems that I can use in validation of my algorithms. I am also looking for researchers with ICRM problems that would be willing to discuss their applications and programs so that we can continue improving support for these problems in Fortran D. Please send me any comments and let me know if you or someone you know has applications in this class. Lorie M. Liebrock lorie@cs.rice.edu Ph.D. Candidate Computer Science Rice University ------------------------------ From: John R. Rice Date: Mon, 08 Nov 93 16:56:09 EST Subject: Position at the Department of Computer Science at Purdue University Purdue University is establishing an interdisciplinary graduate program in Computational Science and Engineering. It is expected to involve eventually perhaps 20 departments, 75-100 faculty and over 100 graduate students. The Depart- ment of Computer Sciences seeks a highly qualified person dedicated both to research and teaching at the Assistant Professor level to support this program. Areas of speciali- zation considered appropriate include scientific computing, high performance computing, geometry systems, mathemtical software, applications of computing to science and engineer- ing, and related areas. The department currently has a number of substantial research projects in this area. A new Computational Science and Engineering laboratory will be established with graphical and multi-media facili- ties for teaching and research. These will supplement the existing extensive computing facilities of the department: several large Sun file/computer servers, a 64 processor nCube 2, nearly 200 workstations from Sun, Silicon Graphics, Hewlett-Packard and a complete video production facility. Purdue also has Intel, IBM, and MasPar parallel/vector com- puters and is a member of the Concurrent Supercomputing Con- sortium which operates a 512 processor Intel Paragon. Applications are solicited for appointments to begin in late August 1994. Send curriculum vita and the names of three references by March 1, 1994 to: Chair, CS&E Search Committee Department of Computer Sciences Purdue University W. Lafayette, IN 47907 Purdue University is in a college town of about 25,000, part of the Lafayette metropolitan area of about 125,000 people. The schools are excellent, commuting is easy, the cost of living is reasonable, and there is a full range of athletic and cultural events at the University. Salaries are competitive and Purdue has one of the best packages of fringe benefits of any university. Purdue University is an Equal Opportunity/Affirmative Action Employer ------------------------------ From: Hans Schneider Date: Mon, 8 Nov 1993 17:38:41 -0600 (CST) Subject: LAA policy on publication of research LAA policy on publication of research. This announcement discusses a certain aspect of the publication policy of LAA (which is probably similar to that of most mathematical research journals). The central point is that LAA publishes *original research* (plus some expository articles, book reviews etc. , which will not be further discussed in this announcment). The obvious consequence is that research previously published elsewhere cannot be republished in LAA. Our policy allows two kinds of previous appearance of this research. First, a preprint (hardcopy or electronic) is not considered to be a publication and therefore a paper that has been made available as a preprint can (of course) be considered for publication in LAA. Second, publication (in LAA or elsewhere) of an (extended) abstract or synopsis of the research does not preclude publication of the full paper in LAA. This sounds simple, but occasionally misunderstandings have arisen because there are grey areas which (in the nature of grey areas) cannot be delineated precisely. But below we shall attempt to give some indications on how to distinguish a publication from a preprint and a paper from an abstract or synopsis. 1. What distinguishes a publication from preprint? An article (or series thereof) may be considered to have been published if any of the following hold: a. it bears the imprint of a recognized publisher, b. it is for sale and can be ordered through a bookstore, c. it is being reviewed by Math Reviews. In-house proceeding of conferences (available to participants only) are not normally considered to be publications. 2. What distinguishes a paper from an abstract or synopsis? This is hard. Obviously, the length of an extended abstract is at most a few pages. Normally, the absence of proofs of essentially all significant new results indicates the article is an abstract. But it should be understood that, when there is doubt, the editor-in-chief reserves the right to decide the above questions in each individual case. ------------------------------ From: John J. Hench Date: Tue, 9 Nov 93 13:12:20 +0100 (MET) Subject: FTP at UTIA Available As of the first of November 1993, technical reports from the Institute of Information Theory and Automation of the Academy of Sciences of the Czech Republic are available via FTP. These reports are available in full as compressed postscript files, and should be printable on 300dpi postscript printers. Furthermore, a separate document is available that contains the abstracts of all of these technical reports. To access these reports, type: ftp visla.utia.cas.cz The computer will respond: Connected to visla.utia.cas.cz. 220 visla FTP server (Version 16.2 Fri May 24 17:03:27 GMT 1991) ready. Name (visla.utia.cas.cz:yourname): Type after the prompt: anonymous The computer will respond: 331 Guest login ok, send ident as password. Password: Use your e-mail address as your password, eg.: yourname@youruniversity.edu The technical report series is contained in the directory /pub/reports . In this section there is a file called README . This contains all of the necessary information to access the technical reports. ------------------------------ From: Philippe Toint Date: Tue, 09 Nov 93 18:03:04 +0100 Subject: Release 1.1 of CUTE is now available CUTE (Constrained and Unconstrained Testing Environment) is a set of Fortran subroutines, system tools and test problems in the area of nonlinear optimization and nonlinear equations. Its purpose is to - provide a way to explore an extensive collection of problems (over 600 different test problems today), - provide means of comparing existing packages, - provide a way to use a large test problem collection with new packages, - provide a mechanism to manage and update the system efficiently, and - do all the above on a variety of popular platforms. NEW * The new release provides interfaces to new optimization packages. In addition * to the existing interfaces for MINOS, OSL, UNCMIN, VF13, VE09 and VE14, * CUTE now contains interfaces for * - NPSOL (Gill, Murray, Saunders and Wright SQP code), * - TENMIN (Schnabel and Chow tensor code) and * - VA15 (Nocedal's limited memory code). * The MINOS interface has also been improved to allow selective sizing in * order to accommodate machines with different amounts of memory. NEW * The new release also supports two new computer platforms. Besides * CRAY/Unicos, DEC/ULTRIX, IBM/AIX and SUN/SunOS, CUTE is now available * with fully automated installation procedures for DEC/OSF and DEC/VMS. NEW * Handling of external libraries, like BLAS and the Harwell Subroutine Library, * has been improved. * Known bugs have also been corrected. CUTE has been written by I. Bongartz, A.R. Conn (both at IBM, Watson Research Center), Nick Gould (CERFACS, France) and Ph. Toint (FUNDP, Belgium). A LaTeX manuscript detailing the package may be obtained by email from any of the authors. It is also included in the distribution. CUTE is written is standard ANSI Fortran 77. Single and double precision versions are available. Machine dependencies are carefully isolated and easily adaptable. The package may be obtained in one of two ways. Firstly, the reader can obtain CUTE electronically (and free of charge) via an anonymous ftp call to the account at the Rutherford Appleton Laboratory camelot.cc.rl.ac.uk (Internet i.d. 130.246.8.61, in the directory pub/cute), or at Facultes Universitaires Notre-Dame de la Paix (Namur) thales.math.fundp.ac.be (Internet i.d. 138.48.4.14, in the directory cute). We request that the userid is given as the password. This will serve to identify those who have obtained a copy via ftp. Secondly, the package can be obtained on a floppy disk or magnetic tape at a minimal price, intended to recoup the costs of media, packaging, preparation and courier delivery. Potentially interested parties should contact Ph. Toint to obtain a suitable order form. Ingrid Bongartz bongart@watson.ibm.com Andy Conn arconn@watson.ibm.com Nick Gould gould@cerfacs.fr Philippe Toint pht@math.fundp.ac.be ------------------------------ From: tschoban@siam.org Date: Thu, 11 Nov 93 09:18:26 EST Subject: SIMAX 15-1 Table of Contents Table of Contents SIMAX 15-1, January 1994 Scaling Matrices to Prescribed Row and Column Maxima Uriel G. Rothblum, Hans Schneider, and Michael H. Schneider A Completed Theory of the Unsymmetric Lanczos Process and Related Algorithms, Part II Martin H. Gutknecht A Bottom-Up Inductive Proof of the Singular Value Decomposition C.-T. Pan and Kermit Sigmon Predicting Structure in Sparse Matrix Computations John R. Gilbert Circulant Preconditioned Toeplitz Least Squares Iterations Raymond H. Chan, James G. Nagy, and Robert J. Plemmons Inverse of Strictly Ultrametric Matrices are of Stieltjes Type Servet Martinez, Gerard Michon, and Jaime San Martin A Linear Algebra Proof that the Inverse of a Strictly Ultrametric Matrix Is a Strictly Diagonally Dominant Stieltjes Matrix Reinhard Nabben and Richard S. Varga Generalized Displacement Structure for Block-Toeplitz, Toeplitz- Block, and Toeplitz-Derived Matrices T. Kailath and J. Chun On the Controllability of Matrix Pairs (A, K) with K Positive Semidefinite, II David Carlson Reduction of a Transfer Function via an Observability Matrix Stephen Barnett The Schur Algorithm for Matrix-Valued Meromorphic Functions Reuven Ackner, Hanoch Lev-Ari, and Thomas Kailath Reducibility Condition of a Class of Rational Function Matrices Kai Sheng Lu and Jia Ning Wei Fast Plane Rotations with Dynamic Scaling Andrew A. Anda and Haesun Park Positive Definiteness and Stability of Interval Matrices Jiri Rohn ESPRIT Direction-of-Arrival Estimation in the Presence of Spatially Correlated Noise Haesun Park Finding the Best Regression Subset by Reduction in Nonfull-Rank Cases Alan H. Feiveson Numerical Solution of the Eigenproblem for Banded, Symmetric Toeplitz Matrices Susan L. Handy and Jesse L. Barlow A Note on Jacobi Being More Accurate Than QR Walter F. Mascarenhas Large Least Squares Problems Involving Kronecker Products Donald W. Fausett and Charles T. Fulton A Shifted Block Lanczos Algorithm for Solving Sparse Symmetric Generalized Eigenproblems Roger G. Grimes, John G. Lewis, and Horst D. Simon Factoring Symmetric Indefinite Matrices on High-Performance Architectures Mark T. Jones and Merrell L. Patrick Computation of Stable Invariant Subspaces of Hamiltonian Matrices R. V. Patel, Z. Lin, and P. Misra Sparsity Patterns with High Rank Extremal Positive Semidefinite Matrices J. William Helton, Daniel Lam, and Hugo J. Woerdeman Norms of Hadamard Multipliers Carl C. Cowen, Michael A. Dritschel, and Richard C. Penney Cyclic Reduction for Special Tridiagonal Systems S. Bondeli and W. Gander Dynamic Condition Estimation and Rayleigh--Ritz Approximation Ping Tak Peter Tang On the Structure of Generalized Singular Value and QR Decompositions Bart De Moor ------------------------------ From: Barry Koren Date: Fri, 12 Nov 1993 11:15:58 +0100 Subject: New book: Numerical Methods for Advection-Diffusion Problems, etc New book: -------- Numerical Methods for Advection-Diffusion Problems, Notes on Numerical Fluid Mechanics, Vol. 45, (C.B. Vreugdenhil, B. Koren, eds.), Vieweg Verlag, Braunschweig (1993), ISSN 0179-9614, ISBN 3-528-07645-3. # pages: 373, price: DM 138,-- Abstract: The book contains a comprehensive overview of numerical methods to solve advection-diffusion problems, occurring in many fields of flow transport (water quality, atmospheric environment, industrial flows, etc.). All major classes of discretization methods are discussed: finite-difference (upwind and centered, low- and high-order, linear and nonlinear), finite-volume, finite-element, spectral, semi-Lagrangian and fluctuation-splitting methods. Further, two types of modern iterative methods are considered: conjugate gradients and multigrid. The numerical methods are subjected to comparative tests. Conclusions are drawn concerning the performance on points as accuracy, positivity, conservation and cost. Using this information, readers have the possibility to select a method according to their specific needs. Chapters: 1. Introduction --------------------------------------------- C.B. Vreugdenhil. 2. Linear central finite-difference methods ----------------- C.B. Vreugdenhil. 3. Linear upwind biased methods ------------ J.C.H. van Eijkeren, B.J. de Haan, G.S. Stelling, Th.L. van Stijn. 4. Some classical non-linear schemes for advection -------------- M. Pourquie'. 5. A robust upwind discretization method for advection, diffusion and source terms --------------------------------------- B. Koren. 6. Essentially non-oscillatory (ENO) schemes ------------------ F.H. Walsteijn. 7. Spectral methods for advection-diffusion problems ------- L.J.P. Timmermans, F.N. van de Vosse. 8. Finite element methods for advection-diffusion equations --------- A. Segal. 9. Backward semi-Lagrangian methods: an adjoint equation method: -------------------------------------- J.C.H. van Eijkeren. 10. Forward semi-Lagrangian methods: the second moment method ----- J.M. de Kok. 11. The fluctuation splitting method ------------------------------- R. Struijs. 12. Optimal iteration methods for large linear systems of equations: ---------------------------- G.L.G. Sleijpen, H.A. van der Vorst. 13. Introduction to multi-grid --------------------------------- R.P. Stevenson. 14. Multigrid and advection ------------------------------------- P.M. de Zeeuw. 15. Evaluation of the numerical results ------------ B. Koren, C.B. Vreugdenhil. ------------------------------ From: flores@siam.org Date: Fri, 12 Nov 93 12:58:15 EST Subject: 1994 SIAM Annual Meeting Announcing... 1994 SIAM Annual Meeting July 25-29, 1994 Sheraton Harbor Island East San Diego, California Plus... Symposium on Control Problems in Industry July 22-23, 1994 Third SIAM Forum on Industrial and Applied Mathematics July 23, 1994 Organizing Committee Chair: Barbara L. Keyfitz, University of Houston Deadline for submission of minisymposium proposals: December 27, 1993 Deadline for submission of contributed abstracts: January 24, 1994 A hard copy of the call for papers for the meeting is now available. Likewise an electronic version of it. To receive either copy, contact: SIAM Conference Department E-Mail Address: meetings@siam.org Telephone: 215-382-9800 Fax: 215-386-7999 Plain TeX or LaTeX macros for submitting abstracts are also available by contacting SIAM at the same address. ------------------------------ From: Dean Schulze Date: Fri, 12 Nov 1993 19:11:59 -0700 (MST) Subject: Algorithm analysis and efficiency Stefano Foresti made some thoughtful comments on the need for a balanced approach when solving numerical problems (NA Digest, v93, #41, 11-7-93). I agree with his statement " A "balanced" knowledge of all aspects of a computational problem, and their interactions, is necessary to compute a reliable and efficient solution. This includes physical problem, input data, continuous model, discrete model, numerical algorithms, finite arithmetic, architecture, language and software." However, there is a cost associated with producing such a reliable and efficient solution: the time required to analyze how all of these factors affect obtaining a solution. This too must be considered when discussing efficiency. Foresti analyzed an example that I had given previously: >Let's consider an example in a previous contribution: > r=exp(exp(-1.0/cos(chi))) >The probability that chi == pi/2, hence cos(chi) == 0 is very slim, >because the approximate representation of pi is not = to real value of >pi. However, it is possible to show that in simple precision variations >up to 4% of chi around around pi/2 would all output r=1. Hence this >computation may forgive a superficial programmer, because it generates >stable results. Nevertheless, that expression is very expensive >(1 division and 2 exponentials) and it is very inefficient and unwise >to compute in an incremental loop, when the result is predictable. >Therefore, the confident use of this formula in the range of exceptions >may indicate more laziness then mastery. Understanding the trade-off between computational expense and precision is part of the numerical analyst's art. However, unless you're paying for CPU time or have to wait for the result, the cost of this computation is zero. The previous analysis is incomplete because it doesn't include the cost of the numerical analyst's time. When this consideration is included it may turn out to be inefficient to optimize an algorithm that is only used occaisonally. In developing software for my research I use algorithms that are clear and simple implementations of the underlying physics, and I don't analyze their efficiency unless improved performance is needed. Software developed in a research environment gets changed so often that clarity and generality are important, but efficiency analysis can rarely be justified. In the example above, I allow IEEE arithmetic to give me a reliable result because the extra time involved is probably undetectable while sitting at a workstation. While reliability is important to me, optimizing algorithms is usually a waste of time. Another drawback to analyzing algorithms for someone whose primary job is something other than code development is that it distracts you from your primary job, which often is interpreting the results (as opposed to just obtaining the results). Of course certain kinds of code development, such as numerical libraries, must be as efficient and robust as possible because they are heavily used. Without comprehensively designed, analyzed, and tested libraries users like myself wouldn't have reliable and efficient tools, and we would be constantly distracted from our primary jobs by exceptions. A computational scientist should be able to do a comprehensive analysis of the various factors that affect performance. However, in many cases it doesn't pay to do it. Dean Schulze ------------------------------ From: Nick Trefethen Date: Sat, 13 Nov 93 10:44:34 -0500 Subject: Upstate Numerical Analysis Day -- Cornell University UPSTATE NUMERICAL ANALYSIS DAY Cornell University Ithaca, NY Thursday, 9 December 1993 On Thursday, 9 December, the Cornell Computer Science Department and Cornell Theory Center will host an informal get-together for numerical analysts. The following half-hour talks are currently scheduled: Tom Coleman or Yuying Li, title to be announced Toby Driscoll, "Interactive Schwarz-Christoffel mapping in Matlab" Arieh Iserles, "Qualitative analysis of discretized ODEs" Dirk Laurie, "Imperfect periodizing of functions for numerical integration -- MUST all derivatives vanish?" Saul Teukolsky, "Numerical Recipes: Physicists versus Numerical Analysts?" Anne Trefethen, "Parallel Matlab and pipe Poiseuille pseudospectra" Charlie Van Loan, "An eigenvalue problem from adaptive optics" Steve Vavasis, "An accelerated interior point method based on layered least-squares" If you're in the area, or feel like visiting the area, please come! Please contact me if you are likely to attend, so that we can get an idea of numbers. For hotel reservations and other local information, contact Cindy Robinson (cindy@cs.cornell.edu, 607-255-0985). Nick Trefethen LNT@cs.cornell.edu (607) 255-4222 ------------------------------ End of NA Digest ************************** -------