================================================== NUMERICAL ANALYSIS TITLES -- Volume 3, Number 2, Part 1 of 3 -- August 27, 1985 ================================================== Please note: Due to its length, this list is being distributed in 3 parts, each part is about 7 pages in length. ##### AT&T BELL LABORATORIES ##### For copies of these reports, send mail to {ucbvax,ihnp4}!research!wmc or wmc.btl@csnet-relay or na.coughran@su-score or Bill Coughran AT&T Bell Labs 2C419 Murray Hill, NJ 07974 (201) 582-6619 ################### [1] R. E. Bank, W. M. Coughran, Jr., W. Fichtner, D. J. Rose, and R. K. Smith, COMPUTATIONAL ASPECTS OF SEMICONDUCTOR DEVICE SIMULATION NAMs 85-3 In this chapter, we present an overview of the numerical techniques used to solve the coupled system of nonlinear partial differential equations that model the behavior of semiconductor devices. These methods have been incorporated into our device simulation package which has been success- fully used to model complex device structures in two and three space dimensions for both steady-state and transient conditions. --------------- [2] R. E. Bank, W. M. Coughran, Jr., W. Fichtner, E. H. Grosse, D. J. Rose, R. K. Smith, TRANSIENT SIMULATION OF SILICON DEVICES AND CIRCUITS NAMs 85-8 In this paper, we present an overview of the physical prin- ciples and numerical methods used to solve the coupled sys- tem of nonlinear partial differential equations that model the transient behavior of silicon VLSI device structures. We also describe how the same techniques are applicable to circuit simulation. A composite linear multistep formula is introduced as the time-integration scheme. Newton-iterative methods are exploited to solve the nonlinear equations that arise at each time step. We also present a simple data structure for nonsymmetric matrices with symmetric nonzero structures that facilitates iterative or direct methods with substantial efficiency gains over other storage schemes. Several computational examples, including a CMOS latchup problem, are presented and discussed. --------------- ##### CORNELL ##### [3] Franklin T. Luk and Sanzheng Qiao A fast but unstable orthogonal triangularization technique for Toeplitz matrices EE-CEG-85-5 Address: School of Electrical Engineering Cornell University Ithaca, NY 14863 < No Abstract > Submitted by: Frank Luk (luk%tesla@cornell.csnet) Obtainable from: Frank Luk Cornell University Ithaca, New York 14853 --------------- [4] Franklin T. Luk Algorithm-based Fault Tolerance for Parallel Matrix Equation Solvers EE-CEG-85-2 School of Electrical Engineering, Cornell University Ithaca, New York 14853 June 1985 We examine the checksum schemes of Abraham et al. for the computation of the LU-factorization using a multiprocessor array. Their methods are very efficient for detecting a transient error, but quite expensive for correcting it due to the need for a computation rollback. In this paper, we show how to avoid the rollback and how to implement pivoting. We also introduce a new checksum method for solving triangular sets of linear equations. Obtainable from: Frank Luk, above. --------------- ##### COURANT INSTITUTE ##### [5] O. McBryan Computational Methods for Discontinuities in Fluids Lectures in Applied Mathematics vol. 22, AMS, Providence, 1985. < No Abstract > Submitted by: Oliver McBryan (mcbryan@nyu.arpa) Obtainable from: Oliver McBryan Courant Institute 251 Mercer St New York, NY 10012 --------------- [6] O. McBryan and E. Van de Velde Parallel Algorithms for Elliptic Equations Proceedings of the 1984 ARO Novel Computing Environments Conference Stanford University, SIAM , to appear. < No Abstract > Obtainable from: O. McBryan, above. --------------- [7] O. McBryan, E. Van de Velde, and P. Vianna Parallel Algorithms for Elliptic and Parabolic Equations Proceedings of the Conference on Parallel Computations in Heat Transfer and Fluid Flows University of Maryland, November 1984. < No Abstract > Obtainable from: O. McBryan, above. --------------- [8] O. McBryan Using CRAY super-computers as Attached Processors Courant Institute Preprint, 1985. < No Abstract > Obtainable from: O. McBryan, above. --------------- [9] O. McBryan State of the Art of Multiprocessors in Scientific Computation Proceedings of European Weather Center Conference on Multiprocessors Reading, England, Dec 1984, to appear. < No Abstract > Obtainable from: O. McBryan, above. --------------- [10] O. McBryan and E. Van de Velde Parallel Algorithms for Elliptic Equation Solution on the HEP Computer Proceedings of the First HEP Conference University of Oklahoma, March 1985. < No Abstract > Obtainable from: O. McBryan, above. --------------- [11] O. McBryan and E. Van de Velde Parallel Algorithms for Elliptic Equations to appear in Commun. Pure and Appl. Math., Feb 1985. < No Abstract > Obtainable from: O. McBryan, above. --------------- [12] O. McBryan and E. Van de Velde Elliptic Equation Algorithms on Parallel Computers Proceedings of the Conference on Parallel Computers and Partial Differential Equations, Commun. in Applied Numerical Methods, University of Texas, Austin, March 1985, to appear. < No Abstract > Obtainable from: O. McBryan, above. --------------- [13] J. Glimm, B. Lindquist, O. McBryan, and G. Tryggvason Sharp and Diffuse Fronts in Oil Reservoirs: Front Tracking and Capillarity Proceedings of the Houston SPE/SIAM meeting on Mathematics of Reservoir Simulation, SIAM, to appear, Feb. 1985. < No Abstract > Obtainable from: O. McBryan, above. --------------- [14] J. Glimm and O. McBryan A Computational Model for Interfaces Courant Institute Preprint, 1985. < No Abstract > Obtainable from: O. McBryan, above. --------------- [15] James W. Demmel and Bo Kagstrom Computing Stable Eigendecompositions of Matrix Pencils Technical Report # 163 Computer Science Department Courant Institute May, 1985 We discuss how to compute an eigendecomposition of a matrix pencil A-zB when A and B are only known to within a tolerance epsilon. When A-zB is regular (i.e. det(A-zB) is not identically zero) we show how to partition the spectrum and eigenspaces of A-zB into clusters which vary smoothly as A-zB varies within a ball of radius epsilon. When A-zB is singular (a case of interest in systems theory) so that the structures we wish to compute are nongeneric, we show that certain spaces and eigenvalues of the pencil vary smoothly if A-zB varies along a lower dimensional surface as well as within a ball of radius epsilon. This result implies that the usual algorithms for analyzing singular pencils generally compute accurate eigenvalues and spaces. We apply this result by computing perturbation bounds for the controllable subspace and uncontrollable modes of a system dx/dt = Cx + Du. Submitted by: James Demmel (demmel.csd2@nyu) Obtainable from: James Demmel Courant Institute 251 Mercer Str. New York, NY 10012 --------------- [16] Jonathan Goodman, Robert Kohn, and Luis Reyna A Numerical Study of a Relaxed Variational Problem We present the numerical solution of an optimization problem that arises in two phase flow, and in the design of a beam out of two different materials in given proportion for optimum torsional rigidity. The problem is to minimize a Dirichlet integral over all possible functions and over all possible subdomains of a given area. Minimizing over functions with the subdomain fixed would lead to a second order elliptic equation with discontinuous coefficients. A naive (but very plausible) algorithm based directly on this formulation is shown to have "premature termination" at points that are not even stationary points. It is known that problems like this often do not have "classical" solutions. Rather, there are "weak" or "relaxed" solutions that involve microscopic mixing of the two materials. Application of homogenization theory gives a relaxed minimization problem that can numerically be solved. We used a variational multigrid proceedure to get high resolution (256 x 256) in reasonable time on a VAX-780. The numerical results show that the region of microscopic mixing can occupy about 15% of the region in some cases. Submitted by: Jonathan Goodman (goodnan@nyu-acf1.csnet) Obtainable from: Jonathan Goodman Courant Institute of Mathematical Sciences 251 Mercer St. New York, New York, 10012 --------------- [17] Jonathan Goodman, Robert Kohn, and Luis Reyna A Numerical Study of a Relaxed Variational Problem We present the numerical solution of an optimization problem that arises in two phase flow, and in the design of a beam out of two different materials in given proportion for optimum torsional rigidity. The problem is to minimize a Dirichlet integral over all possible functions and over all possible subdomains of a given area. Minimizing over functions with the subdomain fixed would lead to a second order elliptic equation with discontinuous coefficients. A naive (but very plausible) algorithm based directly on this formulation is shown to have "premature termination" at points that are not even stationary points. It is known that problems like this often do not have "classical" solutions. Rather, there are "weak" or "relaxed" solutions that involve microscopic mixing of the two materials. Application of homogenization theory gives a relaxed minimization problem that can numerically be solved. We used a variational multigrid proceedure to get high resolution (256 x 256) in reasonable time on a VAX-780. The numerical results show that the region of microscopic mixing can occupy about 15% of the region in some cases. Obtainable from J. Goodman, above --------------- [18] Jonathan Goodman Convergence of the Random Vortex Method The random vortex method, introduced by Chorin, was intended to compute high Reynolds number incompressible flows in 2 or 3 dimensions. We prove that the method converges (with probability one) for smooth flows without boundaries in two dimensions. The error bounds are independent of the viscosity. The proof relies on the form of smoothing (replacing vortex points by vortex blobs) introduced by Hald in his convergence proof for the (non-random) vortex method for the incompressible Euler equations in 2 dimensions. Obtainable from J. Goodman, above --------------- ##### EMORY ##### [19] Henry Wolkowicz and Phil Smith A NONLINEAR EQUATION FOR LINEAR PROGRAMMING Research Report 16 Emory University We present a characterization of the 'normal' optimal solution of the linear programming problem. This characterization involves the solution of m piecewise linear equations in m unknowns. Submitted by: Henry Wolkowicz csnet: henry@emory bitnet: henry_wolkowicz@uqv-mts.bitnet uucp: alberta!uqv-mts!sunn emory!henry Obtainable from: Henry Wolkowicz Department of Mathematics and Computer Science Emory University Atlanta, Georgia 30322 --------------- From GOLUB@SU-SCORE.ARPA Fri Aug 30 15:40:44 1985 Received: from SU-SCORE.ARPA (su-score.arpa.ARPA) by anl-mcs.ARPA ; Fri, 30 Aug 85 15:39:53 cdt Return-Path: Received: from csnet-relay by SU-SCORE.ARPA with TCP; Tue 27 Aug 85 17:57:31-PDT Received: from waterloo by csnet-relay.csnet id af16675; 27 Aug 85 20:36 EDT Date: Tue, 27 Aug 85 13:13:16 edt From: Richard Bartels Message-Id: <8508271713.AA25261@watcgl.UUCP> To: na@SU-SCORE.ARPA Subject: T&A Part 2 of 3 Resent-Date: Fri 30 Aug 85 11:48:00-PDT Resent-From: Gene Golub (415/497-3124) Resent-To: :; Resent-Message-Id: <12139307553.36.GOLUB@SU-SCORE.ARPA> Status: RO ================================================== NUMERICAL ANALYSIS TITLES -- Volume 3, Number 2, Part 2 of 3 -- August 27, 1985 ================================================== Please note: Due to its length, this list is being distributed in 3 parts, each part is about 7 pages in length. ##### GMD, WEST GERMANY ##### All the papers of the GMD may be ordered from Dr. Kurt Brand Gesellschaft fuer Mathematik und Datenverarbeitung (GMD) F1/T Postfach 1240 D-5205 St. Augustin 1 F.R.G. or send a request by electronic mail to gmap18%dbngmd21.bitnet@wiscvm.arpa No abstracts were submitted. ################### [20] K. Becker Ein Mehrgitterverfahren zur Berechnung subsonischer Potential- stroemungen um Tragflaechenprofile Berichte der Gesellschaft fuer Mathematik und Datenverarbeitung, Bericht Nr. 152, Oldenbourg-Verlag, 1985 --------------- [21] K. Becker, U. Trottenberg Development of Multigrid Algorithms for Problems from Fluid Dynamics Arbeitspapiere der GMD no.111, Gesellschaft fuer Mathematik und Datenverarbeitung, Bonn, 1984. (DM 6,-) --------------- [22] A. Brandt Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics GMD-Studien no. 85, Gesellschaft fuer Mathematikund Daten- verarbeitung, Bonn, 1984. (DM 39,-) --------------- [23] O. Kolp Parallelisierung eines Mehrgitterverfahrens fuer einen Baumrechner Arbeitspapiere der GMD no. 82, Bonn, 1984. (DM 10,-) --------------- [24] R. Lorenz Some New Periodic Chebycheff Spaces Arbeitspapiere der GMD no. 79, Gesellschaft fuer Mathematik und Datenverarbeitung, Bonn, 1984 --------------- [25] J. Ruge, K. Stueben Efficient Solution of Finite Difference and Finite Element Equations by Algebraic Multigrid (AMG) Arbeitspapiere der GMD no. 89, Gesellschaft fuer Mathematik und Datenverarbeitung, Bonn, 1984. (DM 10,-) --------------- [26] B. Ruttmann, K. Solchenbach A Multigrid Solver for the computation of in-cylinder turbulent flows in engines Efficient Solutions of Elliptic Systems, Proceedings of GAMM-Seminar, Kiel, January 27 to 29, 1984, (W. Hackbusch ed.). Notes on Numerical Fluid Mechanics, 10, pp. 87-108, Vieweg, Braunschweig, 1984. --------------- [27] K. Stueben, U. Trottenberg, K. Witsch Software Development Based on Multigrid Techniques Arbeitspapiere der GMD no. 84, Gesellschaft fuer Mathematik und Datenverarbeitung, Bonn, 1984. (DM 10,-) --------------- [28] C.-A. Thole, U. Trottenberg Basic Smoothing Procedures for the Multigrid Treatment of Elliptic 3D-Operators Arbeitspapiere der GMD no. 141, Bonn, 1985. (DM 10,-) --------------- [29] U. Trottenberg Schnelle Loesung elliptischer Differentialgleichungen nach dem Mehrgitterprinzip GAMM-Mitteilungen, 1/84, February 1984. --------------- [30] U. Trottenberg, P. Wypior (Ed.) Rechnerarchitekturen fuer die numerische Simulation auf der Basis superschneller Loesungsverfahren I Workshop "Rechnerarchitektur", Erlangen, 14.-15. Juni 1984. GMD-Studien no. 88, Gesellschaft fuer Mathematik und Daten- verarbeitung, Bonn, 1984. (DM 48,-) --------------- [31] U. Trottenberg, P. Wypior (Ed.) Rechnerarchitekturen fuer die numerische Simulation auf der Basis superschneller Loesungsverfahren II Workshop "Simulation/Anwendungen und Numerik", GMD-Studien no. 102, Gesellschaft fuer Mathematik und Daten- verarbeitung, Bonn, 1985. (DM 48,-) --------------- [32] U. Trottenberg Mehrgitterprinzip und Rechnerarchitektur GAMM-Mitteilungen, 1/84, February 1984. --------------- ##### ICASE ##### All ICASE reports listed here may be obtained by writing to: Barbara Kraft ICASE, M/S 132C NASA Langley Research Center Hampton, VA 23665 ################### [33] Zang, T. A. and M. Y. Hussaini A three-dimensional spectral algorithm for simulations of transition and turbulence ICASE Report No. 85-19, March 6, 1985, 39 pages. AIAA Paper No. 85-0296 presented at the AIAA 23rd Aerospace Sciences Meeting, January 14-17, 1985, Reno, Nevada. A spectral algorithm for simulating three-dimensional, incompressible, parallel shear flows is described. It applies to the channel, to the parallel boundary layer, and to other shear flows with one wall-bounded and two periodic directions. Representative applications to the channel and to the heated boundary layer are presented. --------------- [34] Drummond, J. P., M. Y. Hussaini, and T. A. Zang Spectral methods for modeling supersonic chemically reacting flow fields ICASE Report No. 85- 20, March 8, 1985, 37 pages. AIAA J. A numerical algorithm has been developed for solving the equations describing chemically reacting supersonic flows. The algorithm employs a two- stage Runge-Kutta method for integrating the equations in time and a Chebyshev spectral method for integrating the equations in space. The accuracy and efficiency of the technique have been assessed by comparison with an existing implicit finite-difference procedure for modeling chemically reacting flows. The comparison showed that the new procedure yielded equivalent accuracy on much coarser grids as compared to the finite-difference procedure with resultant significant gains in computational efficiency. --------------- [35] LeVeque, R. J Intermediate boundary conditions for LOD, ADI, and approximate factorization methods ICASE Report No. 85-21, April 17, 1985, 24 pages. Submitted to J. Comput. Phys. A general approach to determining the correct intermediate boundary conditions for dimensional splitting methods is presented and illustrated. The intermediate solution U* is viewed as a second-order accurate approximation to a modified equation. Deriving the modified equation and using the relationship between this equation and the original equation allows us to determine the correct boundary conditions for U*. To illustrate this technique, we apply it to LOD and ADI methods for the heat equation in two and three space dimensions. The approximate factorization method is considered in slightly more generality. --------------- [36] Rosen, I. G. Spline-based Rayleigh-Ritz methods for the approximation of the natural modes of vibration for flexible beams with tip bodies ICASE Report No. 85-22, March 18, 1985, 31 pages. Submitted to Quarterly of Applied Mathematics. Rayleigh-Ritz methods for the approximation of the natural modes for a class of vibration problems involving flexible beams with tip bodies using subspaces of piecewise polynomial spline functions are developed. An abstract operator theoretic formulation of the eigenvalue problem is derived and spectral properties investigated. The existing theory for spline-based Rayleigh-Ritz methods applied to elliptic differential operators and the approximation properties of interpolatory splines are used to argue convergence and establish rates of convergence. An example and numerical results are discussed. --------------- [37] Bayliss, A., L. Maestrello, P. Parikh, and E. Turkel Numerical simulation of boundary layer excitation by surface heating/cooling ICASE Report No. 85-23, March 25, 1985, 22 pages. AIAA Paper No. 85-0565, AIAA Shear Flow Control Conference, March 12-14, 1985, Boulder, CO. This paper is a numerical study of the concept of active control of growing disturbances in an unstable compressible flow by using time periodic, localized surface heating. The simulations are calculated by a fourth-order accurate solution of the compressible, laminar Navier-Stokes equations. Fourth-order accuracy is particularly important for this problem because the solution must be computed over many wavelengths. The numerical results demonstrate the growth of an initially small fluctuation into the nonlinear regime where a local breakdown into smaller scale disturbances can be observed. It is shown that periodic surface heating over a small strip can reduce the level of the fluctuation provided that the phase of the heating current is properly chosen. --------------- [38] Hossain, M., G. Vahala, and D. Montgomery Forced MHD turbulence in a uniform external magnetic field ICASE Report No. 85-24, March 28, 1985, 39 pages. Submitted to Phys. Fluid. Two-dimensional dissipative MHD turbulence is randomly driven at small spatial scales and is studied by numerical simulation in the presence of a strong uniform external magnetic field. A novel behavior is observed which is apparently distinct from the inverse cascade which prevails in the absence of an external magnetic field. The magnetic spectrum becomes dominated by the three longest-wavelength Alfv'n waves in the system allowed by the boundary conditions: those which, in a box size of edge 2 pi, have wave numbers (kx, ky) = (1, 0), (1, 1), and (1, -1), where the external magnetic field is in the x direction. At any given instant, one of these three modes dominates the vector potential spectrum, but they do not constitute a resonantly coupled triad. Rather, they are apparently coupled by the smaller- scale turbulence. --------------- [39] Davis, S. F. Shock capturing ICASE Report No. 85-25, April 26, 1985, 23 pages. To appear in Numerical Methods for Partial Differential Equations, (S. I. Hariharan and T. H. Moulder, eds.), Pitman Press, 1986. This chapter describes recent developments which have improved our understanding of how finite difference methods resolve discontinuous solutions to hyperbolic partial differential equations. As a result of this understanding improved shock capturing methods are currently being developed and tested. Some of these methods are described and numerical results are presented showing their performance on problems containing shocks in one and two dimensions. We begin this discussion by defining what is meant by a conservative difference scheme and showing that conservation implies that, except in very special circumstances, shocks must be spread over at least two grid intervals. These two interval shocks are actually attained in one dimension if the shock is steady and an upwind scheme is used. By analyzing this case, we determine the reason for this excellent shock resolution and use this result to provide a mechanism for improving the resolution of two-dimensional steady shocks. Unfortunately, this same analysis shows that these results cannot be extended to shocks which move relative to the computing grid. To deal with moving shocks and contact discontinuities we introduce total variation diminishing (TVD) finite difference schemes and flux limiters. We show that TVD schemes are not necessarily upwind, but that upwind TVD schemes perform better because they permit a wider choice of flux limiters. The advantage of non-upwind TVD schemes is that they are easy to implement. Indeed, it is possible to add an appropriately chosen artificial viscosity to a conventional scheme such as MacCormack's method and make it TVD. We conclude by presenting some theoretical results on flux limiters and some numerical computations to illustrate the theory. --------------- [40] Brandt, A. and S. Ta'asan Multigrid solutions to quasi-elliptic schemes. ICASE Report No. 85-26, May 3, 1985, 21 pages. Progress and Supercomputing in Computational Fluid Dynamics, (Earl. S. Murman and Saul Abarbanel, eds.), Birkhauser Boston, Inc., (tentative publication date: August 20, 1985). Quasi-elliptic schemes arise from central differencing or finite element discretization of elliptic systems with odd order derivatives on non-staggered grids. They are somewhat unstable and less accurate then corresponding staggered-grid schemes. When usual multigrid solvers are applied to them, the asymptotic algebraic convergence is necessarily slow. Nevertheless, it is shown by mode analyses and numerical experiments that the usual FMG algorithm is very efficient in solving quasi-elliptic equations to the level of truncation errors. Also, a new type of multigrid algorithm is presented, mode analyzed and tested, for which even the asymptotic algebraic convergence is fast. The essence of that algorithm is applicable to other kinds of problems, including highly indefinite ones. --------------- [41] Zang, T. A. and M. Y. Hussaini On spectral multigrid methods for the time-dependent Navier-Stokes equations ICASE Report No. 85-27, May 13, 1985, 24 pages. Presented at the 2nd Copper Mountain Conference on Multigrid Methods, April 1-3, 1985, Copper Mountain, CO. A new splitting scheme is proposed for the numerical solution of the time-dependent, incompressible Navier-Stokes equations by spectral methods. A staggered grid is used for the pressure, improved intermediate boundary conditions are employed in the split step for the velocity, and spectral multigrid techniques are used for the solution of the implicit equations. --------------- [42] Osher, S. and E. Tadmor On the convergence of difference approximations to scalar conservation laws ICASE Report No. 85-28, May 14, 1985, 70 pages. Submitted to Math. Comp. We present a unified treatment of explicit in time, two level, second order resolution, total variation diminishing, approximations to scalar conservation laws. The schemes are assumed only to have conservation form and incremental form. We introduce a modified flux and a viscosity coefficient and obtain results in terms of the latter. The existence of a cell entropy inequality is discussed and such an equality for all entropies is shown to imply that the scheme is an E scheme on monotone (actually more general) data, hence at most only first order accurate in general. Convergence for TVD-SOR schemes approximating convex or concave conservation laws is shown by enforcing a single discrete entropy inequality. --------------- [43] Mehrotra, P. and J. Van Rosendale The BLAZE language: A parallel language for scientific programming ICASE Report No. 85-29, May 15, 1985, 57 pages. Submitted to Parallel Computing. Programming multiprocessor parallel architectures is a complex task. This paper describes a Pascal-like scientific programming language, Blaze, designed to simplify this task. Blaze contains array arithmetic, "forall" loops, and APL-style accumulation operators, which allow natural expression of fine grained parallelism. It also employs an applicative or functional procedure invocation mechanism, which makes it easy for compilers to extract coarse grained parallelism using machine specific program restructuring. Thus Blaze should allow one to achieve highly parallel execution on multiprocessor architectures, while still providing the user with conceptually sequential control flow. A central goal in the design of Blaze is portability across a broad range of parallel architectures. The multiple levels of parallelism present in Blaze code, in principle, allows a compiler to extract the types of parallelism appropriate for the given architecture, while neglecting the remainder. This paper describes the features of Blaze, and shows how this language would be used in typical scientific programming. --------------- [44] Trefethen, L. N. and L. Halpern Well-Posedness of one-way wave equations and absorbing boundary conditions ICASE Report No. 85-30, June 10, 1985, 23 pages. Submitted to Math. Comp. A one-way wave equation is a partial differential equation which, in some approximate sense, behaves like the wave equation in one direction but permits no propagation in the opposite one. The construction of such equations can be reduced to the approximation of the square root of 1 - s2 on [-1,1] by a rational function r(s) = Pm(s)/qn(s). This paper characterizes those rational functions r for which the corresponding one-way wave equation is well-posed, both as a partial differential equation and as an absorbing boundary condition for the wave equation. We find that if r(s) interpolates the square root of 1 - s2 at sufficiently many points in (-1,1), then well- posedness is assured. It follows that absorbing boundary conditions based on Pade approximation are well-posed if and only if (m,n) lies in one of two distinct diagonals in the Pade table, the two proposed by Engquist and Majda. Analogous results also hold for one-way wave equations derived from Chebyshev or least-squares approximation. --------------- [45] Majda, G. A new theory for multistep discretizations of stiff ordinary differential equations: Stability with large step sizes ICASE Report No. 85-31, 70 pages. Submitted to Math. Comp. In this paper we consider a large set of variable coefficient linear systems of ordinary differential equations which possess two different time scales, a slow one and a fast one. A small parameter epsilon characterizes the stiffness of these systems. We approximate a system of o.d.e.s in this set by a general class of multistep discretizations which includes both one- leg and linear multistep methods. We determine sufficient conditions under which each solution of a multistep method is uniformly bounded, with a bound which is independent of the stiffness of the system of o.d.e.s, when the step size resolves the slow time scale but not the fast one. We call this property stability with large step sizes. The theory presented in this paper lets us compare properties of one-leg methods and linear multistep methods when they approximate variable coefficient systems of stiff o.d.e.s. In particular, we show that one-leg methods have better stability properties with large step sizes than their linear multistep counterparts. This observation is consistent with results obtained by Dahlquist and Lindberg {11}, Nevanlinna and Liniger {32} and van Veldhuizen {41}. Our theory also allows us to relate the concept of D- stability (van Veldhuizen {41}) to the usual notions of stability and stability domains and to the propagation of errors for multistep methods which use large step sizes. --------------- [46] Banks, H. T. On a variational approach to some parameter estimation problems. ICASE Report No. 85-32, 38 pages. Invited lecture, Internationl Conference on Control Theory for Distributed Parameter Systems and Applications, July 9 - 14, 1984, Voran, Austria. We consider examples (1-D seismic, large flexible structures, bioturbation, nonlinear population dispersal) in which a variational setting can provide a convenient framework for convergence and stability arguments in parameter estimation problems. --------------- [47] Hariharan, S. I. Absorbing boundary conditions for exterior problems ICASE Report No. 85-33, July 18, 1985, 33 pages. To appear in Numerical Methods for Partial Differential Equations, (S. I Hariharan and T. H. Moulden, eds.), Pitman Press, 1986. In this paper we consider elliptic and hyperbolic problems in unbounded regions. These problems, when one wants to solve them numerically, have the difficulty of prescribing boundary conditions at infinity. Computationally, one needs a finite region in which to solve these problems. The corresponding conditions at infinity imposed on the finite distance boundaries should dictate the boundary condition at infinity and be accurate with respect to the interior numerical scheme. Such boundary conditions are commonly referred to as absorbing boundary conditions. This paper presents a survey and covers our own treatment on these boundary conditions for wave-like equations. --------------- From GOLUB@SU-SCORE.ARPA Fri Aug 30 16:44:09 1985 Received: from SU-SCORE.ARPA (su-score.arpa.ARPA) by anl-mcs.ARPA ; Fri, 30 Aug 85 16:43:21 cdt Return-Path: Received: from csnet-relay by SU-SCORE.ARPA with TCP; Wed 28 Aug 85 08:22:34-PDT Received: from waterloo by csnet-relay.csnet id ac19806; 28 Aug 85 7:31 EDT Date: Tue, 27 Aug 85 13:13:45 edt From: Richard Bartels Message-Id: <8508271713.AA25302@watcgl.UUCP> To: na@SU-SCORE.ARPA Subject: T&A Part 3 of 3 Resent-Date: Fri 30 Aug 85 11:48:03-PDT Resent-From: Gene Golub (415/497-3124) Resent-To: :; Resent-Message-Id: <12139307563.36.GOLUB@SU-SCORE.ARPA> Status: RO ================================================== NUMERICAL ANALYSIS TITLES -- Volume 3, Number 2, Part 3 of 3 -- August 27, 1985 ================================================== Please note: Due to its length, this list is being distributed in 3 parts, each part is about 7 pages in length. ##### JOHNS HOPKINS ##### [48] Ralph Byers and Stephen Nash On the Singular "Vectors" of the Lyapunov Operator Tech Rep 438 Mathematical Sciences Department The Johns Hopkins University June 1985 For a real matrix A, the separation of A' and A is sep(A',-A) = min ||A'X + XA||/||X||, where ||.|| represents the Frobenius norm, and A' is the transpose of A. We discuss the conjecture that the minimizer X is symmetric. This conjecture is related to the numerical stability of methods for solving the matrix Lyapunov equation. The quotient is minimized by either a symmetric matrix or a skew symmetric matrix and is maximized by a symmetric matrix. The conjecture is true if A is 2-by-2, if A is normal, if the minimum is zero, or if the real parts of the eigenvalues of A are of one sign. In general the conjecture is false, but counter examples suggest that symmetric matrices are nearly optimal. Submitted by: Steve Nash (sgn@jhu.csnet) Obtainable from: Steve Nash Department of Mathematical Sciences The Johns Hopkins University Baltimore, MD 21218 --------------- ##### MARYLAND ##### [49] Dianne P. O'Leary, Systolic Arrays for Matrix Transpose and Other Reorderings Computer Science Department University of Maryland TR-1481, March, 1985. In this note, a systolic array is described for computing the transpose of an n-by-n matrix in time 3n-1 using n squared switching processors and n squared bit buffers. A one-dimensional implementation is also described. Arrays are also given to take a matrix in by rows and put it out by diagonals, and vice versa. Submitted by: Dianne Oleary (oleary@maryland.arpa) Obtainable from: Dianne Oleary Department of Computer Science University of Maryland College Park, MD 20742 --------------- [50] Dianne P. O'Leary, G. W. Stewart Assignment and Scheduling in Parallel Matrix Factorization Computer Science Department University of Maryland TR-1486, April, 1984. We consider in this paper the problem of factoring a dense n-by-n matrix on a network consisting of P MIMD processors when the net- work is smaller than the number of elements in the matrix 2 (P < n ). The specific example analyzed is a computational net- work that arises in computing the LU, QR, or Cholesky factoriza- tions. We prove that if the nodes of the network are evenly dis- tributed among processors and if computations are scheduled by a round-robin or a least-recently-executed scheduling algorithm, then optimal order of speed-up is achieved. However, such speed- up is not necessarily achieved for other scheduling algorithms or if the computation for the nodes is inappropriately split across processors, and we give examples of these phenomena. Lower bounds on execution time for the algorithm are established for two important node-assignment strategies. Obtainable from: D. Oleary, above. --------------- ##### OAK RIDGE ##### All Oak Ridge reports listed below may be obtained from: Ms. Dawn Human Mathematical Sciences Oak Ridge National Laboratory P. O. Box Y, Bldg. 9207-A Oak Ridge, TN 37831 electronically: human@ornl-msr.arpa ##################### [51] George Ostrouchov ANOVA Model Fitting via Sparse Matrix Computations ORNL Tech. Report, August 1985 The least-squares computational approach is used in fitting analysis of variance models when data are unbalanced or incomplete. For large models containing factors with many levels, standard statistical packages require enormous amounts of time and storage due to the size of the crossproducts matrix. The model matrix X (often called the design matrix) consists of dummy variables and is sparse, thus great reduction in time and storage can be achieved by viewing this as a sparse matrix problem. A method, based on orthogonal Givens factorization of a maximal rank set of sparse columns of X, for computing estimates and residual sums of squares is presented. Selection of a maximal rank set of sparse columns is a key part of this method and is based on the linear dependencies between columns of the model matrix. The linear dependencies are described using a notation based on index sets associated with model terms. Time and storage requirements of the new algorithm are compared to the requirements of GLIM, which uses the same basic numerical algorithm that is used in most statistical packages. Both requirements of the new algorithm are less by up to three orders of magnitude for large models and are competitive for small models. Submitted by: George Ostrouchov -------------- [52] V. Alexiades J.B. Drake G.A. Geist G.E. Giles A.D. Solomon R.F. Wood Mathematical Modeling of Laser-Induced Ultrarapid Melting and Solidification ORNL-6129, July 1985 Mathematical and numerical aspects of laser induced phase change modeling are dicussed. Several numerical formulations, including explicit and implicit enthalpy, adaptive grid finite volume and front tracking are derived and results are presented. In addition, a novel hyperbolic formulation is explored analytically and numerically. The explicit enthalpy approach allows the greatest flexibility and efficiency in modeling problems with complicated phase transitions. Submitted by: Vasili Alexiades -------------- [53] Max Morris Vasili Alexiades Sensitivity Analysis of a Numerically Simulated HgCdTe Solidification Process by Statistical Methods ORNL-6210, August 1985 Statistical response surface methodology is applied to the problem of determining simple approximations for outputs as functions of input parameter values in a numerical simulation of the solidification of a mercury-cadmium-telluride alloy. The approximating polynomials are then differentiated with respect to parameter values to determine sensitivities. A table of percent changes in output values as a result of one per cent changes in parameter values is presented. The empirical procedure used constitutes an unorthodox application of the statistical methodology, but it is easy to use, quite generally applicable and very effective. Submitted by: Vasili Alexiades -------------- [54] V. Alexiades G. A. Geist A. D. Solomon Numerical Simulation of a HgCdTe Solidification Process ORNL-6127, August 1985 The solidification of a cylindrical ingot of mercury-cadmium-telluride is modeled taking into account both heat conduction and solute diffusion. Values of the relevant thermophysical parameters of the pseudo-binary HgTe-CdTe are compiled. The model is implemented numerically by a finite-difference discretization and results of the simulation of a freezing experiment are reported. Submitted by: Vasili Alexiades -------------- [55] George A. Geist Michael T. Heath Parallel Cholesky Factorization on a Hypercube Multiprocessor ORNL-6190, July 1985 Two types of message-passing parallel algorithms are developed for solving symmetric systems of linear equations on a hypercube multiprocessor. One type involves broadcast communication among processors, and the other involves communication along a ring of processors. Details are provided in the form of C programs that implement the algorithms on a hypercube simulator and which should run with little modification on real hypercube hardware. Performance of the various algorithms is demonstrated by means of processor utilization graphs and parallel speedup curves. Submitted by: Mike Heath -------------- [56] Michael T. Heath Parallel Cholesky Factorization in Message-Passing Multiprocessor Environments ORNL-6150, May 1985 Parallel algorithms are presented for computing the Cholesky factorization on multiprocessors having only private local memory. Synchronization of multiple processes is based on message passing. Several possible processor interconnection networks are considered. Submitted by: Mike Heath -------------- [57] George A. Geist ORNL Efficient Parallel LU Factorization with Pivoting on a Hypercube Multiprocessor ORNL-6211, August 1985 A message-passing parallel algorithm is developed for forming the LU factors of general non-singular matrices on a hypercube multiprocessor. Partial pivoting is performed to ensure numerical stability, but the scheduling of tasks is such that the pivot search in the parallel algorithm is completely masked. Empirical tests show that the load imbalance produced by random pivoting causes a 5%-14% increase in execution time. A complementary parallel triangular solution algorithm is also given. Comparisons with the non-pivoting case are used to demonstrate the efficiency of this new algorithm. Submitted by: Al Geist -------------- ##### PITT ##### [58] Rami G. Melhem A Study of Data Interlock in VLSI Computational Networks for Sparse Matrix Multiplication TR-CSD-505 Department of Computer Science Purdue University April 1985 The general question addressed in this study is: Are regular VLSI networks suitable for sparse matrix computations?. More specifically, we consider a special purpose self-timed network that is designed for certain specific dense matrix computation. We add to each cell in the network the capability of recognizing and skipping operations that involve zero operands, and then ask how efficient this resulting network is for sparse matrix computation?. In order to answer this question, it is necessary to study the effect of data interlock on the performance of self-timed networks. For this, the class of pseudo systolic networks is introduced as a hybrid class between systolic and self-timed networks. Networks in this class are easy to analyze, and provide a means for the study of the worst case performance of self-timed networks. The well known concept of computation front is also generalized to include irregular flow of data, and a technique based on the propagation of such computation fronts is suggested for the estimation of the processing time and the communication time of pseudo systolic networks. Submitted by: Rami Melhem (melhem@purdue OR melhem@pitt) Obtainable from: Rami Melhem University of Pittsburgh Department of Mathematics Pittsburgh, PA 15260 --------------- [59] Rami G. Melhem A Modified Frontal Technique Suitable for parallel Systems ICMA-85-84 Department of Mathematics University of Pittsburgh July 1985 Frontal techniques offer the potential for processing the assembly and the factorization phases of finite element analysis in parallel. However, the rows of the stiffness matrix are assembled and factored in different order, thus depriving frontal solvers of the uniformity desirable in parallel processing. On the other hand, band solution techniques handle the factorization phase in a very uniform way but do not interleave assembly and factorization. In this paper, we suggest a technique that borrows from both frontal and band solvers those characteristics that are advantageous for parallel processing. Moreover, book-keeping and data manipulation are simpler in the suggested techniques than in the classical frontal method. This makes the suggested technique also attractive for sequential systems. Obtainable from: Rami Melhem, as above. --------------- ##### STANFORD ##### [60] Gene H. Golub and Carl D. Meyer Simultaneous Computation of Stationary Probabilities with Estimates of Their Sensitivity SIAM ms.no.10958 < No Abstract > Submitted by: Gene H. Golub (golub@su-navajo.arpa) Obtainable from: Gene H. Golub (golub@su-navajo.arpa) Computer Science Department Stanford University Stanford, CA 94305 --------------- [61] Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, and Margaret H. Wright ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR'S PROJECTIVE METHOD We discuss interior-point methods for linear programming derived by applying a logarithmic barrier transformation and performing projected Newton steps for a sequence of barrier parameters. Under certain conditions, one of these ``projected Newton barrier'' methods is shown to be equivalent to Karmarkar's (1984) projective method for linear programming. Details are given of a specific barrier algorithm and its practical implementation. Numerical results are given for several nontrivial test problems. Submitted by: Philip E. Gill (or.gill@su-sierra.arpa) Obtainable from: Philip E. Gill (or.gill@su-sierra.arpa) Systems Optimization Laboratory Operations Research Department Stanford University Stanford, CA 94305 --------------- ##### SUNY/BUFFALO ##### [62] P.J.Eberlein On the Schur Decomposition of a Matrix for Parallel Computation TR 85-689, June 1985, Cornell University An algorithm to solve the eigenproblem for non-symmetric matrices on an N x N array of mesh connected processors, isomorphic to the architecture described by Brent and Luk for symmetric matrices, is presented. This algorithm is a generalization of the classical Jacobi method which holds promise for parallel architectures. Only unitary transformations are used. The rotational parameters are carefully analysed, and many examples of a working program, simulating the parallel architecture, are given. Submitted by: P.J.Eberlein (eberlein%gvax@cornell.arpa) Obtainable from: P.J.Eberlein Dept. of Computer Science SUNY/Buffalo, Bell Hall, Buffalo, N.Y. 14260 --------------- ##### TORONTO ##### [63] D.W. Decker and A. Jepson Convergence cones near bifurcation TR 171/84. < No Abstract > Submitted by: Ken R. Jackson (krj@toronto.csnet) Obtainable from: The Scientific Computing Group, Department of Computer Science, University of Toronto, Toronto, Ontario, Canada M5S 1A4 --------------- [64] Paul Muir Implicit Runge-Kutta methods for two-point boundary value problems TR 175/84. < No Abstract > Obtainable from the above. --------------- [65] Kevin Burrage The order properties of implicit multivalue methods for ordinary differential equations TR 176/84. < No Abstract > Obtainable from the above. --------------- [66] Kevin Burrage Order and stability properties of explicit multivalue methods TR 177/84. < No Abstract > Obtainable from the above. --------------- [67] W.H. Enright, K.R. Jackson, S.P. Norsett, and P.G. Thomsen Interpolants for Runge-Kutta formulas TR 180/85. < No Abstract > Obtainable from the above. --------------- [68] J.M. Fine Low order Runge-Kutta-Nystrom methods with interpolants TR 183/85. < No Abstract > Obtainable from the above. --------------- ##### WASHINGTON STATE ##### [69] ALAN GENZ FULL SYMMETRIC INTERPOLATORY FOR MULTIPLE INTEGRALS CS-85-136 WASHINGTON STATE UNIVERSITY JULY, 1984 A method is given for the direct determination of the weights for fully symmetric integration rules for the hypercube, using multivariable Lagrange interpolation polynomials. The formulas for the weights lead to new classes of efficient rules. Submitted by: Alan Genz ARPANET: na.genz@su-score CSNET: acg@wsu Obtainable from: Alan Genz Computer Science Department Washington State University Pullman, WA 99164-1210 --------------- [70] ALAN GENZ MATRIX METHODS FOR THE FORCED DIFFUSION EQUATION CS-85-137 WASHINGTON STATE UNIVERSITY JULY, 1985 Finite difference methods for the forced diffusion equation with time dependent boundary conditions are developed using matrices to represent both the approximate solution and the difference operations. This technique allows boundary conditions to be included in a natural way and eliminates the need for an analysis of the commutativity of the spatial difference operations. The matrix methods are used to develop algorithms that are second order accurate in space and time for a standard square domain and an annular domain. Obtainable from: Alan Genz, as above. --------------- ##### WATERLOO ##### [71] Senad Busovaca Handling Degeneracy in a Nonlinear L-1 Algorithm Technical Report CS-85-34 Department of Computer Science University of Waterloo This paper is concerned with handling degeneracy in a nonlinear optimization algorithm based on an active set strategy. Although the solution to the problem is given in the context of nonlinear L-1 optimization, the approach is more general and can be used to overcome the non-uniqueness of dual variables in methods that use optimality conditions construc- tively. Submitted by: Richard Bartels Obtainable from: Richard Bartels University of Waterloo Computer Science Department Waterloo, Ontario N2L 3G1 CANADA --------------- .