Subject: NA Digest, V. 93, # 32 NA Digest Sunday, August 29, 1993 Volume 93 : Issue 32 Today's Editor: Cleve Moler The MathWorks, Inc. moler@mathworks.com Today's Topics: SIAM Classics Series Kang Feng Multivariate Numerical Integration in MATLAB? Permanent Calculation Solver for Parabolic/Elliptic Systems. SISTA Publications Available via FTP Report on Claremont Modeling Workshops Structure of Conferences SIAG/LA meetings California Matrix Theory Meeting First International Meeting on Vector and Parallel Processing Two New Books Contents: Applied Numerical Mathematics Contents: SIAM Scientific and Statistical Computing 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: Gene Golub Date: Sat, 28 Aug 93 11:55:11 PDT Subject: SIAM Classics Series I will be editing the SIAM Classics Series; Richard Brualdi, Avner Friedman, Herb Keller, Ingram Olkin and Bob O'Malley will also be associated with the series. If you have any suggstions of books that are out of print and should be reprinted, please let me know. Gene Golub ------------------------------ From: Meiqing Zhang Date: Wed, 25 Aug 93 21:13:25 -0500 Subject: Kang Feng Those who work on finite element methods or symplectic algorithms will be sad to hear that Kang Feng, one of the pioneers in these fields, passed away on August 17 at the age of 72. His memory will remain with us. Meiqing Zhang Dept. of Computer Science University of Illinois at Urbana-Champaign e-mail Zhang@lisboa.ks.uiuc.edu ------------------------------ From: David Brainard Date: Mon, 23 Aug 93 08:28:13 PDT Subject: Multivariate Numerical Integration in MATLAB? Does anyone know of a package for performing multivariate numerical integration in MATLAB? I am open-minded about algorithms, although my own application is for problems where the dimension is between 10 and 20. I will compile responses sent to: brainard@psych.ucsb.edu and return them to the digest. David Brainard Department of Psychology UC Santa Barbara Santa Barbara, CA 93106 brainard@psych.ucsb.edu (805) 893-2011 ------------------------------ From: Xianzhou (Joe) Zhu Date: Mon, 23 Aug 1993 17:14:36 -0700 (PDT) Subject: Permanent Calculation Hi, I would like some help in evaluating the permanent of NxN matrice. The following is a typical 7x7 matrix I am interested in 1 9.96651e-31 0.693521 8.39639e-36 6.03125e-24 5.45151e-31 1.47348e-37 9.96651e-31 1 1.3468e-31 0.000317621 5.04988e-25 0.0527272 5.16714e-05 0.693521 1.3468e-31 1 7.27441e-36 6.31672e-23 3.42605e-31 5.7238e-38 8.39639e-36 0.000317621 7.27441e-36 1 2.23242e-14 4.59726e-06 0.411012 6.03125e-24 5.04988e-25 6.31672e-23 2.23242e-14 1 8.18067e-28 2.03174e-14 5.45151e-31 0.0527272 3.42605e-31 4.59726e-06 8.18067e-28 1 3.80986e-08 1.47348e-37 5.16714e-05 5.7238e-38 0.411012 2.03174e-14 3.80986e-08 1 The diagonal matrix elements are all 1, the off-diagonal maxtrix elements are in the range of 0-1, but are mostly very small. The definition of the permanent is as follows per(A)=sum A_{1,sigma(1)} A_{2,sigma(2)} ... A_{N,sigma(N)} where sigma is the permutation and sigma(i) is the ith element in the permutation. The sum is over all permutations. Currently I am using the Ryser-Nijenhuis-Wilf algorithm to evaluate the permanent. It is OK for N<20. For N>20, this method becomes slow. Probably we can take advantage of the special structure of our matrix and devise a method for the efficient evaluation of the permanent. For example, if we can pick out terms in the sum, and pick the largest one first, then the second largest, ..., the sum should converge very quickly to the permanent. With an error estimate, we can establish the accuracy of the calculation as well. The goal is to evaluate permanent of 1000x1000 matrix of the above stated properties. If you have some bright idea or know somebody who have thought about this, please let me know. Please send your response directly to me because I do not receive nadigest. My contact info is as follows: Joe Zhu zhu@npl.npl.washington.edu 206-543-4080(office) 206-528-0424(home) regards Joe ------------------------------ From: Silvia Veronese Date: Wed, 25 Aug 1993 11:41:09 -0600 Subject: Solver for Parabolic/Elliptic Systems. One of the models for the study of the excitation process in the cardiac tissue leads to the solution of a reaction diffusion system composed of a nonlinear parabolic equation and a linear elliptic equation in u and v of the following form: 1) v_ +f(v)-div M(x)grad v = div M(x)grad u +g(x,t) t 2) div B(x)grad u = -div M(x)grad v with boundary conditions: t n B(x)grad u = 0 t n M(x)grad v = 0 Investigating the solution of the system we expect a traveling wave-front solution v(x,t) presenting an upstroke of approximately 1 msec, that is a step-like function where the "jump" is 1 mm thick and lasts for 1 msec. The main drawback of the numerical simulation of the RD system is the large amount of computational time required to achieve a sufficient accuracy. For example, for a simulation covering 30 ms we need to solve 600-3000 stationary elliptic problems with approx. 50^3-10^6 nodes. Given the characteristic shape of the solution, it seems that adaptive methods could be succesfully used for this problem. I would be very happy to receive any information regarding fast iterative techniques (and available codes) for the solution of the above problem. I am interested in particular in highly parallelizable codes, adaptive techniques and domain decomposition. Thanks, Silvia Veronese Utah Supercomputing Institute University of Utah Salt Lake City, UT 84112 e-mail: silvia@osiris.usi.utah.edu PS. Does anyone know if PLTMG code for the solution of systems is available somewhere? ------------------------------ From: Geert Schelfhout Date: Thu, 26 Aug 1993 10:36:48 +0200 Subject: SISTA Publications Available via FTP The publication list of the research group SISTA is now made available by anonymous ftp. SISTA (Signals, Identification, System Theory and Automation) is the Control and Signal Processing group of the division ESAT (Electronics, Systems, Automation, Technology) of the department of Electrical Engineering of the Katholieke Universiteit Leuven, Belgium. The list can be obtained from gate.esat.kuleuven.ac.be (134.58.56.20). Please type your email address at the password prompt. It is stored in a directory pub/SISTA/publications, both in (compressed) Postscript (publist.ps.Z) and in (compressed) ASCII format (publist.def.Z). Many recent SISTA publications are available at this ftp site as well. ------------------------------ From: David Cohen Date: Fri, 27 Aug 93 16:05:00 -0700 Subject: Report on Claremont Modeling Workshops August 13 to August 21, 1993, Claremont Colleges, Claremont, California, hosted a two-part workshop centered around the process of mathematical modeling. Thirty-five graduate students from universities all across the United States attended the workshop. The first part of the workshop encompassed the truly hands-on portion of the week. On the first day six academics and researchers presented talks to the entire group on the nature of the problems they wished the participants to model. The presenters included John Collura (NSA), Chuck Gartland (Kent State), Alistair Fitt (Univ. of Southhampton), Mark Matthews (MIT), Jerry Purcell (Momentum Data Systems, Newport Beach, California), and Eric Varley (Lehigh). The topics covered such varied subjects as twisted nematic cells in liquid crystal displays (LCD's), plate tectonics, and efficient oil pumping. That afternoon the workshop participants broke into six subgroups each trying to develop a model for one of the topics presented earlier. The participants by and large were placed in groups whose topic was not closely related to their specialization or focus back at school. This tactic insured that the groups were considering the problem from its foundation mathematically rather than worrying about a small specialized part of the problem. The groups worked from the initial presentation to develop a working model. As a specific example of one of the problems posed, one group was presented a set of data representing the relative displacements of points at the surface along a certain section of the San Andreas Fault. The group then modeled motion locally along the fault below the surface to show where the tectonic plates might be locking or to calculate how much energy might be building up along the faults. Their final model gave results that did approximate what one would expect to be happening based on other knowledge of that fault section. After five days of work, all the subgroups gave thirty minute presentations of their models to the rest of the workshop. The models are now in the process of being collected into a technical report including all six subgroups' work. For the last two days, people representing eight different companies came to present current problems in environmental modeling. The vast majority of the presentations focused on groundwater modeling and contamination detection as the preeminent problem today. During the first afternoon of this part, the participants broke into working groups based on the morning's talks and discussed the modeling problems with the presenters themselves. The results of the working session were reported back briefly to the entire group on the second afternoon. Ellis Cummerbatch at Claremont organized the entire event. The National Security Agency sponsored the week's activities. SIAM gave each participant the choice of up to $75 worth of books from its current publications. [Comment from Gene Golub: These meetings seem like an excellent idea. There is a real need for education of this nature. Congratulations Ellis for organizing such a stimulating workshop. -- Gene] ------------------------------ From: Robert I McLachlan Date: Mon, 23 Aug 93 10:57:20 -0600 Subject: Structure of Conferences I am writing to wholeheartedly agree with the points made by Gene Golub in the most recent NA-Digest. I expect the Digest will be deluged with similar letters. I have been to so many bad conferences and a very few good ones that something really has to be done. Here is what I would recommend for a special topic conference, e.g. one on numerical linear algebra, multigrid, or suchlike. 1) The maximum seminar load should be 3 50-minute talks in the morning (ONE session only) and a maximum of two parallel sessions in the afternoon. The afternoon talks could be 30 or 50 minutes. The crucial thing is to get a big audience with everyone alert and involved. 2) One very successful workshop I attended was at the Geometry Center in Minneapolis. They had a large open area next to the seminar room, with computers in it, and people would mingle there for hours. Joint projects started spontaneously and were completed during the workshop! The crucial factors seemed to be a friendly area (not crowded with people shouting over their mini croissants), in a place where people went naturally (often 'research rooms' are out of the way and no one goes there). The computers helped attract people because they could check their email and demo their computer graphics programs. 3) In order of preference, (1) no proceedings to be published except for photocopies of 1-2 page abstracts, handed out _during_ the conference (2) full, _original_ conference papers published, but in a special issue of a journal, _not_ in a book which appears after three years and nobody can ever find ever again (3) a motley collection of minuscule "survey" papers which are really a rehash of the author's previous three papers and have been published five times already You can guess which one I think is most prevalent today. In case (2), the papers could be solicited and refereed up to six months before the conference, i.e. at the time when people first plan to attend. The the proceedings will appear in a reasonable amount of time after the conference, with the post-refereed versions submitted immediately after the conference. 4) Some kind of informal game to get everyone relaxed, e.g. everyone could contribute $2 to a sweepstakes for the best seminar, to be awarded by popular vote. Speakers running over time are disqualified. 5) Another thing for organizers to aim at is to have the seminars, accomodations, and restaurants absolutely as close together as possible. You have to plan to throw people together or it won't work. The ultimate would be to have all three in the same building, e.g. at some country retreat. This would be no more expensive than the usual system and is what I am going to try for in my next conference. Robert McLachlan ------------------------------ From: John Lewis Date: Fri, 27 Aug 93 11:07:54 PDT Subject: SIAG/LA meetings In the last na-digest, Gene Golub raised several concerns about the Third SIAM Conference on Linear Algebra Signals, Systems and Control and, by implication, SIAM conferences in general. The LASSC conferences support a primary goal of the SIAM Activity Group on Linear Algebra (SIAG/LA): to bring together people for whom linear algebra is a necessity and those for whom linear algebra is a livelihood. They have been quite successful by bodycount, but also by the more important measures of relevance and scientific interchange. Some repetition in material from specialized linear algebra meetings may be a necessary cost in promoting interchange. These meetings have been relevant to many of the attendees, as indicated to us by the large number of positive comments, particularly from our colleagues outside of linear algebra. SIAM's meetings are not perfect. They evolve, not always as smoothly or as speedily as they might, to try to serve their attendees better. The structure and pace of SIAM meetings has traditionally included a high degree of parallelism and long working days (SIAM is often rendered as "Session Is At Midnight"). SIAG/LA will be experimenting with one alternative at our next major meeting, the 1994 SIAM Applied Linear Algebra Conference. As we announced here (na-digest, V93,#21): An article describing the new format in detail appears in the current SIAG/LA newsletter, and is also available by anonymous ftp from the machine AE.SIAM.ORG (IP number 192.108.225.1) as PUB/LA-NET/FORMAT.PS (postscript) or FORMAT.TEXT (plain text). We encourage interested parties to retrieve this article and comment on it. This experiment is in response to past comments by many people. Our experimental format reduces the number of sessions and provides more focus to the minisymposia. It will proceed at a somewhat slower pace. It is an experiment. We invite Gene and you to send us ideas and comments regarding our format. We have already surveyed the SIAG/LA membership regarding our 1994 format. Full details of these results will be published in this fall's SIAG/LA newsletter. We hope that our plan and these responses can add to the discussion of these and other issues of SIAM meetings. Change will only occur if we collectively turn our discomfort into constructive measures and better meetings. SIAG/LA is grateful to Biswa Datta for doing just that, for having the energy and foresight to establish and maintain a forum for interaction between linear algebra and several important areas where it is used. This is one of the most important functions of the SIAM Activity Group on Linear Algebra. To this and the other activities of SIAG/LA we always welcome the contributions of our members. -- John Lewis, Chairman, SIAG/LA -- John Gilbert, Program Director, SIAG/LA ------------------------------ From: Jane Day Date: Tue, 24 Aug 93 10:54:02 +0100 Subject: First International Meeting on Vector and Parallel Processing LAST ANNOUNCEMENT AND GENERAL INFORMATION FIRST INTERNATIONAL MEETING ON VECTOR AND PARALLEL PROCESSING Centro de Informatica "Prof. Correia de Araujo" (CICA) Faculdade de Engenharia da Universidade do Porto (FEUP) Porto, Portugal 1993, 29 September - 1 October ATTENTION: ALTERATION ON THE DEADLINE FOR EARLY REGISTRATION: JULY 31 ABOUT THE MEETING The Meeting is interdisciplinary in nature, bringing together people from Science, Engineering and Industry to explore some of the many challenges and promises of vector and parallel processing. The event aims at disseminating state-of-the art knowledge on the topic and at providing a forum for presentation and discussion of basic research and applications in this area. Industrial applications will be emphasized. The Meeting is organized by the Computer Center (CICA) of the University of Porto Engineering Faculty (FEUP) with the support of several other entities. FORMAT AND TOPICS The Meeting will feature invited lectures and selected contributed papers. Topics of the Meeting include architecture concepts, enabling technologies, operating systems, languages, environments and software tools, software and hardware performance, numerical algorithms, applications in Science and Engineering, Industrial systems and applications. INVITED SPEAKERS L. Almeida (Convex, Portugal) M. Dayde (CERFACS-ENSEEIHT, France) J. Dongarra (Univ. Tennessee, USA) I. Duff (CERFACS, France) V. Hernandez (Univ. Polit. Valencia, Spain) J. Kreatsoulas (Digital Equip. Corp., Brussels) F. Moura (Univ. Minho, Portugal) J. Omnes (EEC, Brussels, Belgium) H. Pina (FCCN, Portugal) A. Proenca (Univ. Minho, Portugal) L. Tassakos (Parsytec, Germany) M. Vitaletti (IBM, Italy) LOCAL ORGANIZING COMMITTEE Organizing Committee Chairperson Ligia M. Ribeiro Filomena Dias D' Almeida Joao Falcao e Cunha Joao Pecas Lopes Jose Laginha Palma ADDITIONAL INFORMATION The full announcements and registration form are available via anonymous ftp from garfield.fe.up.pt (192.82.214.12) in directory pub/mvpp. Get files mvpp-anX.ascii and mvpp-rg.ascii (or .ps for Postscript format). General information can be found in the file mvpp-general.ascii (or .ps). For more details please write to the Chairman of the Organizing Committee at the contact address below (email:lmr@fe.up.pt). CONTACT ADDRESS FEUP-CICA email: mvpp@fe.up.pt Meeting VEC/PAR Proc. fax: 351-2-318787 Rua dos Bragas phone: 351-2-2082071 4099 Porto Codex Portugal ------------------------------ From: P.M. Pardalos Date: Tue, 24 Aug 93 10:27:57 EDT Subject: Two New Books "NETWORK OPTIMIZATION PROBLEMS: ALGORITHMS, APPLICATIONS AND COMPLEXITY" (Editors: D.-Z. Du and P.M. Pardalos) World Scientific (1993), 401 pages ISBN -981-02-1277-1 The field of networks is a lively one, both in terms of theoretical developments and in terms of the diversity of its applications. Many problems of design and analysis of large systems can be formulated and solved using techniques of network theory. Such problems include communication systems, electrical networks, computer networks, transportation, scheduling of industrial processes, facility location, and modeling of combinatorial optimization problems. Network theory originated many years ago, before our information age. In the eighteenth century, Euler solved the famous K\"{o}nigsberg Bridge problem and later Kirchoff initiated the theory of electrical networks. But it was not until late last century, when Bell invented the telephone, that many areas of network theory were stimulated. After the appearance of the first graph theory book (by D. K\"{o}nig) in 1936, there was tremendous development regarding the theory and applications of networks. Hitchcock proposed the first complete algorithm for the transportation problem in 1941, Dantzig proposed the simplex algorithm for linear programming in 1947, and algorithms for the minimum spanning tree (Kruskal, 1956) and shortest path problems were proposed (Prim, 1957). During the same period, the first commercial computers became available. As it happened with many other areas of research, the fields of computer science and networks influenced each other in many respects. In 1962 the book by Ford and Fulkerson on "Flows in Networks" appeared. With the development of new data structure techniques and the theory of computational complexity we entered a new era of algorithmic developments in networks. During the second half of our century we saw major technological developments in all areas of human endeavor and particularly in information processing. Computer networks play a vital role in providing fast, reliable, cost-effective means of communication and information sharing. In addition, network techniques and computer technology enable us to solve large-scale network models that appear in applications such as transportation and telecommunications. It is clear that the theory and applications of networks is so great that this book could not give a full account and systematic treatment of the subject in its entirety. It is our intention to introduce a number of special topics in order to show the spectrum of recent research activities and the richness of ideas in the development of algorithms and the applications of networks. While we were able to provide only a glimpse of this expansive field, we felt that this glimpse would allow the reader to sense the breadth and the depth of the field. "COMPLEXITY IN NUMERICAL OPTIMIZATION" (Editor: P.M. Pardalos) World Scientific (1993), 511 pages ISBN 981-02-1415-4 Computational complexity, originated from the interactions between computer science and numerical optimization, is one of the major theories that have revolutionized the approach to solving optimization problems and to analyzing their intrinsic difficulty. The main focus of complexity is the study of whether existing algorithms are efficient for the solution of problems, and which problems are likely to be tractable. The quest for developing efficient algorithms leads also to elegant general approaches for solving optimization problems, and reveals surprising connections among problems and their solutions. This book is a collection of articles on recent complexity developments in numerical optimization. The topics covered include, complexity of approximation algorithms, new polynomial time algorithms for convex quadratic minimization, interior point algorithms, complexity issues regarding test generation of NP-hard problems, complexity of scheduling problems, min-max, fractional combinatorial optimization, fixed point computations, and network flow problems. The collection of articles provide a broad spectrum of the direction in which research is going and help to elucidate the nature of computational complexity in optimization. The book will be a valuable source of information to faculty, students and researchers in numerical optimization and related areas. ------------------------------ From: Serge Petiton Date: Wed, 25 Aug 93 18:27:58 +0200 Subject: Contents: Applied Numerical Mathematics APPLIED NUMERICAL MATHEMATICS, North Holland Vol. 12, Issue 5, 1993 Special Issue Parallel Scientific Computing: From Solvers to Application Editors : Pierre LECA, ONERA and Univ. PARIS VI. Serge PETITON, ETCA and YALE Univ. M.T. JONES and M.L. PATRICK The Lanczos Algorithm for the Generalized Symmetric Eigenproblem on Shared-Memory Architectures B. PHILIPPE and B. VITAL Parallel Implementations for Solving Generalized Eigenvalue Problems with Symetric Sparse Matrices E.R. JESSUP A Case Against a Divide and Conquer Approach to the Nonsymmetric Eigenvalue Problem D.C. MARINESCU, J.R. RICE and E.A VAVALIS Performance of Iterative Methods for Distributed Memory Machines H. SIMON and L. DAGUM Experience in Using SIMD and MIMD Parallelism for Computational Fluid Dynamics C. FARHAT and M. LESOINE Mesh Partitioning Algorithms for the Parallel Solution of Partial Differential Equations Y.-H. De ROECK Non-Linear Elasticity Solved by a Domain-Decomposition Method on a Hypercube A. de La BOURDONNAYE Numerical Treatment of Integral Equation on iPSC ------------------------------ From: SIAM Date: Fri, 27 Aug 93 14:10:18 EST Subject: Contents: SIAM Scientific and Statistical Computing TABLE OF CONTENTS SIAM Scientific and Statistical Computing Vol. 14-6, November 1993 Block-Cyclic Dense Linear Algebra Woody Lichtenstein and S. Lennart Johnsson Computing the Exact Least Median of Squares Estimate and Stability Diagnostics in Multiple Linear Regression Arnold J. Stromberg Numerical and Asymptotic Solutions for Peristaltic Motion of Nonlinear Viscous Flows with Elastic Free Boundaries Dalin Tang and Samuel Rankin A Parallel Algorithm for Reducing Symmetric Banded Matrices to Tridiagonal Form Bruno Lang Computing Periodic Gravity Waves on Water by Using Moving Composite Overlapping Grids N. Anders Petersson A Modified Broyden Update with Interpolation Miguel F. Anjos Fast Fourier Transforms for Nonequispaced Data A. Dutt and V. Rokhlin Numerical Solution of the Riemann Problem for Two-Dimensional Gas Dynamics Carsten W. Schulz-Rinne, James P. Collins, and Harland M. Glaz Construction of K-Dimensional Delaunay Triangulations Using Local Transformations Barry Joe A Method for Devising Efficient Multigrid Smoothers for Complicated PDE Systems Irad Yavneh Computing the Generalized Singular Value Decomposition Zhaojun Bai and James W. Demmel The Use of the L-Curve in the Regularization of Discrete Ill-Posed Problems Per Christian Hansen and Dianne Prost O'Leary ------------------------------ End of NA Digest ************************** -------