Subject: NA Digest, V. 94, # 6 NA Digest Sunday, February 6, 1994 Volume 94 : Issue 6 Today's Editor: Cleve Moler The MathWorks, Inc. moler@mathworks.com Today's Topics: Interior Methods for Electrical Problems Query about Interpolation of Scattered Data Fast Parallel Matrix Multiplication Products of Fourier Transforms SIAM Student Paper Prizes New Book on Grid Generation Workshop on Mathematic Problems in Industry SuperComputing '94 5th Stockholm Optimization Days Numerical Modelling in Continuum Mechanics Interval'94 Conference Object-Oriented Numerics Conference Position at Cornell University Position at CWI, Amsterdam Position at Cray Research Inc Contents, Control, Signals, and Systems Contents, Matem Aplicada e Computacional Contents, SIAM Control and Optimization Contents, SIAM Discrete Mathematics 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: Mustapha Bouhtou Date: Mon, 31 Jan 94 13:51:00 +0100 Subject: Interior Methods for Electrical Problems Can anyone give me some references on the applications of the recent interior point methods in the electrical area. Please send to bouhtou@clr34el.der.edf.fr Thanks in advance. Mustapha Bouhtou Electricite de France ------------------------------ From: Jan Chleboun Date: Tue, 01 Feb 94 19:33:25 EDT Subject: Query about Interpolation of Scattered Data Dear Members of Na-net, My colleague is interested in computer programs (source code preferred) and/or papers related to *local* interpolation of a bivariate function f(x,y) given by a set of scattered data points {[x_i,y_i,z_i]: i=1,...,N}. Any hints and suggestions are very welcome. Many thanks in advance. Please send your responses to Mr. Jaroslav Valach Inst. of Theor. and Appl. Mech. Pod vodarenskou vezi 4 182 00 Prague 8 Czech Republic ------------------------------ From: Yuefan Deng Date: Mon, 31 Jan 94 09:08:19 EST Subject: Fast Parallel Matrix Multiplication This mail is a response to the request for fast matrix multiplication techniques. A paper we have recently finished seems relevant to mention here (title and abstract are included.) Please let me know if more information is needed. A copy of the source code will be provided upon request. TITLE: A Massively Parallel Method for Matrix Multiplication Based on Strassen's Method ABSTRACT: We present the first parallel method for matrix multiplication on distributed-memory architectures based on Strassen's method. Our tests, performed on an Intel Paragon, show that our method is systematically faster than all existing parallel methods. The larger the matrices are, the greater is the improvement of our method. For matrices of order $M= 5000$, our method is about five times faster than the Ring method coupled with the traditional method for matrix multiplication, a typical method on distributed-memory machines. Also, we have noticed nearly perfect speedup when the processor number is divisible by $7$. When the processor number is not divisible by $7$, we have also achieved a reasonable speedup. C.-C. Chou, Yuefan Deng {To whom correspondence should be sent), and Y. Wang Center for Scientific Computing The University at Stony Brook Stony Brook, NY 11794-3600 PS: This paper was submitted to ``SIAM Journal on Scientific Computing'' on Nov. 21, 1993. ------------------------------ From: Rosie Renaut Date: Wed, 2 Feb 94 14:37:29 MST Subject: Products of Fourier Transforms I have received the following question from a graduate student in engineering. Can anyone be of help. Please respond directly to Tim Haynes tim@enws123.eas.asu.edu I am interested in computing Convolution Sums using two- dimensional FFT's and for up to quartic nonlinearities: N/2-1 K/2-1 ------ ------ u1(i,j)= \ \ u1hat(k,n)exp(i k x(i))exp(i n y(j)) / / ------ ------ n=-N/2 k=-K/2 N/2-1 K/2-1 ------ ------ u2(i,j)= \ \ u2hat(k,n)exp(i k x(i))exp(i n y(j)) / / ------ ------ n=-N/2 k=-K/2 .....similar definitions for u3(i,j) and u4(i,j). Here u1(i,j) is the physical quantity on the (x,y) grid and u1hat(k,n) are the corresponding Fourier coefficients. I want to compute the Fourier coefficients of the nonlinear term V(i,j)=u1(i,j)*u2(i,j)*u3(i,j)*u4(i,j) given u1hat(k,n)...u4hat(k,n). This is typically done by (1) performing inverse FFT on the u1hat....u4hat to get u1...u4 in phyiscal space, (2) multiplying u1...u4 in physical space to get V, (3) computing Vhat by forward FFT on V(i,j). This method produces aliasing errors, which could be removed by "padding" or "phase-shifting". "padding" and "phase-shifting" require significantly more computations to remove the aliasing errors. Is there a cheaper way to remove these aliasing errors? I compute these nonlinear terms at each step of an evolution problem, using 2nd-order backward differencing for the time-like variable. ------------------------------ From: Allison Bogardo Date: Wed, 02 Feb 94 16:30:56 EST Subject: SIAM Student Paper Prizes The annual SIAM Student Paper Prizes will be awarded during the 1994 SIAM Annual Meeting. If you are a student or know of a student who would like to take part in the competition, here are the details: The authors of the three best papers in applied and computational mathematics written by students and submitted to SIAM will be invited to attend the 1994 annual meeting in San Diego, July 25-29. Each winner must present his/her paper at the meeting and will receive a $750 cash award as well as gratis registration for the meeting. Winners will be awarded calligraphed certificates at a special prize ceremony at the meeting. Papers must be singly authored and not previously published or submitted for publication to be eligible for consideration. To qualify, authors must be students in good standing who have not received their PhDs at the time of submission. In submitting their work for publication, authors are asked to consider SIAM journals. Submissions must be received by SIAM on or before March 15, 1994. Submissions, which must be in English, can be sent by regular mail or fax. Each submission must include (1) an extended abstract NOT LONGER THAN 5 PAGES (including bibliography); (2) the complete paper, which will be used solely for clarification of any questions; (3) a statement by the student's faculty advisor that the paper has been prepared by the author indicated and that the author is a student in good standing; (4) a letter by the student's faculty advisor describing and evaluating the paper's contribution; and (5) a short biography of the student. Submissions will be judged on originality, significance, and quality of exposition. The winners will be notified by June 1, 1994. If you have any questions, please contact: Allison Bogardo SIAM 3600 University City Science Center Philadelphia, PA 19104-2688 Telephone: (215) 382-9800 E-mail to bogardo@siam.org Fax to (215) 386-7999 ------------------------------ From: Stanly Steinberg Date: Thu, 3 Feb 94 09:47:32 MST Subject: New Book on Grid Generation Now available: Fundamentals of Grid Generation by Patrick M. Knupp Ecodynamics Research Associates and Stanly Steinberg University of New Mexico Summary: The book begins with a discussion of the well-known grid generation methods for logically-rectangular grids, along with a description of how to use the generated grids to solve steady-state (elliptic) partial differential equations. The remainder of the book is devoted to a discussion of variational grid generation techniques. The known practical algorithms are described in detail, and in addition, the reader is also brought up to date on the current research frontiers. A large number of example grids are given and the book comes with a floppy disk that contains program for generating grids and solving partial differential equations. The book is suitable as a text for a advanced undergraduate or graduate text. CRC Press, Inc. 2000 Corporate Blvd., N.W. Boca Raton, FL 33431 USA 1-800-272-7737 ISBN: 0-8493-8987-9 ------------------------------ From: Mary E. Brewster Date: Mon, 31 Jan 1994 11:59:46 +1700 Subject: Workshop on Mathematic Problems in Industry Announcing A WORKSHOP ON MATHEMATICAL PROBLEMS IN INDUSTRY May 16-20, 1994 presented by The Program in Applied Mathematics of the University of Colorado at Boulder The Mathematics Department of Colorado State University The Mathematics Department of the University of Colorado at Denver In order to help meet the need for greater interaction between researchers in industry and applied mathematicians from the academic community, a workshop will be held in Boulder, Colorado during the week of May 16-20, 1994. The workshop is modelled upon successful programs which have been held for many years at Oxford and RPI. Applications are invited from individuals in industry and other research establishments who would like to propose scientific problems for discussion at the workshop. The problem may be at any stage of mathematical formulation ranging between the two extremes: a problem which is yet to be modelled, and one which has been completely reduced to a problem in analysis and/or computation. Academic participants in the workshop will include faculty and students from Colorado Univerisities as well as representatives from other institutions. A written report of the workshop results will be prepared by the participants for the use of the industrial representative. A fee of $1,000 will be charged to each industry participant bringing a problem to the workshop. Industry representatives who do not bring a problem, but do participate in the workshop will be charged a $250 registration fee. There is no registration fee for academic participants. To facilitate planning for the workshop, we request that a brief one-page description of each proposed problem be submitted by March 1, 1994 to one of the members of the organizing committee. Organizing Committee Professor Mary Brewster (303) 492-0593 or maryeb@boulder.colorado.edu Professor Steve McCormick (303) 492-0662 or stevem@boulder.Colorado.EDU Program in Applied Mathematics, University of Colorado at Boulder, CB 526, University of Colorado, Boulder CO 80309-0526, (303) 492-4668, FAX (303) 492-4066 Professor Jay Bourland jayb@MATH.ColoState.EDU Department of Mathematics, Colorado State University, Fort Collins, CO 80523 (303) 491-6327, FAX (303) 491-2161 Professor Bill Briggs (303) 556-4809 or wbriggs@copper.Denver.Colorado.EDU Department of Mathematics, University of Colorado at Denver, Denver, CO 80217 ------------------------------ From: David Halstead Date: Wed, 2 Feb 94 09:58:28 -0600 Subject: SuperComputing '94 CALL FOR PARTICIPATION THE CONFERENCE ON HIGH PERFORMANCE COMPUTING & COMMUNICATIONS Sponsored by IEEE Computer Society and ACM SIGARCH Supercomputing '94, the next conference in the series on high performance computing and communications, will take place November 14-18, 1994, at the Washington D.C. Convention Center. In addition to serving its traditional purpose of advancing the science and application of supercomputing technology, this conference will focus on research and education in computational science and engineering. Particular emphasis will be given to applications in biology and medicine, design and manufacturing, and environmental issues. The educational activities at Supercomputing '94 will span the spectrum from K-12 through graduate school. All contributions to the conference will be evaluated both on the basis of their technical merit and on the degree to which they support the Supercomputing '94 purposes. SUBMISSION DUE DATES April 4, 1994: Papers Proposals for Roundtables Proposals for Tutorials Proposals for Panel Sessions August 1, 1994: Camera-ready final copy of Technical Papers Proposals for Posters Proposals for Research Exhibits Further information and instructions for submitting technical papers, education papers, roundtables, tutorials, research exhibits, posters, and panels can be found in the full text of the Call for Participation, available via anonymous ftp from sc94.ameslab.gov. For more information about Supercomputing '94 you may also contact: Supercomputing '94 Sherman Place 125 South 3rd Ames, Iowa 50010-6793 Phone: 800-854-1677 or 515-294-0673 Fax: 515-294-0888 Email: info@sc94.ameslab.gov ------------------------------ From: Anders Forsgren Date: Wed, 2 Feb 94 21:52:27 +0100 Subject: 5th Stockholm Optimization Days CALL FOR PAPERS 5TH STOCKHOLM OPTIMIZATION DAYS We welcome theoretical, computational and applied papers for the 5th Stockholm Optimization Days, a two-day conference on optimization, to be held at KTH (Royal Institute of Technology) in Stockholm, Sweden, June 27-28, 1994. We plan to have sessions on crew and vehicle scheduling, dual optimization methods and nonlinear programming among other areas. Invited speakers include: T. Coleman, Cornell University, Ithaca, NY, USA J. Desroisiers, HEC, Montreal, Canada D. M. Gay, AT&T, Murray Hill, NJ, USA P. E. Gill, UC San Diego, CA, USA J.-L. Goffin, McGill University, Montreal, Canada N. I. M. Gould, Rutherford Appleton Lab., Chilton, UK D. Hearn, U. Florida, Gainesville, FL, USA K. C. Kiwiel, Systems Research Institute, Warsaw, Poland R. Mifflin, Washington State University, Pullman, WA, USA W. Murray, Stanford University, CA, USA M. L. Overton, Courant Institute, NY, USA M. J. D. Powell, Cambridge University, UK A. Ruszczynski, IIASA, Laxenburg, Austria A. Sartenaer, FUNDP, Namur, Belgium R. B. Schnabel, University of Colorado, Boulder, CO, USA H. D. Sherali, Virginia Tech., Blacksburg, VA, USA Ph. Toint, FUNDP, Namur, Belgium Abstracts (maximum 200 words) should be sent by May 1 (preferably by e-mail) to optdays@math.kth.se or by mail to Optimization Days Division of Optimization and Systems Theory KTH S-100 44 Stockholm Sweden Fax: +46 8 - 22 53 20. Further information can be obtained from the same addresses. The conference is financially supported by the Goran Gustafsson Foundation and the Swedish National Board for Industrial and Technical Development (NUTEK). Organizers are Ulf Brannlund, Anders Forsgren (head), Per Olov Lindberg and Krister Svanberg from the Division of Optimization and Systems Theory, Department of Mathematics, Royal Institute of Technology (KTH). ------------------------------ From: Petr Prikryl Date: Thu, 03 Feb 94 12:32:38 MET Subject: Numerical Modelling in Continuum Mechanics CALL FOR PAPERS NUMERICAL MODELLING IN CONTINUUM MECHANICS Theory, Algorithms, Applications The Second Summer Conference PRAGUE, CZECH REPUBLIC, August 22 - 25, 1994 Charles University in Prague Chairmen: M. Feistauer, Charles University Prague K. Kozel, Technical University Prague R. Rannacher, University Heidelberg Invited Plenary Speakers: I. Babuska (USA), E. Dick (Belgium), R. Ewing (USA), R. Hoppe (FRG), G.C. Hsiao (USA), W. Jaeger (FRG), C. Johnson (Sweden), R. Jeltsch (Schwitzerland), U. Maas (FRG), M. Marion (France), J. Pitkaranta (Finland), V. Rivkind (Russia), E. Suli (Great Britain), G. Warnecke (FRG), M. Wheeler (USA), G. Wittum (FRG) Topics: Fluid Dynamics Porous Media Flows Reactive Flow Problems Structural Mechanics Fees: The fee is 300 US$, which covers Conference Fee, Welcome Party, accomodation in double room (4 nights) and meals (4x breakfast and lunch) (Possibility to pay a supplement for single room) Accompanying persons: 150 US$ Information and Contact: Prof. Dr. M. Feistauer Faculty of Mathematics and Physics Charles University Prague Sokolovska 83 186 00 Praha 8 Czech Republic E-mail: nmicm@karlin.mff.cuni.cz Fax: +42 2 23 10 464 Phone: +42 2 23 10 464 Kindly inform your colleagues interested in this field ------------------------------ From: Ralph B Kearfott Date: Fri, 4 Feb 1994 09:42:56 -0600 Subject: Interval'94 Conference Dear colleagues, We are glad to inform you that preparation of the International Conference on Interval and Computer-Algebraic Methods in Science and Engineering - INTERVAL'94 (March 7-10, 1994, St.Petersburg, Russia) is now in progress. The Organizing Committee has accepted more than 130 abstracts authorized by more than 160 scientists from 25 countries. The collection of abstracts is already in the printing house, but you still can submit a late abstract, and your talk can be included in the program. Please, write to the e-mail address nest@nit.spb.su or fax to the phone number (812) 234-4852 as soon as possible. If your abstract has been already accepted, but you didn't receive a formal invitation for a visa, please also write to The Organizing Committee as soon as possible. We are looking forward to see you in St.Petersburg! V.M.Nesterov, J. Wolff von Gudenberg, Co-chairmen of INTERVAL'94 ------------------------------ From: Margaret Chapman Date: 4 Feb 94 16:38:45 PST Subject: Object-Oriented Numerics Conference THE SECOND ANNUAL OBJECT-ORIENTED NUMERICS CONFERENCE April 24-27, 1994 Sunriver, Oregon This conference provides a forum where computer scientists and scientific programmers can discuss how to use object-oriented programming techniques to more effectively write complex scientific codes. As numerical programs are becoming more and more complicated, people are looking for ways to manage this complexity. Object- oriented programming gives you the ability to write code at a higher level of abstraction, allowing you to reduce the complexity of numerical programs. Anyone and everyone who is currently working in object-oriented numerics, or would like to, should not miss this conference! There will be approximately 38 technical presentations and a poster session in which workers in the field will present the results of their latest efforts in object-oriented numerics. Session topics include: - Components - Modeling - Tools/Optimization - Design/Languages - Components - Optimization/Linear Algebra - Parallel - Components, Applications, and Environments Preliminary Programs available now. SIGN UP NOW!! For information and registration contact: Margaret Chapman Program Coordinator Rogue Wave Software P.O. Box 2328 Corvallis, OR 97339 (503) 754-3010 FAX (503) 757-6650 email: amc@roguewave.com ------------------------------ From: Julie Addy Date: Mon, 31 Jan 1994 15:50:30 -0500 Subject: Position at Cornell University The Cornell University Theory Center invites applications for the position of Scientific Applications Consultant. The Theory Center is supported by the National Science Foundation, as well as other federal, state, and private sector agencies. The Center is dedicated to providing a national focal point for using high performance computing as a tool to accelerate the solution of scientific, engineering, and industrial problems, while at the same time advancing the basic and applied research that underlies that universal tool. This individual will provide highly specialized and complex consulting and scientific applications support to the Theory Center's national and international scientific and research community; provide in-depth consulting and advice to researchers in enabling scientific applications on parallel architectures, analyzing program execution, and optimizing performance; work closely with users in analyzing problems and developing solutions; and investigate, resolve or refer reported problems. The successful candidate will have the minimum of a B.S. degree in a scientific or engineering discipline; Masters or Ph.D. degree, or equivalent combination of education, research, and experience preferred. Minimum 4-5 years FORTRAN or C programming experience in a scientific environment, and related experience. Demonstrated ability to work with researchers using high performance computing. Scientific applications, parallel programming, and UNIX experience highly desirable. Excellent interpersonal, communication, and organizational skills. For consideration, send cover letter and resume to Julia Addy, Dept. NA, Theory Center, Engineering & Theory Center Building, Cornell University, Ithaca, NY 14853-3801. AA/EOE ------------------------------ From: Barry Koren Date: Fri, 4 Feb 1994 11:14:34 +0100 Subject: Position at CWI, Amsterdam At CWI, in the Department of Numerical Mathematics, a vacancy exists for the position of junior researcher in the field of CFD. The research subject concerns the development and application of solution-adaptive, sparse multigrid methods for the 3D, compressible Navier-Stokes equations. (Sparse grid methods are a new, promising approach for efficient 3D computations.) The research tasks are both theoretical (numerical analysis) and practical (implementation and testing), and are carried out in the framework of a European Communities R&D program (BRITE-EURAM Aeronautics Program). The results are directed towards application in some major European aerospace industries. The candidate should hold a recent M.S. degree and be familiar with CFD-research. The research is expected to lead to a Ph.D. degree. The position holds for four years at a maximum. (No educational or organizational obligations exist.) Further information about the position can be obtained from prof.dr. P.W. Hemker (tel: +31.205924108, e-mail: P.W.Hemker@cwi.nl), or dr. B. Koren (tel: +31.205924114, e-mail: Barry.Koren@cwi.nl). Written applications, with resume and marked with "vacancy BRITE", can be sent to: Personeelsdienst van de Stichting Mathematisch Centrum Kruislaan 413 NL-1098 SJ Amsterdam The Netherlands ------------------------------ From: Qasim M.Sheikh Date: Wed, 2 Feb 94 11:17:59 CST Subject: Position at Cray Research Inc The Applications Department of CRI has an open position for a candidate who has a Ph.d. degree in applied mathematics, computational engineering or numerical analysis, with 0 to 5 years of practical experience. This person will work with developers of emerging mathematical technologies for linear and nonlinear iterative solvers. A major portion of the job will involve working with a team of scientists that are responsible for implementation and incorporation of iterative solvers for linear and nonlinear systems of equations and approximation schemes for differential and integral equations in applications software. Additionally, the work will provide support for several of the leading mathematical libraries vendors. Preference will be given to persons with working knowledge of high performance computer architectures, as related to the above activities, and a understanding of one or more of following applications areas: computational electro-magnetics, computational fluid dynamics, reservoir simulation, structural analysis, etc. Please send resumes by surface mail to: David Caliga Tel: 612 683 3682 Fax: 612 683 3699 Manager, Earth & Environmental Sciences Group Cray Research, Inc Eagan, MN 55121 ------------------------------ From: Eduardo Sontag Date: Mon, 31 Jan 94 09:02:27 EST Subject: Contents, Control, Signals, and Systems TABLE OF CONTENTS, Math of Control, Signals, and Systems Volume 6, Number 1 Svatopluk Poljak and Jiri Rohn, Checking robust nonsingularity is NP-complete, pp. 1-9. B.D.O. Anderson and M. Deistler, Identification of Dynamic Systems from Noisy Data: The Case m = n-1, pp.10-29. L. Gurvits, L. Rodman, T. Shalom, Controllability by completions of partial upper triangular matrices, pp. 30-40. Luiz A.B. San Martin, Invariant control sets on flag manifolds, pp. 41-61. A. Le Breton and Dinh Tuan Pham, Maximum Likelihood Estimation for Continuous Time Autoregressive Model by Relaxation on Residual Variances Ratio Parameters, pp. 62-75. Christiaan Heij, Identification of non-controllable systems from impulse response measurements, pp. 76-97. ------------------------------ From: Carlos Demoura Date: Wed, 2 Feb 94 13:52:34 +0100 Subject: Contents, Matem Aplicada e Computacional Computational and Applied Mathematics (Matematica Aplicada e Computacional) Edited by SBMAC - Brazilian Soc. for Comp. and Appl. Mathematics (Rio) Birkhauser Verlag (Boston) Vol.12 N.2 (1993) J.M. Martinez On the convergence of the column-updating method P. Gauzellino & J.E. Santos Numerical methods for wave propagation in elastic and anelastic media G. Aimez & P-A. Gremaud On a penalty method for the Navier-Stokes problem in regions with moving boundaries. J.L. Menaldi & D.A. Tarzia Generalized Lame-Clapeyron solution for a one-phase sourse Stefan problem L. Nachbin Suplattices associated with convex sets, convex cones and affine spaces A.L. Iusem & M. Teboulle On the convergence rate of entropic proximal optimization methods Vol.12 N.3 (1993) J. Baumeister & E.R.von Stockert On a integral equation related to an inverse problem in magnetocardiography J. Douglas Jr. & J. Wang A new family of mixed finite element spaces over rectangles J.M. Stern & S.A Vavasis Active set methods for problems in column block angular form W.C. Connet, WL Golik & A.L. Schwartz, A superconvergent scheme on irregular grids for systems of two-point boundary value problems ------------------------------ From: SIAM Date: Thu, 03 Feb 94 15:36:21 EST Subject: Contents, SIAM Control and Optimization SIAM J. Control and Optimization Volume 32 Number 3 May 1994 TABLE OF CONTENTS On Generalized Second-Order Derivatives and Taylor Expansions in Nonsmooth Optimization W. L. Chan, L. R. Huang, and K. F. Ng Optimal Control on the L Norm of a Diffusion Process Guy Barles, Christian Daher, and Marc Romano On the Game Riccati Equations Arising in H Control Problems Pascal Gahinet Adaptive Boundary and Point Control of Linear Stochastic Distributed Parameter Systems T. E. Duncan, B. Maslowski, and B. Pasik-Duncan Solution of Some Transportation Problems with Relaxed or Additional Constraints S. T. Rachev and L. Ruschendorf The Free Boundary of the Monotone Follower Maria B. Chiarolla and Ulrich G. Haussmann Generalized Solutions of the Hamilton-Jacobi Equation of Stochastic Control Ulrich G. Haussmann On the Nonlinear Dynamics of Fast Filtering Algorithms Christopher I. Byrnes, Anders Lindquist, and Yishao Zhou Controlled Invariance for Singular Distributions Viswanath Ramakrishna Differential Games With Information Lags Xiaojun Qian A Dissipative Feedback Control Synthesis for Systems Arising in Fluid Dynamics Kazufumi Ito and Sungkwon Kang Decentralized Pole Assignment and Product Grassmannians Xiaochang Wang The Output-Nulling Space, Projected Dynamics, and System Decomposition for Linear Time-Varying Singular Systems William J. Terrell New Existence Results for Optimal Controls in the Absence of Convexity: The Importance of Extremality Erik J. Balder ------------------------------ From: SIAM Date: Thu, 03 Feb 94 15:40:15 EST Subject: Contents, SIAM Discrete Mathematics SIAM J. Discrete Mathematics Volume 7 Number 2 May 1994 TABLE OF CONTENTS Indifference Digraphs: A Generalization of Indifference Graphs and Semiorders M. Sen and B. K. Sanyal Some New Bounds on Single-Change Covering Designs Guo-Hui Zhang On the Angular Resolution of Planar Graphs Seth Malitz and Achilleas Papakostas Planar Separators Noga Alon, Paul Seymour, and Robin Thomas A Stochastic Process Interpretation of Partition Identities G. M. Constantine and T. H. Savits The Square of a Hamiltonian Cycle Genghua Fan and Roland Haggkvist An O(n log n) Algorithm for Bandwidth of Interval Graphs Alan P. Sprague The Laplacian Spectrum of a Graph II Robert Grone and Russell Merris A 2d - 1 Lower Bound for Two-Layer Knock-Knee Channel Routing Tom Leighton The Divisors of x2m + x of Constant Derivatives and Degree 2m-2 Claude Carlet The k-Edge-Connected Spanning Subgraph Polyhedron Sunil Chopra Constructing Small Sample Spaces Satisfying Given Constraints Daphne Koller and Nimrod Megiddo The Minimum Satisfiability Problem Rajeev Kohli, Ramesh Krishnamurti, and Prakash Mirchandani On Optimal Depth Threshold Circuits for Multiplication and Related Problems Kai-Yeung Siu and Vwani P. Roychowdhury On Finding Critical Independent and Vertex Sets Alexander A. Ageev Triangulating Vertex-Colored Graphs F. R. McMorris, Tandy J. Warnow, and Thomas Wimer Bipartite Subgraphs of Triangle-Free Graphs Svatopluk Poljak and Zsolt Tuza Sums of Squares of Edge Lengths and Spacefilling Curve Heuristics for the Traveling Salesman Problem Jun Gao and J. Michael Steele Eulerian Self-Dual Codes L. Babai, H. Oral, and K. T. Phelps Clique Graphs of Chordal and Path Graphs Jayme L. Szwarcfiter and Claudson F. Bornstein ------------------------------ End of NA Digest ************************** -------