Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU Path: utzoo!decvax!bellcore!ulysses!ucbvax!daemon From: daemon@ucbvax.BERKELEY.EDU (The devil himself) Newsgroups: mod.techreports Subject: (none) Message-ID: <8601252344.AA08812@csevax.smu> Date: Sat, 25-Jan-86 18:44:20 EST Article-I.D.: csevax.8601252344.AA08812 Posted: Sat Jan 25 18:44:20 1986 Date-Received: Thu, 30-Jan-86 00:59:08 EST Organization: The ARPA Internet Lines: 364 Approved: techreports@smu.csnet ================================================== 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 ---------------