%K [1] "Solving the linear least squares problem on a linear %K array of processors" %K by Ahmed Sameh %K (Sept. 1982) [no abstract] %K [2] "A fast poisson solver for multiprocessors" %K by Ahmed Sameh %K (Jan. 1983) [no abstract] %K [3] "An overview of parallel algorithms in numerical %K linear algebra" %K by Ahmed Sameh %K (March 1983) [no abstract] %K [4] "The computation and communication complexity of a parallel %K banded system solver" %K by Ahmed Sameh %K (March 1983) [no abstract] %K Communicated by: Ahmed Sameh %K Obtainable from: Ahmed Sameh %K (Request in writing) %K ----- %K [5] Alan George and Esmond Ng,"Solution of sparse %K underdetermined systems of linear equations", Research %K report CS-82-39, Dept. of Computer Science, University %K of Waterloo, September 1982. (Presented in Sparse %K Matrix Symposium 1982.) %K In this paper we consider the problem of computing the %K minimal l2-solution to a consistent underdetermined linear %K system Ax=b, where A is m by n with m<=n. The method of %K solution is to reduce A to lower trapezoidal form [L O] %K using orthogonal transformations, where L is m by m and %K lower triangular. The method can be implemented efficiently %K if the matrix AA' is sparse. However if A contains some %K dense columns, AA' may be unacceptably dense. We present a %K method for handling these dense columns. The problem of %K solving a rank-deficient underdetermined system is also %K considered. %K [6] Esmond Ng,"Row elimination in sparse matrices using %K rotations", Research report CS-83-01, Dept. of Computer %K Science, University of Waterloo, January 1983. %K One way of solving a system of linear equations Ax=b, %K where A is an m by n matrix, is to use a QR-decomposition of %K A (or A' if m=n, and let Pr and Pc be %K permutation matrices of order m and n respectively. Suppose %K PrAPc is reduced to upper trapezoidal form [R' O]' using %K Givens rotations, where R is n by n and upper triangular. %K The sparsity structure of R depends only on Pc. For a fixed %K Pc, the number of arithmetic operations required to compute %K R depends on Pr. In this paper, we consider row ordering %K strategies which are appropriate when Pc is obtained from %K nested dissection orderings of A'. Recently, it was shown %K that so-called "width-2" nested dissection orderings of A'A %K could be used to simultaneously obtain good row and column %K orderings for A. In this paper, we show that the %K conventional (width-1) nested dissection orderings can also %K be used to induce good row orderings. In part I of this %K paper, we analyze the application of Givens rotations to a %K sparse matrix A using a bipartite graph model. %K [9] Alan George and Esmond Ng,"A partial pivoting %K implementation of Gaussian elimination for sparse %K systems", Research report CS-83-15, Dept. of Computer %K Science, University of Waterloo, May 1983. (Submitted %K to SIAM J. Sci. Stat. Comput.) %K In this paper, we consider the problem of solving a %K sparse nonsingular system of linear equations. We show that %K the structures of the triangular matrices obtained in the %K LU-decomposition of a sparse nonsingular matrix A using %K Gaussian elimination with partial pivoting are contained in %K those of the Cholesky factors of A', provided that the %K diagonal elements of A are nonzero. Based on this result, a %K method for solving sparse linear systems is then described. %K The main advantage of this method is that the numerical %K computation can be done using a static data structure. %K Numerical experiments comparing this method with other %K implementations of Gaussian elimination for solving sparse %K linear systems are presented and the results indicate that %K the method proposed in this paper is quite competitive with %K other approaches. %K Communicated by: Esmond Ng %K Obtainable from: Department of Computer Science %K University of Waterloo %K Waterloo, Ontario %K Canada N2L 3G1 %K ----- %K [10] Richard H. Bartels and Nezam Mahdavi-Amiri, "On Generating %K Test Problems for Nonlinear Programming Algorithms" %K We present an approach to test-problem generation which pro- %K vides a way of constructing example nonlinear programming prob- %K lems from a wide variety of given functions. The approach per- %K mits one to specify an arbitrary number of points at each one of %K which the problem should satisfy some "interesting" conditions %K (i.e. be optimal or stationary or degenerate) and to determine %K the characteristics of functions and derivatives at these points %K (i.e. choose predetermined values, gradients, Hessians and %K Lagrange multipliers). %K We give a sample of results obtained by using our approach to %K generate test problems for two algorithms to minimize nonlinear- %K least-squares objectives subject to nonlinear constraints. %K Communicated by: Richard Bartels %K Obtainable from: Department of Computer Science %K University of Waterloo %K Waterloo, Ontario %K ----- %K [11] V. S. Manoranjan, A. R. Mitchell, and J. Ll. Morris, %K "Numerical Solutions of the 'Good' Boussinesq Equation", %K Report NA/59, October, 1982. %K The 'good' Boussinesq equation is studied numerically using %K Galerkin methods and soliton solutions are shown to exist. %K An analytic formula for the 2-soliton interaction is presented %K and verified by numerical experiment. %K [12] D. F. Griffiths, A. R. Mitchell, "A Numerical Study of the Nonlinear %K Schroedinger Equation", Report NA/52, May, 1982. %K This paper presents a numerical study of the Nonlinear (cubic) %K Schroedinger (NLS) equation. Of particular interest are soliton %K solutions. The paper presents a one-parameter family of numerical %K schemes for solving the equation and advances a number of arguments, %K based on energy conservation, which isolates an optimum of the parameter. %K The numerical algorithm employs piecewise linear basis functions %K for space discretizations, and this is compared with a class of %K finite difference methods based upon a Crank-Nicolson scheme. %K Numerical results for the evolution of a single soliton and for the %K interaction of two solitons are provided. %K Communicated by: J. Ll. Morris, University of Waterloo. %K Obtainable from: D. F. Griffiths %K Department of Mathematics %K University of Dundee %K Dundee DD1 4HN %K Scotland, U.K. %K ----- %K [13] Thomas F. Coleman and Andrew R. Conn, "On the Local Convergence %K of a Quasi-Newton Method for the Nonlinear Programming Problem". %K In this paper we propose a new local quasi-Newton method %K to solve the equality constrained nonlinear programming prob- %K lem. The pivotal feature of the algorithm is that a projec- %K tion of the Hessian of the Lagrangian is approximated by a %K sequence of symmetric positive definite matrices. The matrix %K approximation is updated at every iteration by a projected %K version of the DFP or BFGS formula. We establish that the %K method is locally convergent and the sequence of x-values %K converges to the solution at a 2-step Q-superlinear rate. %K [14] Andrew R. Conn and Nicholas I.M. Gould, "ON THE LOCATION %K OF DIRECTIONS OF INFINITE DESCENT FOR NON-LINEAR %K PROGRAMMING ALGORITHMS". %K There is much current interest in general %K equality constrained programming problems, both %K for their own sake and for their applicability to %K active set methods for nonlinear programming. In %K the former case, typically, the issues are %K existence of solutions and their determination. %K In the latter instance, non-existence of solutions %K gives rise to directions of infinite descent. %K Such direction may subsequently be used to deter- %K mine a more desirable active set. %K The generalised Cholesky decomposition of %K relevant matrices enables us to answer the ques- %K tion of existence and to determine directions of %K infinite descent (when applicable) in an efficient %K and stable manner. %K The methods examined are related to implemen- %K tations that are suitable for null, range and %K Lagrangian methods. %K Communicated by: Andrew R. Conn %K Obtainable from: Andrew R. Conn %K Computer Science Department %K University of Waterloo %K Waterloo, Ontario %K CANADA N2L 3G1 %K ----- %K Title: "Bibliography of Stanford Computer Science %K Reports, 1962-1983", %K Author: "Kathryn A. Berg", %K Number: "STAN-CS-83-962", %K HCprice: "$5.00", %K MFprice: "$2.00", %K Note: "62 pages", %K Date: "March 1983" %K A chronological listing of all technical reports and theses published by %K the department. The availability and cost of each report is noted. %K Also included are the AI Memos and a number of the Heuristic Programming %K Project publications. %K Communicated by: Gene Golub %K Obtainable from: Computer Science Department %K Stanford University %K Stanford, California %K USA 94305 %K ----- %K [15] Performance of Various Computers Using Standard Linear %K Algebra Software in a Fortran Environment %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K Tele: 312-972-7246 %K Arpa: Dongarra@anl-mcs %K In this note we compare a number of different computer systems %K for solving dense systems of linear equations using the LINPACK %K software in a Fortran environment. There are about 50 computers %K compared, ranging from a Cray X-MP to the 68000 based systems %K such as Apollo and Masscomp. %K [16] Squeezing the Most out of an Algorithm %K in Cray Fortran %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K and %K Stanley C. Eisenstat %K Department of Computer Science and %K Research Center for Scientific Computation %K Yale University %K Abstract - This paper discusses a technique for achieving super-vector %K performance on a Cray in a purely Fortran environment (i.e., without %K resorting to assembly language). The technique can be applied %K to a wide variety of algorithms in linear algebra, and is beneficial %K in other architectural settings. %K Communicated by: Jack Dongarra %K Obtainable from: Jack Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K ----- %K [17] "Block Preconditioning For The Conjugate Gradient Method" %K P. Concus, G.H. Golub and G. Meurant %K Block preconditionings for the conjugate gradient method are %K investigated for solving positive definite block tridiagonal %K systems of linear equations arising from discretization of %K boundary value problems for elliptic partial %K differentialequations. The preconditionings rest on the use of %K sparse approximate matrix inverses to generate incomplete block %K cholesky factorizations. Carrying out of the factorizations can %K be guaranteed under suitable conditions. Numerical experiments %K on test problems for two dimensions indicate that a particularly %K attractive preconditioning, which uses special properties of %K tridiagonal matrix inverses, can be computationally more %K efficient for the same computer storage than other %K preconditionings, including the popular point incomplete Cholesky %K factorization. %K Key words: conjugate gradient method, elliptic partial %K differential equations, incomplete factorization, iterative %K methods, preconditioning, sparse matrices. %K Communicated by: Gene Golub %K Computer Science Department %K Stanford University %K Stanford, California %K USA 94305 %K Available from: The authors %K ------- %K [18] Inaccuracy in Quasi-Newton Methods: Local Improvement Theorems %K (Rice University MASC Technical Report 83-11, March 1983.) %K by %K J.E. Dennis, Jr. %K Mathematical Sciences Department, Rice University, Houston, Texas 77251. %K and %K Homer F. Walker %K Department of Mathematics, University of Houston, Houston, Texas 77004. %K In this paper, we consider the use of bounded-deterioration quasi-Newton %K methods implemented in floating-point arithmetic to find solutions to %K F(x) = 0 where only inaccurate F-values are available. Our analysis is for %K the case where the relative error in F is less than one. We obtain theorems %K specifying local rates of improvement and limiting accuracies depending on %K the nearness to Newton's method of the basic algorithm, the accuracy of its %K implementation, the relative errors in the function values, the accuracy of %K the solutions of the linear systems for the Newton steps, and the %K unit-rounding errors in the addition of the Newton steps. %K Communicated by: John Dennis %K Available from: The authors %K --------------- %K [19] "Sharp Estimates for Multigrid Rates of Convergence" %K by Randolph E. Bank[$] and Craig C. Douglas[%] %K [$] Department of Mathematics, University of California at San Diego %K [%] Department of Computer Science, Yale University %K Yale University, Department of Computer Science Research Report #277 %K Available on request from: %K (U.S. Mail) (Phone) %K Craig C. Douglas 203/436-3761 %K Yale University %K Department of Computer Science (ARPAnet) %K 10 Hillhouse Ave. DOUGLAS-CRAIG@YALE %K P.O. Box 2158 Yale Station %K New Haven, CT 06520 %K Summary: In this paper, we prove the convergence of the multilevel iterative %K method for solving linear equations that arise from elliptic partial %K differential equations. Our theory is presented entirely in terms of the %K generalized condition number K of the matrix A and the smoothing matrix B. %K This leads to a completely algebraic analysis of the method as an iterative %K technique for solving linear equations; the properties of the elliptic %K equation and discretization procedure enter only when we seek to estimate K, %K just as in the case of most standard iterative methods. Here we consider the %K fundamental two level iteration, and the V and W cycles of the j-level %K iteration (j > 2). We prove that the V and W cyles converge even when only %K one smoothing iteration is used. We present several examples of the %K computation of K using both Fourier analysis and standard finite element %K techniques. We compare the predictions of our theorems with the actual rate %K of convergence. Our analysis also shows that adaptive iterative methods, both %K fixed (Chebyshev) and adaptive (conjugate gradients and conjugate residuals), %K are effective as smoothing procedures. %K ------- %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 1, Number 2 %K September, 1983 %K ================================================== %K [1] J.J. Dongarra and C.B. Moler, EISPACK - A Package for Solving %K Matrix Eigenvalue Problems, Argonne National Laboratory, %K Mathematics and Computer Science Division, ANL/MCS-TM-12, %K August 1983. %K This is a two part paper on the software package EISPACK. %K The first part describes the development and usage of %K EISPACK and is intended as an introduction to the package. %K The second part describes changes made to the package for the %K current release and how to install the package. EISPACK is a %K systemized collection of subroutines that compute the eigenvalues %K and eigenvectors of different classes of matrices. %K Submitted by: Jack Dongarra %K Obtainable from: %K Jack Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [2] ESTIMATION OF SPARSE HESSIAN MATRICES AND %K GRAPH COLORING PROBLEMS %K Thomas F. Coleman and Jorge J. More' %K Large scale optimization problems often require an approximation %K to the Hessian matrix. If the Hessian matrix is sparse then %K estimation by differences of gradients is attractive because the %K number of required differences is usually small compared to the %K dimension of the problem. The problem of estimating Hessian matrices %K by differences can be phrased as follows: Given the sparsity structure %K of a symmetric matrix A, obtain p vectors d(1), ..., d(p) such that %K Ad(1), ..., Ad(p) determine A uniquely with p as small as possible. %K We approach this problem from a graph theoretic point of view and %K show that both direct and indirect approaches to this problem have a %K natural graph coloring interpretation. The complexity of the problem %K is analyzed and efficient practical heuristic procedures are developed. %K Numerical results illustrate the differences between the various approaches. %K Submitted by: Jorge J. More' %K Obtainable from: %K Jorge More' %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [3] SOFTWARE FOR ESTIMATION OF SPARSE JACOBIAN MATRICES %K Thomas F. Coleman, Burton S. Garbow, and Jorge J. More' %K In many nonlinear problems it is necessary to estimate the Jacobian %K matrix of a nonlinear mapping F. In large scale problems the %K Jacobian of F is usually sparse, and then estimation by differences %K is attractive because the number of differences can be small compared %K to the dimension of the problem. For example, if the Jacobian matrix %K is banded then the number of differences needed to estimate the Jacobian %K matrix is, at most, the width of the band. In this paper we describe a %K set of Fortran 77 subroutines whose purpose is to estimate the Jacobian %K matrix of a mapping F with the least possible number of function evaluations. %K Submitted by: Jorge J. More' %K Obtainable from: Jorge More' (address above) %K --------------- %K [4] THE MINPACK PROJECT %K Jorge J. More', Danny C. Sorensen, %K Burton S. Garbow, and Kenneth E. Hillstrom %K The MINPACK project is a research effort whose goal is the development %K of a systematized collection of quality optimization software. In this %K paper we provide an overview of the MINPACK project. We describe the %K circumstances that led to the project and the various changes that %K occurred during the next four years. We also describe the techniques %K we have used to produce reliable, easy-to-use, transportable software. %K We discuss those topics that are relevant to the development of software %K optimization libraries: scale invariance, robustness, convergence testing, %K user interface and documentation standards. %K Submitted by: Jorge J. More' %K Obtainable from: Jorge J. More' (address above) %K --------------- %K [5] A Nonlinear Version of Gauss's Minimum Variance Theorem %K with Applications to an Errors-in-the-Variables Model %K G. W. Stewart %K TR-1263, April 1983 %K This paper consists of two parts. In the first, a %K theorem of Gauss, commonly known as the Gauss- %K Markov theorem, is generalized and extended to %K apply to nonlinear least squares estimation. The %K result justifies the use of nonlinear least %K squares under the classical assumptions that the %K errors have mean zero and equal variances, with %K the additional proviso that the variance is suffi- %K ciently small. In the second part of the paper %K the theory developed in the first is applied to an %K errors-in-the-variables model to justify the use %K of a form of latent root regression to estimate %K regression coefficients. However, it is further %K shown that in terms of the theory ordinary least %K squares is equally good, which suggests that the %K latter is to be prefered on grounds of computa- %K tional simplicity. %K Submitted by: G. W. Stewart %K Obtainable from: %K G. W. Stewart %K University of Maryland %K Department of Computer Science %K College Park, MD 20742 %K U.S.A. %K --------------- %K [6] On the Asymptotic Behavior of Scaled Singular Value %K and QR Decompositions. %K G. W. Stewart %K TR-1307, July 1983 %K Asymptotic expressions are derived for the singu- %K lar value decomposition of a matrix some of whose %K columns approach zero. Expressions are also %K derived for the QR factorization of a matrix some %K of whose rows approach zero. The expressions give %K insight into the method of weights for approximat- %K ing the solutions of constrained least squares %K problems. %K Submitted by: G. W. Stewart %K Obtainable from: G. W. Stewart (address above) %K --------------- %K [7] A Jacobi-like Algorithm for Computing the Schur %K Decomposition of a Non-Hermitian Matrix %K G. W. Stewart %K TR-1321, August 1983 %K (Dedicated to Peter Henrici on his sixtieth birthday.) %K This paper describes an iterative method for %K reducing a general matrix to upper triangular form %K by unitary similarity transformations. The method %K is similar to Jacobi's method for the symmetric %K eigenvalue problem in that it uses plane rotations %K to annihilate off-diagonal elements, and when the %K matrix is Hermitian it reduces to a variant of %K Jacobi's method. Although the method cannot com- %K pete with the QR algorithm in serial implementa- %K tion, it admits of a parallel implementation in %K which a double sweep of the matrix can be done in %K time proportional to the order of the matrix. %K Submitted by: G. W. Stewart %K Obtainable from: G. W. Stewart (address above) %K --------------- %K [8] On Lipschitzian Proximity Maps %K J. R. Respess and E. W. Cheney %K CNA-174, July 1981 %K [No abstract] %K Submitted by: David Kincaid %K Obtainable from: %K Center for Numerical Analysis %K R. L. Moore Hall, 13.150 %K University of Texas %K Austin, Texas 78712 %K (At the time the report is sent, an invoice in the amount of $1 per %K copy to cover duplication and postage will be included.) %K --------------- %K [9] The Characterization of Best Approximations in Tensor Product Spaces %K W. A. Light and E. W. Cheney %K CNA-175, September 1981 %K Given compact Hausdorff spaces S and T, a subspace W of %K C(SxT) is defined by %K W = G*C(T) + C(S)*H %K where G and H are finite dimensional subspaces of C(S) and C(T) %K respectively, and "*" represents the tensor product. Necessary and %K sufficient conditions are developed for a function in C(SxT) to %K have a best approximation in W. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [10] Generalized Conjugate Gradient Acceleration of Iterative Methods %K Kang Chang Jea %K CNA-176, February 1982 %K Acceleration of basic iterative methods is considered %K for solving large sparse systems of linear equations which are ei- %K ther not symmetrizable or for which no symmetrization matrix is %K conveniently available. Work on developing a method which will %K work as well as Chebyshev acceleration but requires no eigenvalue %K estimates is described. Algorithms are analyzed and numerical re- %K sults given. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [11] Adapting ITPACK Routines for Use on a Vector Computer %K David R. Kincaid, Thomas Oppe, and David M. Young %K CNA-177, August 1982 %K A description of recent work involving vectorization of %K the ITPACK package of iterative algorithms for the solution of %K large sparse systems of linear equations is given along with nu- %K merical results from runs on the CDC CYBER 203 and 205 computers. %K A more complete vectorization involving, in some cases, total re- %K design of algorithms is projected. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [12] ITPACK on Supercomputers %K David R. Kincaid and Thomas Oppe %K CNA-178, September 1982 %K Results of preliminary testing of a vector version of %K ITPACK are presented. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [13] The Best Approximation of Bivariate Functions by Separable Functions %K M. von Golitschek and E. W. Cheney %K CNA-179, December 1982 %K [No abstract] %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [14] The ITPACK Project: Past, Present, and Future %K David R. Kincaid and David M. Young %K CNA-180, March 1983 %K The objectives of the ITPACK project are reviewed, pro- %K gress to date is summarized, and plans for future work are out- %K lined. The present packages for use on scalar and vector compu- %K ters are described. An overview is given of developmental work on %K other software involving preconditioners and nonsymmetric proce- %K dures. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [15] Accelerating Nonsymmetrizable Iterative Methods %K David M. Young, Kang Chang Jea, and David R. Kincaid %K CNA-181, March 1983 %K We discuss recent work done at the University of Texas %K and elsewhere on accelerating basic iterative methods for the %K solution of systems of linear equations which have a nonsym- %K metrizable coefficient matrix. Approaches discussed include that %K of Concus and Golub and of Widlund as well as the use of normal %K equations, Chebyshev acceleration, and generalized conjugate gra- %K dient procedures. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [16] The ITPACK Software Package %K David M. Young and David R. Kincaid %K CNA-182, June 1983 %K We discuss iterative methods for the solution of sys- %K tems of linear equations in general and their implementation in %K ITPACK. Future modifications of the package including vectoriza- %K tion and modularization are considered. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [17] The Embedding of Proximinal Sets %K Carlo Franchetti and E. W. Cheney %K CNA-183, June 1983 %K Given Banach spaces Y < X < Z (where "<" denotes the %K subset relation) such that Y is proximinal in X, we discuss con- %K ditions under which Y remains proximinal when considered as a %K subspace of Z. %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [18] Minimal Projections in Tensor Product Spaces %K Carlo Franchetti and E. W. Cheney %K CNA-184, July 1983 %K [No abstract] %K Submitted by: David Kincaid %K Obtainable from: Center for Numerical Analysis %K (address above, $1 charge) %K --------------- %K [19] Splines in Interactive Computer Graphics %K Richard H. Bartels %K (Invited presentation, Dundee Conference, 1983) %K Computer graphics, particularly interactive computer graphics, is %K not, as the name might imply, concerned with drawing graphs, but %K rather with the broadest issues of manipulating, transforming, %K and displaying information in visual format. It is interactive %K in so far as operations can be carried out in real time -- which %K requires algorithms of high computational efficiency and low com- %K plexity. Splines are a valuable tool in graphics, but they are %K often applied in a way not used by the mathematician. This %K difference raises computational issues which the numerical %K analyst might otherwise never see. This talk will provide a %K brief introduction to such issues and follow with a study of two %K current developments. We begin with a review of the graphics en- %K vironment, mentioning the modelling and display process and %K pointing out some of the costly issues. The novel use of splines %K in interactive graphics comes through the construction of sur- %K faces as weighted averages of selected points, called control %K vertices in which B-splines are taken as the weighting functions. %K Some examples will illustrate the characteristics of this use of %K B-splines. With this background we consider two recent develop- %K ments. The first is the control-vertex recurrence of Riesenfeld, %K Cohen, and Lyche; the second is Barsky's work on geometric vs. %K mathematical continuity, and his introduction of Beta-splines. %K We will close with some results on current research concerned %K with a synthesis of these two developments. %K Submitted by: Richard Bartels %K Obtainable from: %K Richard Bartels %K University of Waterloo %K Department of Computer Science %K Waterloo, Ontario %K Canada N2L 3G1 %K --------------- %K [20] NUMERICAL DECOMPOSITION OF A CONVEX FUNCTION %K Mike Lamoureux Henry Wolkowicz %K Department of Mathematics Department of Mathematics %K Stanford University University of Alberta %K Given the n by p orthogonal matrix A and the convex function %K f: R(n) to R, we find two orthogonal matrices P and Q such that %K f is 'almost' constant on the convex hull of the columns of %K P and -P, f is 'sufficiently' nonconstant on the column space %K of Q, and the column spaces of P and Q provide an orthogonal %K direct sum decomposition of the column space of A. This %K provides a numerically stable algorithm for calculating the %K cone of directions of constancy, at a point x, of a convex %K function. Applications to convex programming are discussed. %K Submitted by: Henry Wolkowicz %K Obtainable from: %K Henry Wolkowicz %K Department of Mathematics %K University of Alberta %K Edmonton, Canada T6G 2G1 %K --------------- %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 2, Number 1 %K March, 1984 %K ================================================== %K [1] Daniel Szyld: %K A Two-level Iterative Method for Large Sparse %K Generalized Eigenvalue Calculations %K We present a method for the solution of the generalized symmetric %K eigenvalue problem. The matrices in the pencil are assumed to %K be too expensive to factor. The outer level of iteration is a step of %K either Inverse or Rayleigh Quotient iteration. The choice is made at %K each step to guarantee superlinear convergence to an eigenvalue in %K (or close to) a prescribed interval. The indefinite linear system is %K solved at each step with the conjugate gradient type method SYMMLQ, for %K which a variational formulation and error bounds are presented. %K Submitted by: Daniel Szyld %K Obtainable from: %K Daniel B. Szyld %K %K Institute for Economic Analysis %K New York University %K 269 Mercer Street, Second Floor %K New York, NY 10003 %K --------------- %K [2] Daniel Szyld: %K Preliminary Results in Implementing a Model of the %K World Economy on the Cyber 205: %K A Case of Large Sparse Nonsymmetric Linear Equations %K presented at the Cyber 200 Applications Seminar, %K Oct.10-12, 1983, NASA Godard Ctr. Md. %K A brief description of the Institutes' Model of the Wrold Economy is %K presented, together with our experience in converting the software to %K vector code.Includes running times. %K Submitted by: Daniel Szyld %K Obtainable from: %K Daniel B. Szyld %K (address above) %K --------------- %K [3] G. W. Stewart %K A Generalization of the %K Eckart-Young Approximation Theorem %K TR-1325 %K Department of Computer Science %K University of Maryland at College Park %K September 1983 %K The Eckart-Young theorem solves the problem of %K approximating a matrix by one of lower rank. How- %K ever, the approximation generally differs from the %K original in all its elements. In this paper it is %K shown how to obtain a best approximation of lower %K rank in which a specified set of columns of the %K matrix remains fixed. The paper concludes with %K some applications of the generalization. %K Submitted by: G. W. Stewart %K Obtainable from: %K G. W. Stewart %K %K Department of Computer Science %K and Institute for Physical Science and Technology %K The University of Maryland at College Park %K College Park, Maryland 20742 %K --------------- %K [4] Dianne P. O'Leary and G. W. Stewart %K DATA-FLOW ALGORITHMS FOR %K PARALLEL MATRIX COMPUTATIONS %K In this work we develop some algorithms and tools for solv- %K ing matrix problems on parallel processing computers. %K Operations are synchronized through data-flow alone, which %K makes global synchronization unnecessary and enables the %K algorithms to be implemented on machines with very simple %K operating systems and communications protocols. As exam- %K ples, we present algorithms that form the main modules for %K solving Liaponuv matrix equations. We compare this approach %K to wavefront array processors and systolic arrays, and note %K its advantages in handling missized problems, in evaluating %K variations of algorithms or architectures, in moving algo- %K rithms from system to system, and in debugging parallel %K algorithms on sequential machines. %K Submitted by: G. W. Stewart %K Obtainable from: %K G. W. Stewart %K (address above) %K --------------- %K [5] GENE H. GOLUB AND DAVID MAYERS %K THE USE OF PRE-CONDITIONING OVER IRREGULAR REGIONS %K Some ideas and techniques for solving elliptic pde.'s over irregular regions %K is discussed. The basic idea is to break up the domain into subdomains and %K then to use the pre-conditioned conjugate gradient method for obtaining the %K solution over the entire domain. The solution of Poisson's equation over a %K T-shaped region is described in some detail and a numerical example is given. %K Submitted by: Gene H. Golub %K Obtainable from: %K Gene H. Golub %K %K Computer Science Department %K Stanford University %K Stanford, California 94305 %K --------------- %K [6] Robert Schreiber %K Computing Genrealized Inverses and Eigenvalues %K of Symmetric Matrices Using Systolic Arrays. %K Manuscript NA-83-03. %K Stanford NA Project %K New systolic arrays methods are presented for tridiagonalization %K of a dense, symmetric n x n matrix in O(n**3/2) time, tridiagonalization %K of a matrix of bandwidth b in O(bn) time, and finding the eigenvalues of a %K symmetric tridiagonal matrix in O(n) time. Systolic arrays for implementing %K an iterative method for the generalized inverse are given. They allow %K computation of the generalized inverse of an m x n matrix in O(m) time. %K Submitted by: Gene Golub %K Obtainable from: %K Gene Golub %K (address above) %K --------------- %K [7] Rodrigo Fontecilla %K %K Technical Report 1370 %K Department of Computer Science %K University of Maryland at College Park %K January 1984 %K In solving nonlinear equality constrained optimization prob- %K lems using secant methods we often have to solve two or %K three linear systems of equations at each iteration. We use %K the theory developed by Dembo, Eisenstat and Steihaug in %K inexact Newton methods to solve at least one of the linear %K system inexactly. We analyze the case when the number of %K constraints is much smaller than the number of variables. In %K this case we solve the smallest linear system (the one used %K to find the multipliers) exactly while solving the bigger %K system (the one giving the step on the variables) inexactly %K at each iteration. Algorithms using the DFP and the BFGS %K secant updates are proposed. Conditions on the residual are %K given in order to allow the user the possibility of a trade- %K off between the rate of convergence (q-superlinear) and the %K amount of work per iteration. %K Submitted by: Rodrigo Fontecilla %K Obtainable from: %K Rodrigo Fontecilla %K <rod%umcp-cs@csnet-cic> %K Department of Computer Science and %K Institute for Physical Science and Technology %K University of Maryland %K College Park, Maryland 20742 %K --------------- %K [8] Richard H. Bartels and John J. Jezioranski %K On Least Squares Fitting Using Orthogonal Multinomials %K Forsythe (1) has given a method for generating basis polynomials %K in a single variable which are orthogonal with respect to a given %K inner product. Weisfeld (2) later demonstrated that Forsythe's %K approach could be extended to polynomials in an arbitrary number %K of variables. In this paper we sharpen Weisfeld's results and %K present a program for computing weighted, multinomial, least %K squares approximations to discrete data. %K ----- %K (1) G. E. Forsythe (1957), Generation and Use of Orthogonal %K Polynomials for Data-Fitting with a Digital Computer, J. SIAM %K 5, 74-87. %K (2) M. Weisfeld (1959), Orthogonal polynomials in Several %K Variables, Numer. Math. 1, 38-40. %K Submitted by: Richard H. Bartels %K Obtainable from: %K Richard H. Bartels %K University of Waterloo %K Department of Computer Science %K Waterloo, Ontario %K Canada N2L 3G1 %K --------------- %K [9] Ulrich Tulowitzki %K Inexact Successive Linearization Methods %K for Variational Inequality Problems %K We extend the inexact Newton rate of convergence characterization of %K Dembo, Eisenstat and Steihaug to variational inequality problems. Our %K characterization theorem is expressed in terms of the relative error %K in the solution of a linearized subproblem and does not require the %K set of active inequalities to remain constant. An immediate consequence %K of our theorem is a practical termination criterion for truncating %K an iterative procedure applied to the subproblems in successive %K quadratic programming algorithms for nonlinear optimization. %K Submitted by: Ulrich Tulowitzki %K Obtainable from: %K Ulrich Tulowitzki %K <Tulowitzki@YALE.ARPA> %K Yale University %K School of Organization and Management %K Box 1-A %K New Haven, CT 06520 %K --------------- %K [10] Ron S. Dembo and Siddhartha Sahi %K A Convergent Framework for %K Constrained Nonlinear Optimization %K Working Paper, Series B #69 %K School of Organization and Management %K Yale University %K September, 1983 %K We describe a simple, practical algorithmic framework for %K constrained nonlinear optimization. Any algorithm that %K may be expressed in this framework, and most existing %K algorithms can, will converge to a local minimum from an %K arbitrary feasible starting point. The framework is %K particularly suitable for the analysis and development of %K algorithms for large-scale optimization, since it permits %K radical changes in the active set to occur at each step %K and can be implemented in terms of quantities that are %K easily computed. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K Box 1-A %K New Haven, CT 06520 %K --------------- %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 2, Number 2 %K June, 1984 %K ================================================== %K [1] Ron S. Dembo and Ulrich Tulowitzki %K On the Minimization of Quadratic Functions %K Subject to Box Constraints %K SOM Working Paper Series B #71 %K Yale University School of %K Organization and Management %K 1983 %K We study efficient algorithms for very large quadratic problems %K subject to box constraints an propose some new convergent methods %K that permit the addition and deletion of many constraints each %K time a search direction is calculated. Numerical experiments, %K on problems of up to 10,000 variables, indicate that the perfor- %K mance of some of the proposed algorithms appears to be insensitive %K to the number of binding constraints at the optimal solution or %K to the starting point. Also it appears as if solving the box %K constrained problem is at worst marginally more expensive than %K solving the same problem without constraints. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K P.O. Box 1A %K New Haven, Conn. 06520 %K --------------- %K [2] Ron S. Dembo %K A Primal Truncated Newton Algorithm with %K Application to Large-Scale Nonlinear %K Network Optimization %K SOM Working Paper Series B #72 %K Yale University School of %K Organization and Management %K March 1983 %K We describe a new, convergent, primal-feasible algorithm for %K linearly constrained optimization. It is capable of rapid %K asymptotic behavior and has relatively low storage requirements. %K Its application to large scale nonlinear network optimization %K is discussed and computational results on problems of over %K 2,000 variables and 1,000 constraints are presented. Indications %K are that it could prove to be significantly better than known %K methods for this class of problem. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K (address above) %K --------------- %K ================================================= %K NUMERICAL ANALYSIS TITLES -- Volume 2, Number 3 %K September, 1984 %K ================================================= %K [1] R. C. Y. Chin, G. W. Hedstrom, and F. A. Howes %K Considerations on Solving Problems %K with Multiple Scales %K Lawrence Livermore National Laboratory %K Report UCRL-90791 %K (No abstract given.) %K Submitted by: Gerald Hedstrom, L-387 %K Obtainable from: %K Gerald Hedstrom, L-387 %K P. O. Box 808 %K LLNL %K Livermore, California 94550 %K (na.hedstrom@su-score.arpa) %K --------------- %K [2] R. C. Y. Chin, G. W. Hedstrom, and Lewis Thigpen %K Numerical methods in seismology %K J. Comput. Phys. 54 (1984), 18-56. %K (No abstract given.) %K Submitted by: Gerald Hedstrom, L-387 %K Obtainable from: %K Gerald Hedstrom, L-387 %K P. O. Box 808 %K LLNL %K Livermore, California 94550 %K (na.hedstrom@su-score.arpa) %K --------------- %K [3] R. C. Y. Chin, G. W. Hedstrom, and Lewis Thigpen %K Matrix methods in synthetic seismograms %K Geophys. J. R. astron. Soc. 77 (1984), 483-502. %K Submitted by: Gerald Hedstrom, L-387 %K Obtainable from: %K Gerald Hedstrom, L-387 %K P. O. Box 808 %K LLNL %K Livermore, California 94550 %K (na.hedstrom@su-score.arpa) %K --------------- %K [4] W. H. Enright and J. D. Pryce %K Two Fortran Packages for Assessing Initial %K Value Methods %K University of Toronto %K Computer Science Department %K TR 167/83 %K (No abstract given.) %K Submitted by: Kenneth R. Jackson %K Obtainable from: %K USENET {decvax linus ihnp4 allegra floyd decwrl garfield qucis cornell %K mcgill-vision sask watmath uw-beaver ubc-vision}!utcsrgv!enright %K or %K CSNET enright@toronto %K --------------- %K [5] Allan D. Jepson and Alastair Spence %K The Numerical Solution of Nonlinear %K Equations having Several Parameters %K University of Toronto %K Computer Science Department %K TR 168/83 %K (No abstract submitted.) %K Submitted by: Kenneth R. Jackson %K Obtainable from: %K USENET { decvax linus ihnp4 allegra floyd decwrl garfield qucis cornell %K mcgill-vision sask watmath uw-beaver ubc-vision }!utcsrgv!jepson %K or %K CSNET jepson@toronto %K --------------- %K [6] Tony F. Chan and Kenneth R. Jackson %K The use of Iterative Linear-Equation %K Solvers in Codes for Large Systems of %K Stiff IVPs for ODEs %K University of Toronto %K Computer Science Department %K TR 170/84. %K (No abstract given.) %K Submitted by: Kenneth R. Jackson %K Obtainable from: %K USENET { decvax linus ihnp4 allegra floyd decwrl garfield qucis cornell %K mcgill-vision sask watmath uw-beaver ubc-vision }!utcsrgv!krj %K CSNET krj@toronto %K --------------- %K [7] Robert Schreiber %K Computing Generalized Inverses %K and Eigenvalues of Symmetric Matrices %K Using Systolic Arrays. %K Stanford NA Manuscript %K NA-83-03. %K New systolic array methods are presented for tridiagonalization of a dense, %K symmetric n x n matrix in O(n**3/2) time, tridiagonalization of a matrix of %K bandwidth b in O(bn) time, and finding the eigenvalues of a symmetric, %K tridiagonal matrix in O(n) time. Systolic arrays for implementing an %K iterative method for the generalized inverse are given. They allow %K computation of the generalized inverse of an m x n matrix in O(m) time. %K Submitted by: Robert Schreiber %K Obtainable from: %K Robert Schreiber %K ESL Inc. %K 495 Java Drive, %K Sunnyvale, CA 94086. %K --------------- %K [8] Robert Schreiber %K Implementation of Adaptive Array Algorithms %K Stanford NA Manuscript %K NA-84-28. %K The computational procedures used to implement some standard and some %K recently proposed adaptive methods for direction finding and beamforming by %K sensor arrays are considered. Among these methods are the minimum %K variance beamforming method and several high-resolution methods that %K are based on the covariance matrix of the signal. We discuss %K recursive implementation of these procedures: the covariance matrix %K is periodically updated by the addition of a matrix of rank one. %K We propose some efficient, numerically stable algorithms for updating %K the solution. %K Submitted by: Robert Schreiber %K Obtainable from: %K Robert Schreiber %K ESL Inc. %K 495 Java Drive, %K Sunnyvale, CA 94086. %K --------------- %K [9] S. S. Chen, J. J. Dongarra, and C. C. Hsiung %K Multiprocessing Linear Algebra Algorithms %K on the CRAY X-MP-2: Experiences with %K Small Granularity %K Argonne National Laboratory Report %K MCS-TM-24 (February 1984) %K This paper gives an overview of the CRAY X-MP-2 general-purpose %K multiprocessor system and discusses how it can be used effective- %K ly to solve problems that have small granularity. An implementa- %K tion is described for linear algebra algorithms that solve sys- %K tems of linear equations when the matrix is general and when the %K matrix is symmetric and positive definite. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [10] J. J. Dongarra %K Performance of Various Computers %K Using Standard Linear Equations %K Software in a Fortran Environment %K Argonne National Laboratory %K Report MCS-TM-23 (updated August 1984) %K This note compares the performance of different computer systems %K while solving dense systems of linear equations using the LINPACK %K software in a Fortran environment. About 50 computers, ranging %K from a CRAY X-MP to the 68000-based systems such as the Apollo %K and SUN workstations, are compared. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [11] J. J. Dongarra and A. Sameh %K On Some Parallel Banded System Solvers %K Argonne National Laboratory Report %K MCS-TM-27 (March 1984) %K This paper describes algorithms for solving narrow banded systems %K and the Helmholtz difference equations that are suitable for mul- %K tiprocessing systems. The organization of the algorithms %K highlight the large grain parallelism inherent in the problems. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [12] J.J. Dongarra, E.L. Lusk, R.A. Overbeek, B.T. Smith, and D.C. Sorensen %K New Directions in Software for %K Advanced Computer Architectures %K Argonne National Laboratory Report %K MCS/TM 32 (August, 1984) %K This report contains a collection of short position papers that %K were prepared for the Workshop on Taxonomy of Parallel Algorithms %K sponsored by Los Alamos National Laboratory and held at Santa Fe, %K New Mexico Nov. 30 - Dec. 2, 1983. These papers represent the %K authors views on directions of research that should be undertaken %K with regards to programming methodology, algorithm design, and %K software implementation for advanced computer architectures. %K Several projects have been initiated by the authors within the %K general framework outlined in these articles since they were %K written. The concepts formulated here are expected to serve as a %K foundation for future work in multiprocessing. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [13] D. C. Sorensen %K Analysis of Pairwise Pivoting in Gaussian Elimination %K Argonne National Laboratory Report %K MCS-TM-26 (February 1984) %K The method of Gaussian Elimination using triangularization by %K elementary stabilized matrices constructed by pairwise pivoting %K is analyzed. It is shown that a variant of this scheme which is %K suitable for implementation on a parallel computer is numerically %K stable although the bound is larger than the one for the standard %K partial pivoting algorithm. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [14] D. C. Sorensen %K Buffering for Vector Performance %K on a Pipelined MIMD Machine %K Argonne National Laboratory Report %K MCS-TM-29 (April 1984) %K A technique is presented for obtaining vector performance from a %K pipelined MIMD computer that does not have hardwired vector in- %K structions. The specific computer in mind is the Denelcor HEP, %K but the technique might influence the use and possibly even the %K design of future machines with this type of architecture. This %K preliminary report presents the basic idea and demonstrates that %K it can be implemented. Buffering blocks of data to registers is %K used in conjunction with pipelined floating point operations to %K achieve vector performance. Empirical evidence is presented to %K show that up to 5.8 megaflop performance is possible from the %K Denelcor HEP on very regular tasks such as matrix vector pro- %K ducts. While this rate is not in the "super-computer" range, it %K is certainly respectable given the hardware capabilities of the %K HEP (this machine is rated at 10 MIPS peak). This performance %K indicates that an apparently minor refinement to the architectur- %K al design could provide very efficient vector operations in addi- %K tion to the parallelism and low-overhead synchronization already %K offered by the HEP architecture. %K Submitted by: Jack J. Dongarra %K Obtainable from: %K Jack J. Dongarra %K Mathematics and Computer Science Division %K Argonne National Laboratory %K Argonne, Illinois 60439 %K --------------- %K [15] Thomas F.Coleman and Alex Pothen %K The Sparse Null Space Problem %K Tecnical Report:TR 84-598 %K Computer Science %K Cornell University %K The sparse null space basis problem is the following. %K Let A be a given t*n matrix, t < n, of rank t. %K Find a matrix N, with the fewest nonzeroes in it, whose columns %K span the null space of A. This problem arises in the design of %K practical algorithms for large scale numerical optimization %K problems. In this paper we analyze the complexity of this problem, %K using combinatorial tools, and we propose approximation algorithms. %K Submitted by: Thomas F. Coleman %K Obtainable from: %K Thomas F.Coleman %K Computer Science Department %K Cornell University %K Ithace NY 14853 %K (coleman@cornell.csnet) %K --------------- %K [16] Richard H. Byrd %K An Example of Irregular Convergence in Some Constrained %K Optimization Methods That Use the Projected Hessian %K In this paper we give examples illustrating the behavior of the Coleman- %K Conn horizontal vertical method and of successive quadratic programming %K with a Hessian approximation exact on the tangent space of the constraints. %K One example shows that these methods in general are not one-step %K superlinearly convergent. %K Submitted by: Richard H. Byrd %K Obtainable from: %K Richard H. Byrd %K Department of Computer Science %K University of Colorado %K Boulder, Colorado 80309 %K --------------- %K [17] Richard H. Byrd %K On the Convergence of Constrained %K Optimization Methods with Accurate %K Hessian Information on a Subspace %K In this paper we analyze methods of the type proposed by Coleman and Conn %K for nonlinearly constrained optimization. We show that if the reduced %K Hessian approximation is sufficiently accurate, then the method generates %K a sequence of iterates which converges one-step superlinearly. %K This result applies to a quasi-Newton implementation. If the reduced exact %K Hessian is used the method has an R-order equal to that of the secant method. %K We also prove a similar result for a modified version of successive %K quadratic programming. Finally some parallels between convergence results %K for methods that approximate the reduced Hessian, and multiplier methods that %K use the reduced Hessian inverse are pointed out. %K Submitted by: Richard H. Byrd %K Obtainable from: %K Richard H. Byrd %K Department of Computer Science %K University of Colorado %K Boulder, Colorado 80309 %K --------------- %K [18] G. H. Golub, Pierre Manneback, and Phillippe Toint %K A COMPARISON BETWEEN SOME DIRECT AND %K ITERATIVE METHODS FOR LARGE SCALE %K GEODETIC LEAST SQUARES PROBLEMS %K The purpose of this paper is to describe and compare some %K numerical methods for solving large dimensional linear least squares %K problems that arise in geodesy and, more specially, from Doppler posi- %K tioning. The methods that are considered are the direct orthogonal decompo- %K sition, and the combination of conjugate gradient type algorithms with %K projects as well as the exploitatioin of "Property A". Numerical results %K are given and the respective advantage of thef methods are discussed with %K respect to such parameters as CPLU time, input/output and storage require- %K ments. Extensions of the results to more general problems are also %K discussed. %K Submitted by: G. H. Golub %K Obtainable from: %K G. H. Golub %K Stanford University %K Computer Science Department %K Stanford, CA 94305 %K (golub@navajo.arpa) %K --------------- %K [19] Franklin T. Luk %K A Jacobi-like Method for Computing %K the QR-decomposition %K Technical Report 84-612 %K Department of Computer Science %K Cornell University %K A parallel Jacobi-like method for computing the QR-decomposition of %K an nxn matrix is proposed. It requires O(n**2) processors and O(n) %K units of time. The method can be extended to handle an mxn matrix %K (m>=n). The requirements become O(n**2) processors and O(m) time. %K Submitted by: Franklin T. Luk %K Obtainable from: %K Librarian %K Department of Computer Science %K Cornell University %K Ithaca, NY 14853 %K --------------- %K [20] Franklin T. Luk %K A Triangular Processor Array for Computing %K the Singular Value Decomposition. %K Technical Report 84-625 %K Department of Computer Science %K Cornell University %K A triangular processor array for computing a singular value decomposition %K (SVD) of an mxn (m>=n) matrix is proposed. A Jacobi-type method is used %K to first triangularize the given matrix and then diagonalize the resultant %K triangular form. The requirements are O(m) time and n**2/4 + O(n) processors. %K Submitted by: Franklin T. Luk %K Obtainable from: %K Librarian %K Department of Computer Science %K Cornell University %K Ithaca, NY 14853 %K --------------- %K [21] Richard P. Brent and Franklin T. Luk %K The Solution of Singular Value Problems %K Using Systolic Arrays. %K Technical Report 84-626 %K Department of Computer Science %K Cornell University %K This paper concerns the computation of the singular value decomposition %K using systolic arrays. Two different linear time algorithms are presented. %K Submitted by: Franklin T. Luk %K Obtainable from: %K Librarian %K Department of Computer Science %K Cornell University %K Ithaca, NY 14853 %K --------------- %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 2, Number 4 %K November 23, 1984 %K ================================================== %K [1] Finbarr O'Sullivan and Grace Wahba %K A Cross Validated Bayesian Retrieval Algorithm %K For Non-Linear Remote Sensing Experiments %K To appear, Journal of Computational Physics %K We present a fully automated retrieval algorithm for estimating %K the solution of a mildly non linear Fredholm Integral Equation of %K the First Kind, when the data are discrete, noisy (experimental) %K measurements. This algorithm combines a simple Gauss-Newton interation %K with an extended form of Generalized Cross Validation , applied in the %K context of Tihonov Regularization with moment discretization. The %K performance of the algorithm is illustrated in the context of a remote %K sensing problem arising in satellite meteorology. %K Submitted by: Grace Wahba %K Obtainable from: %K Grace Wahba %K Department of Statistics %K University of Wisconsin, Madison %K (na.wahba@su-score.arpa) %K --------------- %K [2] ANDREW R. CONN %K NONLINEAR PROGRAMMING, EXACT PENALTY FUNCTIONS AND %K PROJECTION TECHNIQUES FOR NON-SMOOTH FUNCTIONS %K We present a personal overview of various %K approaches to solving nonlinear programs with %K nonlinear constraints that make use of the %K L-1 exact penalty function. %K The advantages, disadvantages and related %K remaining difficulties of these approaches will be %K considered. %K Finally some recent research and extensions %K are given. %K Submitted by: Andrew R. Conn %K Obtainable from: %K Andrew R. Conn %K Computer Science Department %K University of Waterloo %K Waterloo, Ontario N2L 3G1 %K CANADA %K (arconn@waterloo.csnet) %K --------------- %K [3] Richard H. Byrd and Robert B. Schnabel %K Continuity of the Null Space Basis and Constrained Optimization %K Univ. of Colorado Comp. Sci. Report %K CU-CS-271-84 %K Many constrained optimization algorithms use a basis for the %K null space of the matrix of constraint gradients. %K Recently, methods have been proposed that enable this null space %K basis to vary continuously as a function of the iterates in a %K neighborhood of the solution. %K This paper reports results from topology showing that, %K in general, there is no continuous function that generates the %K null space basis of all full rank rectangular matrices of a fixed size. %K We also give some indication of where these discontinuities must occur. %K We then propose an alternative implementation of a class of %K constrained optimization algorithms that uses approximations to the %K reduced Hessian of the Lagrangian but is independent of the choice %K of null space basis. %K Submitted by: Richard Byrd %K Obtainable from: %K Richard Byrd %K Department of Computer Science %K University of Colorado %K Boulder, Colorado 80309 %K (richard@boulder.csnet) %K --------------- %K [4] Y. Saad, A. Sameh, and P. Saylor %K Solving Elliptic Difference %K Equations on a Linear Array of Processors. %K In this paper we consider the organization of three iterative methods %K for solving self adjoint elliptic difference on a set of linearly con- %K nected processors. These algorithms are the cyclic Chebyshev semi-iterative %K scheme, a preconditioned conjugate gradient method, and a generalization %K of the Chebyshev method. We also consider their performance on this multi- %K processor as a function of the cost of interprocessor communication. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K Computer Science Dept. %K University of Illinois %K Urbana-Champaine, Illinois %K (saylor@uiuc.csnet) %K --------------- %K [5] Y. Saad, A. Sameh, and P. Saylor %K An Optimum Semi-iterative Method for %K Solving Any Linear Set With a Square Matrix. %K An algorithm is presented to solve Ax=b by computing optimum %K iteration parameters for Richardson's iteration. The algorithm re- %K quires some information on the location of the eigenvalues of A. %K The algorithm yields parameters well-suited for matrices for which %K Chebyshev parameters are not appropriate. %K It therefore supplements the Manteuffel algorithm, developed for the %K Chebyshev case. Numerical examples are described. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K (as above) %K --------------- %K [6] Y. Saad, A. Sameh, and P. Saylor %K A Generalization of the Golub-Welsch Algorithm to Complex %K Orthogonal and Kernel Polynomials. %K The Golub-Welsch algorithm is a stable algorithm to compute %K the roots of real orthogonal polynomials and kernel polynomials. %K It is generalized to the complex cases. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K (as above) %K --------------- %K [7] R.T. Gregory %K A finite number system for digital computers which %K gives exact results with rational operands. %K University of Tennessee Computer Science Report CS-84-57 %K A mapping is established between those rational numbers a/b with both %K a and b bounded in absolute value by a constant N, and a finite set of %K integers. When N is chosen to be the largest integer satisfying the %K inequality %K 2N*2 + 1 <= p %K where p is a very large prime, then the mapping is one-to-one and onto %K the set (0,1,2,...,p-1). Computation involving the rational numbers %K can be replaced by computation on the integers modulo p. In practice %K more than one modulus is used and this report deals with the multi- %K modulus case. %K Submitted by: Robert T. Gregory (shortly before his death) %K Obtainable from: %K Computer Science Department %K University of Tennessee %K Knoxville, Tenn. %K --------------- %K [8] Daniel Boley, University of Minnesota %K A Parallel Method for the Generalized Eigenvalue Problem %K University of Minnesota %K Computer Science Tech Report 84-21 %K Sept 1984. %K We present a parallel method to solve the %K generalized eigenvalue problem on a linear array %K of processors, each connected to their nearest %K neighbors and operating synchronously. We also %K include a wraparound connection from end to end. %K Our method is based on the well-known QZ algorithm %K of Moler and Stewart, which simultaneously reduces %K two nxn matrices to upper triangular form by %K orthogonal or unitary tranformations. We show how %K this algorithm may be partitioned and distributed %K over n+1 processors, achieving a speed-up over the %K serial algorithm of O(n). We use the concept of %K windows to describe the action of each processor %K at each step. We show how to incorporate single %K shifts, and how to apply orthogonal plane rota- %K tions on either side of a matrix without the need %K to transpose the matrix itself. %K Submitted by: Daniel Boley %K Obtainable from: %K Daniel Boley %K University of Minnesota %K (boley@umn-cs.csnet) %K --------------- %K [9] Ito, Kazufumi %K An iterative method for indefinite systems of linear equations %K ICASE Report No. 84-13, April 2, 1984, 21 pages %K Submitted to SIAM J. Numer. Anal. %K An iterative method for solving nonsymmetric indefinite linear systems is %K proposed. The method involves the successive use of a modified version of the %K conjugate residual method. A numerical example is given to illustrate the %K method. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K ICASE, Mail Stop l32C %K NASA Langley Research Center %K Hampton, VA 23665 %K (804) 865-3992. %K --------------- %K [10] Adams, Loyce M. and Harry F. Jordan %K Is SOR color-blind? %K ICASE Report No. 84-14, May 21, 1984, 39 pages %K Submitted to SIAM J. Sci. Statist. Comput. %K The work of Young [1971] showed that the Red/Black ordering and the %K natural rowwise ordering of matrices with Property A, such as those arising %K from the 5-point discretization of Poisson's equation, lead to SOR iteration %K matrices with identical eigenvalues. With the advent of parallel computers, %K multi-color point SOR schemes have been proposed for more complicated stencils %K on 2-dimensional rectangular grids, see Adams and Ortega [1982] for example, %K but to our knowledge, no theory has been provided for the rate of convergence %K of these methods relative to that of the natural rowwise scheme. %K New results show that certain matrices may be reordered so the resulting %K multi-color SOR matrix has the same eigenvalues as that for the original %K ordering. In addition, for a wide range of stencils, we show how to choose %K multi-color orderings so the multi-color SOR matrices have the same %K eigenvalues as the natural rowwise SOR matrix. The strategy for obtaining %K these results is based on "data flow" concepts and can be used to reach %K Young's conclusions above for the 5-point stencil. %K The importance of these results is threefold. Firstly, a constructive %K and easy means of finding these multi-colorings is a direct consequence of the %K theory; secondly, multi-color SOR methods can be found that have the same rate %K of convergence as the natural rowwise SOR method for a wide range of stencils %K used to discretize partial differential equations; and thirdly, these multi- %K color SOR methods can be efficiently implemented on a wide class of parallel %K computers. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [11] Gatski, Thomas B. and Chester E. Grosch %K A numerical study of the two- and three-dimensional %K unsteady Navier-Stokes equations in velocity-vorticity %K variables using compact difference schemes %K ICASE Report No. 84-15, May 22, 1984, 20 pages %K Proc. of 9th ICNMED, Saclay, France, June 23-29, 1984 %K LECTURE NOTES IN PHYSICS %K Springer-Verlag. %K A compact finite-difference approximation to the unsteady Navier-Stokes %K equations in velocity-vorticity variables is used to numerically simulate a %K number of flows. These include two-dimensional laminar flow of a vortex %K evolving over a flat plate with an embedded cavity, the unsteady flow over an %K elliptic cylinder, and aspects of the transient dynamics of the flow over a %K rearward facing step. The methodology required to extend the two-dimensional %K formulation to three-dimensions is presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [12] Hafez, Mohamed, M. and Phillips, Timothy N. %K A modified least squares formulation %K for a system of first-order equations %K ICASE Report No. 84-16, May 29, 1984, 21 pages %K Submitted to IMACS J. Numer. Math. %K Second-order equations in terms of auxiliary variables similar to %K potential and stream functions are obtained by applying a weighted least %K squares formulation to a first-order system. The additional boundary %K conditions which are necessary to solve the higher order equations are %K determined and numerical results are presented for the Cauchy-Riemann %K equations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [13] Hall, Phillip %K The Gortler vortex instability mechanism in %K three-dimensional boundary layers %K ICASE Report No. 84-17, June 6, 1984, 37 pages. %K Submitted to the Royal Society of London. %K It is well known that the two-dimensional boundary layer on a concave %K wall is centrifugally unstable with respect to vortices aligned with the basic %K flow for sufficiently high values of the Gortler number. However, in most %K situations of practical interest the basic flow is three-dimensional and %K previous theoretical investigations do not apply. In this paper the linear %K stability of the flow over an infinitely long swept wall of variable curvature %K is considered. If there is no pressure gradient in the boundary layer it is %K shown that the instability problem can always be related to an equivalent two- %K dimensional calculation. However, in general, this is not the case and even %K for small values of the crossflow velocity field dramatic differences between %K the two and three-dimensional problems emerge. In particular, it is shown %K that when the relative size of the crossflow and chordwise flow is (R**(-l/2)) %K where R is the Reynolds number of the flow, the most unstable mode is time- %K dependent. When the size of the crossflow is further increased, the vortices %K in the neutral location have their axes locally perpendicular to the vortex %K lines of the basic flow. In this regime the eigenfunctions associated with %K the instability become essentially 'centre modes' of the Orr-Sommerfeld %K equation destabilized by centrifugal effects. The critical Gortler number for %K such modes can be predicted by a large wavenumber asymptotic analysis; the %K results suggest that for order unity values of the ratio of the crossflow and %K chordwise velocity fields, the Gortler instability mechanism is almost %K certainly not operational. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [14] Gozani, J., Nachshon, A., and Turkel, E. %K Conjugate gradient coupled with %K multigrid for an indefinite problem %K ICASE Report No. 84-18, June 7, 1984, 11 pages %K Submitted to Proc. of 3rd IMACS International Symposium %K on Computer Methods for Partial Differential Equations %K Lehigh University, %K Bethlehem, PA, June 20-22, 1984 %K An iterative algorithm for the Helmholtz equation is presented. This %K scheme is based on the preconditioned conjugate gradient method for the normal %K equations. The preconditioning is one cycle of a multigrid method for the %K discrete Laplacian. The smoothing algorithm is red-black Gauss-Seidel and is %K constructed so it is a symmetric operator. The total number of iterations %K needed by the algorithm is independent of h. By varying the number of grids, %K the number of iterations depends only weakly on k when k**3 h**2 is %K constant. Comparisons with a SSOR preconditioner are presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [15] Malik, M. R., Zang, T. A., and Hussaini, M. Y. %K A spectral collocation method %K for the Navier-Stokes equations %K ICASE Report No. 84-19, June 8, 1984, 48 pages %K Submitted to J. Comput. Phys. %K A Fourier-Chebyshev spectral method for the incompressible Navier-Stokes %K equations is described. It is applicable to a variety of problems including %K some with fluid properties which vary strongly both in the normal direction %K and in time. In this fully spectral algorithm, a preconditioned iterative %K technique is used for solving the implicit equations arising from semi- %K implicit treatment of pressure, mean advection and vertical diffusion terms. %K The algorithm is tested by applying it to hydrodynamic stability problems in %K channel flow and in external boundary layers with both constant and variable %K viscosity. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [16] Davis, Stephen F. %K TVD finite difference schemes and artificial viscosity. %K ICASE Report No. 84-20, June 11, 1984, 35 pages %K Submitted to SIAM J. Sci. Statis. Comput. %K In this paper we show that the total variation diminishing (TVD) finite %K difference scheme which was analysed by Sweby can be interpreted as a Lax- %K Wendroff scheme plus an upwind weighted artificial dissipation term. We then %K show that if we choose a particular flux limiter and remove the requirement %K for upwind weighting, we obtain an artificial dissipation term which is based %K on the theory of TVD schemes, which does not contain any problem dependent %K parameters and which can be added to existing MacCormack method codes. %K Finally, we conduct numerical experiments to examine the performance of this %K new method. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [17] Canuto, C., Hariharan, S. I., and Lustman, L. %K Spectral methods for exterior %K elliptic problems %K ICASE Report No. 84-21, June 12, 1984, 33 pages. %K Submitted to Numer. Math. %K This paper deals with spectral approximations for exterior elliptic %K problems in two dimensions. As in the conventional finite difference or %K finite element methods, it is found that the accuracy of the numerical %K solutions is limited by the order of the numerical farfield conditions. We %K introduce a spectral boundary treatment at infinity, which is compatible with %K the "infinite order" interior spectral scheme. Computational results are %K presented to demonstrate the spectral accuracy attainable. Although we deal %K with a simple Laplace problem throughout the paper, our analysis covers more %K complex and general cases. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [18] Graif, E. and K. Kunisch %K Parameter estimation for the Euler-Bernoulli-beam %K ICASE Report No. 84-22, June 20, 1984, 43 pages. %K Submitted to IEEE Trans. Auto. Control. %K An approximation involving cubic spline functions for parameter %K estimation problems in the Euler-Bernoulli-beam equation (phrased as an %K optimization problem with respect to the parameters) is described and %K convergence is proved. The resulting algorithm was implemented and several of %K the test examples are documented. It is observed that the use of penalty %K terms in the cost functional can improve the rate of convergence. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [19] Rosen, I. Gary %K A numerical scheme for the identification of hybrid systems %K describing the vibration of flexible beams with tip bodies %K ICASE Report No. 84-23, June 21, 1984, 36 pages. %K Submitted to J. Math. Anal. Appl. %K A cubic spline based Galerkin-like method is developed for the %K identification of a class of hybrid systems which describe the transverse %K vibration of flexible beams with attached tip bodies. The identification %K problem is formulated as a least squares fit to data subject to the system %K dynamics given by a coupled system of ordinary and partial differential %K equations recast as an abstract evolution equation (AEE) in an appropriate %K infinite dimensional Hilbert space. Projecting the AEE into spline-based %K subspaces leads naturally to a sequence of approximating finite diemnsional %K identification problems. The solutions to these problems are shown to exist, %K are relatively easily computed, and are shown to, in some sense, converge to %K solutions to the original identification problem. Numerical results for a %K variety of examples are discussed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [20] Banks, H. Thomas and Katherine A. Murphy %K Estimation of coefficients and %K boundary parameters in hyperbolic systems %K ICASE Report No. 84-24, June 21, 1984, 52 pages. %K Submitted to SIAM J. Control Optim. %K We consider semi-discrete Galerkin approximation schemes in connection %K with inverse problems for the estimation of spatially varying coefficients and %K boundary condition parameters in second order hyperbolic systems typical of %K those arising in 1-D surface seismic problems. Spline based algorithms are %K proposed for which theoretical convergence results along with a representative %K sample of numerical findings are given. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [21] Vardi, A. %K A new minmax problem %K ICASE Report No. 84-25, June 26, 1984, 35 pages. %K Submitted to J. Optim., Theory and Appl. %K For the classical minimax problem we design a new active set strategy in which %K there are three types of functions: active, semi-active, and non-active. %K This technique will help in preventing zigzagging which often occurs when an %K active set strategy is used. Some of the inequality constraints are handled %K with slack variables. Also a trust region strategy is used in which at each %K iteration there is a sphere around the current point in which the local %K approximation of the function is trusted. The algorithm suggested in the %K paper was implemented into a successful computer program. Numerical results %K are provided. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [22] Banks, H. T. and I. G. Rosen %K Approximation techniques for parameter estimation and %K feedback control for distributed models of large flexible structures %K ICASE Report No. 84-26, June 22, 1984, 19 pages. %K Submitted to Workshop on Identification and Control of %K Flexible Space Structures, San Diego, CA, June 4-6, 1984, %K G. Rodgriguez (ed.). %K We discuss approximation ideas that can be used in parameter estimation %K and feedback control for Euler-Bernoulli models of elastic systems. Focusing %K on parameter estimation problems, we outline how one can obtain convergence %K results for cubic spline-based schemes for hybrid models involving an elastic %K cantilevered beam with tip mass and base acceleration. Sample numerical %K findings are also presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [23] Turkel, E. and Bram van Leer %K Flux vector splitting and Runge-Kutta methods %K for the Euler equations %K ICASE Report No. 84-27, June 23, 2984, 9 pages. %K To appear in Proc. of the 9th Intl. Conference on Numerical Methods %K in Fluid Dynamics, Saclay, France, June 25-29, 1984. %K Runge-Kutta schemes have been used as a method of solving the Euler %K equations exterior to an airfoil. In the past this has been coupled with %K central differences and an artificial viscosity in space. In this study we %K couple the Runge-Kutta time stepping scheme with an upwinded space approxima %K tion based on flux-vector splitting. Several acceleration techniques are also %K considered including a local time step, residual smoothing and multigrid. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [24] Turkel, Eli %K Fast solutions to the steady state compressible and %K incompressible fluid dynamics equations %K ICASE Report No. 84-28, June 23, 1984, 8 pages. %K To appear in Proc. of the 9th Intl. Conference on %K Numerical Methods in Fluid Dynamics %K Saclay, France, June 25-29, 1984. %K It is well known that for low speed flows the use of the compressible %K fluid dynamic equations is inefficient. The use of an explicit scheme %K requires delta-t to be bounded by 1/c. However, the physical parameters %K change over time scales of order 1/u which is much larger. Hence, it is not %K appropriate to use explicit schemes for very subsonic flows. Implicit schemes %K are hard to vectorize and frequently do not converge quickly for very subsonic %K flows. We shall demonstrate that if one is only interested in the steady %K state then a minor change to an existing code can greatly increase the %K efficiency of an explicit method. Even when using an implicit method the %K proposed changes increase the efficiency of the scheme. We shall first %K consider the Euler equations for low speed flows and then incompressible %K flows. We then indicate how to generalize the method to include viscous %K effects. We also show how to accelerate supersonic flow by essentially %K decoupling the equations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [25] Gottlieb, D. %K Spectral methods for compressible flow problems %K ICASE Report No. 84-29, June 21, 1984, 20 pages. %K Proc. 9th Intl. Conference on %K Numerical Methods in Fluid Dynamics %K Saclay, France, June 25-29, 1984. %K In this article we review recent results concerning numerical simulation %K of shock waves using spectral methods. We discuss shock fitting techniques as %K well as shock capturing techniques with finite difference artificial %K viscosity. We also discuss the notion of the information contained in the %K numerical results obtained by spectral methods and show how this information %K can be recovered. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [26] Ipsen, Ilse C. F. %K Singular value decomposition with systolic arrays %K ICASE Report No. 84-30, July 9, 1984, 22 pages. %K Proc. of the Society of Photo-Optical Engineers %K San Diego, CA, August 19-24, 1984. %K Systolic arrays for determining the Singular Value Decomposition of a %K matrix A of bandwidth w are presented. After A has been %K reduced to bidiagonal form B by means of Givens plane rotations, the %K differential equations. Part II: The linear quadratic control problem. %K ICASE Report No. 84-31, July 6, 1984, 65 pages. Submitted to SIAM J. %K Control Optim. %K The numerical scheme based on the Legendre-tau approximation is proposed %K to approximate the feedback solution to the linear quadratic optimal control %K problem for hereditary differential systems. The convergence property is %K established using Trotter ideas. The method yields very good approximations %K at low orders and provides an approximation technique for computing closed- %K loop eigenvalues of the feedback system. A comparison with existing methods %K (based on "averaging" and "spline" approximations) is made. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [27] Turkel, Eli %K Acceleration to a steady state for the Euler equations %K ICASE Report No. 84-32, July 7, 1984, 45 pages. %K Proc. INRIA Euler Workshop (SIAM) %K Rocquencourt, France, December 7-9, 1983. %K A multi-stage Runge-Kutta method is analyzed for solving the Euler %K equations exterior to an airfoil. Highly subsonic, transonic and supersonic %K flows are evaluated. Various techniques for accelerating the convergence to a %K steady state are introduced and analyzed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [28] Bokhari, Shahid H. and A. D. Raza %K Augmenting computer networks %K ICASE Report No. 84-33, July 8, 1984, 16 pages. %K Proc. 1984 Intl. Conference on Parallel Processing %K Bellaire, MI, August 21-24, 1984. %K Three methods of augmenting computer networks by adding at most one link %K per processor are discussed. %K 1. A tree of N nodes may be augmented such that the resulting graph %K has diameter no greater than 4 log2((N+2)/3)-2. This 0(N**3) algorithm can %K be applied to any spanning tree of a connected graph to reduce the diameter of %K that graph to 0(log N). %K 2. Given a binary tree T and a chain C of N nodes each, C may be %K augmented to produce C' so that T is a subgraph of C'. This algorithm %K is 0(N) and may be used to produce augmented chains or rings that have %K diameter no greater than 2 log2 (N+2)/3) and are planar. %K 3. Any rectangular two-dimensional 4 (8) nearest neighbor array of %K size N = 2**k may be augmented so that it can emulate a single step shuffle- %K exchange network of size N/2 in 3(t) time steps. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [29] Reed, Daniel A. and Merrell L. Patrick %K A model of asynchronous iterative algorithms %K for solving large, sparse, linear systems %K ICASE Report No. 84-34, July 31, 1984, 27 pages. %K Proceedings of the 1984 International %K Conference on Parallel Processing %K August 21-24, 1984, Bellaire, MI. %K Solving large, sparse, linear systems of equations is one of the %K fundamental problems in large scale scientific and engineering computation. %K A model of a general class of asynchronous, iterative solution methods for %K linear systems is developed. In the model, the system is solved by creating %K several cooperating tasks that each compute a portion of the solution vector. %K This model is then analyzed to determine the expected intertask data transfer %K and task computational complexity as functions of the number of tasks. Based %K on the analysis, recommendations for task partitioning are made. These %K recommendations are a function of the sparseness of the linear system, its %K structure (i.e., randomly sparse or banded), and dimension. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [30] Reed, Daniel A. and Merrell L. Patrick %K Parallel, iterative solution of sparse linear systems: %K Models and architectures %K ICASE Report No. 84-35, August 1, 1984, 45 pages. %K Submitted to Parallel Computing. %K Solving large, sparse, linear systems of equations is a fundamental %K problem in large scale scientific and engineering computation. A model of a %K general class of asychronous, iterative solution methods for linear systems is %K developed. In the model, the system is solved by creating several cooperating %K tasks that each compute a portion of the solution vector. A data transfer %K model predicting both the probability that data must be transferred between %K two tasks and the amount of data to be transferred is presented. This model %K is used to derive an execution time model for predicting parallel execution %K time and an optimal number of tasks given the dimension and sparsity of the %K coefficient matrix and the costs of computation, synchronization, and %K communication. %K The suitability of different parallel architectures for solving randomly %K sparse linear systems is discussed. Based on the complexity of task %K scheduling, one parallel architecture, based on a broadcast bus, is presented %K and analyzed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [31] Tadmor, Eitan %K The well-posedness of the Kuramoto-Sivashinsky equation. %K ICASE Report No. 84-36, August 7, 1984, 22 pages. %K Submitted to SIAM J. Appl. Math. %K The Kuramoto-Sivashinsky equation arises in a variety of applications, %K among which are modeling reaction-diffusion systems, flame-propagation and %K viscous flow problems. It is considered here, as a prototype to the larger %K class of generalized Burgers equations: those consist of quadratic %K nonlinearity and arbitrary linear parabolic part. We show that such equations %K are well-posed, thus admitting a unique smooth solution, continuously %K dependent on its initial data. As an attractive alternative to standard %K energymethods, existence and stability are derived in this case, by "patching" %K in the large short time solutions without "loss of derivatives". %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [32] Lustman, Liviu %K The time evolution of spectral discretizations of hyperbolic %K systems %K ICASE Report No. 84-37, August 7, 1984, 12 pages. %K Submitted to SIAM J. Numer. Anal. %K A Chebyshev collocation spectral method, applied to hyperbolic systems is %K considered, particularly for those initial boundary value problems which %K possess only solutions tending to zero at large times. It is shown that the %K numerical solutions of the system will also vanish at infinity, if and only %K if, the numerical solution of a scalar equation of the same type does. This %K result is then generalized for other spectral approximations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [33] Bayliss, A., C. I. Goldstein, and E. Turkel %K On accuracy conditions for the %K numerical computation of waves %K ICASE Report No. 84-38, August 9, 1984, 16 pages. %K Submitted to J. Comput. Phys. %K The Helmholtz equation with a variable index of refraction, and a %K suitable radiation condition at infinity serves as a model for a wide variety %K of wave propagation problems. Such problems can be solved numerically by first %K truncating the given unbounded domain and imposing a suitable outgoing %K radiation condition on an artificial boundary and then solving the resulting %K problem on the bounded domain by direct discretization (for example, using a %K finite element method). In practical applications, the mesh size h and the %K wave number K, are not independent but are constrained by the accuracy of the %K desired computation. It will be shown that the number of points per %K wavelength, measured by l/Kh, is not sufficient to determine the accuracy of %K a given discretization. For example, the quantity K**3 h**2 is shown to %K determine the accuracy in the L-two norm for a second-order discretization %K method applied to several propagation models. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [34] Hariharan, S. I. %K Numerical solutions of acoustic wave propagation %K problems using Euler computations %K ICASE Report No. 84-39, August 10, 1984, 29 pages. %K Proc. of the AIAA 9th Aeroacoustics Conference %K Williamsburg, VA, August 15-17, 1984. %K This paper reports solution procedures for problems arising from the %K study of engine inlet wave propagation. The first problem is the study of %K sound waves radiated from cylindrical inlets. The second one is a quasi-one- %K dimensional problem to study the effect of nonlinearities and the third one is %K the study of nonlinearities in two dimensions. In all three problems Euler %K computations are done with a fourth-order explicit scheme. For the first %K problem results are shown in agreement with experimental data and for the %K second problem comparisons are made with an existing asymptotic theory. The %K third problem is part of an ongoing work and preliminary results are presented %K for this case. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [35] Tadmor, Eitan %K The exponential accuracy of Fourier %K and Tchebyshev differencing methods %K ICASE Report No. 84-40, August 20, 1984, 24 pages. %K Submitted to SIAM J. Numer. Anal. %K It is shown that when differencing analytic functions using the %K pseudospectral Fourier or Tchebyshev methods, the error committed decays to %K zero at an exponential rate. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [36] Gannon, Dennis and John Van Rosendale %K On the impact of communication complexity %K in the design of parallel numerical algorithms %K ICASE Report No. 84-41, August 22, 1984, 37 pages. %K To appear in IEEE Trans. on Computers. %K This paper describes two models of the cost of data movement in parallel %K numerical algorithms. One model is a generalization of an approach due to %K Hockney, and is suitable for shared memory multiprocessors where each %K processor has vector capabilities. The other model is applicable to highly %K parallel nonshared memory MIMD systems. In the second model, algorithm %K performance is characterized in terms of the communication network design. %K Techniques used in VLSI complexity theory are also brought in, and algorithm %K independent upper bounds on system performance are derived for several %K problems that are important to scientific computation. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [37] Ito, Kazufumi %K Legendre-Tau approximation for functional differential %K equations, Part III: Eigenvalue approximations and uniform stability. %K ICASE Report No 84-42, August 24, 1984, 34 pages. %K Proc. Second International Conference on Control Theory %K for Distributed Parameter Systems and Applications %K Vorau, Austria, 1984. %K The stability and convergence properties of the Legendre-tau %K approximation for hereditary differential systems are analyzed. We derive a %K characteristic equation for the eigenvalues of the resulting approximate %K system. As a result of this derivation we are able to establish that the %K uniform exponential stability of the solution semigroup is preserved under %K approximation. It is the key to obtaining the convergence of approximate %K solutions of the algebraic Riccati equation in trace norm. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [38] Berger, M. J. %K On conservation at grid interfaces %K ICASE Report No. 84-43, September 7, 1984, 25 pages. %K Submitted to J. Comput. Phys. %K This paper considers the solution of hyperbolic systems of conservation %K laws on discontinuous grids. In particular, we consider what happens to %K conservation at grid interfaces. A procedure is presented to derive %K conservative difference approximations at the grid interfaces for two- %K dimensional grids which overlap in an arbitrary configuration. The same %K procedures are applied to compute interface formulas for grids which are %K refined in space and/or time, and for continuous grids where a switch in the %K scheme causes the discontinuity. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [39] Osher, S. and S. Chakravarthy %K Very high order accurate TVD schemes %K ICASE Report No. 84-44, September 10, 1984, 61 pages. %K Submitted to SIAM J. Numer. Anal. %K A systematic procedure for constructing semi-discrete families of 2m-1 %K order accurate, 2m order dissipative, variation diminishing, 2m+1 point %K bandwidth, conservation form approximations to scalar conservation laws is %K presented. Here m is any integer between 2 and 8. Simple first-order forward %K time discretization, used together with any of these approximations to the %K space derivatives, also results in a fully discrete, variation diminishing %K algorithm. These schemes all use simple flux limiters, without which each of %K these fully discrete algorithms is even linearly unstable. Extensions to %K systems, using a nonlinear field-by-field decomposition are presented, and %K shown to have many of the same properties as in the scalar case. For linear %K systems, these nonlinear approximations are variation diminishing, and hence %K convergent. A new and general criterion for approximations to be variation %K diminishing is also given. Finally, numerical experiments using some of these %K algorithms are presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [40] Elcrat, A. R. and L. N. Trefethen %K Classical free-streamline flow over a polygonal obstacle %K ICASE Report No. 84-45, September 10, 1984, 61 pages. %K Submitted to J. Comput. Appl. Math. %K In classical Kirchhoff flow, an ideal incompressible fluid flows past an %K obstacle and around a motionless wake bounded by free streamlines. Since 1869 %K it has been known that in principle, the two-dimensional Kirchhoff flow over a %K polygonal obstacle can be determined by constructing a conformal map onto a %K polygon in the log-hodograph plane. In practice, however, this idea has %K rarely been put to use except for very simple obstacles, because the conformal %K mapping problem has been too difficult. This paper presents a practical %K method for computing flows over arbitrary polygonal obstacles to high accuracy %K in a few seconds of computer time. We achieve this high speed and flexibility %K by working with a modified Schwarz-Christoffel integral that maps onto the %K flow region directly rather than onto the log-hodograph polygon. This integral %K and its associated parameter problem are treated numerically by methods %K developed earlier by Trefethen for standard Schwarz-Christoffel maps. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [41] Krause, Egon %K Review of some vortex relations %K ICASE Report No. 84-46, September 12, 1984, 8 pages. %K Submitted to Computer and Fluids. %K The evaluation of the circulation from numerical solutions of the %K momentum and energy equations is discussed for incompressible and compressible %K flows. It is shown how artificial damping directly influences the time rate %K of change of the circulation. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [42] Tal-Ezer, Hillel %K A pseudospectral Legendre method for hyperbolic equations %K with an improved stability condition %K ICASE Report No. 84-48, September 14, 1984, 46 pages. %K Submitted to J. Comput. Phys. %K A new pseudospectral method is introduced for solving hyperbolic partial %K differential equations. This method uses different grid points than %K previously used pseudospectral methods: in fact the grid points are related %K to the zeroes of the Legendre polynomials. The main advantage of this method %K is that the allowable time step is proportional to the inverse of the number %K of grid points 1/N rather than to 1/N**2 (as in the case of other %K pseudospectral methods applied to mixed initial boundary value problems). A %K highly accurate time discretization suitable for these spectral methods is %K discussed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [43] Bayliss, A., C. I. Goldstein, and E. Turkel %K The numerical solution of the Helmholtz equation for %K wave propagation problems in underwater acoustics %K ICASE Report No. 84-49, September 17, 1983, 29 pages. %K Submitted to J. Comput. Math. Appl. %K The Helmholtz Equation with a variable index of refraction, and a %K suitable radiation condition at infinity serves as a model for a %K wide variety of wave propagation problems. A numerical algorithm has %K been developed and a computer code implemented that can effectively %K solve this equation in the intermediate frequency range. The equation %K is discretized using the finite element method, thus allowing for the %K modeling of complicated geometries (including interfaces) and %K complicated boundary conditions. A global radiation boundary condition %K is imposed at the far field boundary that is exact for an arbitrary %K number of propagating modes. %K The resulting large, non-selfadjoint system of linear equations with %K indefinite symmetric part is solved using the preconditioned conjugate %K gradient method applied to the normal equations. A new preconditioner is %K developed based on the multigrid method. This preconditioner is vectorizable %K and is extremely effective over a wide range of frequencies provided the %K number of grid levels is reduced for large frequencies. A heuristic argument %K is given that indicates the superior convergence properties of this %K preconditioner. The relevant limit to analyze convergence is for K %K increasing and a fixed prescribed accuracy level. The efficiency and %K robustness of the numerical algorithm is confirmed for large acoustic models, %K including interfaces with strong velocity contrasts. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [44] Burns, John A., Ito, Kazufumi, Powers, Robert K. %K Chandrasekhar equations and computational %K algorithms for distributed parameter systems %K ICASE Report No. 84-50, September 20, 1984, 23 pages. %K Proc. of 23rd Conference on Decision and Control, %K December 12-14, 1984, Las Vegas, NV. %K In this paper we consider the Chandrasekhar equations arising in optimal %K control problems for linear distributed parameter systems. The equations are %K derived via approximation theory. This approach is used to obtain existence, %K uniqueness and strong differentiability of the solutions and provides the %K basis for a convergent computation scheme for approximating feedback gain %K operators. A numerical example is presented to illustrate these ideas. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [45] Petter E. Bjorstad and Olof B. Widlund %K Iterative Methods for the Solution of Elliptic %K Problems on Regions Partitioned into Substructures %K Finite element problems can often naturally be divided into subproblems which %K correspond to subregions into which the region has been partitioned or from %K which it was originally assembled. A class of iterative methods is discussed %K in which these subproblems are solved by direct methods,while the interaction %K across the curves or surfaces which divide the region is handled by a conju- %K gate gradient method. A mathematical framework for this workis provided by %K regularity theory for elliptic finite element problems and by block Gauss %K elimination. A full development of the theory,which shows that certain of %K these methods are optimal, is given for Lagrangian finite element approxi- %K mations of second order linear elliptic problems in the plane.Results from %K numerical experiments are also reported. %K Submitted by: Olaf Widlund %K Obtainable from: %K Olaf Widlund %K Courant Institute %K 251 Mercer St. %K N.Y., N.Y. 10012. %K (WIDLUND@NYU-ACF1.ARPA) %K --------------- %K [46] Ron S. Dembo and Ulrich Tulowitzki %K Local Convergence Analysis for Successive %K Inexact Quadratic Programming Methods %K SOM Working Paper Series B #78 %K Yale School of Organization and Management %K October, 1984 %K Successive quadratic programming (SQP) methods for the %K solution of constrained nonlinear optimization problems are %K attractive because they converge rapidly from any sufficiently %K good initial solution. However, solving the quadratic subproblems %K at each stage can be expensive, particularly if the number of %K unknowns is large and may be not justified when far away from %K an optimal solution. Therefore, we consider a class of successive %K inexact quadratic programming (SIQP) methods that solve the %K subproblems only approximately. We characterize the rate of %K convergence in terms of the relative error incurred in the %K subproblems in a manner that does not assume that the set of %K active constraints remains constant. This leads to practical %K termination criteria for truncating various iterative algorithms %K applied to the quadratic subproblems. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K P.O. Box 1A %K New Haven, Conn. 06520 %K --------------- %K [47] Ron S. Dembo and Ulrich Tulowitzki %K Sequential Truncated Quadratic Programming Methods %K To appear in the Proceedings of the SIAM Conference %K on Numerical Optimization, Boulder, Colo., June, 1984 %K In a sequential quadratic programming (SQP) method for nonlinear %K optimization it is possible to truncate an iterative procedure, applied %K to each quadratic subproblem, prior to reaching a solution, without %K affecting the asymptotic rate of convergence. We describe some %K practical termination criteria which ensure that an SQP method, executed %K without exact solution of the QP subproblem, inherits the rate of %K convergence of its (exact) SQP counterpart. Numerical experiments on %K linearly-constrained problems of up to 2230 variables indicate that %K substantial savings can be achieved by inexact solution of the QP %K subproblems with little or no adverse effect on the convergence rate. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K P.O. Box 1A %K New Haven, Conn. 06520 %K --------------- %K From rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa Tue Jul 16 13:45:20 1985 %K Received: from csnet-relay (csnet-relay.arpa.ARPA) by anl-mcs.ARPA ; Tue, 16 Jul 85 13:42:53 cdt %K Received: from waterloo by csnet-relay.csnet id a001168; 16 Jul 85 14:21 EDT %K Date: Sun, 14 Jul 85 20:30:55 edt %K From: Richard Bartels <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Message-Id: <8507150030.AA20616@watcgl.UUCP> %K To: dongarra@anl-mcs %K Status: R %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 2, Number 4 %K November 23, 1984 %K ================================================== %K [1] Finbarr O'Sullivan and Grace Wahba %K A Cross Validated Bayesian Retrieval Algorithm %K For Non-Linear Remote Sensing Experiments %K To appear, Journal of Computational Physics %K We present a fully automated retrieval algorithm for estimating %K the solution of a mildly non linear Fredholm Integral Equation of %K the First Kind, when the data are discrete, noisy (experimental) %K measurements. This algorithm combines a simple Gauss-Newton interation %K with an extended form of Generalized Cross Validation , applied in the %K context of Tihonov Regularization with moment discretization. The %K performance of the algorithm is illustrated in the context of a remote %K sensing problem arising in satellite meteorology. %K Submitted by: Grace Wahba %K Obtainable from: %K Grace Wahba %K Department of Statistics %K University of Wisconsin, Madison %K (na.wahba@su-score.arpa) %K --------------- %K [2] ANDREW R. CONN %K NONLINEAR PROGRAMMING, EXACT PENALTY FUNCTIONS AND %K PROJECTION TECHNIQUES FOR NON-SMOOTH FUNCTIONS %K We present a personal overview of various %K approaches to solving nonlinear programs with %K nonlinear constraints that make use of the %K L-1 exact penalty function. %K The advantages, disadvantages and related %K remaining difficulties of these approaches will be %K considered. %K Finally some recent research and extensions %K are given. %K Submitted by: Andrew R. Conn %K Obtainable from: %K Andrew R. Conn %K Computer Science Department %K University of Waterloo %K Waterloo, Ontario N2L 3G1 %K CANADA %K (arconn@waterloo.csnet) %K --------------- %K [3] Richard H. Byrd and Robert B. Schnabel %K Continuity of the Null Space Basis and Constrained Optimization %K Univ. of Colorado Comp. Sci. Report %K CU-CS-271-84 %K Many constrained optimization algorithms use a basis for the %K null space of the matrix of constraint gradients. %K Recently, methods have been proposed that enable this null space %K basis to vary continuously as a function of the iterates in a %K neighborhood of the solution. %K This paper reports results from topology showing that, %K in general, there is no continuous function that generates the %K null space basis of all full rank rectangular matrices of a fixed size. %K We also give some indication of where these discontinuities must occur. %K We then propose an alternative implementation of a class of %K constrained optimization algorithms that uses approximations to the %K reduced Hessian of the Lagrangian but is independent of the choice %K of null space basis. %K Submitted by: Richard Byrd %K Obtainable from: %K Richard Byrd %K Department of Computer Science %K University of Colorado %K Boulder, Colorado 80309 %K (richard@boulder.csnet) %K --------------- %K [4] Y. Saad, A. Sameh, and P. Saylor %K Solving Elliptic Difference %K Equations on a Linear Array of Processors. %K In this paper we consider the organization of three iterative methods %K for solving self adjoint elliptic difference on a set of linearly con- %K nected processors. These algorithms are the cyclic Chebyshev semi-iterative %K scheme, a preconditioned conjugate gradient method, and a generalization %K of the Chebyshev method. We also consider their performance on this multi- %K processor as a function of the cost of interprocessor communication. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K Computer Science Dept. %K University of Illinois %K Urbana-Champaine, Illinois %K (saylor@uiuc.csnet) %K --------------- %K [5] Y. Saad, A. Sameh, and P. Saylor %K An Optimum Semi-iterative Method for %K Solving Any Linear Set With a Square Matrix. %K An algorithm is presented to solve Ax=b by computing optimum %K iteration parameters for Richardson's iteration. The algorithm re- %K quires some information on the location of the eigenvalues of A. %K The algorithm yields parameters well-suited for matrices for which %K Chebyshev parameters are not appropriate. %K It therefore supplements the Manteuffel algorithm, developed for the %K Chebyshev case. Numerical examples are described. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K (as above) %K --------------- %K [6] Y. Saad, A. Sameh, and P. Saylor %K A Generalization of the Golub-Welsch Algorithm to Complex %K Orthogonal and Kernel Polynomials. %K The Golub-Welsch algorithm is a stable algorithm to compute %K the roots of real orthogonal polynomials and kernel polynomials. %K It is generalized to the complex cases. %K Submitted by: Paul Saylor %K Obtainable from: %K Paul Saylor %K (as above) %K --------------- %K [7] R.T. Gregory %K A finite number system for digital computers which %K gives exact results with rational operands. %K University of Tennessee Computer Science Report CS-84-57 %K A mapping is established between those rational numbers a/b with both %K a and b bounded in absolute value by a constant N, and a finite set of %K integers. When N is chosen to be the largest integer satisfying the %K inequality %K 2N*2 + 1 <= p %K where p is a very large prime, then the mapping is one-to-one and onto %K the set (0,1,2,...,p-1). Computation involving the rational numbers %K can be replaced by computation on the integers modulo p. In practice %K more than one modulus is used and this report deals with the multi- %K modulus case. %K Submitted by: Robert T. Gregory (shortly before his death) %K Obtainable from: %K Computer Science Department %K University of Tennessee %K Knoxville, Tenn. %K --------------- %K [8] Daniel Boley, University of Minnesota %K A Parallel Method for the Generalized Eigenvalue Problem %K University of Minnesota %K Computer Science Tech Report 84-21 %K Sept 1984. %K We present a parallel method to solve the %K generalized eigenvalue problem on a linear array %K of processors, each connected to their nearest %K neighbors and operating synchronously. We also %K include a wraparound connection from end to end. %K Our method is based on the well-known QZ algorithm %K of Moler and Stewart, which simultaneously reduces %K two nxn matrices to upper triangular form by %K orthogonal or unitary tranformations. We show how %K this algorithm may be partitioned and distributed %K over n+1 processors, achieving a speed-up over the %K serial algorithm of O(n). We use the concept of %K windows to describe the action of each processor %K at each step. We show how to incorporate single %K shifts, and how to apply orthogonal plane rota- %K tions on either side of a matrix without the need %K to transpose the matrix itself. %K Submitted by: Daniel Boley %K Obtainable from: %K Daniel Boley %K University of Minnesota %K (boley@umn-cs.csnet) %K --------------- %K [9] Ito, Kazufumi %K An iterative method for indefinite systems of linear equations %K ICASE Report No. 84-13, April 2, 1984, 21 pages %K Submitted to SIAM J. Numer. Anal. %K An iterative method for solving nonsymmetric indefinite linear systems is %K proposed. The method involves the successive use of a modified version of the %K conjugate residual method. A numerical example is given to illustrate the %K method. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K ICASE, Mail Stop l32C %K NASA Langley Research Center %K Hampton, VA 23665 %K (804) 865-3992. %K --------------- %K [10] Adams, Loyce M. and Harry F. Jordan %K Is SOR color-blind? %K ICASE Report No. 84-14, May 21, 1984, 39 pages %K Submitted to SIAM J. Sci. Statist. Comput. %K The work of Young [1971] showed that the Red/Black ordering and the %K natural rowwise ordering of matrices with Property A, such as those arising %K from the 5-point discretization of Poisson's equation, lead to SOR iteration %K matrices with identical eigenvalues. With the advent of parallel computers, %K multi-color point SOR schemes have been proposed for more complicated stencils %K on 2-dimensional rectangular grids, see Adams and Ortega [1982] for example, %K but to our knowledge, no theory has been provided for the rate of convergence %K of these methods relative to that of the natural rowwise scheme. %K New results show that certain matrices may be reordered so the resulting %K multi-color SOR matrix has the same eigenvalues as that for the original %K ordering. In addition, for a wide range of stencils, we show how to choose %K multi-color orderings so the multi-color SOR matrices have the same %K eigenvalues as the natural rowwise SOR matrix. The strategy for obtaining %K these results is based on "data flow" concepts and can be used to reach %K Young's conclusions above for the 5-point stencil. %K The importance of these results is threefold. Firstly, a constructive %K and easy means of finding these multi-colorings is a direct consequence of the %K theory; secondly, multi-color SOR methods can be found that have the same rate %K of convergence as the natural rowwise SOR method for a wide range of stencils %K used to discretize partial differential equations; and thirdly, these multi- %K color SOR methods can be efficiently implemented on a wide class of parallel %K computers. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [11] Gatski, Thomas B. and Chester E. Grosch %K A numerical study of the two- and three-dimensional %K unsteady Navier-Stokes equations in velocity-vorticity %K variables using compact difference schemes %K ICASE Report No. 84-15, May 22, 1984, 20 pages %K Proc. of 9th ICNMED, Saclay, France, June 23-29, 1984 %K LECTURE NOTES IN PHYSICS %K Springer-Verlag. %K A compact finite-difference approximation to the unsteady Navier-Stokes %K equations in velocity-vorticity variables is used to numerically simulate a %K number of flows. These include two-dimensional laminar flow of a vortex %K evolving over a flat plate with an embedded cavity, the unsteady flow over an %K elliptic cylinder, and aspects of the transient dynamics of the flow over a %K rearward facing step. The methodology required to extend the two-dimensional %K formulation to three-dimensions is presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [12] Hafez, Mohamed, M. and Phillips, Timothy N. %K A modified least squares formulation %K for a system of first-order equations %K ICASE Report No. 84-16, May 29, 1984, 21 pages %K Submitted to IMACS J. Numer. Math. %K Second-order equations in terms of auxiliary variables similar to %K potential and stream functions are obtained by applying a weighted least %K squares formulation to a first-order system. The additional boundary %K conditions which are necessary to solve the higher order equations are %K determined and numerical results are presented for the Cauchy-Riemann %K equations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [13] Hall, Phillip %K The Gortler vortex instability mechanism in %K three-dimensional boundary layers %K ICASE Report No. 84-17, June 6, 1984, 37 pages. %K Submitted to the Royal Society of London. %K It is well known that the two-dimensional boundary layer on a concave %K wall is centrifugally unstable with respect to vortices aligned with the basic %K flow for sufficiently high values of the Gortler number. However, in most %K situations of practical interest the basic flow is three-dimensional and %K previous theoretical investigations do not apply. In this paper the linear %K stability of the flow over an infinitely long swept wall of variable curvature %K is considered. If there is no pressure gradient in the boundary layer it is %K shown that the instability problem can always be related to an equivalent two- %K dimensional calculation. However, in general, this is not the case and even %K for small values of the crossflow velocity field dramatic differences between %K the two and three-dimensional problems emerge. In particular, it is shown %K that when the relative size of the crossflow and chordwise flow is (R**(-l/2)) %K where R is the Reynolds number of the flow, the most unstable mode is time- %K dependent. When the size of the crossflow is further increased, the vortices %K in the neutral location have their axes locally perpendicular to the vortex %K lines of the basic flow. In this regime the eigenfunctions associated with %K the instability become essentially 'centre modes' of the Orr-Sommerfeld %K equation destabilized by centrifugal effects. The critical Gortler number for %K such modes can be predicted by a large wavenumber asymptotic analysis; the %K results suggest that for order unity values of the ratio of the crossflow and %K chordwise velocity fields, the Gortler instability mechanism is almost %K certainly not operational. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [14] Gozani, J., Nachshon, A., and Turkel, E. %K Conjugate gradient coupled with %K multigrid for an indefinite problem %K ICASE Report No. 84-18, June 7, 1984, 11 pages %K Submitted to Proc. of 3rd IMACS International Symposium %K on Computer Methods for Partial Differential Equations %K Lehigh University, %K Bethlehem, PA, June 20-22, 1984 %K An iterative algorithm for the Helmholtz equation is presented. This %K scheme is based on the preconditioned conjugate gradient method for the normal %K equations. The preconditioning is one cycle of a multigrid method for the %K discrete Laplacian. The smoothing algorithm is red-black Gauss-Seidel and is %K constructed so it is a symmetric operator. The total number of iterations %K needed by the algorithm is independent of h. By varying the number of grids, %K the number of iterations depends only weakly on k when k**3 h**2 is %K constant. Comparisons with a SSOR preconditioner are presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [15] Malik, M. R., Zang, T. A., and Hussaini, M. Y. %K A spectral collocation method %K for the Navier-Stokes equations %K ICASE Report No. 84-19, June 8, 1984, 48 pages %K Submitted to J. Comput. Phys. %K A Fourier-Chebyshev spectral method for the incompressible Navier-Stokes %K equations is described. It is applicable to a variety of problems including %K some with fluid properties which vary strongly both in the normal direction %K and in time. In this fully spectral algorithm, a preconditioned iterative %K technique is used for solving the implicit equations arising from semi- %K implicit treatment of pressure, mean advection and vertical diffusion terms. %K The algorithm is tested by applying it to hydrodynamic stability problems in %K channel flow and in external boundary layers with both constant and variable %K viscosity. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [16] Davis, Stephen F. %K TVD finite difference schemes and artificial viscosity. %K ICASE Report No. 84-20, June 11, 1984, 35 pages %K Submitted to SIAM J. Sci. Statis. Comput. %K In this paper we show that the total variation diminishing (TVD) finite %K difference scheme which was analysed by Sweby can be interpreted as a Lax- %K Wendroff scheme plus an upwind weighted artificial dissipation term. We then %K show that if we choose a particular flux limiter and remove the requirement %K for upwind weighting, we obtain an artificial dissipation term which is based %K on the theory of TVD schemes, which does not contain any problem dependent %K parameters and which can be added to existing MacCormack method codes. %K Finally, we conduct numerical experiments to examine the performance of this %K new method. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [17] Canuto, C., Hariharan, S. I., and Lustman, L. %K Spectral methods for exterior %K elliptic problems %K ICASE Report No. 84-21, June 12, 1984, 33 pages. %K Submitted to Numer. Math. %K This paper deals with spectral approximations for exterior elliptic %K problems in two dimensions. As in the conventional finite difference or %K finite element methods, it is found that the accuracy of the numerical %K solutions is limited by the order of the numerical farfield conditions. We %K introduce a spectral boundary treatment at infinity, which is compatible with %K the "infinite order" interior spectral scheme. Computational results are %K presented to demonstrate the spectral accuracy attainable. Although we deal %K with a simple Laplace problem throughout the paper, our analysis covers more %K complex and general cases. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [18] Graif, E. and K. Kunisch %K Parameter estimation for the Euler-Bernoulli-beam %K ICASE Report No. 84-22, June 20, 1984, 43 pages. %K Submitted to IEEE Trans. Auto. Control. %K An approximation involving cubic spline functions for parameter %K estimation problems in the Euler-Bernoulli-beam equation (phrased as an %K optimization problem with respect to the parameters) is described and %K convergence is proved. The resulting algorithm was implemented and several of %K the test examples are documented. It is observed that the use of penalty %K terms in the cost functional can improve the rate of convergence. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [19] Rosen, I. Gary %K A numerical scheme for the identification of hybrid systems %K describing the vibration of flexible beams with tip bodies %K ICASE Report No. 84-23, June 21, 1984, 36 pages. %K Submitted to J. Math. Anal. Appl. %K A cubic spline based Galerkin-like method is developed for the %K identification of a class of hybrid systems which describe the transverse %K vibration of flexible beams with attached tip bodies. The identification %K problem is formulated as a least squares fit to data subject to the system %K dynamics given by a coupled system of ordinary and partial differential %K equations recast as an abstract evolution equation (AEE) in an appropriate %K infinite dimensional Hilbert space. Projecting the AEE into spline-based %K subspaces leads naturally to a sequence of approximating finite diemnsional %K identification problems. The solutions to these problems are shown to exist, %K are relatively easily computed, and are shown to, in some sense, converge to %K solutions to the original identification problem. Numerical results for a %K variety of examples are discussed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [20] Banks, H. Thomas and Katherine A. Murphy %K Estimation of coefficients and %K boundary parameters in hyperbolic systems %K ICASE Report No. 84-24, June 21, 1984, 52 pages. %K Submitted to SIAM J. Control Optim. %K We consider semi-discrete Galerkin approximation schemes in connection %K with inverse problems for the estimation of spatially varying coefficients and %K boundary condition parameters in second order hyperbolic systems typical of %K those arising in 1-D surface seismic problems. Spline based algorithms are %K proposed for which theoretical convergence results along with a representative %K sample of numerical findings are given. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [21] Vardi, A. %K A new minmax problem %K ICASE Report No. 84-25, June 26, 1984, 35 pages. %K Submitted to J. Optim., Theory and Appl. %K For the classical minimax problem we design a new active set strategy in which %K there are three types of functions: active, semi-active, and non-active. %K This technique will help in preventing zigzagging which often occurs when an %K active set strategy is used. Some of the inequality constraints are handled %K with slack variables. Also a trust region strategy is used in which at each %K iteration there is a sphere around the current point in which the local %K approximation of the function is trusted. The algorithm suggested in the %K paper was implemented into a successful computer program. Numerical results %K are provided. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [22] Banks, H. T. and I. G. Rosen %K Approximation techniques for parameter estimation and %K feedback control for distributed models of large flexible structures %K ICASE Report No. 84-26, June 22, 1984, 19 pages. %K Submitted to Workshop on Identification and Control of %K Flexible Space Structures, San Diego, CA, June 4-6, 1984, %K G. Rodgriguez (ed.). %K We discuss approximation ideas that can be used in parameter estimation %K and feedback control for Euler-Bernoulli models of elastic systems. Focusing %K on parameter estimation problems, we outline how one can obtain convergence %K results for cubic spline-based schemes for hybrid models involving an elastic %K cantilevered beam with tip mass and base acceleration. Sample numerical %K findings are also presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [23] Turkel, E. and Bram van Leer %K Flux vector splitting and Runge-Kutta methods %K for the Euler equations %K ICASE Report No. 84-27, June 23, 2984, 9 pages. %K To appear in Proc. of the 9th Intl. Conference on Numerical Methods %K in Fluid Dynamics, Saclay, France, June 25-29, 1984. %K Runge-Kutta schemes have been used as a method of solving the Euler %K equations exterior to an airfoil. In the past this has been coupled with %K central differences and an artificial viscosity in space. In this study we %K couple the Runge-Kutta time stepping scheme with an upwinded space approxima %K tion based on flux-vector splitting. Several acceleration techniques are also %K considered including a local time step, residual smoothing and multigrid. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [24] Turkel, Eli %K Fast solutions to the steady state compressible and %K incompressible fluid dynamics equations %K ICASE Report No. 84-28, June 23, 1984, 8 pages. %K To appear in Proc. of the 9th Intl. Conference on %K Numerical Methods in Fluid Dynamics %K Saclay, France, June 25-29, 1984. %K It is well known that for low speed flows the use of the compressible %K fluid dynamic equations is inefficient. The use of an explicit scheme %K requires delta-t to be bounded by 1/c. However, the physical parameters %K change over time scales of order 1/u which is much larger. Hence, it is not %K appropriate to use explicit schemes for very subsonic flows. Implicit schemes %K are hard to vectorize and frequently do not converge quickly for very subsonic %K flows. We shall demonstrate that if one is only interested in the steady %K state then a minor change to an existing code can greatly increase the %K efficiency of an explicit method. Even when using an implicit method the %K proposed changes increase the efficiency of the scheme. We shall first %K consider the Euler equations for low speed flows and then incompressible %K flows. We then indicate how to generalize the method to include viscous %K effects. We also show how to accelerate supersonic flow by essentially %K decoupling the equations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [25] Gottlieb, D. %K Spectral methods for compressible flow problems %K ICASE Report No. 84-29, June 21, 1984, 20 pages. %K Proc. 9th Intl. Conference on %K Numerical Methods in Fluid Dynamics %K Saclay, France, June 25-29, 1984. %K In this article we review recent results concerning numerical simulation %K of shock waves using spectral methods. We discuss shock fitting techniques as %K well as shock capturing techniques with finite difference artificial %K viscosity. We also discuss the notion of the information contained in the %K numerical results obtained by spectral methods and show how this information %K can be recovered. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [26] Ipsen, Ilse C. F. %K Singular value decomposition with systolic arrays %K ICASE Report No. 84-30, July 9, 1984, 22 pages. %K Proc. of the Society of Photo-Optical Engineers %K San Diego, CA, August 19-24, 1984. %K Systolic arrays for determining the Singular Value Decomposition of a %K matrix A of bandwidth w are presented. After A has been %K reduced to bidiagonal form B by means of Givens plane rotations, the %K differential equations. Part II: The linear quadratic control problem. %K ICASE Report No. 84-31, July 6, 1984, 65 pages. Submitted to SIAM J. %K Control Optim. %K The numerical scheme based on the Legendre-tau approximation is proposed %K to approximate the feedback solution to the linear quadratic optimal control %K problem for hereditary differential systems. The convergence property is %K established using Trotter ideas. The method yields very good approximations %K at low orders and provides an approximation technique for computing closed- %K loop eigenvalues of the feedback system. A comparison with existing methods %K (based on "averaging" and "spline" approximations) is made. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [27] Turkel, Eli %K Acceleration to a steady state for the Euler equations %K ICASE Report No. 84-32, July 7, 1984, 45 pages. %K Proc. INRIA Euler Workshop (SIAM) %K Rocquencourt, France, December 7-9, 1983. %K A multi-stage Runge-Kutta method is analyzed for solving the Euler %K equations exterior to an airfoil. Highly subsonic, transonic and supersonic %K flows are evaluated. Various techniques for accelerating the convergence to a %K steady state are introduced and analyzed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [28] Bokhari, Shahid H. and A. D. Raza %K Augmenting computer networks %K ICASE Report No. 84-33, July 8, 1984, 16 pages. %K Proc. 1984 Intl. Conference on Parallel Processing %K Bellaire, MI, August 21-24, 1984. %K Three methods of augmenting computer networks by adding at most one link %K per processor are discussed. %K 1. A tree of N nodes may be augmented such that the resulting graph %K has diameter no greater than 4 log2((N+2)/3)-2. This 0(N**3) algorithm can %K be applied to any spanning tree of a connected graph to reduce the diameter of %K that graph to 0(log N). %K 2. Given a binary tree T and a chain C of N nodes each, C may be %K augmented to produce C' so that T is a subgraph of C'. This algorithm %K is 0(N) and may be used to produce augmented chains or rings that have %K diameter no greater than 2 log2 (N+2)/3) and are planar. %K 3. Any rectangular two-dimensional 4 (8) nearest neighbor array of %K size N = 2**k may be augmented so that it can emulate a single step shuffle- %K exchange network of size N/2 in 3(t) time steps. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [29] Reed, Daniel A. and Merrell L. Patrick %K A model of asynchronous iterative algorithms %K for solving large, sparse, linear systems %K ICASE Report No. 84-34, July 31, 1984, 27 pages. %K Proceedings of the 1984 International %K Conference on Parallel Processing %K August 21-24, 1984, Bellaire, MI. %K Solving large, sparse, linear systems of equations is one of the %K fundamental problems in large scale scientific and engineering computation. %K A model of a general class of asynchronous, iterative solution methods for %K linear systems is developed. In the model, the system is solved by creating %K several cooperating tasks that each compute a portion of the solution vector. %K This model is then analyzed to determine the expected intertask data transfer %K and task computational complexity as functions of the number of tasks. Based %K on the analysis, recommendations for task partitioning are made. These %K recommendations are a function of the sparseness of the linear system, its %K structure (i.e., randomly sparse or banded), and dimension. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [30] Reed, Daniel A. and Merrell L. Patrick %K Parallel, iterative solution of sparse linear systems: %K Models and architectures %K ICASE Report No. 84-35, August 1, 1984, 45 pages. %K Submitted to Parallel Computing. %K Solving large, sparse, linear systems of equations is a fundamental %K problem in large scale scientific and engineering computation. A model of a %K general class of asychronous, iterative solution methods for linear systems is %K developed. In the model, the system is solved by creating several cooperating %K tasks that each compute a portion of the solution vector. A data transfer %K model predicting both the probability that data must be transferred between %K two tasks and the amount of data to be transferred is presented. This model %K is used to derive an execution time model for predicting parallel execution %K time and an optimal number of tasks given the dimension and sparsity of the %K coefficient matrix and the costs of computation, synchronization, and %K communication. %K The suitability of different parallel architectures for solving randomly %K sparse linear systems is discussed. Based on the complexity of task %K scheduling, one parallel architecture, based on a broadcast bus, is presented %K and analyzed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [31] Tadmor, Eitan %K The well-posedness of the Kuramoto-Sivashinsky equation. %K ICASE Report No. 84-36, August 7, 1984, 22 pages. %K Submitted to SIAM J. Appl. Math. %K The Kuramoto-Sivashinsky equation arises in a variety of applications, %K among which are modeling reaction-diffusion systems, flame-propagation and %K viscous flow problems. It is considered here, as a prototype to the larger %K class of generalized Burgers equations: those consist of quadratic %K nonlinearity and arbitrary linear parabolic part. We show that such equations %K are well-posed, thus admitting a unique smooth solution, continuously %K dependent on its initial data. As an attractive alternative to standard %K energymethods, existence and stability are derived in this case, by "patching" %K in the large short time solutions without "loss of derivatives". %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [32] Lustman, Liviu %K The time evolution of spectral discretizations of hyperbolic %K systems %K ICASE Report No. 84-37, August 7, 1984, 12 pages. %K Submitted to SIAM J. Numer. Anal. %K A Chebyshev collocation spectral method, applied to hyperbolic systems is %K considered, particularly for those initial boundary value problems which %K possess only solutions tending to zero at large times. It is shown that the %K numerical solutions of the system will also vanish at infinity, if and only %K if, the numerical solution of a scalar equation of the same type does. This %K result is then generalized for other spectral approximations. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [33] Bayliss, A., C. I. Goldstein, and E. Turkel %K On accuracy conditions for the %K numerical computation of waves %K ICASE Report No. 84-38, August 9, 1984, 16 pages. %K Submitted to J. Comput. Phys. %K The Helmholtz equation with a variable index of refraction, and a %K suitable radiation condition at infinity serves as a model for a wide variety %K of wave propagation problems. Such problems can be solved numerically by first %K truncating the given unbounded domain and imposing a suitable outgoing %K radiation condition on an artificial boundary and then solving the resulting %K problem on the bounded domain by direct discretization (for example, using a %K finite element method). In practical applications, the mesh size h and the %K wave number K, are not independent but are constrained by the accuracy of the %K desired computation. It will be shown that the number of points per %K wavelength, measured by l/Kh, is not sufficient to determine the accuracy of %K a given discretization. For example, the quantity K**3 h**2 is shown to %K determine the accuracy in the L-two norm for a second-order discretization %K method applied to several propagation models. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [34] Hariharan, S. I. %K Numerical solutions of acoustic wave propagation %K problems using Euler computations %K ICASE Report No. 84-39, August 10, 1984, 29 pages. %K Proc. of the AIAA 9th Aeroacoustics Conference %K Williamsburg, VA, August 15-17, 1984. %K This paper reports solution procedures for problems arising from the %K study of engine inlet wave propagation. The first problem is the study of %K sound waves radiated from cylindrical inlets. The second one is a quasi-one- %K dimensional problem to study the effect of nonlinearities and the third one is %K the study of nonlinearities in two dimensions. In all three problems Euler %K computations are done with a fourth-order explicit scheme. For the first %K problem results are shown in agreement with experimental data and for the %K second problem comparisons are made with an existing asymptotic theory. The %K third problem is part of an ongoing work and preliminary results are presented %K for this case. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [35] Tadmor, Eitan %K The exponential accuracy of Fourier %K and Tchebyshev differencing methods %K ICASE Report No. 84-40, August 20, 1984, 24 pages. %K Submitted to SIAM J. Numer. Anal. %K It is shown that when differencing analytic functions using the %K pseudospectral Fourier or Tchebyshev methods, the error committed decays to %K zero at an exponential rate. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [36] Gannon, Dennis and John Van Rosendale %K On the impact of communication complexity %K in the design of parallel numerical algorithms %K ICASE Report No. 84-41, August 22, 1984, 37 pages. %K To appear in IEEE Trans. on Computers. %K This paper describes two models of the cost of data movement in parallel %K numerical algorithms. One model is a generalization of an approach due to %K Hockney, and is suitable for shared memory multiprocessors where each %K processor has vector capabilities. The other model is applicable to highly %K parallel nonshared memory MIMD systems. In the second model, algorithm %K performance is characterized in terms of the communication network design. %K Techniques used in VLSI complexity theory are also brought in, and algorithm %K independent upper bounds on system performance are derived for several %K problems that are important to scientific computation. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [37] Ito, Kazufumi %K Legendre-Tau approximation for functional differential %K equations, Part III: Eigenvalue approximations and uniform stability. %K ICASE Report No 84-42, August 24, 1984, 34 pages. %K Proc. Second International Conference on Control Theory %K for Distributed Parameter Systems and Applications %K Vorau, Austria, 1984. %K The stability and convergence properties of the Legendre-tau %K approximation for hereditary differential systems are analyzed. We derive a %K characteristic equation for the eigenvalues of the resulting approximate %K system. As a result of this derivation we are able to establish that the %K uniform exponential stability of the solution semigroup is preserved under %K approximation. It is the key to obtaining the convergence of approximate %K solutions of the algebraic Riccati equation in trace norm. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [38] Berger, M. J. %K On conservation at grid interfaces %K ICASE Report No. 84-43, September 7, 1984, 25 pages. %K Submitted to J. Comput. Phys. %K This paper considers the solution of hyperbolic systems of conservation %K laws on discontinuous grids. In particular, we consider what happens to %K conservation at grid interfaces. A procedure is presented to derive %K conservative difference approximations at the grid interfaces for two- %K dimensional grids which overlap in an arbitrary configuration. The same %K procedures are applied to compute interface formulas for grids which are %K refined in space and/or time, and for continuous grids where a switch in the %K scheme causes the discontinuity. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [39] Osher, S. and S. Chakravarthy %K Very high order accurate TVD schemes %K ICASE Report No. 84-44, September 10, 1984, 61 pages. %K Submitted to SIAM J. Numer. Anal. %K A systematic procedure for constructing semi-discrete families of 2m-1 %K order accurate, 2m order dissipative, variation diminishing, 2m+1 point %K bandwidth, conservation form approximations to scalar conservation laws is %K presented. Here m is any integer between 2 and 8. Simple first-order forward %K time discretization, used together with any of these approximations to the %K space derivatives, also results in a fully discrete, variation diminishing %K algorithm. These schemes all use simple flux limiters, without which each of %K these fully discrete algorithms is even linearly unstable. Extensions to %K systems, using a nonlinear field-by-field decomposition are presented, and %K shown to have many of the same properties as in the scalar case. For linear %K systems, these nonlinear approximations are variation diminishing, and hence %K convergent. A new and general criterion for approximations to be variation %K diminishing is also given. Finally, numerical experiments using some of these %K algorithms are presented. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [40] Elcrat, A. R. and L. N. Trefethen %K Classical free-streamline flow over a polygonal obstacle %K ICASE Report No. 84-45, September 10, 1984, 61 pages. %K Submitted to J. Comput. Appl. Math. %K In classical Kirchhoff flow, an ideal incompressible fluid flows past an %K obstacle and around a motionless wake bounded by free streamlines. Since 1869 %K it has been known that in principle, the two-dimensional Kirchhoff flow over a %K polygonal obstacle can be determined by constructing a conformal map onto a %K polygon in the log-hodograph plane. In practice, however, this idea has %K rarely been put to use except for very simple obstacles, because the conformal %K mapping problem has been too difficult. This paper presents a practical %K method for computing flows over arbitrary polygonal obstacles to high accuracy %K in a few seconds of computer time. We achieve this high speed and flexibility %K by working with a modified Schwarz-Christoffel integral that maps onto the %K flow region directly rather than onto the log-hodograph polygon. This integral %K and its associated parameter problem are treated numerically by methods %K developed earlier by Trefethen for standard Schwarz-Christoffel maps. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [41] Krause, Egon %K Review of some vortex relations %K ICASE Report No. 84-46, September 12, 1984, 8 pages. %K Submitted to Computer and Fluids. %K The evaluation of the circulation from numerical solutions of the %K momentum and energy equations is discussed for incompressible and compressible %K flows. It is shown how artificial damping directly influences the time rate %K of change of the circulation. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [42] Tal-Ezer, Hillel %K A pseudospectral Legendre method for hyperbolic equations %K with an improved stability condition %K ICASE Report No. 84-48, September 14, 1984, 46 pages. %K Submitted to J. Comput. Phys. %K A new pseudospectral method is introduced for solving hyperbolic partial %K differential equations. This method uses different grid points than %K previously used pseudospectral methods: in fact the grid points are related %K to the zeroes of the Legendre polynomials. The main advantage of this method %K is that the allowable time step is proportional to the inverse of the number %K of grid points 1/N rather than to 1/N**2 (as in the case of other %K pseudospectral methods applied to mixed initial boundary value problems). A %K highly accurate time discretization suitable for these spectral methods is %K discussed. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [43] Bayliss, A., C. I. Goldstein, and E. Turkel %K The numerical solution of the Helmholtz equation for %K wave propagation problems in underwater acoustics %K ICASE Report No. 84-49, September 17, 1983, 29 pages. %K Submitted to J. Comput. Math. Appl. %K The Helmholtz Equation with a variable index of refraction, and a %K suitable radiation condition at infinity serves as a model for a %K wide variety of wave propagation problems. A numerical algorithm has %K been developed and a computer code implemented that can effectively %K solve this equation in the intermediate frequency range. The equation %K is discretized using the finite element method, thus allowing for the %K modeling of complicated geometries (including interfaces) and %K complicated boundary conditions. A global radiation boundary condition %K is imposed at the far field boundary that is exact for an arbitrary %K number of propagating modes. %K The resulting large, non-selfadjoint system of linear equations with %K indefinite symmetric part is solved using the preconditioned conjugate %K gradient method applied to the normal equations. A new preconditioner is %K developed based on the multigrid method. This preconditioner is vectorizable %K and is extremely effective over a wide range of frequencies provided the %K number of grid levels is reduced for large frequencies. A heuristic argument %K is given that indicates the superior convergence properties of this %K preconditioner. The relevant limit to analyze convergence is for K %K increasing and a fixed prescribed accuracy level. The efficiency and %K robustness of the numerical algorithm is confirmed for large acoustic models, %K including interfaces with strong velocity contrasts. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [44] Burns, John A., Ito, Kazufumi, Powers, Robert K. %K Chandrasekhar equations and computational %K algorithms for distributed parameter systems %K ICASE Report No. 84-50, September 20, 1984, 23 pages. %K Proc. of 23rd Conference on Decision and Control, %K December 12-14, 1984, Las Vegas, NV. %K In this paper we consider the Chandrasekhar equations arising in optimal %K control problems for linear distributed parameter systems. The equations are %K derived via approximation theory. This approach is used to obtain existence, %K uniqueness and strong differentiability of the solutions and provides the %K basis for a convergent computation scheme for approximating feedback gain %K operators. A numerical example is presented to illustrate these ideas. %K Submitted by: emily@icase.csnet %K Obtainable from: %K Ms. Barbara Kraft %K (as above) %K --------------- %K [45] Petter E. Bjorstad and Olof B. Widlund %K Iterative Methods for the Solution of Elliptic %K Problems on Regions Partitioned into Substructures %K Finite element problems can often naturally be divided into subproblems which %K correspond to subregions into which the region has been partitioned or from %K which it was originally assembled. A class of iterative methods is discussed %K in which these subproblems are solved by direct methods,while the interaction %K across the curves or surfaces which divide the region is handled by a conju- %K gate gradient method. A mathematical framework for this workis provided by %K regularity theory for elliptic finite element problems and by block Gauss %K elimination. A full development of the theory,which shows that certain of %K these methods are optimal, is given for Lagrangian finite element approxi- %K mations of second order linear elliptic problems in the plane.Results from %K numerical experiments are also reported. %K Submitted by: Olaf Widlund %K Obtainable from: %K Olaf Widlund %K Courant Institute %K 251 Mercer St. %K N.Y., N.Y. 10012. %K (WIDLUND@NYU-ACF1.ARPA) %K --------------- %K [46] Ron S. Dembo and Ulrich Tulowitzki %K Local Convergence Analysis for Successive %K Inexact Quadratic Programming Methods %K SOM Working Paper Series B #78 %K Yale School of Organization and Management %K October, 1984 %K Successive quadratic programming (SQP) methods for the %K solution of constrained nonlinear optimization problems are %K attractive because they converge rapidly from any sufficiently %K good initial solution. However, solving the quadratic subproblems %K at each stage can be expensive, particularly if the number of %K unknowns is large and may be not justified when far away from %K an optimal solution. Therefore, we consider a class of successive %K inexact quadratic programming (SIQP) methods that solve the %K subproblems only approximately. We characterize the rate of %K convergence in terms of the relative error incurred in the %K subproblems in a manner that does not assume that the set of %K active constraints remains constant. This leads to practical %K termination criteria for truncating various iterative algorithms %K applied to the quadratic subproblems. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K P.O. Box 1A %K New Haven, Conn. 06520 %K --------------- %K [47] Ron S. Dembo and Ulrich Tulowitzki %K Sequential Truncated Quadratic Programming Methods %K To appear in the Proceedings of the SIAM Conference %K on Numerical Optimization, Boulder, Colo., June, 1984 %K In a sequential quadratic programming (SQP) method for nonlinear %K optimization it is possible to truncate an iterative procedure, applied %K to each quadratic subproblem, prior to reaching a solution, without %K affecting the asymptotic rate of convergence. We describe some %K practical termination criteria which ensure that an SQP method, executed %K without exact solution of the QP subproblem, inherits the rate of %K convergence of its (exact) SQP counterpart. Numerical experiments on %K linearly-constrained problems of up to 2230 variables indicate that %K substantial savings can be achieved by inexact solution of the QP %K subproblems with little or no adverse effect on the convergence rate. %K Submitted by: Ron Dembo %K Obtainable from: %K Ron Dembo %K Yale University %K School of Organization and Management %K P.O. Box 1A %K New Haven, Conn. 06520 %K --------------- %K From rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa Tue Jul 16 14:50:12 1985 %K Received: from csnet-relay (csnet-relay.arpa.ARPA) by anl-mcs.ARPA ; Tue, 16 Jul 85 14:46:21 cdt %K Received: from waterloo by csnet-relay.csnet id aa01168; 16 Jul 85 14:32 EDT %K Date: Sun, 14 Jul 85 20:31:32 edt %K From: Richard Bartels <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Message-Id: <8507150031.AA20620@watcgl.UUCP> %K To: dongarra@anl-mcs %K Status: R %K ================================================== %K NUMERICAL ANALYSIS TITLES -- Volume 3, Number 1 %K April 1, 1985 (No foolin') %K ================================================== %K Note: %K Responding to a request by John Lewis, and for the %K benefit of the SIGNUM Newsletter, these titles and %K abstracts are now ordered alphabetically by insti- %K tution. %K ##### ARGONNE ##### %K All Argonne reports listed here may be %K obtained by writing to the person listed as %K submitting the report at the following address: %K Argonne National Laboratory %K Mathematics and Computer Science Division %K 9700 S. Cass Ave. %K Argonne, IL 60439 %K ################### %K [1] %K Proceedings for the Argonne Workshop on Programming the %K Next Generation of SuperComputers, October 1984 %K Report ANL/MCS-TM-34 %K Argonne National Lab %K On February 27-28, 1984, an Argonne National Laboratory workshop %K titled "Programming the Next Generation of Supercomputers" was held at %K the Amfac Hotel in Albuquerque, New Mexico. The purpose of the workshop %K was to gather together researchers from the DOE laboratories who were %K using multiprocessors and to have these investigators relate their %K experiences with the programming languages supplied with these %K processors. The goal was to identify those areas where additional %K language primitives would aid in the development of portable software. %K Upon the identification of such needs, extensions to the Fortran %K language would then be proposed to such groups as the DOE Language %K Working Group and the X3J3 Fortran committee for further study. %K The topics presented at the workshop included reviews of existing %K languages that address concurrency and parallel computation, %K presentations on portable programming methods for parallel processing, %K users' views of what is needed to program multiprocessors, and the %K supplier's views of what is needed to drive their processors. %K This report collects the presentations given at this workshop and %K records the organized discussion held after each presentation and each %K session. In most cases, the materials reproduced here are the slides %K given by each author at the workshop. In some cases, papers were %K prepared by the authors and included in this report. A summary of the %K conclusions reached by the workshop is also included. %K Submitted by: Brian T. Smith <smith@anl-mcs.arpa> %K --------------- %K [2] Iain S. Duff %K Parallel implementation of multifrontal schemes %K ANL/MCS-TM-49, March, 1985 %K We consider the direct solution of large sparse sets of %K linear equations in an MIMD environment. We base our algorithm %K on a multifrontal approach and show how to distribute tasks among %K processors according to an elimination tree which can be automat- %K ically generated from any pivot strategy. We study organiza- %K tional aspects of the scheme for shared memory multiprocessor %K configurations and consider implications for multiprocessors with %K local memories and a communication network. %K Submitted by: Iain S. Duff <duff@anl-mcs.arpa> %K --------------- %K [3] I.S. Duff, A.M. Erisman, C.W. Gear, and J.K. Reid %K Some remarks on inverses of sparse matrices %K ANL/MCS-TM-51, March, 1985 %K We discuss some of the properties of the structure of the %K inverse of a sparse matrix. In particular, we show that the %K structural inverse of an irreducible sparse matrix is always %K full. We first show that Gaussian elimination always yields a %K full structural inverse and then show the result directly. We %K believe that our lemmas concerning Gaussian elimination are of %K interest in their own right. %K Submitted by: Iain S. Duff <duff@anl-mcs.arpa> %K --------------- %K [4] I.S. Duff and C.W. Gear %K Computing the structural index %K ANL/MCS-TM-50, March, 1985 %K The index of many differential/algebraic equations is deter- %K mined by the structure of the system, that is, by the pattern of %K nonzero entries in the Jacobians. It is important to be able to %K determine if the index does not exceed two because such problems %K can be solved numerically. In this paper we present an algorithm %K that determines if the index is one, two, or greater, based only %K on the structure. The algorithm can be exponential in its execu- %K tion time: we do not know whether it is possible to get an asymp- %K totically faster algorithm. However, in many practical problems, %K this algorithm will execute in polynomial time. %K Submitted by: Iain S. Duff <duff@anl-mcs.arpa> %K --------------- %K [5] Jack J. Dongarra, Linda Kaufman and, Sven Hammarling, %K Squeezing the Most out of Eigenvalue Solvers on High-Performance Computers %K ANL-MCS/TM 46, January, 1985 %K This paper describes modifications to many of the standard algorithms %K used in computing eigenvalues and eigenvectors of matrices. These %K modifications can dramatically increase the performance of the %K underlying software on high performance computers without resorting %K to assembler language, without significantly influencing the floating %K point operation count, and without affecting the roundoff error properties %K of the algorithms. The techniques are applied to a wide variety of %K algorithms and are beneficial in various architectural settings. %K Submitted by: Jack J. Dongarra <dongarra@anl-mcs.apa> %K --------------- %K [6] Jack J. Dongarra, Jeremy Du Croz, Sven Hammarling, and Richard J. Hanson %K A Proposal for an Extended Set of Basic Linear Algebra Subprograms %K ANL-MCS/TM 41, December, 1984 %K This paper describes an extension to the set of Basic Linear Algebra %K Subprograms. The extensions proposed are targeted at matrix vector %K operations which should provide for more efficient and portable %K implementations of algorithms for high performance computers. %K Submitted by: Jack J. Dongarra <dongarra@anl-mcs.apa> %K --------------- %K [7] J.J. Dongarra, A.H. Sameh, and D.C. Sorensen %K Implementation of Some Concurrent Algorithms for Matrix Factorization %K ANL-MCS/TM 25, October, 1984 %K Three parallel algorithms for computing the QR-factorization of %K a matrix are presented. The discussion is primarily concerned with %K implementation of these algorithms on a computer that supports %K tightly coupled parallel processes sharing a large common memory. %K The particular experiments were conducted on the Denelcor HEP computer. %K The three algorithms are a Householder method based upon high-level %K modules, a Windowed Householder method that avoids fork-join synchronization, %K and a Pipelined Givens method that is a variant of the data-flow type %K algorithms offering large enough granularity to mask synchronization %K costs. Computational results indicate that the Pipelined Givens method %K is preferred and that this is primarily due to the number of array %K references required by the various algorithms. %K Submitted by: Jack J. Dongarra <dongarra@anl-mcs.apa> %K --------------- %K [8] J.J. Dongarra and D.C. Sorensen %K A Parallel Linear Algebra Library for the Denelcor HEP %K ANL-MCS/TM 33, October, 1984 %K This paper discusses the implementation of a library of algorithms for %K problems in linear algebra on the Denelcor HEP. The package includes %K some of the most heavily used subroutines from LINPACK, that is, solution %K of linear systems based on LU, Cholesky, and QR factorizations as well %K as the appropriate triangular solvers. The concept followed is to code %K these routines in terms of high-level modules, which provides a vehicle %K to achieve both transportability and efficiency across a wide range of %K architectures. We discuss this concept in the context of a numerical %K linear algebra software library which is adaptable to highly parallel %K computing systems. However, the concept is expected to applicable to %K other libraries as well. %K Submitted by: Jack J. Dongarra <dongarra@anl-mcs.apa> %K --------------- %K [9] M. T. Heath and D.C. Sorensen %K A Pipelined Givens Method for Computing the QR %K Factorization of a Sparse Matrix %K ANL-MCS/TM 47, February, 1985 %K This paper discusses an extension of the Pipelined Givens method for %K computing the QR factorization of a real m x n matrix to the %K case in which the matrix is sparse. When restricted to one process, %K the algorithm performs the same computation as the serial sparse Givens %K algorithm of George and Heath. Our implementation is compatible with %K the data structures used in SPARSPAK. The pipelined algorithm is well %K suited to parallel computers having globally shared memory and low %K overhead synchronization primitives, such as the Denelcor HEP, for %K which computational results are presented. We point out certain %K synchronization problems that arise in the adaptation to the sparse %K setting and discuss the effect on parallel speedup of accessing a %K serial data file. %K Submitted by: Jack J. Dongarra <dongarra@anl-mcs.apa> %K --------------- %K ##### BELL LABS ##### %K All Bell Laboratories reports were submitted by %K Eric Grosse <{ucbvax,ihnp4}!research!ehg> %K and they may be obtained by writing to him at: %K AT&T Bell Labs 2c471 %K Murray Hill, NJ 07974 %K or by requesting them of him through electronic mail. %K ##################### %K [10] Eric Grosse %K AUTOMATIC CHOICE OF COLORS FOR LEVEL PLOTS %K TR/NAMs 85-1 %K AT&T Bell Labs %K Color level plots are becoming popular in scientific computing but often %K require manually adjusting the color codes. A formula, fit by Friele, %K MacAdam, and Chickering to ellipses of measured color discrimination, %K provides the basis for a spectrum of equally spaced colors. The color %K choice problem is formulated as a nonlinear least squares optimization %K and solved numerically. A table can be precomputed to adjust the hue %K coordinate in the hexcone model of Alvy Ray Smith, just as compensation %K tables are used for gamma correction of CRTs. %K --------------- %K [11] William M. Coughran, Jr. and Eric Grosse %K THE GROVE EDITOR %K TR/NAMs 83-3 %K We describe a structure editor, grove, which manipulates groves of trees %K rather than text files. Various commands for searching and modifying nodes %K and subtrees are described. We also document some routines for performing %K basic operations on trees, which facilitate the construction of program- %K transformation systems. %K --------------- %K [12] William M. Coughran, Jr. and Eric Grosse %K THE PINE PROGRAMMING LANGUAGE %K TR/NAMs 83-4 %K Pine is a language intended to bring to scientific computation convenient %K program transformation, array operations, and simplified calls to libraries. %K Pine programs can be translated into FORTRAN. The key features added to %K FORTRAN are array operations, heap-based dynamic memory allocation, more %K convenient input/output, generic functions, operators of the form +=, %K expression-language syntax, and control structures. The lexical form of %K the language, based on a screen editor of trees, is designed to simplify %K program transformations. This manual describes pine and its processor to %K those already familiar with the issues involved in compiling into FORTRAN. %K --------------- %K [13] William M. Coughran, Jr., Eric Grosse, and Donald J. Rose %K VARIATION DIMINISHING SPLINES IN SIMULATION %K TR/NAMs 84-3 %K Variation diminishing splines provide an effective tool for modeling %K active elements in circuit simulation. Using quadratic tensor product %K splines and maintaining uniform sampling at the boundary by linear %K extension of the data yields an algorithm that is smooth (unlike simple %K table lookup), shape preserving (unlike simple interpolation), and %K efficient (30 microseconds to evaluate on a Cray-1A). The rate of %K convergence to function and derivative values is O(h**2). %K --------------- %K [14] Brenda S. Baker, Eric Grosse, and Conor S. Rafferty %K NON-OBTUSE TRIANGULATION OF A POLYGON %K TR/NAMs 84-4 %K We show how to triangulate a polygon without using any obtuse triangles. %K Such triangulations can be used to discretize partial differential equations %K in a way that guarantees the resulting matrix is Stieltjes, a desirable %K property both for computation and for theoretical analysis. A simple %K divide-and-conquer approach would fail because adjacent subproblems cannot %K be solved independently, but this can be overcome by careful subdivision. %K Overlay a square grid on the polygon, preferably with the polygon vertices %K at grid points. Choose boundary cells so they can be triangulated without %K propagating irregular points to adjacent cells. The remaining interior is %K rectangular and easily triangulated. Small angles can also be avoided in %K these constructions. %K --------------- %K [15] Jack J. Dongarra and Eric Grosse %K DISTRIBUTION OF MATHEMATICAL SOFTWARE VIA ELECTRONIC MAIL %K TR/NAMs 85-2 %K A large collection of mathematical software is now available via electronic %K mail. Messages sent to "netlib@anl-mcs" (on the Arpanet/CSNET) or to %K "research!netlib" (on the UNIX\(tm network) wake up a server that %K distributes items from the collection. For example the one-line message, %K "send index", gets a library catalog by return mail. We describe how to %K use the service and some of the issues in its implementation. %K --------------- %K [15] Linda Kaufman, Jack Dongarra, and Sven Hammarling %K SQUEEZING THE MOST OUT OF EIGENVALUE SOLVERS ON HIGH-PERFORMANCE COMPUTERS %K TR/NAMs 84-7 %K This paper describes modifications to many of the standard algorithms used %K in computing eigenvalues and eigenvectors of matrices which decrease the %K number of vector-memory references. These modifications can dramatically %K increase the performance of the underlying software without resorting to %K assembly language and without significantly influencing the floating point %K operation count. %K --------------- %K ##### CORNELL ##### %K [16] Franklin T. Luk %K A Parallel Method for Computing %K the Generalized Singular Value Decomposition %K TR/EE-CEG-85-1 %K We describe a new parallel algorithm for computing the generalized %K singular value decomposition of two n-by-n matrices, one of %K which is nonsingular. Our procedure requires O(n) time %K and one triangular array of O( n**2 ) processors. %K Submitted by: Franklin T. Luk <luk%tesla@cornell.arpa> %K Obtainable from: %K Franklin T. Luk %K School of Electrical Engineering %K Phillips Hall %K Cornell University %K Ithaca, New York 14853 %K --------------- %K [17] Thomas F. Coleman, Burton S. Garbow, and Jorge J. More' %K Software for Estimating Sparse Hessian Matrices %K Argonne National Laboratory Cornell University %K MCS/TM-43 CSD/TR 85-660 %K January, 1985 %K The solution of a nonlinear optimization problem often requires %K an estimate of the Hessian matrix for a function f. %K In large scale problems the Hessian matrix is usually sparse, and %K then estimation by differences of gradients is attractive because %K the number of differences can be small compared to the dimension %K of the problem. In this paper we describe a set of subroutines whose %K purpose is to estimate the Hessian matrix %K with the least possible number of gradient evaluations. %K Submitted by: Thomas F. Coleman <coleman%gvax@cornell.arpa> %K Obtainable from: %K Thomas F. Coleman %K Cornell University %K Computer Science Dept. %K Ithaca, NY 14853 %K --------------- %K ##### NYU: COURANT INSTITUTE ##### %K [18] James Demmel %K On the Conditioning of Pole Assignment %K Computer Science Dept. Technical Report, Jan 85 %K An algorithm for the pole assignment problem has recently been %K given by Kautsky,Nichols, and Van Dooren. Given the n by n matrix %K A, the n by m full rank matrix B (m<n), and the n complex numbers %K z(i), the problem is to find F such that A+BF has the z(i) as %K eigenvalues. The quality of the solution is measured by the %K condition number of X, the matrix of eigenvectors of A+BF. %K In this note we show that a lower bound on cond(X) is given %K essentially by the reciprocal of the product of three terms: %K the condition number of B, the maximum condition number of %K any A- z(i)I, and the relative distance from the pair (A,B) to %K the nearest uncontrollable pair. This last term can be interpreted %K as follows: the lower bound on cond(X) becomes large as the %K relative distance from the problem to the nearest %K "infinitely ill-conditioned" problem becomes small. %K Submitted by: James Demmel <demmal@nyu-csd2.arpa> %K Obtainable from: %K James Demmel %K Courant Institute %K 251 Mercer Str. %K New York, NY 10012 %K --------------- %K ##### DELFT (NETHERLANDS) ##### %K [19] Henk A. van der Vorst %K The Performance of FORTRAN Implementations for %K Preconditioned Conjugate Gradients on Vector Computers %K We will consider in detail the performance of FORTRAN implemen- %K tations for the conjugate gradient algorithm, for the solution of large %K linear systems, on a number of well-known vectorcomputers: CRAY-1, %K CRAY X-MP and CYBER 205. %K Lowerbounds on the CPU-times, required for separate parts of the %K algorithm, are presented and these are compared to the actually observed %K CPU-times. It appears that these lowerbounds are reasonably sharp. %K Submitted by: Henk A. van der Vorst <decvax!mcvax!dutinfd!numan> %K Obtainable from: %K Henk A. van der Vorst %K Department of Mathematics %K University of Technology at Delft %K Julianalaan 132 %K Delft, the Netherlands %K --------------- %K ##### EMORY ##### %K [20] J.M. Borwein and H. Wolkowicz %K A Simple Constraint Qualification in Infinite Dimensional Programming %K A new, simple, constraint qualification for infinite dimensional programs %K with linear programming type constraints is used to derive the dual program. %K Applications include a proof of the explicit solution of the best interpolation %K problem of Micchelli, Smith, Swetits, and Ward. %K Submitted by: Henry Wolkowicz <henry@emory.csnet> %K Obtainable from: %K J.M. Borwein %K Dalhousie University %K Halifax, Nova Scotia B3H 4H8 %K Canada %K (or from Henry, but he didn't include his address). %K --------------- %K ##### IBM ##### %K [21] Jane Cullum and Ralph A. Willoughby %K A Practical Procedure for Computing Eigenvalues %K of Large Sparse Nonsymmetric Matrices %K IBM Research Report, RC 10988, 2/14/85 %K We propose a Lanczos procedure with no reorthogonalization %K for computing eigenvalues of very large nonsymmetric matrices. %K (This procedure can also be used to compute corresponding eigenvectors %K but that issue will be dealt with in a separate paper.) %K Such computations are for example, central to transient %K stability analyses of electrical power systems and for determining %K parameters for iterative schemes for the numerical solution of partial %K differential equations. Numerical results for several large %K matrices are presented to demonstrate the effectiveness of this %K procedure. %K Submitted by: Jane Cullum <cullumj%yktvmv@ibm-sj.csnet> %K Obtainable from: %K Jane Cullum and Ralph A. Willoughby %K IBM T.J. Watson Research Center, P.O. Box 218 %K Yorktown Heights, New York 10598 %K --------------- %K ##### ICASE ##### %K Barbara Kraft %K ICASE, M/S 132C %K NASA Langley Research Center %K Hampton, VA 23665 %K may be contacted for all ICASE reports, %K or a message may be sent to: %K emily@icase.csnet %K All of these reports were submitted by "Emily". %K (The list below has been abbreviated to the %K numerically-oriented reports. Only the original %K technical-report information is given, although %K some of these have appeared in proceedings and journals. %K Sorry. -RHB) %K ################## %K [22] Rosen, I. G. %K Approximation methods for inverse problems involving the %K vibration of beams with tip bodies. %K ICASE Report No. 84-51, September 26, 1984, 10 pages. %K Proc. 23rd IEEE Conference on Decisions and Control, Las %K Vegas, NV, Decmeber 12-14, 1984. %K We outline two cubic spline based approximation schemes for the %K estimation of structural parameters associated with the transverse vibration %K of flexible beams with tip appendages. The identification problem is %K formulated as a least squares fit to data subject to the system dynamics which %K are given by a hybrid system of coupled ordinary and partial differential %K equations. The first approximation scheme is based upon an abstract semigroup %K formulation of the state equation while a weak/variational form is the basis %K for the second. Cubic spline based subspaces together with a Rayleigh-Ritz- %K Galerkin approach was used to construct sequences of easily solved finite %K dimensional approximating identification problems. Convergence results are %K briefly discussed and a numerical example demonstrating the feasibility of the %K schemes and exhibiting their relative performance for purposes of comparison %K is provided. %K --------------- %K [23] Canuto, C. %K Boundary Conditions in Chebyshev and Legendre Methods %K ICASE Report No. 84-52, October 1, 1984, 38 pages %K We discuss two different ways of treating non-Dirichlet boundary %K conditions in Chebyshev and Legendre collocation methods for second order %K differential problems. %K An error analysis is provided. The effect of preconditioning the %K corresponding spectral operators by finite difference matrices is also %K investigated. %K --------------- %K [24] Roe, P. L. %K Generalized formulation of TVD Lax-Wendroff schemes %K ICASE Report No. 84-53, October 23, 1984, 14 pages %K The work of Davis which imports the concept of total-variation- %K diminution (TVD) into non-upwinded, Lax-Wendroff type schemes is reformulated %K in a way which is easier to analyze. The analysis reveals a class of TVD %K schemes not observed by Davis. %K --------------- %K [25] Bokhari, Shahid H. %K Shuffle-exchanges on augmented meshes %K ICASE Report No. 84-54, October 24, 1984, 12 pages %K Proc. 1985 Intl. Conference on Distributed Computer Systems %K Denver, CO. %K Prior research has shown how a mesh connected array of size N = 2**K an %K integer, can be augmented by adding at most one edge per node such that it can %K perform a shuffle-exchange of size N/2 in constant time. %K We now show how to perform a shuffle-exchange of size N on this augmented %K array in constant time. This is done by combining the available perfect %K shuffle of size N/2 with the existing nearest neighbor connections of the %K mesh. By carefully scheduling the different permutations that are composed in %K order to achieve the shuffle, the time required is reduced to 5 steps, which %K is shown to be optimal for this network. %K --------------- %K [26] Goodman, Jonathan B. and Randall J. LeVeque %K A geometric approach to high resolution TVD schemes %K ICASE Report No. 84-55, October 29, 1984, 35 pages %K We use a geometric approach, similar to Van Leer's MUSCL schemes, to %K construct a second-order accurate generalization of Godunov's method for %K solving scalar conservation laws. By making suitable approximations we obtain %K a scheme which is easy to implement and total variation diminishing. We also %K investigate the entropy condition from the standpoint of the spreading of %K rarefaction waves. For Godunov's method we obtain quantitative information on %K the rate of spreading which explain the kinks in rarefaction waves often %K observed at the sonic point. %K --------------- %K [27] Tin-Chee Wong, C. H. Liu, and James Geer %K Comparison of uniform perturbation solutions and numerical %K solutions for some potential flows past slender bodies %K ICASE Report No. 84-56, October 29, 1984, 32 pages %K Approximate solutions for potential flow past an axisymmetric slender %K body and past a thin airfoil are calculated using a uniform perturbation %K method and then compared with either the exact analytical solution or the %K solution obtained using a purely numerical method. The perturbation method is %K based upon a representation of the disturbance flow as the superposition of %K singularities distributed entirely within the body, while the numerical %K (panel) method is based upon a distribution of singularities on the surface of %K the body. It is found that the perturbation method provides very good results %K for small values of the slenderness ratio and for small angles of attack. %K Moreover, for comparable accuracy, the perturbation method is simpler to %K implement, requires less computer memory, and generally uses less computation %K time than the panel method. In particular, the uniform perturbation method %K yields good resolution near the regions of the leading and trailing edges %K where other methods fail or require special attention. %K --------------- %K [28] Salas, M. D., S. Abarbanel and D. Gottlieb %K Multiple steady states for characteristic initial value problems %K ICASE Report No. 84-57, November 1, 1984, 43 pages %K The time dependent, isentropic, quasi-one-dimensional equations of gas %K dynamics and other model equations are considered under the constraint of %K characteristic boundary conditions. Analysis of the time evolution shows how %K different initial data may lead to different steady states and how seemingly %K anamolous behavior of the solution may be resolved. Numerical experimentation %K using time consistent explicit algorithms verifies the conclusions of the %K analysis. The use of implicit schemes with very large time steps leads to %K erroneous results. %K --------------- %K [29] Rose, Milton E. %K A compact finite element method for elastic bodies %K ICASE Report No. 84-58, November 7, 1984, 38 pages %K A nonconforming finite element method is described for treating linear %K equilibrium problems, and a convergence proof showing second order accuracy is %K given. The close relationship to a related compact finite difference scheme %K due to Phillips and Rose is examined. A condensation technique is shown %K to preserve the compactness property and suggests an approach to a certain %K type of homogenization. %K --------------- %K [30] Lustman, Liviu %K A review of spectral methods %K ICASE Report No. 84-59, November 19, 1984, 25 pages %K This paper presents a brief outline of spectral methods for partial %K differential equations. The basic ideas, together with simple proofs are %K discussed. An application to potential transonic flow is also reviewed. %K --------------- %K [31] Hussaini, M. Y. and W. D. Lakin %K Existence and non-uniqueness of similarity %K solutions of a boundary layer problem %K ICASE Report No. 84-60, November 21, 1984, 17 pages %K This work considers a Blasius boundary value problem with inhomogeneous %K lower boundary conditions f(0) = 0 and f'(0) = - L with L strictly %K positive. The Crocco variable formulation of this problem has a key term %K which changes sign in the interval of interest. It is shown that solutions of %K the boundary value problem do not exist for values of L larger than a positive %K critical value LC. The existence of solutions is proved for 0 < L _ LC by %K considering an equivalent initial value problem. However, for 0 < L < LC, %K solutions of the boundary value problem are found to be nonunique. %K Physically, this non-uniqueness is related to multiple values of the skin %K friction. %K --------------- %K [32] Bayliss, Alvin, Maestrello, Lucio and Turkel, Eli %K On the interaction of a sound pulse with the shear %K layer of an axisymmetric jet, III. Nonlinear effects %K ICASE Report No. 84-61 November 23, 1984, 22 pages %K The fluctuating field of a jet excited by transient mass injection is %K simulated numerically. The model is developed by expanding the state vector %K as a mean state plus a fluctuating state. Nonlinear terms are not neglected, %K and the effect of nonlinearity is studied. A high order numerical method is %K used to compute the solution. The results show a significant spectral %K broadening in the flow field due to the nonlinearity. In addition, large %K scale structures are broken down into smaller scales. %K --------------- %K [33] Swanson, R. C. and Eli Turkel %K A multistage time-stepping scheme for the Navier-Stokes equations %K ICASE Report No. 84-62, November 23, 1984, 28 pages %K A class of explicit multistage time-stepping schemes is used to construct %K an algorithm for solving the compressible Navier-Stokes equations. Flexibility %K in treating arbitrary geometries is obtained with a finite-volume formulation. %K Numerical efficiency is achieved by employing techniques for accelerating %K convergence to steady state. Computer processing is enhanced through %K vectorization of the algorithm. The scheme is evaluated by solving laminar %K and turbulent flows over a flat plate and an NACA 0012 airfoil. Numerical %K results are compared with theoretical solutions or other numerical solutions %K and/or experimental data. %K --------------- %K [34] Brenier, Yann and Stanley Osher %K Approximate Riemann solvers and numerical flux functions %K ICASE Report No. 84-63, December 5, 1984, 33 pages %K Given a monotone function z(x) which connects two constant states, %K uL < uR, (uL > uR), we find the unique (up to a constant) convex (concave) %K flux function, F(u) such that z(x/t) is the physically correct solution to %K the associated Riemann problem. For z(x/t), an approximate Riemann solver to %K a given conservation law, we derive simple necessary and sufficient conditions %K for it to be consistent with any entropy inequality. Associated with any %K member of a general class of consistent numerical fluxes, hf(uR,uL), we have %K an approximate Riemann solver defined through z(Z) = (-d/dZ)hfZ(uR,uL), where %K fZ(u) = f(u) - Zu. We obtain the corresponding F(u) via a Legendre %K transform and show that it is consistent with all entropy inequalities iff %K hfZ(uR,uL) is an E flux for each relevant Z. Examples involving commonly %K used two point numerical fluxes are given, as are comparisons with related %K work. %K --------------- %K [35] Hall, Philip and Mujeeb R. Malik %K On the instability of a three-dimensional attachment line %K boundary layer: Weakly nonlinear theory and a numerical approach %K ICASE Report No. 84-64, December 6, 1984, 65 pages %K The instability of a three-dimensional attachment line boundary layer is %K considered in the nonlinear regime. Using weakly nonlinear theory, it is %K found that, apart from a small interval near the (linear) critical Reynolds %K number, finite amplitude solutions bifurcate subcritically from the upper %K branch of the neutral curve. The time-dependent Navier-Stokes equations for %K the attachment line flow have been solved using a Fourier-Chebyshev spectral %K method and the subcritical instability is found at wavenumbers that correspond %K to the upper branch. Both the theory and the numerical calculations show the %K existence of supercritical finite amplitude (equilibrium) states near the %K lower branch which explains why the observed flow exhibits a preference for %K the lower branch modes. The effect of blowing and suction on nonlinear %K stability of the attachment line boundary layer is also investigated. %K --------------- %K [36] Fix, George J. and Manil Suri %K Three-dimensional mass conserving elements for compressible flows %K ICASE Report No. 84-65, December 13, 1984, 27 pages %K A variety of finite element schemes has been used in the numerical %K approximation of compressible flows particularly in underwater acoustics. In %K many instances instabilities have been generated due to the lack of mass %K conservation. In this paper we develop new two- and three-dimensional %K elements which avoid these problems. %K --------------- %K [37] Banks, H. Thomas and James M. Crowley %K Estimation of material parameters in elastic systems %K ICASE Report No. 84-66, December 28, 1984, 45 pages %K In this paper we present theoretical and numerical results for inverse %K problems involving estimation of spatially varying parameters such as %K stiffness and damping in distributed models for elastic structures such as %K Euler-Bernoulli beams. An outline of algorithms we have used and a summary of %K some of our computational experiences are presented. %K --------------- %K [38] Ito, Kazufumi and Robert K. Powers %K Chansrasekhar equations for infinite dimensional systems %K ICASE Report No. 84-67, December 31, 1984, 36 pages %K In this paper we derive the Chandrasekhar equations for linear time %K invariant systems defined on Hilbert spaces using a functional analytic %K technique. An important consequence of this is that the solution to the %K evolutional Riccati equation is strongly differentiable in time and one can %K define a 'strong' solution of the Riccati differential equation. A detailed %K discussion on the linear quadratic optimal control problem for hereditary %K differential systems is also included. %K --------------- %K [39] Ortega, James M. and Robert G. Voigt %K Solution of partial differential equations on %K vector and parallel computers %K ICASE Report No. 85-1, January 2, 1985, 173 pages %K In this paper we review the present status of numerical methods for %K partial differential equations on vector and parallel computers. A discussion %K of the relevant aspects of these computers and a brief review of their %K development is included, with particular attention paid to those %K characteristics that influence algorithm selection. Both direct and iterative %K methods are given for elliptic equations as well as explicit and implicit %K methods for initial-boundary value problems. The intent is to point out %K attractive methods as well as areas where this class of computer architecture %K cannot be fully utilized because of either hardware restrictions or the lack %K of adequate algorithms. A brief discussion of application areas utilizing %K these computers is included. %K --------------- %K [40] Voigt, Robert G. %K Where are the parallel algorithms? %K ICASE Report No. 85-2, January 16, 1985, 14 pages %K Four paradigms that can be useful in developing parallel algorithms are %K discussed. These include computational complexity analysis, changing the %K order of computation, asynchronous computation, and divide and conquer. Each %K is illustrated with an example from scientific computation, and it is shown %K that computational complexity must be used with great care or an inefficient %K algorithm may be selected. %K --------------- %K [41] Gottlieb, D. and E. Tadmor %K Recovering pointwise values of discontinuous %K data within spectral accuracy %K ICASE Report No. 85-3, January 31, 1985, 20 pages %K We show how pointwise values of a function, f(x), can be accurately %K recovered either from its spectral or pseudospectral approximations, so that %K the accuracy solely depends on the local smoothness of f in the neighborhood %K of the point x. Most notably, given the equidistant function grid values, %K its intermediate point values are recovered within spectral accuracy, despite %K the possible presence of discontinuities scattered in the domain. (Recall %K that the usual spectral convergence rate decelerates otherwise to first order, %K throughout). %K To this end we employ a highly oscillatory smoothing kernel, in contrast %K to the more standard positive unit-mass mollifiers. %K In particular, post-processing of a stable Fourier method applied to %K hyperbolic equations with discontinuous data, recovers the exact solution %K modulo a spectrally small error. Numerical examples are presented. %K --------------- %K [42] Lakin, W. D. %K Differentiating Matrices for Arbitrarily Spaced Grid Points %K ICASE Report No. 85-5, January 31, 1985, 23 pages %K Differentiating matrices allow the numerical differentiation of functions %K defined at points of a discrete grid. The present work considers a type of %K differentiating matrix based on local approximation on a sequence of sliding %K subgrids. Previous derivations of this type of matrix have been restricted to %K grids with uniformly spaced points, and the resulting derivative %K approximations have lacked precision, especially at endpoints. The new %K formulation allows grids which have arbitrarily spaced points. It is shown %K that high accuracy can be achieved through use of differentiating matrices on %K non-uniform grids which include "near-boundary" points. Use of the %K differentiating matrix as an operator to solve eigenvalue problems involving %K ordinary differential equations is also considered. %K --------------- %K [43] Fleming, Peter J. %K SUBOPT - A CAD program for suboptimal linear regulators %K ICASE Report No. 85-6, February 4, 1985, 16 pages. %K This interactive software package provides design solutions for both %K standard linear quadratic regulator (LQR) and suboptimal linear regulator %K problems. Intended for time-invariant continuous systems the package is %K easily modified to include sampled-data systems. LQR designs are obtained by %K established techniques while the large class of suboptimal problems containing %K controller and/or performance index options is solved using a robust gradient %K minimization technique. Numerical examples demonstrate features of the %K package and recent developments are described. %K --------------- %K [44] Banks, H. Thomas and I. Gary Rosen %K A Galerkin method for the estimation of %K parameters in hybrid systems governing the %K vibration of flexible beams with tip bodies %K ICASE Report No. 85-7, February 5, 1985, 44 pages %K In this report we develop an approximation scheme for the identification %K of hybrid systems describing the transverse vibrations of flexible beams with %K attached tip bodies. In particular, problems involving the estimation of %K functional parameters (spatially varying stiffness and/or linear mass density, %K temporally and/or spatially varying loads, etc.) are considered. The %K identification problem is formulated as a least squares fit to data subject to %K the coupled system of partial and ordinary differential equations describing %K the transverse displacement of the beam and the motion of the tip bodies %K respectively. A cubic spline-based Galerkin method applied to the state %K equations in weak form and the discretization of the admissible parameter %K space yield a sequence of approximting finite dimensional identification %K problems. We demonstrate that each of the approximating problems admits a %K solution and that from the resulting sequence of optimal solutions a %K convergent subsequence can be extracted, the limit of which is a solution to %K the original identification problem. The approximating identification %K problems can be solved using standard techniques and readily available %K software. Numerical results for a variety of examples are provided. %K --------------- %K [45] Tal-Ezer, Hillel %K The eigenvalues of the pseudospectral Fourier %K approximation to the operator sin(2x) (d/dx) %K ICASE Report No. 85-8, February 7, 1985, %K In this note we show that the eigenvalues of the pseudospectral Fourier %K approximation to the operator sin(2x) (d/dx) have real parts either equal to %K zero or equal to plus or minus one. %K Whereas this does not prove stability for the Fourier method, applied to the %K hyperbolic equation %K dU/dt = sin(2x)(dU/dx) - Pi < x < - Pi; %K it indicates that the growth in time of the numerical solution is essentially %K the same as that of the solution to the differential equation. %K --------------- %K [46] Tal-Ezer, Hillel %K Spectral methods in time for parabolic problems %K ICASE Report No. 85-9, February 8, 1985, 19 pages %K A pseudospectral explicit scheme for solving linear, periodic, parabolic %K problems is described. It has infinite accuracy both in time and in space. %K The high accuracy is achieved while the time resolution parameter M (M = %K 0(1/(delta t)) for time marching algorithm) and the space resolution parameter %K N (N = 0(1/(delta t)) have to satisfy M = 0(N**(1 + ep)) ep > 0, compared to %K the common stability condition M = 0(N**2) which has to be satisfied in any %K explicit finite order time algorthm. %K --------------- %K [47] Tadmor, Eitan %K Complex symmetric matrices with strongly stable iterates %K ICASE Report No. 85-10, February 14, 1985, 22 pages %K We study complex-valued symmetric matrices. A simple expression for the %K spectral norm of such matrices is obtained, by utilizing a unitarily congruent %K invariant form. Consequently, we provide a sharp criterion for identifying %K those symmetric matrices whose spectral norm is not exceeding one: such %K strongly stable matrices are usually sought in connection with convergent %K difference approximations to partial differential equations. As an example, %K we apply the derived criterion to conclude the strong stability of a Lax- %K Wendroff scheme. %K --------------- %K [48] Turkel, Eli %K Algorithms for the Euler and Navier-Stokes %K equations for supercomputers %K ICASE Report No. 85-11, February 14, 1985, 27 pages %K We consider the steady state Euler and Navier-Stokes equations for both %K compressible and incompressible flow. Methods are found for accelerating the %K convergence to a steady state. This acceleration is based on preconditioning %K the system so that it is no longer time consistent. In order that the %K acceleration technique be scheme independent this preconditioning is done at %K the differential equation level. Applications are presented for very slow %K flows and also for the incompressible equations. %K --------------- %K [49] Pratt, Terrence W. %K PISCES: an environment for parallel scientific computation %K ICASE Report No. 85-12, February 15, 1985, 30 pages %K PISCES (Parallel Implementation of Scientific Computing EnvironmentS) is %K a project to provide high-level programming environments for parallel MIMD %K computers. Pisces 1, the first of these environments, is a Fortran 77 based %K environment which runs under the UNIX operating system. The Pisces 1 user %K programs in Pisces Fortran, an extension of Fortran 77 for parallel %K processing. The major emphasis in the Pisces 1 design is in providing a %K carefully specified "virtual machine" that defines the run-time environment %K within which Pisces Fortran programs are executed. Each implementation then %K provides the same virtual machine, regardless of differences in the underlying %K architecture. The design is intended to be portable to a variety of %K architectures. Currently Pisces 1 is implemented on a network of Apollo %K workstations and on a DEC VAX uniprocessor via simulation of the task level %K parallelism. An implementation for the Flexible Computing Corp. FLEX/32 is %K under construction. This paper provides an introduction to the Pisces 1 %K virtual computer and the Fortran 77 extensions. An example of an algorithm %K for the iterative solution of a system of equations is given. The most %K notable features of the design are the provision for several different %K "granularities" of parallelism in programs and the provision of a "window" %K mechanism for distributed access to large arrays of data. %K --------------- %K [50] Harabetian, Eduard %K A convergent series expansion for hyperbolic systems of %K conservation laws %K ICASE Report No. 85-13, February 20, 1985, 88 pages %K We consider the discontinuous piecewise analytic initial value problem %K for a wide class of conservation laws that includes the full three-dimensional %K Euler equations. The initial interaction at an arbitrary curved surface is %K resolved in time by a convergent series. Among other features the solution %K exhibits shock, contact, and expansion waves as well as sound waves %K propagating on characteristic surfaces. The expansion waves correspond to the %K one-dimensional rarefactions but have a more complicated structure. The sound %K waves are generated in place of zero strength shocks, and they are caused by %K mismatches in derivatives. %K --------------- %K [51] Abarbanel, Saul and David Gottlieb %K Information content in spectral calculations %K ICASE Report No. 85-14, February 21, 1985, 13 pages %K Spectral solutions of hyperbolic partial differential equations induce a %K Gibbs phenomenon near local discontinuities or strong gradients. %K A procedure is presented for extracting the piecewise smooth behavior of %K the solution out of the oscillatory numerical solution data. The procedure is %K developed from the theory of linear partial differential equations. Its %K application to a non-linear system (the two-dimensional Euler equations of gas %K dynamics) is shown to be efficacious for the particular situation. %K --------------- %K [52] Cox, Christopher L. and George J. Fix %K On the accuracy of least squares methods in the presence %K of corner singularities %K ICASE Report No. 85-15, February 21, 1985, 24 pages %K This paper treats elliptic problems with corner singularities. Finite %K element approximations based on variational principles of the least squares %K type tend to display poor convergence properties in such contexts. Moreover, %K mesh refinement or the use of special singular elements do not appreciably %K improve matters. Here we show that if the least squares formulation is done %K in appropriately weighted space, then optimal convergence results in %K unweighted spaces like L two. %K --------------- %K [53] Maday, Yvon %K Analysis of spectral operators in one-dimensional domains %K ICASE Report No. 85-17, February 28, 1985, 26 pages %K We prove results concerning certain projection operators on the space of %K all polynomials of degree less than or equal to N with respect to a class of %K one-dimensional weighted Sobolev spaces. These results are useful in the %K theory of the approximation of partial differential equations with spectral %K methods. %K --------------- %K [54] Roe, Philip L. %K Discrete models for the numerical analysis of time-dependent %K multidimensional gas dynamics %K ICASE Report No. 85-18, March 1, 1985, 36 pages %K This paper explores a possible technique for extending to %K multidimensional flows some of the upwind-differencing methods that have %K proved highly successful in the one-dimensional case. Attention here is %K concentrated on the two-dimensional case, and the flow domain is supposed to %K be divided into polygonal computational elements. Inside each element the %K flow is represented by a local superposition of elementary solutions %K consisting of plane waves not necessarily aligned with the element boundaries. %K --------------- %K ##### LIVERMORE ##### %K [55] R. C. Y. Chin, G. W. Hedstrom, F. A. Howes, and J. R. McGraw %K Parallel computation of multiple-scale problems %K Report UCRL-92007 %K Lawrence Livermore National Laboratory %K <No Abstract> %K Submitted by: Gerald Hedstrom <hedstrom@lll-crg.arpa> %K Obtainable from: %K Gerald Hedstrom %K Lawrence Livermore National Laboratory %K Livermore, CA 94550 %K --------------- %K ##### MARYLAND ##### %K All of the Maryland titles were %K submitted by: %K Rodrigo Fontecilla <rod@maryland.arpa> %K They may be obtained from: %K Rodrigo Fontecilla %K University of Maryland %K Dept. of Computer Science %K College Park, MD 20742 %K #################### %K [56] Rodrigo Fontecilla %K A globally convergent algorithm for %K nonlinear equality constrained %K optimization using a double line search. %K In this paper, we present a globally convergent algo- %K rithm based on the 2-step algorithms developed by the %K author. Two different line searches with Goldstein-Armijo %K conditions are implemented. We show that the horizontal step %K is a descent direction for the objective function and that %K the vertical step is a descent direction for the $l sub 2#- %K norm of the constraints. Further, we show that the total %K step (horizontal+vertical) is a descent direction for both, %K the Lagrangian and the $l sub 2#-norm of the constraints. It %K is shown that the algorithm generates a sequence {$x sub k#} %K converging in the weak sense, i.e. the gradient of the %K Lagrangian and the constraints converge to zero. Fast con- %K vergence is guaranteed close to the solution with a 2-step %K q-quadratic rate. The BFGS secant update is implemented, a %K global convergence result is also obtained, and close to the %K solution the convergence is 2-step q-superlinear. Numerical %K results using a finite difference approximation of the Hes- %K sian and the BFGS secant update on 30 test problems are %K presented. %K --------------- %K [57] Rodrigo Fontecilla %K SUBSPACE INVARIANCE OF BROYDEN'S $THETA$-CLASS %K University of Maryland %K Computer Science Department %K Technical Report 1430 %K Broyden's $theta#-class of updating formulae have the pro- %K perty that if the current approximation matrix is symmetric %K and positive definite, then the updated matrix maintains %K those same properties under certain conditions. It is shown %K that if the current approximation matrix is symmetric and %K positive definite on a subspace of $Rn#, then the updated %K matrix is symmetric and positive definite along the same %K subspace under certain conditions. Applications of these %K results to the implementation of quasi-Newton methods for %K solving nonlinear constrained optimization problems are %K presented. %K --------------- %K ##### MINNESOTA ##### %K All of the reports from Minnesota were %K submitted without abstracts by: %K Panos Pardalos %K They are available from him at: %K Computer Science Department %K University of Minnesota %K Lind Hall 136 %K Minneapolis MN 55455 %K ##################### %K [58] J.B.Rosen %K Computational Experience with Large-Scale %K Constrained Global Optimization %K Tech. Report 84-13 %K June 1984 %K --------------- %K [59] J.B.Rosen and P.M.Pardalos %K Global Minimization of Large-Scale Constrained %K Concave Quadratic Problems by Separable Programming %K Tech. Report 84-29 %K October 1984 %K --------------- %K [60] P.M.Pardalos and J.B.Rosen %K Reduction of Nonlinear Integer Separable %K Programming Problems to Zero-One Linear Programming Problems %K Tech. Report 84-25 %K October 1984 %K --------------- %K [61] P.M.Pardalos and J.B.Rosen %K Methods for Global Concave Minimization: A Bibliographic Survey %K Tech. Report 84-31 %K November 1984 %K --------------- %K [62] P.M.Pardalos and J.B.Rosen %K A Global Optimization Approach to the %K Linear Complementarity Problem %K December 1984 %K --------------- %K ##### OAK RIDGE ##### %K [63] M. T. Heath A. J. Laub C. C. Paige R. C. Ward %K ORNL UC-Santa Barbara McGill Univ. ORNL %K COMPUTING THE SINGULAR VALUE DECOMPOSITION %K OF A PRODUCT OF TWO MATRICES %K Tech. Rept. ORNL-6118, January 1985 %K An algorithm is developed for computing the singular value %K decomposition of a product of two general matrices without explicitly %K forming the product. The algorithm is based on an earlier Jacobi-like %K method due to Kogbetliantz and uses plane rotations applied to the two %K matrices separately. A triangular variant of the basic algorithm is %K developed that reduces the amount of work required. %K Submitted by: Bob Ward <ward@ornl-msr.arpa> %K Obtainable from: Mathematical Sciences %K Oak Ridge National Laboratory %K P. O. Box Y, Bldg. 9207-A %K Oak Ridge, Tennessee 37831 %K ------------------- %K [64] Alan George Michael T. Heath Joseph Liu %K University of Waterloo ORNL York University %K PARALLEL CHOLESKY FACTORIZATION ON A MULTIPROCESSOR %K Tech. Rept. ORNL-6124, March 1985 %K A parallel algorithm is developed for Cholesky factorization %K on a multiprocessor. The algorithm is based on self-scheduling of a %K pool of tasks. The subtasks in several variants of the basic %K elimination algorithm are analyzed for potential concurrency in terms %K of precedence relations, work profiles, and processor utilization. %K This analysis is supported by simulation results. The most promising %K variant, which we call column-Cholesky, is identified and implemented %K for the Denelcor HEP multiprocessor. Experimental results are given %K for this machine. %K Submitted by: Bob Ward %K Obtainable from: Mathematical Sciences %K Oak Ridge National Laboratory %K P. O. Box Y, Bldg. 9207-A %K Oak Ridge, Tennessee 37831 %K ----------------- %K [65] R. E. Funderlic C. D. Meyer, Jr. %K Oak Ridge National Laboratory North Carolina State University %K SENSITIVITY OF THE STATIONARY DISTRIBUTION VECTOR %K FOR AN ERGODIC MARKOV CHAIN %K Technical Report ORNL-6098, January 1985 %K Stationary distribution vectors p for Markov chains %K with associated transition matrices T are important in the %K analysis of many models in the mathematical sciences, such as %K queuing networks, input-output economic models and compartmental %K tracer analysis models. The purpose of this paper is to provide %K insight into the sensitivity of p to perturbations in the %K transition probabilities of T and to understand some of the %K difficulties in computing an accurate p. The group inverse A# of %K I-T is shown to be of fundamental importance in understanding %K sensitivity or conditioning of p. The main result shows that if %K there is a state that is accessible from every other state and %K the corresponding column of T has no small off-diagonal elements, %K then p cannot be sensitive to small perturbations in T. %K Ecological examples are given. A new stable algorithm for %K calculating A# is described. %K Submitted by: Bob Ward %K Obtainable from: Mathematical Sciences %K Oak Ridge National Laboratory %K P. O. Box Y, Bldg. 9207-A %K Oak Ridge, Tennessee 37831 %K --------------- %K [66] George Ostrouchov %K Symbolic Givens Reduction in Large Sparse Least Squares %K ORNL-6102 %K Oak Ridge National Laboratory %K December 1984 %K Orthogonal Givens factorization is a popular method for solving large %K sparse least squares problems. In order to exploit sparsity and to use %K a fixed data structure in Givens reduction, a preliminary symbolic %K factorization needs to be performed. Some results on row-ordering and %K structure of rows in a partially reduced matrix are obtained using a %K graph-theoretic representation. These results provide a basis for a %K symbolic Givens factorization. Column-ordering is also discussed, and %K an algorithm for symbolic Givens reduction is developed and tested. %K --------------- %K ##### UBC ##### %K [67] Manfred R. Trummer %K Nystroem's method versus Fourier type methods for the %K numerical solution of integral equations. %K Tech. Rep. 84-23 %K It is shown that Nystroem's method and Fourier %K type methods produce the same approximation to a solution %K of an integral equation at the collocation points for %K Nystroem's method. The quadrature rule for numerical %K integration must have these collocation points as abscissa. %K Submitted by: Manfred R. Trummer <trummer@ubc.csnet> %K Obtainable from: %K Department of Computer Science %K The University of British Columbia %K Vancouver, B.C., Canada V6T 1W5 %K --------------- %K [68] Manfred R. Trummer %K An efficient implementation of a conformal mapping method %K using the Szego kernel. %K Tech. Rep. 84-24 %K An implementation, based on iterative techniques, %K of a method to compute the Riemann mapping function is presented. %K The method has been recently introduced by N. Kerzman and the %K author. It expresses the Szego kernel as the solution of an %K integral equation of the second kind. It is shown how to treat %K symmetric regions. The algorithm is tested on five examples. %K The numerical results show that the method is competitive, %K with respect to accuracy, stability, and efficiency. %K Submitted by: Manfred R. Trummer <trummer@ubc.csnet> %K Obtainable from: %K Department of Computer Science %K The University of British Columbia %K Vancouver, B.C., Canada V6T 1W5 %K --------------- %K [69] Uri Ascher and G. Bader %K STABILITY OF COLLOCATION AT GAUSSIAN POINTS %K Technical Report 84-13 %K Revised, February, 1985 %K Symmetric Runge-Kutta schemes are particularly useful %K for solving stiff two-point boundary value problems. %K Such A-stable schemes perform well in many cases, %K but it is demonstrated that in some instances the %K stronger property of algebraic stability is required. %K A characterization of symmetric, algebraically stable %K Runge-Kutta schemes is given. The class of schemes %K thus defined turns out not to be very rich: The only %K collocation schemes in it are those based on Gauss %K points, and other schemes in the class do not seem %K to offer any advantage over collocation at Gaussian points. %K Submitted by: Uri Ascher <ascher@ubc.csnet> %K Obtainable from: %K Uri Ascher %K Department of Computer Science %K University of British Columbia %K Vancouver, British Columbia %K Canada V6T 1W5 %K --------------- %K [70] Uri Ascher %K COLLOCATION FOR TWO-POINT BOUNDARY VALUE PROBLEMS REVISITED %K Technical Report 84-17 %K November, 1984 %K Collocation methods for two-point boundary value problems %K for higher order differential equations are considered. %K By using appropriate monomial bases, we relate these %K methods to corresponding one-step schemes for 1st order %K systems of differential equations. This allows us to present %K the theory for nonstiff problems in relatively simple terms, %K refining at the same time %K some convergence results and discussing stability. %K No restriction is placed on the meshes used. %K Submitted by: Uri Ascher <ascher@ubc.csnet> %K Obtainable from: %K Uri Ascher %K Department of Computer Science %K University of British Columbia %K Vancouver, British Columbia %K Canada V6T 1W5 %K --------------- %K ##### WATERLOO ##### %K [71] P. H. Calamai and A. R. Conn %K A projected Newton method for $l sub p$ location problems. %K The University of Waterloo %K Computer Science Department %K Tech Rept CS-85-07 %K This paper is concerned with the numerical solution of con- %K tinuous minisum multifacility location problems involving the $l %K sub p$ norm, where 1<p<infinity This class of problems is poten- %K tially difficult to solve because the objective function is not %K everywhere differentiable. After developing conditions that %K characterize the minimum of the problem under consideration, a %K second-order algorithm is presented. This algorithm is based on %K the solution of a finite sequence of linearly constrained sub- %K problems. Descent directions for these subproblems are obtained %K by projecting the Newton direction onto the corresponding con- %K straint manifold. Univariate minimization is acheived via a spe- %K cialized line search which recognizes the possibility of first %K derivative discontinuity ( and second derivative unboundedness) %K at point along the descent direction. Th algorithm, motivated by %K earlier work by Calamai and Calamai and Conn and related to %K methods recently described by Overton and Dax, is shown to pos- %K sess both global and quadratic convergence properties. %K Degeneracy can complicate the numerical solution of the sub- %K problems. This degeneracy is identified, and a method that cir- %K cumvents this degeneracy is included. %K An implementation of the algorithm, that exploits the %K intrinsic structure of the location problem formulation, is then %K described along with a discusion of numerical results. %K Submitted by: Andrew R. Conn <arconn%water@waterloo.csnet> %K Obtainable from: %K Andrew R. Conn %K The University of Waterloo %K Computer Science Department %K Waterloo, Ontario N2L 3G1 %K Canada %K --------------- %K [72] R. H. Bartels and J. C. Beatty %K Beta-Splines with a Difference %K University of Waterloo %K Computer Science Department %K Technical Report CS-83-40 %K Local control of the shape parameters beta-1 and beta-2 %K in a beta-spline has previously relied on quintic Hermite %K interpolation of the distinct beta values associated with %K the joints in a geometrically-continuous piecewise %K parametric polynomial curve. Here we introduce an alternative %K means of obtaining local control of geometrically continuous %K piecewise polynomial curves. The essential idea is to %K generalize the truncated power functions suitably to account %K for the discontinuities allowed by geometric continuity, %K and to generate the beta-splines from a differencing %K process. The resulting basis functions are piecewise cubic, %K partition unity, have local support, and are nonegative for %K "reasonable" values of beta-1 and beta-2. They accommodate %K variable knot spacing as well as different beta values at %K each knot. %K Submitted by: Richard H. Bartels <rhbartels@waterloo.csnet> %K Obtainable from: %K Richard H. Bartels or John C. Beatty %K The University of Waterloo %K Computer Science Department %K Waterloo, Ontario N2L 3G1 %K Canada %K --------------- %K ##### YALE ##### %K [73] Howard C. Elman %K A Stability Analysis of Incomplete LU Factorizations %K Report YALEU/DCS/RR-365 %K <No Abstract> %K Submitted by: Howard C. Elman <elman%yale-bulldog@yale.arpa> %K Obtainable from: %K Howard C. Elman %K Yale University %K New Have, Conn. %K --------------- %K From GOLUB@SU-SCORE.ARPA Fri Aug 30 14:45:54 1985 %K Received: from SU-SCORE.ARPA (su-score.arpa.ARPA) by anl-mcs.ARPA ; Fri, 30 Aug 85 14:45:11 cdt %K Return-Path: <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Received: from csnet-relay by SU-SCORE.ARPA with TCP; Tue 27 Aug 85 17:48:23-PDT %K Received: from waterloo by csnet-relay.csnet id ae16675; 27 Aug 85 20:33 EDT %K Date: Tue, 27 Aug 85 13:12:38 edt %K From: Richard Bartels <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Message-Id: <8508271712.AA25227@watcgl.UUCP> %K To: na@SU-SCORE.ARPA %K Subject: T&A Part 1 of 3 %K Resent-Date: Fri 30 Aug 85 11:47:55-PDT %K Resent-From: Gene Golub (415/497-3124) <GOLUB@SU-SCORE.ARPA> %K Resent-To: :; %K Resent-Message-Id: <12139307538.36.GOLUB@SU-SCORE.ARPA> %K Status: R %K ================================================== %K NUMERICAL ANALYSIS TITLES %K -- Volume 3, Number 2, Part 1 of 3 %K -- August 27, 1985 %K ================================================== %K Please note: Due to its length, this list is %K being distributed in 3 parts, each %K part is about 7 pages in length. %K ##### AT&T BELL LABORATORIES ##### %K For copies of these reports, send mail to %K {ucbvax,ihnp4}!research!wmc %K or %K wmc.btl@csnet-relay %K or %K na.coughran@su-score %K or %K Bill Coughran %K AT&T Bell Labs 2C419 %K Murray Hill, NJ 07974 %K (201) 582-6619 %K ################### %K [1] R. E. Bank, W. M. Coughran, Jr., W. Fichtner, %K D. J. Rose, and R. K. Smith, %K COMPUTATIONAL ASPECTS OF SEMICONDUCTOR DEVICE SIMULATION %K NAMs 85-3 %K In this chapter, we present an overview of the numerical %K techniques used to solve the coupled system of nonlinear %K partial differential equations that model the behavior of %K semiconductor devices. These methods have been incorporated %K into our device simulation package which has been success- %K fully used to model complex device structures in two and %K three space dimensions for both steady-state and transient %K conditions. %K --------------- %K [2] R. E. Bank, W. M. Coughran, Jr., W. Fichtner, %K E. H. Grosse, D. J. Rose, R. K. Smith, %K TRANSIENT SIMULATION OF SILICON DEVICES AND CIRCUITS %K NAMs 85-8 %K In this paper, we present an overview of the physical prin- %K ciples and numerical methods used to solve the coupled sys- %K tem of nonlinear partial differential equations that model %K the transient behavior of silicon VLSI device structures. %K We also describe how the same techniques are applicable to %K circuit simulation. A composite linear multistep formula is %K introduced as the time-integration scheme. Newton-iterative %K methods are exploited to solve the nonlinear equations that %K arise at each time step. We also present a simple data %K structure for nonsymmetric matrices with symmetric nonzero %K structures that facilitates iterative or direct methods with %K substantial efficiency gains over other storage schemes. %K Several computational examples, including a CMOS latchup %K problem, are presented and discussed. %K --------------- %K ##### CORNELL ##### %K [3] Franklin T. Luk and Sanzheng Qiao %K A fast but unstable orthogonal triangularization technique %K for Toeplitz matrices %K EE-CEG-85-5 %K Address: School of Electrical Engineering %K Cornell University %K Ithaca, NY 14863 %K < No Abstract > %K Submitted by: Frank Luk (luk%tesla@cornell.csnet) %K Obtainable from: %K Frank Luk %K Cornell University %K Ithaca, New York 14853 %K --------------- %K [4] Franklin T. Luk %K Algorithm-based Fault Tolerance for Parallel %K Matrix Equation Solvers %K EE-CEG-85-2 %K School of Electrical Engineering, Cornell University %K Ithaca, New York 14853 %K June 1985 %K We examine the checksum schemes of Abraham et al. for %K the computation of the LU-factorization using a multiprocessor array. %K Their methods are very efficient for detecting a transient error, %K but quite expensive for correcting it %K due to the need for a computation rollback. %K In this paper, we show how to avoid the rollback and how to implement pivoting. %K We also introduce a new checksum method %K for solving triangular sets of linear equations. %K Obtainable from: Frank Luk, above. %K --------------- %K ##### COURANT INSTITUTE ##### %K [5] O. McBryan %K Computational Methods for Discontinuities in Fluids %K Lectures in Applied Mathematics %K vol. 22, AMS, Providence, 1985. %K < No Abstract > %K Submitted by: Oliver McBryan (mcbryan@nyu.arpa) %K Obtainable from: %K Oliver McBryan %K Courant Institute %K 251 Mercer St %K New York, NY 10012 %K --------------- %K [6] O. McBryan and E. Van de Velde %K Parallel Algorithms for Elliptic Equations %K Proceedings of the %K 1984 ARO Novel Computing Environments Conference %K Stanford University, SIAM , to appear. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [7] O. McBryan, E. Van de Velde, and P. Vianna %K Parallel Algorithms for Elliptic and Parabolic Equations %K Proceedings of the Conference on Parallel Computations %K in Heat Transfer and Fluid Flows %K University of Maryland, November 1984. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [8] O. McBryan %K Using CRAY super-computers as Attached Processors %K Courant Institute Preprint, 1985. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [9] O. McBryan %K State of the Art of Multiprocessors in Scientific Computation %K Proceedings of European %K Weather Center Conference on Multiprocessors %K Reading, England, Dec 1984, to appear. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [10] O. McBryan and E. Van de Velde %K Parallel Algorithms for Elliptic Equation %K Solution on the HEP Computer %K Proceedings of the First HEP Conference %K University of Oklahoma, March 1985. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [11] O. McBryan and E. Van de Velde %K Parallel Algorithms for Elliptic Equations %K to appear in Commun. Pure and Appl. Math., Feb 1985. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [12] O. McBryan and E. Van de Velde %K Elliptic Equation Algorithms on Parallel Computers %K Proceedings of the Conference on Parallel Computers %K and Partial Differential Equations, %K Commun. in Applied Numerical Methods, %K University of Texas, Austin, March 1985, to appear. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [13] J. Glimm, B. Lindquist, O. McBryan, and G. Tryggvason %K Sharp and Diffuse Fronts in Oil Reservoirs: %K Front Tracking and Capillarity %K Proceedings of the Houston SPE/SIAM meeting %K on Mathematics of Reservoir Simulation, %K SIAM, to appear, Feb. 1985. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [14] J. Glimm and O. McBryan %K A Computational Model for Interfaces %K Courant Institute Preprint, 1985. %K < No Abstract > %K Obtainable from: O. McBryan, above. %K --------------- %K [15] James W. Demmel and Bo Kagstrom %K Computing Stable Eigendecompositions of Matrix Pencils %K Technical Report # 163 %K Computer Science Department %K Courant Institute %K May, 1985 %K We discuss how to compute an eigendecomposition of a matrix pencil %K A-zB when A and B are only known to within a tolerance epsilon. When %K A-zB is regular (i.e. det(A-zB) is not identically zero) we show how %K to partition the spectrum and eigenspaces of A-zB into clusters which %K vary smoothly as A-zB varies within a ball of radius epsilon. When %K A-zB is singular (a case of interest in systems theory) so that the %K structures we wish to compute are nongeneric, we show that certain spaces %K and eigenvalues of the pencil vary smoothly if A-zB varies along a lower %K dimensional surface as well as within a ball of radius epsilon. This %K result implies that the usual algorithms for analyzing singular pencils %K generally compute accurate eigenvalues and spaces. We apply this result %K by computing perturbation bounds for the controllable subspace and %K uncontrollable modes of a system dx/dt = Cx + Du. %K Submitted by: James Demmel (demmel.csd2@nyu) %K Obtainable from: %K James Demmel %K Courant Institute %K 251 Mercer Str. %K New York, NY 10012 %K --------------- %K [16] Jonathan Goodman, Robert Kohn, and Luis Reyna %K A Numerical Study of a Relaxed Variational Problem %K We present the numerical solution of an optimization problem that arises %K in two phase flow, and in the design of a beam out of two different materials %K in given proportion for optimum torsional rigidity. The problem is to %K minimize a Dirichlet integral over all possible functions and over all possible %K subdomains of a given area. Minimizing over functions with the subdomain fixed %K would lead to a second order elliptic equation with discontinuous coefficients. %K A naive (but very plausible) algorithm based directly on this formulation is %K shown to have "premature termination" at points that are not even stationary %K points. It is known that problems like this often do not have "classical" %K solutions. Rather, there are "weak" or "relaxed" solutions that involve %K microscopic mixing of the two materials. Application of homogenization theory %K gives a relaxed minimization problem that can numerically be solved. We used a %K variational multigrid proceedure to get high resolution (256 x 256) in %K reasonable time on a VAX-780. The numerical results show that the region of %K microscopic mixing can occupy about 15% of the region in some cases. %K Submitted by: Jonathan Goodman (goodnan@nyu-acf1.csnet) %K Obtainable from: %K Jonathan Goodman %K Courant Institute of Mathematical Sciences %K 251 Mercer St. %K New York, New York, 10012 %K --------------- %K [17] Jonathan Goodman, Robert Kohn, and Luis Reyna %K A Numerical Study of a Relaxed Variational Problem %K We present the numerical solution of an optimization problem that arises %K in two phase flow, and in the design of a beam out of two different materials %K in given proportion for optimum torsional rigidity. The problem is to %K minimize a Dirichlet integral over all possible functions and over all possible %K subdomains of a given area. Minimizing over functions with the subdomain fixed %K would lead to a second order elliptic equation with discontinuous coefficients. %K A naive (but very plausible) algorithm based directly on this formulation is %K shown to have "premature termination" at points that are not even stationary %K points. It is known that problems like this often do not have "classical" %K solutions. Rather, there are "weak" or "relaxed" solutions that involve %K microscopic mixing of the two materials. Application of homogenization theory %K gives a relaxed minimization problem that can numerically be solved. We used a %K variational multigrid proceedure to get high resolution (256 x 256) in %K reasonable time on a VAX-780. The numerical results show that the region of %K microscopic mixing can occupy about 15% of the region in some cases. %K Obtainable from J. Goodman, above %K --------------- %K [18] Jonathan Goodman %K Convergence of the Random Vortex Method %K The random vortex method, introduced by Chorin, was intended to compute %K high Reynolds number incompressible flows in 2 or 3 dimensions. We prove %K that the method converges (with probability one) for smooth flows without %K boundaries in two dimensions. The error bounds are independent of the %K viscosity. The proof relies on the form of smoothing (replacing vortex %K points by vortex blobs) introduced by Hald in his convergence proof for %K the (non-random) vortex method for the incompressible Euler equations in %K 2 dimensions. %K Obtainable from J. Goodman, above %K --------------- %K ##### EMORY ##### %K [19] Henry Wolkowicz and Phil Smith %K A NONLINEAR EQUATION FOR LINEAR PROGRAMMING %K Research Report 16 %K Emory University %K We present a characterization of the 'normal' optimal solution of the linear %K programming problem. This characterization involves the solution of %K m piecewise linear equations in m unknowns. %K Submitted by: Henry Wolkowicz %K csnet: henry@emory %K bitnet: henry_wolkowicz@uqv-mts.bitnet %K uucp: alberta!uqv-mts!sunn %K emory!henry %K Obtainable from: %K Henry Wolkowicz %K Department of Mathematics and Computer Science %K Emory University %K Atlanta, Georgia 30322 %K --------------- %K From GOLUB@SU-SCORE.ARPA Fri Aug 30 15:40:44 1985 %K Received: from SU-SCORE.ARPA (su-score.arpa.ARPA) by anl-mcs.ARPA ; Fri, 30 Aug 85 15:39:53 cdt %K Return-Path: <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Received: from csnet-relay by SU-SCORE.ARPA with TCP; Tue 27 Aug 85 17:57:31-PDT %K Received: from waterloo by csnet-relay.csnet id af16675; 27 Aug 85 20:36 EDT %K Date: Tue, 27 Aug 85 13:13:16 edt %K From: Richard Bartels <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Message-Id: <8508271713.AA25261@watcgl.UUCP> %K To: na@SU-SCORE.ARPA %K Subject: T&A Part 2 of 3 %K Resent-Date: Fri 30 Aug 85 11:48:00-PDT %K Resent-From: Gene Golub (415/497-3124) <GOLUB@SU-SCORE.ARPA> %K Resent-To: :; %K Resent-Message-Id: <12139307553.36.GOLUB@SU-SCORE.ARPA> %K Status: RO %K ================================================== %K NUMERICAL ANALYSIS TITLES %K -- Volume 3, Number 2, Part 2 of 3 %K -- August 27, 1985 %K ================================================== %K Please note: Due to its length, this list is %K being distributed in 3 parts, each %K part is about 7 pages in length. %K ##### GMD, WEST GERMANY ##### %K All the papers of the GMD may be ordered from %K Dr. Kurt Brand %K Gesellschaft fuer Mathematik und %K Datenverarbeitung (GMD) %K F1/T %K Postfach 1240 %K D-5205 St. Augustin 1 %K F.R.G. %K or send a request by electronic mail to %K gmap18%dbngmd21.bitnet@wiscvm.arpa %K No abstracts were submitted. %K ################### %K [20] K. Becker %K Ein Mehrgitterverfahren zur Berechnung subsonischer Potential- %K stroemungen um Tragflaechenprofile %K Berichte der Gesellschaft fuer Mathematik und Datenverarbeitung, %K Bericht Nr. 152, Oldenbourg-Verlag, 1985 %K --------------- %K [21] K. Becker, U. Trottenberg %K Development of Multigrid Algorithms for Problems from Fluid Dynamics %K Arbeitspapiere der GMD no.111, Gesellschaft fuer Mathematik und %K Datenverarbeitung, Bonn, 1984. (DM 6,-) %K --------------- %K [22] A. Brandt %K Multigrid Techniques: 1984 Guide with Applications to Fluid Dynamics %K GMD-Studien no. 85, Gesellschaft fuer Mathematikund Daten- %K verarbeitung, Bonn, 1984. (DM 39,-) %K --------------- %K [23] O. Kolp %K Parallelisierung eines Mehrgitterverfahrens fuer einen Baumrechner %K Arbeitspapiere der GMD no. 82, Bonn, 1984. (DM 10,-) %K --------------- %K [24] R. Lorenz %K Some New Periodic Chebycheff Spaces %K Arbeitspapiere der GMD no. 79, Gesellschaft fuer Mathematik und %K Datenverarbeitung, Bonn, 1984 %K --------------- %K [25] J. Ruge, K. Stueben %K Efficient Solution of Finite Difference and Finite Element %K Equations by Algebraic Multigrid (AMG) %K Arbeitspapiere der GMD no. 89, Gesellschaft fuer Mathematik %K und Datenverarbeitung, Bonn, 1984. (DM 10,-) %K --------------- %K [26] B. Ruttmann, K. Solchenbach %K A Multigrid Solver for the computation of in-cylinder turbulent %K flows in engines %K Efficient Solutions of Elliptic Systems, %K Proceedings of GAMM-Seminar, Kiel, January 27 to 29, 1984, %K (W. Hackbusch ed.). %K Notes on Numerical Fluid Mechanics, 10, pp. 87-108, Vieweg, %K Braunschweig, 1984. %K --------------- %K [27] K. Stueben, U. Trottenberg, K. Witsch %K Software Development Based on Multigrid Techniques %K Arbeitspapiere der GMD no. 84, Gesellschaft fuer Mathematik %K und Datenverarbeitung, Bonn, 1984. (DM 10,-) %K --------------- %K [28] C.-A. Thole, U. Trottenberg %K Basic Smoothing Procedures for the Multigrid Treatment of %K Elliptic 3D-Operators %K Arbeitspapiere der GMD no. 141, Bonn, 1985. (DM 10,-) %K --------------- %K [29] U. Trottenberg %K Schnelle Loesung elliptischer Differentialgleichungen nach dem %K Mehrgitterprinzip %K GAMM-Mitteilungen, 1/84, February 1984. %K --------------- %K [30] U. Trottenberg, P. Wypior (Ed.) %K Rechnerarchitekturen fuer die numerische Simulation auf der %K Basis superschneller Loesungsverfahren I %K Workshop "Rechnerarchitektur", Erlangen, 14.-15. Juni 1984. %K GMD-Studien no. 88, Gesellschaft fuer Mathematik und Daten- %K verarbeitung, Bonn, 1984. (DM 48,-) %K --------------- %K [31] U. Trottenberg, P. Wypior (Ed.) %K Rechnerarchitekturen fuer die numerische Simulation auf der %K Basis superschneller Loesungsverfahren II %K Workshop "Simulation/Anwendungen und Numerik", %K GMD-Studien no. 102, Gesellschaft fuer Mathematik und Daten- %K verarbeitung, Bonn, 1985. (DM 48,-) %K --------------- %K [32] U. Trottenberg %K Mehrgitterprinzip und Rechnerarchitektur %K GAMM-Mitteilungen, 1/84, February 1984. %K --------------- %K ##### ICASE ##### %K All ICASE reports listed here may be %K obtained by writing to: %K Barbara Kraft %K ICASE, M/S 132C %K NASA Langley Research Center %K Hampton, VA 23665 %K ################### %K [33] Zang, T. A. and M. Y. Hussaini %K A three-dimensional spectral algorithm for %K simulations of transition and turbulence %K ICASE Report No. 85-19, March 6, 1985, 39 pages. %K AIAA Paper No. 85-0296 presented at the AIAA 23rd %K Aerospace Sciences Meeting, January 14-17, 1985, Reno, Nevada. %K A spectral algorithm for simulating three-dimensional, incompressible, %K parallel shear flows is described. It applies to the channel, to the parallel %K boundary layer, and to other shear flows with one wall-bounded and two %K periodic directions. Representative applications to the channel and to the %K heated boundary layer are presented. %K --------------- %K [34] Drummond, J. P., M. Y. Hussaini, and T. A. Zang %K Spectral methods for modeling supersonic %K chemically reacting flow fields %K ICASE Report No. 85- 20, %K March 8, 1985, 37 pages. AIAA J. %K A numerical algorithm has been developed for solving the equations %K describing chemically reacting supersonic flows. The algorithm employs a two- %K stage Runge-Kutta method for integrating the equations in time and a Chebyshev %K spectral method for integrating the equations in space. The accuracy and %K efficiency of the technique have been assessed by comparison with an existing %K implicit finite-difference procedure for modeling chemically reacting flows. %K The comparison showed that the new procedure yielded equivalent accuracy on %K much coarser grids as compared to the finite-difference procedure with %K resultant significant gains in computational efficiency. %K --------------- %K [35] LeVeque, R. J %K Intermediate boundary conditions for LOD, ADI, %K and approximate factorization methods %K ICASE Report No. 85-21, April 17, 1985, 24 pages. %K Submitted to J. Comput. Phys. %K A general approach to determining the correct intermediate boundary %K conditions for dimensional splitting methods is presented and illustrated. %K The intermediate solution U* is viewed as a second-order accurate %K approximation to a modified equation. Deriving the modified equation and %K using the relationship between this equation and the original equation allows %K us to determine the correct boundary conditions for U*. To illustrate this %K technique, we apply it to LOD and ADI methods for the heat equation in two and %K three space dimensions. The approximate factorization method is considered in %K slightly more generality. %K --------------- %K [36] Rosen, I. G. %K Spline-based Rayleigh-Ritz methods for the approximation of the %K natural modes of vibration for flexible beams with tip bodies %K ICASE Report No. 85-22, March 18, 1985, 31 pages. %K Submitted to Quarterly of Applied Mathematics. %K Rayleigh-Ritz methods for the approximation of the natural modes for a %K class of vibration problems involving flexible beams with tip bodies using %K subspaces of piecewise polynomial spline functions are developed. An abstract %K operator theoretic formulation of the eigenvalue problem is derived and %K spectral properties investigated. The existing theory for spline-based %K Rayleigh-Ritz methods applied to elliptic differential operators and the %K approximation properties of interpolatory splines are used to argue %K convergence and establish rates of convergence. An example and numerical %K results are discussed. %K --------------- %K [37] Bayliss, A., L. Maestrello, P. Parikh, and E. Turkel %K Numerical simulation of boundary layer excitation %K by surface heating/cooling %K ICASE Report No. 85-23, March 25, 1985, 22 pages. %K AIAA Paper No. 85-0565, AIAA Shear Flow %K Control Conference, March 12-14, 1985, Boulder, CO. %K This paper is a numerical study of the concept of active control of %K growing disturbances in an unstable compressible flow by using time periodic, %K localized surface heating. The simulations are calculated by a fourth-order %K accurate solution of the compressible, laminar Navier-Stokes equations. %K Fourth-order accuracy is particularly important for this problem because the %K solution must be computed over many wavelengths. The numerical results %K demonstrate the growth of an initially small fluctuation into the nonlinear %K regime where a local breakdown into smaller scale disturbances can be %K observed. It is shown that periodic surface heating over a small strip can %K reduce the level of the fluctuation provided that the phase of the heating %K current is properly chosen. %K --------------- %K [38] Hossain, M., G. Vahala, and D. Montgomery %K Forced MHD turbulence in a uniform external magnetic field %K ICASE Report No. 85-24, March 28, 1985, 39 pages. %K Submitted to Phys. Fluid. %K Two-dimensional dissipative MHD turbulence is randomly driven at small %K spatial scales and is studied by numerical simulation in the presence of a %K strong uniform external magnetic field. A novel behavior is observed which is %K apparently distinct from the inverse cascade which prevails in the absence of %K an external magnetic field. The magnetic spectrum becomes dominated by the %K three longest-wavelength Alfv'n waves in the system allowed by the boundary %K conditions: those which, in a box size of edge 2 pi, have wave numbers %K (kx, ky) = (1, 0), (1, 1), and (1, -1), where the external magnetic field is %K in the x direction. At any given instant, one of these three modes %K dominates the vector potential spectrum, but they do not constitute a %K resonantly coupled triad. Rather, they are apparently coupled by the smaller- %K scale turbulence. %K --------------- %K [39] Davis, S. F. %K Shock capturing %K ICASE Report No. 85-25, April 26, 1985, 23 pages. %K To appear in Numerical Methods for Partial Differential Equations, %K (S. I. Hariharan and T. H. Moulder, eds.), Pitman Press, 1986. %K This chapter describes recent developments which have improved our %K understanding of how finite difference methods resolve discontinuous solutions %K to hyperbolic partial differential equations. As a result of this %K understanding improved shock capturing methods are currently being developed %K and tested. Some of these methods are described and numerical results are %K presented showing their performance on problems containing shocks in one and %K two dimensions. %K We begin this discussion by defining what is meant by a conservative %K difference scheme and showing that conservation implies that, except in very %K special circumstances, shocks must be spread over at least two grid intervals. %K These two interval shocks are actually attained in one dimension if the shock %K is steady and an upwind scheme is used. By analyzing this case, we determine %K the reason for this excellent shock resolution and use this result to provide %K a mechanism for improving the resolution of two-dimensional steady shocks. %K Unfortunately, this same analysis shows that these results cannot be extended %K to shocks which move relative to the computing grid. %K To deal with moving shocks and contact discontinuities we introduce total %K variation diminishing (TVD) finite difference schemes and flux limiters. We %K show that TVD schemes are not necessarily upwind, but that upwind TVD schemes %K perform better because they permit a wider choice of flux limiters. The %K advantage of non-upwind TVD schemes is that they are easy to implement. %K Indeed, it is possible to add an appropriately chosen artificial viscosity to %K a conventional scheme such as MacCormack's method and make it TVD. We %K conclude by presenting some theoretical results on flux limiters and some %K numerical computations to illustrate the theory. %K --------------- %K [40] Brandt, A. and S. Ta'asan %K Multigrid solutions to quasi-elliptic schemes. %K ICASE Report No. 85-26, May 3, 1985, 21 pages. %K Progress and Supercomputing in Computational Fluid Dynamics, %K (Earl. S. Murman and Saul Abarbanel, eds.), %K Birkhauser Boston, Inc., (tentative publication date: %K August 20, 1985). %K Quasi-elliptic schemes arise from central differencing or finite element %K discretization of elliptic systems with odd order derivatives on non-staggered %K grids. They are somewhat unstable and less accurate then corresponding %K staggered-grid schemes. When usual multigrid solvers are applied to them, the %K asymptotic algebraic convergence is necessarily slow. Nevertheless, it is %K shown by mode analyses and numerical experiments that the usual FMG algorithm %K is very efficient in solving quasi-elliptic equations to the level of %K truncation errors. Also, a new type of multigrid algorithm is presented, mode %K analyzed and tested, for which even the asymptotic algebraic convergence is %K fast. The essence of that algorithm is applicable to other kinds of problems, %K including highly indefinite ones. %K --------------- %K [41] Zang, T. A. and M. Y. Hussaini %K On spectral multigrid methods for the %K time-dependent Navier-Stokes equations %K ICASE Report No. 85-27, May 13, 1985, 24 pages. %K Presented at the 2nd Copper Mountain Conference on Multigrid %K Methods, April 1-3, 1985, Copper Mountain, CO. %K A new splitting scheme is proposed for the numerical solution of the %K time-dependent, incompressible Navier-Stokes equations by spectral methods. A %K staggered grid is used for the pressure, improved intermediate boundary %K conditions are employed in the split step for the velocity, and spectral %K multigrid techniques are used for the solution of the implicit equations. %K --------------- %K [42] Osher, S. and E. Tadmor %K On the convergence of difference approximations %K to scalar conservation laws %K ICASE Report No. 85-28, May 14, 1985, 70 pages. %K Submitted to Math. Comp. %K We present a unified treatment of explicit in time, two level, second %K order resolution, total variation diminishing, approximations to scalar %K conservation laws. The schemes are assumed only to have conservation form and %K incremental form. We introduce a modified flux and a viscosity coefficient and %K obtain results in terms of the latter. The existence of a cell entropy %K inequality is discussed and such an equality for all entropies is shown to %K imply that the scheme is an E scheme on monotone (actually more general) %K data, hence at most only first order accurate in general. Convergence for %K TVD-SOR schemes approximating convex or concave conservation laws is shown by %K enforcing a single discrete entropy inequality. %K --------------- %K [43] Mehrotra, P. and J. Van Rosendale %K The BLAZE language: A parallel language %K for scientific programming %K ICASE Report No. 85-29, May 15, 1985, 57 %K pages. Submitted to Parallel Computing. %K Programming multiprocessor parallel architectures is a complex task. %K This paper describes a Pascal-like scientific programming language, Blaze, %K designed to simplify this task. Blaze contains array arithmetic, "forall" %K loops, and APL-style accumulation operators, which allow natural expression of %K fine grained parallelism. It also employs an applicative or functional %K procedure invocation mechanism, which makes it easy for compilers to extract %K coarse grained parallelism using machine specific program restructuring. Thus %K Blaze should allow one to achieve highly parallel execution on multiprocessor %K architectures, while still providing the user with conceptually sequential %K control flow. %K A central goal in the design of Blaze is portability across a broad range %K of parallel architectures. The multiple levels of parallelism present in %K Blaze code, in principle, allows a compiler to extract the types of %K parallelism appropriate for the given architecture, while neglecting the %K remainder. This paper describes the features of Blaze, and shows how this %K language would be used in typical scientific programming. %K --------------- %K [44] Trefethen, L. N. and L. Halpern %K Well-Posedness of one-way wave equations and %K absorbing boundary conditions %K ICASE Report No. 85-30, June 10, 1985, 23 pages. %K Submitted to Math. Comp. %K A one-way wave equation is a partial differential equation which, in some %K approximate sense, behaves like the wave equation in one direction but permits %K no propagation in the opposite one. The construction of such equations can be %K reduced to the approximation of the square root of 1 - s2 on [-1,1] by a %K rational function r(s) = Pm(s)/qn(s). This paper characterizes those %K rational functions r for which the corresponding one-way wave equation is %K well-posed, both as a partial differential equation and as an absorbing %K boundary condition for the wave equation. We find that if r(s) interpolates %K the square root of 1 - s2 at sufficiently many points in (-1,1), then well- %K posedness is assured. It follows that absorbing boundary conditions based on %K Pade approximation are well-posed if and only if (m,n) lies in one of two %K distinct diagonals in the Pade table, the two proposed by Engquist and %K Majda. Analogous results also hold for one-way wave equations derived from %K Chebyshev or least-squares approximation. %K --------------- %K [45] Majda, G. %K A new theory for multistep discretizations of stiff ordinary %K differential equations: Stability with large step sizes %K ICASE Report No. 85-31, 70 pages. %K Submitted to Math. Comp. %K In this paper we consider a large set of variable coefficient linear %K systems of ordinary differential equations which possess two different time %K scales, a slow one and a fast one. A small parameter epsilon characterizes %K the stiffness of these systems. We approximate a system of o.d.e.s in this %K set by a general class of multistep discretizations which includes both one- %K leg and linear multistep methods. We determine sufficient conditions under %K which each solution of a multistep method is uniformly bounded, with a bound %K which is independent of the stiffness of the system of o.d.e.s, when the step %K size resolves the slow time scale but not the fast one. We call this property %K stability with large step sizes. %K The theory presented in this paper lets us compare properties of one-leg %K methods and linear multistep methods when they approximate variable %K coefficient systems of stiff o.d.e.s. In particular, we show that one-leg %K methods have better stability properties with large step sizes than their %K linear multistep counterparts. This observation is consistent with results %K obtained by Dahlquist and Lindberg {11}, Nevanlinna and Liniger {32} and van %K Veldhuizen {41}. Our theory also allows us to relate the concept of D- %K stability (van Veldhuizen {41}) to the usual notions of stability and %K stability domains and to the propagation of errors for multistep methods which %K use large step sizes. %K --------------- %K [46] Banks, H. T. %K On a variational approach to some %K parameter estimation problems. %K ICASE Report No. 85-32, 38 pages. %K Invited lecture, Internationl Conference on %K Control Theory for Distributed Parameter %K Systems and Applications, July 9 - 14, 1984, Voran, Austria. %K We consider examples (1-D seismic, large flexible structures, %K bioturbation, nonlinear population dispersal) in which a variational setting %K can provide a convenient framework for convergence and stability arguments in %K parameter estimation problems. %K --------------- %K [47] Hariharan, S. I. %K Absorbing boundary conditions for exterior problems %K ICASE Report No. 85-33, July 18, 1985, 33 pages. %K To appear in Numerical Methods for Partial Differential %K Equations, (S. I Hariharan and T. H. Moulden, eds.), %K Pitman Press, 1986. %K In this paper we consider elliptic and hyperbolic problems in unbounded %K regions. These problems, when one wants to solve them numerically, have the %K difficulty of prescribing boundary conditions at infinity. Computationally, %K one needs a finite region in which to solve these problems. The corresponding %K conditions at infinity imposed on the finite distance boundaries should %K dictate the boundary condition at infinity and be accurate with respect to the %K interior numerical scheme. Such boundary conditions are commonly referred to %K as absorbing boundary conditions. This paper presents a survey and covers our %K own treatment on these boundary conditions for wave-like equations. %K --------------- %K From GOLUB@SU-SCORE.ARPA Fri Aug 30 16:44:09 1985 %K Received: from SU-SCORE.ARPA (su-score.arpa.ARPA) by anl-mcs.ARPA ; Fri, 30 Aug 85 16:43:21 cdt %K Return-Path: <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Received: from csnet-relay by SU-SCORE.ARPA with TCP; Wed 28 Aug 85 08:22:34-PDT %K Received: from waterloo by csnet-relay.csnet id ac19806; 28 Aug 85 7:31 EDT %K Date: Tue, 27 Aug 85 13:13:45 edt %K From: Richard Bartels <rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa> %K Message-Id: <8508271713.AA25302@watcgl.UUCP> %K To: na@SU-SCORE.ARPA %K Subject: T&A Part 3 of 3 %K Resent-Date: Fri 30 Aug 85 11:48:03-PDT %K Resent-From: Gene Golub (415/497-3124) <GOLUB@SU-SCORE.ARPA> %K Resent-To: :; %K Resent-Message-Id: <12139307563.36.GOLUB@SU-SCORE.ARPA> %K Status: RO %K ================================================== %K NUMERICAL ANALYSIS TITLES %K -- Volume 3, Number 2, Part 3 of 3 %K -- August 27, 1985 %K ================================================== %K Please note: Due to its length, this list is %K being distributed in 3 parts, each %K part is about 7 pages in length. %K ##### JOHNS HOPKINS ##### %K [48] Ralph Byers and Stephen Nash %K On the Singular "Vectors" of the Lyapunov Operator %K Tech Rep 438 %K Mathematical Sciences Department %K The Johns Hopkins University %K June 1985 %K For a real matrix A, the separation of A' and A is sep(A',-A) = %K min ||A'X + XA||/||X||, where ||.|| represents the Frobenius norm, %K and A' is the transpose of A. We discuss the conjecture that the %K minimizer X is symmetric. This conjecture is related to the numerical %K stability of methods for solving the matrix Lyapunov equation. The %K quotient is minimized by either a symmetric matrix or a skew symmetric %K matrix and is maximized by a symmetric matrix. The conjecture is true %K if A is 2-by-2, if A is normal, if the minimum is zero, or if the real %K parts of the eigenvalues of A are of one sign. In general the conjecture %K is false, but counter examples suggest that symmetric matrices are %K nearly optimal. %K Submitted by: Steve Nash (sgn@jhu.csnet) %K Obtainable from: %K Steve Nash %K Department of Mathematical Sciences %K The Johns Hopkins University %K Baltimore, MD 21218 %K --------------- %K ##### MARYLAND ##### %K [49] Dianne P. O'Leary, %K Systolic Arrays for Matrix Transpose and Other Reorderings %K Computer Science Department %K University of Maryland %K TR-1481, March, 1985. %K In this note, a systolic array is described for computing the %K transpose of an n-by-n matrix in time 3n-1 using n squared switching %K processors and n squared bit buffers. A one-dimensional implementation %K is also described. Arrays are also given to take a matrix in by %K rows and put it out by diagonals, and vice versa. %K Submitted by: Dianne Oleary (oleary@maryland.arpa) %K Obtainable from: %K Dianne Oleary %K Department of Computer Science %K University of Maryland %K College Park, MD 20742 %K --------------- %K [50] Dianne P. O'Leary, G. W. Stewart %K Assignment and Scheduling in Parallel Matrix Factorization %K Computer Science Department %K University of Maryland %K TR-1486, April, 1984. %K We consider in this paper the problem of factoring a dense n-by-n %K matrix on a network consisting of P MIMD processors when the net- %K work is smaller than the number of elements in the matrix %K 2 %K (P < n ). The specific example analyzed is a computational net- %K work that arises in computing the LU, QR, or Cholesky factoriza- %K tions. We prove that if the nodes of the network are evenly dis- %K tributed among processors and if computations are scheduled by a %K round-robin or a least-recently-executed scheduling algorithm, %K then optimal order of speed-up is achieved. However, such speed- %K up is not necessarily achieved for other scheduling algorithms or %K if the computation for the nodes is inappropriately split across %K processors, and we give examples of these phenomena. Lower %K bounds on execution time for the algorithm are established for %K two important node-assignment strategies. %K Obtainable from: D. Oleary, above. %K --------------- %K ##### OAK RIDGE ##### %K All Oak Ridge reports listed below %K may be obtained from: %K Ms. Dawn Human %K Mathematical Sciences %K Oak Ridge National Laboratory %K P. O. Box Y, Bldg. 9207-A %K Oak Ridge, TN 37831 %K electronically: %K human@ornl-msr.arpa %K ##################### %K [51] George Ostrouchov %K ANOVA Model Fitting via Sparse Matrix Computations %K ORNL Tech. Report, August 1985 %K The least-squares computational approach is used in fitting %K analysis of variance models when data are unbalanced or incomplete. %K For large models containing factors with many levels, standard %K statistical packages require enormous amounts of time and storage due %K to the size of the crossproducts matrix. The model matrix X (often %K called the design matrix) consists of dummy variables and is sparse, %K thus great reduction in time and storage can be achieved by viewing %K this as a sparse matrix problem. %K A method, based on orthogonal Givens factorization of a maximal %K rank set of sparse columns of X, for computing estimates and residual %K sums of squares is presented. Selection of a maximal rank set of %K sparse columns is a key part of this method and is based on the linear %K dependencies between columns of the model matrix. The linear %K dependencies are described using a notation based on index sets %K associated with model terms. %K Time and storage requirements of the new algorithm are compared to %K the requirements of GLIM, which uses the same basic numerical algorithm %K that is used in most statistical packages. Both requirements of the %K new algorithm are less by up to three orders of magnitude for large %K models and are competitive for small models. %K Submitted by: George Ostrouchov %K -------------- %K [52] V. Alexiades J.B. Drake G.A. Geist G.E. Giles A.D. Solomon R.F. Wood %K Mathematical Modeling of Laser-Induced Ultrarapid %K Melting and Solidification %K ORNL-6129, July 1985 %K Mathematical and numerical aspects of laser induced phase change %K modeling are dicussed. Several numerical formulations, including %K explicit and implicit enthalpy, adaptive grid finite volume and %K front tracking are derived and results are presented. In addition, %K a novel hyperbolic formulation is explored analytically and %K numerically. The explicit enthalpy approach allows the greatest %K flexibility and efficiency in modeling problems with complicated %K phase transitions. %K Submitted by: Vasili Alexiades %K -------------- %K [53] Max Morris Vasili Alexiades %K Sensitivity Analysis of a Numerically Simulated %K HgCdTe Solidification Process by Statistical Methods %K ORNL-6210, August 1985 %K Statistical response surface methodology is applied to the problem of %K determining simple approximations for outputs as functions of input %K parameter values in a numerical simulation of the solidification of %K a mercury-cadmium-telluride alloy. The approximating polynomials are %K then differentiated with respect to parameter values to determine %K sensitivities. A table of percent changes in output values as a %K result of one per cent changes in parameter values is presented. %K The empirical procedure used constitutes an unorthodox application %K of the statistical methodology, but it is easy to use, quite generally %K applicable and very effective. %K Submitted by: Vasili Alexiades %K -------------- %K [54] V. Alexiades G. A. Geist A. D. Solomon %K Numerical Simulation of a HgCdTe Solidification Process %K ORNL-6127, August 1985 %K The solidification of a cylindrical ingot of mercury-cadmium-telluride is %K modeled taking into account both heat conduction and solute diffusion. %K Values of the relevant thermophysical parameters of the pseudo-binary %K HgTe-CdTe are compiled. The model is implemented numerically by a %K finite-difference discretization and results of the simulation of a %K freezing experiment are reported. %K Submitted by: Vasili Alexiades %K -------------- %K [55] George A. Geist Michael T. Heath %K Parallel Cholesky Factorization on a Hypercube Multiprocessor %K ORNL-6190, July 1985 %K Two types of message-passing parallel algorithms are developed for %K solving symmetric systems of linear equations on a hypercube %K multiprocessor. One type involves broadcast communication among %K processors, and the other involves communication along a ring of %K processors. Details are provided in the form of C programs that %K implement the algorithms on a hypercube simulator and which should run %K with little modification on real hypercube hardware. Performance of %K the various algorithms is demonstrated by means of processor %K utilization graphs and parallel speedup curves. %K Submitted by: Mike Heath %K -------------- %K [56] Michael T. Heath %K Parallel Cholesky Factorization in %K Message-Passing Multiprocessor Environments %K ORNL-6150, May 1985 %K Parallel algorithms are presented for computing the Cholesky %K factorization on multiprocessors having only private local memory. %K Synchronization of multiple processes is based on message passing. %K Several possible processor interconnection networks are considered. %K Submitted by: Mike Heath %K -------------- %K [57] George A. Geist %K ORNL %K Efficient Parallel LU Factorization with Pivoting %K on a Hypercube Multiprocessor %K ORNL-6211, August 1985 %K A message-passing parallel algorithm is developed for forming %K the LU factors of general non-singular matrices on a hypercube %K multiprocessor. Partial pivoting is performed to ensure numerical %K stability, but the scheduling of tasks is such that the pivot search %K in the parallel algorithm is completely masked. Empirical tests show %K that the load imbalance produced by random pivoting causes a 5%-14% %K increase in execution time. A complementary parallel triangular %K solution algorithm is also given. Comparisons with the non-pivoting %K case are used to demonstrate the efficiency of this new algorithm. %K Submitted by: Al Geist %K -------------- %K ##### PITT ##### %K [58] Rami G. Melhem %K A Study of Data Interlock in VLSI Computational %K Networks for Sparse Matrix Multiplication %K TR-CSD-505 %K Department of Computer Science %K Purdue University %K April 1985 %K The general question addressed in this study is: Are regular VLSI networks %K suitable for sparse matrix computations?. More specifically, we consider %K a special purpose self-timed network that is designed for certain specific %K dense matrix computation. We add to each cell in the network the capability %K of recognizing and skipping operations that involve zero operands, and then %K ask how efficient this resulting network is for sparse matrix computation?. %K In order to answer this question, it is necessary to study the effect of %K data interlock on the performance of self-timed networks. For this, the %K class of pseudo systolic networks is introduced as a hybrid class between %K systolic and self-timed networks. Networks in this class are easy to analyze, %K and provide a means for the study of the worst case performance of self-timed %K networks. The well known concept of computation front is also generalized to %K include irregular flow of data, and a technique based on the propagation of %K such computation fronts is suggested for the estimation of the processing %K time and the communication time of pseudo systolic networks. %K Submitted by: Rami Melhem (melhem@purdue OR melhem@pitt) %K Obtainable from: %K Rami Melhem %K University of Pittsburgh %K Department of Mathematics %K Pittsburgh, PA 15260 %K --------------- %K [59] Rami G. Melhem %K A Modified Frontal Technique Suitable for parallel Systems %K ICMA-85-84 %K Department of Mathematics %K University of Pittsburgh %K July 1985 %K Frontal techniques offer the potential for processing the assembly and %K the factorization phases of finite element analysis in parallel. %K However, the rows of the stiffness matrix are assembled and factored %K in different order, thus depriving frontal solvers of the uniformity %K desirable in parallel processing. On the other hand, band solution %K techniques handle the factorization phase in a very uniform way but %K do not interleave assembly and factorization. In this paper, we %K suggest a technique that borrows from both frontal and band solvers %K those characteristics that are advantageous for parallel processing. Moreover, %K book-keeping and data manipulation are simpler in the suggested %K techniques than in the classical frontal method. %K This makes the suggested technique also attractive for sequential systems. %K Obtainable from: Rami Melhem, as above. %K --------------- %K ##### STANFORD ##### %K [60] Gene H. Golub and Carl D. Meyer %K Simultaneous Computation of Stationary Probabilities %K with Estimates of Their Sensitivity %K SIAM ms.no.10958 %K < No Abstract > %K Submitted by: Gene H. Golub (golub@su-navajo.arpa) %K Obtainable from: %K Gene H. Golub (golub@su-navajo.arpa) %K Computer Science Department %K Stanford University %K Stanford, CA 94305 %K --------------- %K [61] Philip E. Gill, Walter Murray, Michael A. Saunders, %K J. A. Tomlin, and Margaret H. Wright %K ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR %K PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR'S PROJECTIVE METHOD %K We discuss interior-point methods for linear programming derived by applying %K a logarithmic barrier transformation and performing projected Newton steps %K for a sequence of barrier parameters. Under certain conditions, %K one of these ``projected Newton barrier'' methods is shown to be %K equivalent to Karmarkar's (1984) projective method for linear programming. %K Details are given of a specific barrier algorithm and its practical %K implementation. Numerical results are given for several nontrivial test %K problems. %K Submitted by: Philip E. Gill (or.gill@su-sierra.arpa) %K Obtainable from: %K Philip E. Gill (or.gill@su-sierra.arpa) %K Systems Optimization Laboratory %K Operations Research Department %K Stanford University %K Stanford, CA 94305 %K --------------- %K ##### SUNY/BUFFALO ##### %K [62] P.J.Eberlein %K On the Schur Decomposition of a Matrix for Parallel Computation %K TR 85-689, June 1985, Cornell University %K An algorithm to solve the eigenproblem for non-symmetric matrices on %K an N x N array of mesh connected processors, isomorphic to the architecture %K described by Brent and Luk for symmetric matrices, is presented. This %K algorithm is a generalization of the classical Jacobi method which holds %K promise for parallel architectures. Only unitary transformations are used. %K The rotational parameters are carefully analysed, and many examples of a %K working program, simulating the parallel architecture, are given. %K Submitted by: P.J.Eberlein (eberlein%gvax@cornell.arpa) %K Obtainable from: %K P.J.Eberlein %K Dept. of Computer Science %K SUNY/Buffalo, Bell Hall, %K Buffalo, N.Y. 14260 %K --------------- %K ##### TORONTO ##### %K [63] D.W. Decker and A. Jepson %K Convergence cones near bifurcation %K TR 171/84. %K < No Abstract > %K Submitted by: Ken R. Jackson (krj@toronto.csnet) %K Obtainable from: %K The Scientific Computing Group, %K Department of Computer Science, %K University of Toronto, %K Toronto, Ontario, %K Canada M5S 1A4 %K --------------- %K [64] Paul Muir %K Implicit Runge-Kutta methods for %K two-point boundary value problems %K TR 175/84. %K < No Abstract > %K Obtainable from the above. %K --------------- %K [65] Kevin Burrage %K The order properties of implicit multivalue %K methods for ordinary differential equations %K TR 176/84. %K < No Abstract > %K Obtainable from the above. %K --------------- %K [66] Kevin Burrage %K Order and stability properties of %K explicit multivalue methods %K TR 177/84. %K < No Abstract > %K Obtainable from the above. %K --------------- %K [67] W.H. Enright, K.R. Jackson, S.P. Norsett, and P.G. Thomsen %K Interpolants for Runge-Kutta formulas %K TR 180/85. %K < No Abstract > %K Obtainable from the above. %K --------------- %K [68] J.M. Fine %K Low order Runge-Kutta-Nystrom methods with interpolants %K TR 183/85. %K < No Abstract > %K Obtainable from the above. %K --------------- %K ##### WASHINGTON STATE ##### %K [69] ALAN GENZ %K FULL SYMMETRIC INTERPOLATORY FOR MULTIPLE INTEGRALS %K CS-85-136 %K WASHINGTON STATE UNIVERSITY %K JULY, 1984 %K A method is given for the direct determination of the weights for fully %K symmetric integration rules for the hypercube, using multivariable Lagrange %K interpolation polynomials. The formulas for the weights lead to new classes %K of efficient rules. %K Submitted by: Alan Genz %K ARPANET: na.genz@su-score %K CSNET: acg@wsu %K Obtainable from: %K Alan Genz %K Computer Science Department %K Washington State University %K Pullman, WA 99164-1210 %K --------------- %K [70] ALAN GENZ %K MATRIX METHODS FOR THE FORCED DIFFUSION EQUATION %K CS-85-137 %K WASHINGTON STATE UNIVERSITY %K JULY, 1985 %K Finite difference methods for the forced diffusion equation with time %K dependent boundary conditions are developed using matrices to represent both %K the approximate solution and the difference operations. This technique allows %K boundary conditions to be included in a natural way and eliminates the need %K for an analysis of the commutativity of the spatial difference operations. %K The matrix methods are used to develop algorithms that are second order %K accurate in space and time for a standard square domain and an annular domain. %K Obtainable from: Alan Genz, as above. %K --------------- %K ##### WATERLOO ##### %K [71] Senad Busovaca %K Handling Degeneracy in a Nonlinear L-1 Algorithm %K Technical Report CS-85-34 %K Department of Computer Science %K University of Waterloo %K This paper is concerned with handling degeneracy %K in a nonlinear optimization algorithm based on an %K active set strategy. Although the solution to the %K problem is given in the context of nonlinear L-1 %K optimization, the approach is more general and can be %K used to overcome the non-uniqueness of dual variables %K in methods that use optimality conditions construc- %K tively. %K Submitted by: Richard Bartels %K Obtainable from: %K Richard Bartels %K University of Waterloo %K Computer Science Department %K Waterloo, Ontario N2L 3G1 %K CANADA %K --------------- .