================================================== NUMERICAL ANALYSIS TITLES -- Volume 2, Number 4 November 23, 1984 ================================================== [1] Finbarr O'Sullivan and Grace Wahba A Cross Validated Bayesian Retrieval Algorithm For Non-Linear Remote Sensing Experiments To appear, Journal of Computational Physics We present a fully automated retrieval algorithm for estimating the solution of a mildly non linear Fredholm Integral Equation of the First Kind, when the data are discrete, noisy (experimental) measurements. This algorithm combines a simple Gauss-Newton interation with an extended form of Generalized Cross Validation , applied in the context of Tihonov Regularization with moment discretization. The performance of the algorithm is illustrated in the context of a remote sensing problem arising in satellite meteorology. Submitted by: Grace Wahba Obtainable from: Grace Wahba Department of Statistics University of Wisconsin, Madison (na.wahba@su-score.arpa) --------------- [2] ANDREW R. CONN NONLINEAR PROGRAMMING, EXACT PENALTY FUNCTIONS AND PROJECTION TECHNIQUES FOR NON-SMOOTH FUNCTIONS We present a personal overview of various approaches to solving nonlinear programs with nonlinear constraints that make use of the L-1 exact penalty function. The advantages, disadvantages and related remaining difficulties of these approaches will be considered. Finally some recent research and extensions are given. Submitted by: Andrew R. Conn Obtainable from: Andrew R. Conn Computer Science Department University of Waterloo Waterloo, Ontario N2L 3G1 CANADA (arconn@waterloo.csnet) --------------- [3] Richard H. Byrd and Robert B. Schnabel Continuity of the Null Space Basis and Constrained Optimization Univ. of Colorado Comp. Sci. Report CU-CS-271-84 Many constrained optimization algorithms use a basis for the null space of the matrix of constraint gradients. Recently, methods have been proposed that enable this null space basis to vary continuously as a function of the iterates in a neighborhood of the solution. This paper reports results from topology showing that, in general, there is no continuous function that generates the null space basis of all full rank rectangular matrices of a fixed size. We also give some indication of where these discontinuities must occur. We then propose an alternative implementation of a class of constrained optimization algorithms that uses approximations to the reduced Hessian of the Lagrangian but is independent of the choice of null space basis. Submitted by: Richard Byrd Obtainable from: Richard Byrd Department of Computer Science University of Colorado Boulder, Colorado 80309 (richard@boulder.csnet) --------------- [4] Y. Saad, A. Sameh, and P. Saylor Solving Elliptic Difference Equations on a Linear Array of Processors. In this paper we consider the organization of three iterative methods for solving self adjoint elliptic difference on a set of linearly con- nected processors. These algorithms are the cyclic Chebyshev semi-iterative scheme, a preconditioned conjugate gradient method, and a generalization of the Chebyshev method. We also consider their performance on this multi- processor as a function of the cost of interprocessor communication. Submitted by: Paul Saylor Obtainable from: Paul Saylor Computer Science Dept. University of Illinois Urbana-Champaine, Illinois (saylor@uiuc.csnet) --------------- [5] Y. Saad, A. Sameh, and P. Saylor An Optimum Semi-iterative Method for Solving Any Linear Set With a Square Matrix. An algorithm is presented to solve Ax=b by computing optimum iteration parameters for Richardson's iteration. The algorithm re- quires some information on the location of the eigenvalues of A. The algorithm yields parameters well-suited for matrices for which Chebyshev parameters are not appropriate. It therefore supplements the Manteuffel algorithm, developed for the Chebyshev case. Numerical examples are described. Submitted by: Paul Saylor Obtainable from: Paul Saylor (as above) --------------- [6] Y. Saad, A. Sameh, and P. Saylor A Generalization of the Golub-Welsch Algorithm to Complex Orthogonal and Kernel Polynomials. The Golub-Welsch algorithm is a stable algorithm to compute the roots of real orthogonal polynomials and kernel polynomials. It is generalized to the complex cases. Submitted by: Paul Saylor Obtainable from: Paul Saylor (as above) --------------- [7] R.T. Gregory A finite number system for digital computers which gives exact results with rational operands. University of Tennessee Computer Science Report CS-84-57 A mapping is established between those rational numbers a/b with both a and b bounded in absolute value by a constant N, and a finite set of integers. When N is chosen to be the largest integer satisfying the inequality 2N*2 + 1 <= p where p is a very large prime, then the mapping is one-to-one and onto the set (0,1,2,...,p-1). Computation involving the rational numbers can be replaced by computation on the integers modulo p. In practice more than one modulus is used and this report deals with the multi- modulus case. Submitted by: Robert T. Gregory (shortly before his death) Obtainable from: Computer Science Department University of Tennessee Knoxville, Tenn. --------------- [8] Daniel Boley, University of Minnesota A Parallel Method for the Generalized Eigenvalue Problem University of Minnesota Computer Science Tech Report 84-21 Sept 1984. We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wraparound connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two nxn matrices to upper triangular form by orthogonal or unitary tranformations. We show how this algorithm may be partitioned and distributed over n+1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate single shifts, and how to apply orthogonal plane rota- tions on either side of a matrix without the need to transpose the matrix itself. Submitted by: Daniel Boley Obtainable from: Daniel Boley University of Minnesota (boley@umn-cs.csnet) --------------- [9] Ito, Kazufumi An iterative method for indefinite systems of linear equations ICASE Report No. 84-13, April 2, 1984, 21 pages Submitted to SIAM J. Numer. Anal. An iterative method for solving nonsymmetric indefinite linear systems is proposed. The method involves the successive use of a modified version of the conjugate residual method. A numerical example is given to illustrate the method. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft ICASE, Mail Stop l32C NASA Langley Research Center Hampton, VA 23665 (804) 865-3992. --------------- [10] Adams, Loyce M. and Harry F. Jordan Is SOR color-blind? ICASE Report No. 84-14, May 21, 1984, 39 pages Submitted to SIAM J. Sci. Statist. Comput. The work of Young [1971] showed that the Red/Black ordering and the natural rowwise ordering of matrices with Property A, such as those arising from the 5-point discretization of Poisson's equation, lead to SOR iteration matrices with identical eigenvalues. With the advent of parallel computers, multi-color point SOR schemes have been proposed for more complicated stencils on 2-dimensional rectangular grids, see Adams and Ortega [1982] for example, but to our knowledge, no theory has been provided for the rate of convergence of these methods relative to that of the natural rowwise scheme. New results show that certain matrices may be reordered so the resulting multi-color SOR matrix has the same eigenvalues as that for the original ordering. In addition, for a wide range of stencils, we show how to choose multi-color orderings so the multi-color SOR matrices have the same eigenvalues as the natural rowwise SOR matrix. The strategy for obtaining these results is based on "data flow" concepts and can be used to reach Young's conclusions above for the 5-point stencil. The importance of these results is threefold. Firstly, a constructive and easy means of finding these multi-colorings is a direct consequence of the theory; secondly, multi-color SOR methods can be found that have the same rate of convergence as the natural rowwise SOR method for a wide range of stencils used to discretize partial differential equations; and thirdly, these multi- color SOR methods can be efficiently implemented on a wide class of parallel computers. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [11] Gatski, Thomas B. and Chester E. Grosch A numerical study of the two- and three-dimensional unsteady Navier-Stokes equations in velocity-vorticity variables using compact difference schemes ICASE Report No. 84-15, May 22, 1984, 20 pages Proc. of 9th ICNMED, Saclay, France, June 23-29, 1984 LECTURE NOTES IN PHYSICS Springer-Verlag. A compact finite-difference approximation to the unsteady Navier-Stokes equations in velocity-vorticity variables is used to numerically simulate a number of flows. These include two-dimensional laminar flow of a vortex evolving over a flat plate with an embedded cavity, the unsteady flow over an elliptic cylinder, and aspects of the transient dynamics of the flow over a rearward facing step. The methodology required to extend the two-dimensional formulation to three-dimensions is presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [12] Hafez, Mohamed, M. and Phillips, Timothy N. A modified least squares formulation for a system of first-order equations ICASE Report No. 84-16, May 29, 1984, 21 pages Submitted to IMACS J. Numer. Math. Second-order equations in terms of auxiliary variables similar to potential and stream functions are obtained by applying a weighted least squares formulation to a first-order system. The additional boundary conditions which are necessary to solve the higher order equations are determined and numerical results are presented for the Cauchy-Riemann equations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [13] Hall, Phillip The Gortler vortex instability mechanism in three-dimensional boundary layers ICASE Report No. 84-17, June 6, 1984, 37 pages. Submitted to the Royal Society of London. It is well known that the two-dimensional boundary layer on a concave wall is centrifugally unstable with respect to vortices aligned with the basic flow for sufficiently high values of the Gortler number. However, in most situations of practical interest the basic flow is three-dimensional and previous theoretical investigations do not apply. In this paper the linear stability of the flow over an infinitely long swept wall of variable curvature is considered. If there is no pressure gradient in the boundary layer it is shown that the instability problem can always be related to an equivalent two- dimensional calculation. However, in general, this is not the case and even for small values of the crossflow velocity field dramatic differences between the two and three-dimensional problems emerge. In particular, it is shown that when the relative size of the crossflow and chordwise flow is (R**(-l/2)) where R is the Reynolds number of the flow, the most unstable mode is time- dependent. When the size of the crossflow is further increased, the vortices in the neutral location have their axes locally perpendicular to the vortex lines of the basic flow. In this regime the eigenfunctions associated with the instability become essentially 'centre modes' of the Orr-Sommerfeld equation destabilized by centrifugal effects. The critical Gortler number for such modes can be predicted by a large wavenumber asymptotic analysis; the results suggest that for order unity values of the ratio of the crossflow and chordwise velocity fields, the Gortler instability mechanism is almost certainly not operational. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [14] Gozani, J., Nachshon, A., and Turkel, E. Conjugate gradient coupled with multigrid for an indefinite problem ICASE Report No. 84-18, June 7, 1984, 11 pages Submitted to Proc. of 3rd IMACS International Symposium on Computer Methods for Partial Differential Equations Lehigh University, Bethlehem, PA, June 20-22, 1984 An iterative algorithm for the Helmholtz equation is presented. This scheme is based on the preconditioned conjugate gradient method for the normal equations. The preconditioning is one cycle of a multigrid method for the discrete Laplacian. The smoothing algorithm is red-black Gauss-Seidel and is constructed so it is a symmetric operator. The total number of iterations needed by the algorithm is independent of h. By varying the number of grids, the number of iterations depends only weakly on k when k**3 h**2 is constant. Comparisons with a SSOR preconditioner are presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [15] Malik, M. R., Zang, T. A., and Hussaini, M. Y. A spectral collocation method for the Navier-Stokes equations ICASE Report No. 84-19, June 8, 1984, 48 pages Submitted to J. Comput. Phys. A Fourier-Chebyshev spectral method for the incompressible Navier-Stokes equations is described. It is applicable to a variety of problems including some with fluid properties which vary strongly both in the normal direction and in time. In this fully spectral algorithm, a preconditioned iterative technique is used for solving the implicit equations arising from semi- implicit treatment of pressure, mean advection and vertical diffusion terms. The algorithm is tested by applying it to hydrodynamic stability problems in channel flow and in external boundary layers with both constant and variable viscosity. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [16] Davis, Stephen F. TVD finite difference schemes and artificial viscosity. ICASE Report No. 84-20, June 11, 1984, 35 pages Submitted to SIAM J. Sci. Statis. Comput. In this paper we show that the total variation diminishing (TVD) finite difference scheme which was analysed by Sweby can be interpreted as a Lax- Wendroff scheme plus an upwind weighted artificial dissipation term. We then show that if we choose a particular flux limiter and remove the requirement for upwind weighting, we obtain an artificial dissipation term which is based on the theory of TVD schemes, which does not contain any problem dependent parameters and which can be added to existing MacCormack method codes. Finally, we conduct numerical experiments to examine the performance of this new method. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [17] Canuto, C., Hariharan, S. I., and Lustman, L. Spectral methods for exterior elliptic problems ICASE Report No. 84-21, June 12, 1984, 33 pages. Submitted to Numer. Math. This paper deals with spectral approximations for exterior elliptic problems in two dimensions. As in the conventional finite difference or finite element methods, it is found that the accuracy of the numerical solutions is limited by the order of the numerical farfield conditions. We introduce a spectral boundary treatment at infinity, which is compatible with the "infinite order" interior spectral scheme. Computational results are presented to demonstrate the spectral accuracy attainable. Although we deal with a simple Laplace problem throughout the paper, our analysis covers more complex and general cases. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [18] Graif, E. and K. Kunisch Parameter estimation for the Euler-Bernoulli-beam ICASE Report No. 84-22, June 20, 1984, 43 pages. Submitted to IEEE Trans. Auto. Control. An approximation involving cubic spline functions for parameter estimation problems in the Euler-Bernoulli-beam equation (phrased as an optimization problem with respect to the parameters) is described and convergence is proved. The resulting algorithm was implemented and several of the test examples are documented. It is observed that the use of penalty terms in the cost functional can improve the rate of convergence. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [19] Rosen, I. Gary A numerical scheme for the identification of hybrid systems describing the vibration of flexible beams with tip bodies ICASE Report No. 84-23, June 21, 1984, 36 pages. Submitted to J. Math. Anal. Appl. A cubic spline based Galerkin-like method is developed for the identification of a class of hybrid systems which describe the transverse vibration of flexible beams with attached tip bodies. The identification problem is formulated as a least squares fit to data subject to the system dynamics given by a coupled system of ordinary and partial differential equations recast as an abstract evolution equation (AEE) in an appropriate infinite dimensional Hilbert space. Projecting the AEE into spline-based subspaces leads naturally to a sequence of approximating finite diemnsional identification problems. The solutions to these problems are shown to exist, are relatively easily computed, and are shown to, in some sense, converge to solutions to the original identification problem. Numerical results for a variety of examples are discussed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [20] Banks, H. Thomas and Katherine A. Murphy Estimation of coefficients and boundary parameters in hyperbolic systems ICASE Report No. 84-24, June 21, 1984, 52 pages. Submitted to SIAM J. Control Optim. We consider semi-discrete Galerkin approximation schemes in connection with inverse problems for the estimation of spatially varying coefficients and boundary condition parameters in second order hyperbolic systems typical of those arising in 1-D surface seismic problems. Spline based algorithms are proposed for which theoretical convergence results along with a representative sample of numerical findings are given. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [21] Vardi, A. A new minmax problem ICASE Report No. 84-25, June 26, 1984, 35 pages. Submitted to J. Optim., Theory and Appl. For the classical minimax problem we design a new active set strategy in which there are three types of functions: active, semi-active, and non-active. This technique will help in preventing zigzagging which often occurs when an active set strategy is used. Some of the inequality constraints are handled with slack variables. Also a trust region strategy is used in which at each iteration there is a sphere around the current point in which the local approximation of the function is trusted. The algorithm suggested in the paper was implemented into a successful computer program. Numerical results are provided. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [22] Banks, H. T. and I. G. Rosen Approximation techniques for parameter estimation and feedback control for distributed models of large flexible structures ICASE Report No. 84-26, June 22, 1984, 19 pages. Submitted to Workshop on Identification and Control of Flexible Space Structures, San Diego, CA, June 4-6, 1984, G. Rodgriguez (ed.). We discuss approximation ideas that can be used in parameter estimation and feedback control for Euler-Bernoulli models of elastic systems. Focusing on parameter estimation problems, we outline how one can obtain convergence results for cubic spline-based schemes for hybrid models involving an elastic cantilevered beam with tip mass and base acceleration. Sample numerical findings are also presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [23] Turkel, E. and Bram van Leer Flux vector splitting and Runge-Kutta methods for the Euler equations ICASE Report No. 84-27, June 23, 2984, 9 pages. To appear in Proc. of the 9th Intl. Conference on Numerical Methods in Fluid Dynamics, Saclay, France, June 25-29, 1984. Runge-Kutta schemes have been used as a method of solving the Euler equations exterior to an airfoil. In the past this has been coupled with central differences and an artificial viscosity in space. In this study we couple the Runge-Kutta time stepping scheme with an upwinded space approxima tion based on flux-vector splitting. Several acceleration techniques are also considered including a local time step, residual smoothing and multigrid. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [24] Turkel, Eli Fast solutions to the steady state compressible and incompressible fluid dynamics equations ICASE Report No. 84-28, June 23, 1984, 8 pages. To appear in Proc. of the 9th Intl. Conference on Numerical Methods in Fluid Dynamics Saclay, France, June 25-29, 1984. It is well known that for low speed flows the use of the compressible fluid dynamic equations is inefficient. The use of an explicit scheme requires delta-t to be bounded by 1/c. However, the physical parameters change over time scales of order 1/u which is much larger. Hence, it is not appropriate to use explicit schemes for very subsonic flows. Implicit schemes are hard to vectorize and frequently do not converge quickly for very subsonic flows. We shall demonstrate that if one is only interested in the steady state then a minor change to an existing code can greatly increase the efficiency of an explicit method. Even when using an implicit method the proposed changes increase the efficiency of the scheme. We shall first consider the Euler equations for low speed flows and then incompressible flows. We then indicate how to generalize the method to include viscous effects. We also show how to accelerate supersonic flow by essentially decoupling the equations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [25] Gottlieb, D. Spectral methods for compressible flow problems ICASE Report No. 84-29, June 21, 1984, 20 pages. Proc. 9th Intl. Conference on Numerical Methods in Fluid Dynamics Saclay, France, June 25-29, 1984. In this article we review recent results concerning numerical simulation of shock waves using spectral methods. We discuss shock fitting techniques as well as shock capturing techniques with finite difference artificial viscosity. We also discuss the notion of the information contained in the numerical results obtained by spectral methods and show how this information can be recovered. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [26] Ipsen, Ilse C. F. Singular value decomposition with systolic arrays ICASE Report No. 84-30, July 9, 1984, 22 pages. Proc. of the Society of Photo-Optical Engineers San Diego, CA, August 19-24, 1984. Systolic arrays for determining the Singular Value Decomposition of a matrix A of bandwidth w are presented. After A has been reduced to bidiagonal form B by means of Givens plane rotations, the differential equations. Part II: The linear quadratic control problem. ICASE Report No. 84-31, July 6, 1984, 65 pages. Submitted to SIAM J. Control Optim. The numerical scheme based on the Legendre-tau approximation is proposed to approximate the feedback solution to the linear quadratic optimal control problem for hereditary differential systems. The convergence property is established using Trotter ideas. The method yields very good approximations at low orders and provides an approximation technique for computing closed- loop eigenvalues of the feedback system. A comparison with existing methods (based on "averaging" and "spline" approximations) is made. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [27] Turkel, Eli Acceleration to a steady state for the Euler equations ICASE Report No. 84-32, July 7, 1984, 45 pages. Proc. INRIA Euler Workshop (SIAM) Rocquencourt, France, December 7-9, 1983. A multi-stage Runge-Kutta method is analyzed for solving the Euler equations exterior to an airfoil. Highly subsonic, transonic and supersonic flows are evaluated. Various techniques for accelerating the convergence to a steady state are introduced and analyzed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [28] Bokhari, Shahid H. and A. D. Raza Augmenting computer networks ICASE Report No. 84-33, July 8, 1984, 16 pages. Proc. 1984 Intl. Conference on Parallel Processing Bellaire, MI, August 21-24, 1984. Three methods of augmenting computer networks by adding at most one link per processor are discussed. 1. A tree of N nodes may be augmented such that the resulting graph has diameter no greater than 4 log2((N+2)/3)-2. This 0(N**3) algorithm can be applied to any spanning tree of a connected graph to reduce the diameter of that graph to 0(log N). 2. Given a binary tree T and a chain C of N nodes each, C may be augmented to produce C' so that T is a subgraph of C'. This algorithm is 0(N) and may be used to produce augmented chains or rings that have diameter no greater than 2 log2 (N+2)/3) and are planar. 3. Any rectangular two-dimensional 4 (8) nearest neighbor array of size N = 2**k may be augmented so that it can emulate a single step shuffle- exchange network of size N/2 in 3(t) time steps. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [29] Reed, Daniel A. and Merrell L. Patrick A model of asynchronous iterative algorithms for solving large, sparse, linear systems ICASE Report No. 84-34, July 31, 1984, 27 pages. Proceedings of the 1984 International Conference on Parallel Processing August 21-24, 1984, Bellaire, MI. Solving large, sparse, linear systems of equations is one of the fundamental problems in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. This model is then analyzed to determine the expected intertask data transfer and task computational complexity as functions of the number of tasks. Based on the analysis, recommendations for task partitioning are made. These recommendations are a function of the sparseness of the linear system, its structure (i.e., randomly sparse or banded), and dimension. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [30] Reed, Daniel A. and Merrell L. Patrick Parallel, iterative solution of sparse linear systems: Models and architectures ICASE Report No. 84-35, August 1, 1984, 45 pages. Submitted to Parallel Computing. Solving large, sparse, linear systems of equations is a fundamental problem in large scale scientific and engineering computation. A model of a general class of asychronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. A data transfer model predicting both the probability that data must be transferred between two tasks and the amount of data to be transferred is presented. This model is used to derive an execution time model for predicting parallel execution time and an optimal number of tasks given the dimension and sparsity of the coefficient matrix and the costs of computation, synchronization, and communication. The suitability of different parallel architectures for solving randomly sparse linear systems is discussed. Based on the complexity of task scheduling, one parallel architecture, based on a broadcast bus, is presented and analyzed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [31] Tadmor, Eitan The well-posedness of the Kuramoto-Sivashinsky equation. ICASE Report No. 84-36, August 7, 1984, 22 pages. Submitted to SIAM J. Appl. Math. The Kuramoto-Sivashinsky equation arises in a variety of applications, among which are modeling reaction-diffusion systems, flame-propagation and viscous flow problems. It is considered here, as a prototype to the larger class of generalized Burgers equations: those consist of quadratic nonlinearity and arbitrary linear parabolic part. We show that such equations are well-posed, thus admitting a unique smooth solution, continuously dependent on its initial data. As an attractive alternative to standard energymethods, existence and stability are derived in this case, by "patching" in the large short time solutions without "loss of derivatives". Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [32] Lustman, Liviu The time evolution of spectral discretizations of hyperbolic systems ICASE Report No. 84-37, August 7, 1984, 12 pages. Submitted to SIAM J. Numer. Anal. A Chebyshev collocation spectral method, applied to hyperbolic systems is considered, particularly for those initial boundary value problems which possess only solutions tending to zero at large times. It is shown that the numerical solutions of the system will also vanish at infinity, if and only if, the numerical solution of a scalar equation of the same type does. This result is then generalized for other spectral approximations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [33] Bayliss, A., C. I. Goldstein, and E. Turkel On accuracy conditions for the numerical computation of waves ICASE Report No. 84-38, August 9, 1984, 16 pages. Submitted to J. Comput. Phys. The Helmholtz equation with a variable index of refraction, and a suitable radiation condition at infinity serves as a model for a wide variety of wave propagation problems. Such problems can be solved numerically by first truncating the given unbounded domain and imposing a suitable outgoing radiation condition on an artificial boundary and then solving the resulting problem on the bounded domain by direct discretization (for example, using a finite element method). In practical applications, the mesh size h and the wave number K, are not independent but are constrained by the accuracy of the desired computation. It will be shown that the number of points per wavelength, measured by l/Kh, is not sufficient to determine the accuracy of a given discretization. For example, the quantity K**3 h**2 is shown to determine the accuracy in the L-two norm for a second-order discretization method applied to several propagation models. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [34] Hariharan, S. I. Numerical solutions of acoustic wave propagation problems using Euler computations ICASE Report No. 84-39, August 10, 1984, 29 pages. Proc. of the AIAA 9th Aeroacoustics Conference Williamsburg, VA, August 15-17, 1984. This paper reports solution procedures for problems arising from the study of engine inlet wave propagation. The first problem is the study of sound waves radiated from cylindrical inlets. The second one is a quasi-one- dimensional problem to study the effect of nonlinearities and the third one is the study of nonlinearities in two dimensions. In all three problems Euler computations are done with a fourth-order explicit scheme. For the first problem results are shown in agreement with experimental data and for the second problem comparisons are made with an existing asymptotic theory. The third problem is part of an ongoing work and preliminary results are presented for this case. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [35] Tadmor, Eitan The exponential accuracy of Fourier and Tchebyshev differencing methods ICASE Report No. 84-40, August 20, 1984, 24 pages. Submitted to SIAM J. Numer. Anal. It is shown that when differencing analytic functions using the pseudospectral Fourier or Tchebyshev methods, the error committed decays to zero at an exponential rate. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [36] Gannon, Dennis and John Van Rosendale On the impact of communication complexity in the design of parallel numerical algorithms ICASE Report No. 84-41, August 22, 1984, 37 pages. To appear in IEEE Trans. on Computers. This paper describes two models of the cost of data movement in parallel numerical algorithms. One model is a generalization of an approach due to Hockney, and is suitable for shared memory multiprocessors where each processor has vector capabilities. The other model is applicable to highly parallel nonshared memory MIMD systems. In the second model, algorithm performance is characterized in terms of the communication network design. Techniques used in VLSI complexity theory are also brought in, and algorithm independent upper bounds on system performance are derived for several problems that are important to scientific computation. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [37] Ito, Kazufumi Legendre-Tau approximation for functional differential equations, Part III: Eigenvalue approximations and uniform stability. ICASE Report No 84-42, August 24, 1984, 34 pages. Proc. Second International Conference on Control Theory for Distributed Parameter Systems and Applications Vorau, Austria, 1984. The stability and convergence properties of the Legendre-tau approximation for hereditary differential systems are analyzed. We derive a characteristic equation for the eigenvalues of the resulting approximate system. As a result of this derivation we are able to establish that the uniform exponential stability of the solution semigroup is preserved under approximation. It is the key to obtaining the convergence of approximate solutions of the algebraic Riccati equation in trace norm. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [38] Berger, M. J. On conservation at grid interfaces ICASE Report No. 84-43, September 7, 1984, 25 pages. Submitted to J. Comput. Phys. This paper considers the solution of hyperbolic systems of conservation laws on discontinuous grids. In particular, we consider what happens to conservation at grid interfaces. A procedure is presented to derive conservative difference approximations at the grid interfaces for two- dimensional grids which overlap in an arbitrary configuration. The same procedures are applied to compute interface formulas for grids which are refined in space and/or time, and for continuous grids where a switch in the scheme causes the discontinuity. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [39] Osher, S. and S. Chakravarthy Very high order accurate TVD schemes ICASE Report No. 84-44, September 10, 1984, 61 pages. Submitted to SIAM J. Numer. Anal. A systematic procedure for constructing semi-discrete families of 2m-1 order accurate, 2m order dissipative, variation diminishing, 2m+1 point bandwidth, conservation form approximations to scalar conservation laws is presented. Here m is any integer between 2 and 8. Simple first-order forward time discretization, used together with any of these approximations to the space derivatives, also results in a fully discrete, variation diminishing algorithm. These schemes all use simple flux limiters, without which each of these fully discrete algorithms is even linearly unstable. Extensions to systems, using a nonlinear field-by-field decomposition are presented, and shown to have many of the same properties as in the scalar case. For linear systems, these nonlinear approximations are variation diminishing, and hence convergent. A new and general criterion for approximations to be variation diminishing is also given. Finally, numerical experiments using some of these algorithms are presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [40] Elcrat, A. R. and L. N. Trefethen Classical free-streamline flow over a polygonal obstacle ICASE Report No. 84-45, September 10, 1984, 61 pages. Submitted to J. Comput. Appl. Math. In classical Kirchhoff flow, an ideal incompressible fluid flows past an obstacle and around a motionless wake bounded by free streamlines. Since 1869 it has been known that in principle, the two-dimensional Kirchhoff flow over a polygonal obstacle can be determined by constructing a conformal map onto a polygon in the log-hodograph plane. In practice, however, this idea has rarely been put to use except for very simple obstacles, because the conformal mapping problem has been too difficult. This paper presents a practical method for computing flows over arbitrary polygonal obstacles to high accuracy in a few seconds of computer time. We achieve this high speed and flexibility by working with a modified Schwarz-Christoffel integral that maps onto the flow region directly rather than onto the log-hodograph polygon. This integral and its associated parameter problem are treated numerically by methods developed earlier by Trefethen for standard Schwarz-Christoffel maps. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [41] Krause, Egon Review of some vortex relations ICASE Report No. 84-46, September 12, 1984, 8 pages. Submitted to Computer and Fluids. The evaluation of the circulation from numerical solutions of the momentum and energy equations is discussed for incompressible and compressible flows. It is shown how artificial damping directly influences the time rate of change of the circulation. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [42] Tal-Ezer, Hillel A pseudospectral Legendre method for hyperbolic equations with an improved stability condition ICASE Report No. 84-48, September 14, 1984, 46 pages. Submitted to J. Comput. Phys. A new pseudospectral method is introduced for solving hyperbolic partial differential equations. This method uses different grid points than previously used pseudospectral methods: in fact the grid points are related to the zeroes of the Legendre polynomials. The main advantage of this method is that the allowable time step is proportional to the inverse of the number of grid points 1/N rather than to 1/N**2 (as in the case of other pseudospectral methods applied to mixed initial boundary value problems). A highly accurate time discretization suitable for these spectral methods is discussed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [43] Bayliss, A., C. I. Goldstein, and E. Turkel The numerical solution of the Helmholtz equation for wave propagation problems in underwater acoustics ICASE Report No. 84-49, September 17, 1983, 29 pages. Submitted to J. Comput. Math. Appl. The Helmholtz Equation with a variable index of refraction, and a suitable radiation condition at infinity serves as a model for a wide variety of wave propagation problems. A numerical algorithm has been developed and a computer code implemented that can effectively solve this equation in the intermediate frequency range. The equation is discretized using the finite element method, thus allowing for the modeling of complicated geometries (including interfaces) and complicated boundary conditions. A global radiation boundary condition is imposed at the far field boundary that is exact for an arbitrary number of propagating modes. The resulting large, non-selfadjoint system of linear equations with indefinite symmetric part is solved using the preconditioned conjugate gradient method applied to the normal equations. A new preconditioner is developed based on the multigrid method. This preconditioner is vectorizable and is extremely effective over a wide range of frequencies provided the number of grid levels is reduced for large frequencies. A heuristic argument is given that indicates the superior convergence properties of this preconditioner. The relevant limit to analyze convergence is for K increasing and a fixed prescribed accuracy level. The efficiency and robustness of the numerical algorithm is confirmed for large acoustic models, including interfaces with strong velocity contrasts. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [44] Burns, John A., Ito, Kazufumi, Powers, Robert K. Chandrasekhar equations and computational algorithms for distributed parameter systems ICASE Report No. 84-50, September 20, 1984, 23 pages. Proc. of 23rd Conference on Decision and Control, December 12-14, 1984, Las Vegas, NV. In this paper we consider the Chandrasekhar equations arising in optimal control problems for linear distributed parameter systems. The equations are derived via approximation theory. This approach is used to obtain existence, uniqueness and strong differentiability of the solutions and provides the basis for a convergent computation scheme for approximating feedback gain operators. A numerical example is presented to illustrate these ideas. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [45] Petter E. Bjorstad and Olof B. Widlund Iterative Methods for the Solution of Elliptic Problems on Regions Partitioned into Substructures Finite element problems can often naturally be divided into subproblems which correspond to subregions into which the region has been partitioned or from which it was originally assembled. A class of iterative methods is discussed in which these subproblems are solved by direct methods,while the interaction across the curves or surfaces which divide the region is handled by a conju- gate gradient method. A mathematical framework for this workis provided by regularity theory for elliptic finite element problems and by block Gauss elimination. A full development of the theory,which shows that certain of these methods are optimal, is given for Lagrangian finite element approxi- mations of second order linear elliptic problems in the plane.Results from numerical experiments are also reported. Submitted by: Olaf Widlund Obtainable from: Olaf Widlund Courant Institute 251 Mercer St. N.Y., N.Y. 10012. (WIDLUND@NYU-ACF1.ARPA) --------------- [46] Ron S. Dembo and Ulrich Tulowitzki Local Convergence Analysis for Successive Inexact Quadratic Programming Methods SOM Working Paper Series B #78 Yale School of Organization and Management October, 1984 Successive quadratic programming (SQP) methods for the solution of constrained nonlinear optimization problems are attractive because they converge rapidly from any sufficiently good initial solution. However, solving the quadratic subproblems at each stage can be expensive, particularly if the number of unknowns is large and may be not justified when far away from an optimal solution. Therefore, we consider a class of successive inexact quadratic programming (SIQP) methods that solve the subproblems only approximately. We characterize the rate of convergence in terms of the relative error incurred in the subproblems in a manner that does not assume that the set of active constraints remains constant. This leads to practical termination criteria for truncating various iterative algorithms applied to the quadratic subproblems. Submitted by: Ron Dembo Obtainable from: Ron Dembo Yale University School of Organization and Management P.O. Box 1A New Haven, Conn. 06520 --------------- [47] Ron S. Dembo and Ulrich Tulowitzki Sequential Truncated Quadratic Programming Methods To appear in the Proceedings of the SIAM Conference on Numerical Optimization, Boulder, Colo., June, 1984 In a sequential quadratic programming (SQP) method for nonlinear optimization it is possible to truncate an iterative procedure, applied to each quadratic subproblem, prior to reaching a solution, without affecting the asymptotic rate of convergence. We describe some practical termination criteria which ensure that an SQP method, executed without exact solution of the QP subproblem, inherits the rate of convergence of its (exact) SQP counterpart. Numerical experiments on linearly-constrained problems of up to 2230 variables indicate that substantial savings can be achieved by inexact solution of the QP subproblems with little or no adverse effect on the convergence rate. Submitted by: Ron Dembo Obtainable from: Ron Dembo Yale University School of Organization and Management P.O. Box 1A New Haven, Conn. 06520 --------------- From rhbartels%watcgl%waterloo.csnet@csnet-relay.arpa Tue Jul 16 13:45:20 1985 Received: from csnet-relay (csnet-relay.arpa.ARPA) by anl-mcs.ARPA ; Tue, 16 Jul 85 13:42:53 cdt Received: from waterloo by csnet-relay.csnet id a001168; 16 Jul 85 14:21 EDT Date: Sun, 14 Jul 85 20:30:55 edt From: Richard Bartels Message-Id: <8507150030.AA20616@watcgl.UUCP> To: dongarra@anl-mcs Status: R ================================================== NUMERICAL ANALYSIS TITLES -- Volume 2, Number 4 November 23, 1984 ================================================== [1] Finbarr O'Sullivan and Grace Wahba A Cross Validated Bayesian Retrieval Algorithm For Non-Linear Remote Sensing Experiments To appear, Journal of Computational Physics We present a fully automated retrieval algorithm for estimating the solution of a mildly non linear Fredholm Integral Equation of the First Kind, when the data are discrete, noisy (experimental) measurements. This algorithm combines a simple Gauss-Newton interation with an extended form of Generalized Cross Validation , applied in the context of Tihonov Regularization with moment discretization. The performance of the algorithm is illustrated in the context of a remote sensing problem arising in satellite meteorology. Submitted by: Grace Wahba Obtainable from: Grace Wahba Department of Statistics University of Wisconsin, Madison (na.wahba@su-score.arpa) --------------- [2] ANDREW R. CONN NONLINEAR PROGRAMMING, EXACT PENALTY FUNCTIONS AND PROJECTION TECHNIQUES FOR NON-SMOOTH FUNCTIONS We present a personal overview of various approaches to solving nonlinear programs with nonlinear constraints that make use of the L-1 exact penalty function. The advantages, disadvantages and related remaining difficulties of these approaches will be considered. Finally some recent research and extensions are given. Submitted by: Andrew R. Conn Obtainable from: Andrew R. Conn Computer Science Department University of Waterloo Waterloo, Ontario N2L 3G1 CANADA (arconn@waterloo.csnet) --------------- [3] Richard H. Byrd and Robert B. Schnabel Continuity of the Null Space Basis and Constrained Optimization Univ. of Colorado Comp. Sci. Report CU-CS-271-84 Many constrained optimization algorithms use a basis for the null space of the matrix of constraint gradients. Recently, methods have been proposed that enable this null space basis to vary continuously as a function of the iterates in a neighborhood of the solution. This paper reports results from topology showing that, in general, there is no continuous function that generates the null space basis of all full rank rectangular matrices of a fixed size. We also give some indication of where these discontinuities must occur. We then propose an alternative implementation of a class of constrained optimization algorithms that uses approximations to the reduced Hessian of the Lagrangian but is independent of the choice of null space basis. Submitted by: Richard Byrd Obtainable from: Richard Byrd Department of Computer Science University of Colorado Boulder, Colorado 80309 (richard@boulder.csnet) --------------- [4] Y. Saad, A. Sameh, and P. Saylor Solving Elliptic Difference Equations on a Linear Array of Processors. In this paper we consider the organization of three iterative methods for solving self adjoint elliptic difference on a set of linearly con- nected processors. These algorithms are the cyclic Chebyshev semi-iterative scheme, a preconditioned conjugate gradient method, and a generalization of the Chebyshev method. We also consider their performance on this multi- processor as a function of the cost of interprocessor communication. Submitted by: Paul Saylor Obtainable from: Paul Saylor Computer Science Dept. University of Illinois Urbana-Champaine, Illinois (saylor@uiuc.csnet) --------------- [5] Y. Saad, A. Sameh, and P. Saylor An Optimum Semi-iterative Method for Solving Any Linear Set With a Square Matrix. An algorithm is presented to solve Ax=b by computing optimum iteration parameters for Richardson's iteration. The algorithm re- quires some information on the location of the eigenvalues of A. The algorithm yields parameters well-suited for matrices for which Chebyshev parameters are not appropriate. It therefore supplements the Manteuffel algorithm, developed for the Chebyshev case. Numerical examples are described. Submitted by: Paul Saylor Obtainable from: Paul Saylor (as above) --------------- [6] Y. Saad, A. Sameh, and P. Saylor A Generalization of the Golub-Welsch Algorithm to Complex Orthogonal and Kernel Polynomials. The Golub-Welsch algorithm is a stable algorithm to compute the roots of real orthogonal polynomials and kernel polynomials. It is generalized to the complex cases. Submitted by: Paul Saylor Obtainable from: Paul Saylor (as above) --------------- [7] R.T. Gregory A finite number system for digital computers which gives exact results with rational operands. University of Tennessee Computer Science Report CS-84-57 A mapping is established between those rational numbers a/b with both a and b bounded in absolute value by a constant N, and a finite set of integers. When N is chosen to be the largest integer satisfying the inequality 2N*2 + 1 <= p where p is a very large prime, then the mapping is one-to-one and onto the set (0,1,2,...,p-1). Computation involving the rational numbers can be replaced by computation on the integers modulo p. In practice more than one modulus is used and this report deals with the multi- modulus case. Submitted by: Robert T. Gregory (shortly before his death) Obtainable from: Computer Science Department University of Tennessee Knoxville, Tenn. --------------- [8] Daniel Boley, University of Minnesota A Parallel Method for the Generalized Eigenvalue Problem University of Minnesota Computer Science Tech Report 84-21 Sept 1984. We present a parallel method to solve the generalized eigenvalue problem on a linear array of processors, each connected to their nearest neighbors and operating synchronously. We also include a wraparound connection from end to end. Our method is based on the well-known QZ algorithm of Moler and Stewart, which simultaneously reduces two nxn matrices to upper triangular form by orthogonal or unitary tranformations. We show how this algorithm may be partitioned and distributed over n+1 processors, achieving a speed-up over the serial algorithm of O(n). We use the concept of windows to describe the action of each processor at each step. We show how to incorporate single shifts, and how to apply orthogonal plane rota- tions on either side of a matrix without the need to transpose the matrix itself. Submitted by: Daniel Boley Obtainable from: Daniel Boley University of Minnesota (boley@umn-cs.csnet) --------------- [9] Ito, Kazufumi An iterative method for indefinite systems of linear equations ICASE Report No. 84-13, April 2, 1984, 21 pages Submitted to SIAM J. Numer. Anal. An iterative method for solving nonsymmetric indefinite linear systems is proposed. The method involves the successive use of a modified version of the conjugate residual method. A numerical example is given to illustrate the method. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft ICASE, Mail Stop l32C NASA Langley Research Center Hampton, VA 23665 (804) 865-3992. --------------- [10] Adams, Loyce M. and Harry F. Jordan Is SOR color-blind? ICASE Report No. 84-14, May 21, 1984, 39 pages Submitted to SIAM J. Sci. Statist. Comput. The work of Young [1971] showed that the Red/Black ordering and the natural rowwise ordering of matrices with Property A, such as those arising from the 5-point discretization of Poisson's equation, lead to SOR iteration matrices with identical eigenvalues. With the advent of parallel computers, multi-color point SOR schemes have been proposed for more complicated stencils on 2-dimensional rectangular grids, see Adams and Ortega [1982] for example, but to our knowledge, no theory has been provided for the rate of convergence of these methods relative to that of the natural rowwise scheme. New results show that certain matrices may be reordered so the resulting multi-color SOR matrix has the same eigenvalues as that for the original ordering. In addition, for a wide range of stencils, we show how to choose multi-color orderings so the multi-color SOR matrices have the same eigenvalues as the natural rowwise SOR matrix. The strategy for obtaining these results is based on "data flow" concepts and can be used to reach Young's conclusions above for the 5-point stencil. The importance of these results is threefold. Firstly, a constructive and easy means of finding these multi-colorings is a direct consequence of the theory; secondly, multi-color SOR methods can be found that have the same rate of convergence as the natural rowwise SOR method for a wide range of stencils used to discretize partial differential equations; and thirdly, these multi- color SOR methods can be efficiently implemented on a wide class of parallel computers. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [11] Gatski, Thomas B. and Chester E. Grosch A numerical study of the two- and three-dimensional unsteady Navier-Stokes equations in velocity-vorticity variables using compact difference schemes ICASE Report No. 84-15, May 22, 1984, 20 pages Proc. of 9th ICNMED, Saclay, France, June 23-29, 1984 LECTURE NOTES IN PHYSICS Springer-Verlag. A compact finite-difference approximation to the unsteady Navier-Stokes equations in velocity-vorticity variables is used to numerically simulate a number of flows. These include two-dimensional laminar flow of a vortex evolving over a flat plate with an embedded cavity, the unsteady flow over an elliptic cylinder, and aspects of the transient dynamics of the flow over a rearward facing step. The methodology required to extend the two-dimensional formulation to three-dimensions is presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [12] Hafez, Mohamed, M. and Phillips, Timothy N. A modified least squares formulation for a system of first-order equations ICASE Report No. 84-16, May 29, 1984, 21 pages Submitted to IMACS J. Numer. Math. Second-order equations in terms of auxiliary variables similar to potential and stream functions are obtained by applying a weighted least squares formulation to a first-order system. The additional boundary conditions which are necessary to solve the higher order equations are determined and numerical results are presented for the Cauchy-Riemann equations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [13] Hall, Phillip The Gortler vortex instability mechanism in three-dimensional boundary layers ICASE Report No. 84-17, June 6, 1984, 37 pages. Submitted to the Royal Society of London. It is well known that the two-dimensional boundary layer on a concave wall is centrifugally unstable with respect to vortices aligned with the basic flow for sufficiently high values of the Gortler number. However, in most situations of practical interest the basic flow is three-dimensional and previous theoretical investigations do not apply. In this paper the linear stability of the flow over an infinitely long swept wall of variable curvature is considered. If there is no pressure gradient in the boundary layer it is shown that the instability problem can always be related to an equivalent two- dimensional calculation. However, in general, this is not the case and even for small values of the crossflow velocity field dramatic differences between the two and three-dimensional problems emerge. In particular, it is shown that when the relative size of the crossflow and chordwise flow is (R**(-l/2)) where R is the Reynolds number of the flow, the most unstable mode is time- dependent. When the size of the crossflow is further increased, the vortices in the neutral location have their axes locally perpendicular to the vortex lines of the basic flow. In this regime the eigenfunctions associated with the instability become essentially 'centre modes' of the Orr-Sommerfeld equation destabilized by centrifugal effects. The critical Gortler number for such modes can be predicted by a large wavenumber asymptotic analysis; the results suggest that for order unity values of the ratio of the crossflow and chordwise velocity fields, the Gortler instability mechanism is almost certainly not operational. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [14] Gozani, J., Nachshon, A., and Turkel, E. Conjugate gradient coupled with multigrid for an indefinite problem ICASE Report No. 84-18, June 7, 1984, 11 pages Submitted to Proc. of 3rd IMACS International Symposium on Computer Methods for Partial Differential Equations Lehigh University, Bethlehem, PA, June 20-22, 1984 An iterative algorithm for the Helmholtz equation is presented. This scheme is based on the preconditioned conjugate gradient method for the normal equations. The preconditioning is one cycle of a multigrid method for the discrete Laplacian. The smoothing algorithm is red-black Gauss-Seidel and is constructed so it is a symmetric operator. The total number of iterations needed by the algorithm is independent of h. By varying the number of grids, the number of iterations depends only weakly on k when k**3 h**2 is constant. Comparisons with a SSOR preconditioner are presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [15] Malik, M. R., Zang, T. A., and Hussaini, M. Y. A spectral collocation method for the Navier-Stokes equations ICASE Report No. 84-19, June 8, 1984, 48 pages Submitted to J. Comput. Phys. A Fourier-Chebyshev spectral method for the incompressible Navier-Stokes equations is described. It is applicable to a variety of problems including some with fluid properties which vary strongly both in the normal direction and in time. In this fully spectral algorithm, a preconditioned iterative technique is used for solving the implicit equations arising from semi- implicit treatment of pressure, mean advection and vertical diffusion terms. The algorithm is tested by applying it to hydrodynamic stability problems in channel flow and in external boundary layers with both constant and variable viscosity. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [16] Davis, Stephen F. TVD finite difference schemes and artificial viscosity. ICASE Report No. 84-20, June 11, 1984, 35 pages Submitted to SIAM J. Sci. Statis. Comput. In this paper we show that the total variation diminishing (TVD) finite difference scheme which was analysed by Sweby can be interpreted as a Lax- Wendroff scheme plus an upwind weighted artificial dissipation term. We then show that if we choose a particular flux limiter and remove the requirement for upwind weighting, we obtain an artificial dissipation term which is based on the theory of TVD schemes, which does not contain any problem dependent parameters and which can be added to existing MacCormack method codes. Finally, we conduct numerical experiments to examine the performance of this new method. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [17] Canuto, C., Hariharan, S. I., and Lustman, L. Spectral methods for exterior elliptic problems ICASE Report No. 84-21, June 12, 1984, 33 pages. Submitted to Numer. Math. This paper deals with spectral approximations for exterior elliptic problems in two dimensions. As in the conventional finite difference or finite element methods, it is found that the accuracy of the numerical solutions is limited by the order of the numerical farfield conditions. We introduce a spectral boundary treatment at infinity, which is compatible with the "infinite order" interior spectral scheme. Computational results are presented to demonstrate the spectral accuracy attainable. Although we deal with a simple Laplace problem throughout the paper, our analysis covers more complex and general cases. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [18] Graif, E. and K. Kunisch Parameter estimation for the Euler-Bernoulli-beam ICASE Report No. 84-22, June 20, 1984, 43 pages. Submitted to IEEE Trans. Auto. Control. An approximation involving cubic spline functions for parameter estimation problems in the Euler-Bernoulli-beam equation (phrased as an optimization problem with respect to the parameters) is described and convergence is proved. The resulting algorithm was implemented and several of the test examples are documented. It is observed that the use of penalty terms in the cost functional can improve the rate of convergence. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [19] Rosen, I. Gary A numerical scheme for the identification of hybrid systems describing the vibration of flexible beams with tip bodies ICASE Report No. 84-23, June 21, 1984, 36 pages. Submitted to J. Math. Anal. Appl. A cubic spline based Galerkin-like method is developed for the identification of a class of hybrid systems which describe the transverse vibration of flexible beams with attached tip bodies. The identification problem is formulated as a least squares fit to data subject to the system dynamics given by a coupled system of ordinary and partial differential equations recast as an abstract evolution equation (AEE) in an appropriate infinite dimensional Hilbert space. Projecting the AEE into spline-based subspaces leads naturally to a sequence of approximating finite diemnsional identification problems. The solutions to these problems are shown to exist, are relatively easily computed, and are shown to, in some sense, converge to solutions to the original identification problem. Numerical results for a variety of examples are discussed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [20] Banks, H. Thomas and Katherine A. Murphy Estimation of coefficients and boundary parameters in hyperbolic systems ICASE Report No. 84-24, June 21, 1984, 52 pages. Submitted to SIAM J. Control Optim. We consider semi-discrete Galerkin approximation schemes in connection with inverse problems for the estimation of spatially varying coefficients and boundary condition parameters in second order hyperbolic systems typical of those arising in 1-D surface seismic problems. Spline based algorithms are proposed for which theoretical convergence results along with a representative sample of numerical findings are given. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [21] Vardi, A. A new minmax problem ICASE Report No. 84-25, June 26, 1984, 35 pages. Submitted to J. Optim., Theory and Appl. For the classical minimax problem we design a new active set strategy in which there are three types of functions: active, semi-active, and non-active. This technique will help in preventing zigzagging which often occurs when an active set strategy is used. Some of the inequality constraints are handled with slack variables. Also a trust region strategy is used in which at each iteration there is a sphere around the current point in which the local approximation of the function is trusted. The algorithm suggested in the paper was implemented into a successful computer program. Numerical results are provided. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [22] Banks, H. T. and I. G. Rosen Approximation techniques for parameter estimation and feedback control for distributed models of large flexible structures ICASE Report No. 84-26, June 22, 1984, 19 pages. Submitted to Workshop on Identification and Control of Flexible Space Structures, San Diego, CA, June 4-6, 1984, G. Rodgriguez (ed.). We discuss approximation ideas that can be used in parameter estimation and feedback control for Euler-Bernoulli models of elastic systems. Focusing on parameter estimation problems, we outline how one can obtain convergence results for cubic spline-based schemes for hybrid models involving an elastic cantilevered beam with tip mass and base acceleration. Sample numerical findings are also presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [23] Turkel, E. and Bram van Leer Flux vector splitting and Runge-Kutta methods for the Euler equations ICASE Report No. 84-27, June 23, 2984, 9 pages. To appear in Proc. of the 9th Intl. Conference on Numerical Methods in Fluid Dynamics, Saclay, France, June 25-29, 1984. Runge-Kutta schemes have been used as a method of solving the Euler equations exterior to an airfoil. In the past this has been coupled with central differences and an artificial viscosity in space. In this study we couple the Runge-Kutta time stepping scheme with an upwinded space approxima tion based on flux-vector splitting. Several acceleration techniques are also considered including a local time step, residual smoothing and multigrid. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [24] Turkel, Eli Fast solutions to the steady state compressible and incompressible fluid dynamics equations ICASE Report No. 84-28, June 23, 1984, 8 pages. To appear in Proc. of the 9th Intl. Conference on Numerical Methods in Fluid Dynamics Saclay, France, June 25-29, 1984. It is well known that for low speed flows the use of the compressible fluid dynamic equations is inefficient. The use of an explicit scheme requires delta-t to be bounded by 1/c. However, the physical parameters change over time scales of order 1/u which is much larger. Hence, it is not appropriate to use explicit schemes for very subsonic flows. Implicit schemes are hard to vectorize and frequently do not converge quickly for very subsonic flows. We shall demonstrate that if one is only interested in the steady state then a minor change to an existing code can greatly increase the efficiency of an explicit method. Even when using an implicit method the proposed changes increase the efficiency of the scheme. We shall first consider the Euler equations for low speed flows and then incompressible flows. We then indicate how to generalize the method to include viscous effects. We also show how to accelerate supersonic flow by essentially decoupling the equations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [25] Gottlieb, D. Spectral methods for compressible flow problems ICASE Report No. 84-29, June 21, 1984, 20 pages. Proc. 9th Intl. Conference on Numerical Methods in Fluid Dynamics Saclay, France, June 25-29, 1984. In this article we review recent results concerning numerical simulation of shock waves using spectral methods. We discuss shock fitting techniques as well as shock capturing techniques with finite difference artificial viscosity. We also discuss the notion of the information contained in the numerical results obtained by spectral methods and show how this information can be recovered. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [26] Ipsen, Ilse C. F. Singular value decomposition with systolic arrays ICASE Report No. 84-30, July 9, 1984, 22 pages. Proc. of the Society of Photo-Optical Engineers San Diego, CA, August 19-24, 1984. Systolic arrays for determining the Singular Value Decomposition of a matrix A of bandwidth w are presented. After A has been reduced to bidiagonal form B by means of Givens plane rotations, the differential equations. Part II: The linear quadratic control problem. ICASE Report No. 84-31, July 6, 1984, 65 pages. Submitted to SIAM J. Control Optim. The numerical scheme based on the Legendre-tau approximation is proposed to approximate the feedback solution to the linear quadratic optimal control problem for hereditary differential systems. The convergence property is established using Trotter ideas. The method yields very good approximations at low orders and provides an approximation technique for computing closed- loop eigenvalues of the feedback system. A comparison with existing methods (based on "averaging" and "spline" approximations) is made. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [27] Turkel, Eli Acceleration to a steady state for the Euler equations ICASE Report No. 84-32, July 7, 1984, 45 pages. Proc. INRIA Euler Workshop (SIAM) Rocquencourt, France, December 7-9, 1983. A multi-stage Runge-Kutta method is analyzed for solving the Euler equations exterior to an airfoil. Highly subsonic, transonic and supersonic flows are evaluated. Various techniques for accelerating the convergence to a steady state are introduced and analyzed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [28] Bokhari, Shahid H. and A. D. Raza Augmenting computer networks ICASE Report No. 84-33, July 8, 1984, 16 pages. Proc. 1984 Intl. Conference on Parallel Processing Bellaire, MI, August 21-24, 1984. Three methods of augmenting computer networks by adding at most one link per processor are discussed. 1. A tree of N nodes may be augmented such that the resulting graph has diameter no greater than 4 log2((N+2)/3)-2. This 0(N**3) algorithm can be applied to any spanning tree of a connected graph to reduce the diameter of that graph to 0(log N). 2. Given a binary tree T and a chain C of N nodes each, C may be augmented to produce C' so that T is a subgraph of C'. This algorithm is 0(N) and may be used to produce augmented chains or rings that have diameter no greater than 2 log2 (N+2)/3) and are planar. 3. Any rectangular two-dimensional 4 (8) nearest neighbor array of size N = 2**k may be augmented so that it can emulate a single step shuffle- exchange network of size N/2 in 3(t) time steps. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [29] Reed, Daniel A. and Merrell L. Patrick A model of asynchronous iterative algorithms for solving large, sparse, linear systems ICASE Report No. 84-34, July 31, 1984, 27 pages. Proceedings of the 1984 International Conference on Parallel Processing August 21-24, 1984, Bellaire, MI. Solving large, sparse, linear systems of equations is one of the fundamental problems in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. This model is then analyzed to determine the expected intertask data transfer and task computational complexity as functions of the number of tasks. Based on the analysis, recommendations for task partitioning are made. These recommendations are a function of the sparseness of the linear system, its structure (i.e., randomly sparse or banded), and dimension. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [30] Reed, Daniel A. and Merrell L. Patrick Parallel, iterative solution of sparse linear systems: Models and architectures ICASE Report No. 84-35, August 1, 1984, 45 pages. Submitted to Parallel Computing. Solving large, sparse, linear systems of equations is a fundamental problem in large scale scientific and engineering computation. A model of a general class of asychronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. A data transfer model predicting both the probability that data must be transferred between two tasks and the amount of data to be transferred is presented. This model is used to derive an execution time model for predicting parallel execution time and an optimal number of tasks given the dimension and sparsity of the coefficient matrix and the costs of computation, synchronization, and communication. The suitability of different parallel architectures for solving randomly sparse linear systems is discussed. Based on the complexity of task scheduling, one parallel architecture, based on a broadcast bus, is presented and analyzed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [31] Tadmor, Eitan The well-posedness of the Kuramoto-Sivashinsky equation. ICASE Report No. 84-36, August 7, 1984, 22 pages. Submitted to SIAM J. Appl. Math. The Kuramoto-Sivashinsky equation arises in a variety of applications, among which are modeling reaction-diffusion systems, flame-propagation and viscous flow problems. It is considered here, as a prototype to the larger class of generalized Burgers equations: those consist of quadratic nonlinearity and arbitrary linear parabolic part. We show that such equations are well-posed, thus admitting a unique smooth solution, continuously dependent on its initial data. As an attractive alternative to standard energymethods, existence and stability are derived in this case, by "patching" in the large short time solutions without "loss of derivatives". Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [32] Lustman, Liviu The time evolution of spectral discretizations of hyperbolic systems ICASE Report No. 84-37, August 7, 1984, 12 pages. Submitted to SIAM J. Numer. Anal. A Chebyshev collocation spectral method, applied to hyperbolic systems is considered, particularly for those initial boundary value problems which possess only solutions tending to zero at large times. It is shown that the numerical solutions of the system will also vanish at infinity, if and only if, the numerical solution of a scalar equation of the same type does. This result is then generalized for other spectral approximations. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [33] Bayliss, A., C. I. Goldstein, and E. Turkel On accuracy conditions for the numerical computation of waves ICASE Report No. 84-38, August 9, 1984, 16 pages. Submitted to J. Comput. Phys. The Helmholtz equation with a variable index of refraction, and a suitable radiation condition at infinity serves as a model for a wide variety of wave propagation problems. Such problems can be solved numerically by first truncating the given unbounded domain and imposing a suitable outgoing radiation condition on an artificial boundary and then solving the resulting problem on the bounded domain by direct discretization (for example, using a finite element method). In practical applications, the mesh size h and the wave number K, are not independent but are constrained by the accuracy of the desired computation. It will be shown that the number of points per wavelength, measured by l/Kh, is not sufficient to determine the accuracy of a given discretization. For example, the quantity K**3 h**2 is shown to determine the accuracy in the L-two norm for a second-order discretization method applied to several propagation models. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [34] Hariharan, S. I. Numerical solutions of acoustic wave propagation problems using Euler computations ICASE Report No. 84-39, August 10, 1984, 29 pages. Proc. of the AIAA 9th Aeroacoustics Conference Williamsburg, VA, August 15-17, 1984. This paper reports solution procedures for problems arising from the study of engine inlet wave propagation. The first problem is the study of sound waves radiated from cylindrical inlets. The second one is a quasi-one- dimensional problem to study the effect of nonlinearities and the third one is the study of nonlinearities in two dimensions. In all three problems Euler computations are done with a fourth-order explicit scheme. For the first problem results are shown in agreement with experimental data and for the second problem comparisons are made with an existing asymptotic theory. The third problem is part of an ongoing work and preliminary results are presented for this case. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [35] Tadmor, Eitan The exponential accuracy of Fourier and Tchebyshev differencing methods ICASE Report No. 84-40, August 20, 1984, 24 pages. Submitted to SIAM J. Numer. Anal. It is shown that when differencing analytic functions using the pseudospectral Fourier or Tchebyshev methods, the error committed decays to zero at an exponential rate. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [36] Gannon, Dennis and John Van Rosendale On the impact of communication complexity in the design of parallel numerical algorithms ICASE Report No. 84-41, August 22, 1984, 37 pages. To appear in IEEE Trans. on Computers. This paper describes two models of the cost of data movement in parallel numerical algorithms. One model is a generalization of an approach due to Hockney, and is suitable for shared memory multiprocessors where each processor has vector capabilities. The other model is applicable to highly parallel nonshared memory MIMD systems. In the second model, algorithm performance is characterized in terms of the communication network design. Techniques used in VLSI complexity theory are also brought in, and algorithm independent upper bounds on system performance are derived for several problems that are important to scientific computation. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [37] Ito, Kazufumi Legendre-Tau approximation for functional differential equations, Part III: Eigenvalue approximations and uniform stability. ICASE Report No 84-42, August 24, 1984, 34 pages. Proc. Second International Conference on Control Theory for Distributed Parameter Systems and Applications Vorau, Austria, 1984. The stability and convergence properties of the Legendre-tau approximation for hereditary differential systems are analyzed. We derive a characteristic equation for the eigenvalues of the resulting approximate system. As a result of this derivation we are able to establish that the uniform exponential stability of the solution semigroup is preserved under approximation. It is the key to obtaining the convergence of approximate solutions of the algebraic Riccati equation in trace norm. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [38] Berger, M. J. On conservation at grid interfaces ICASE Report No. 84-43, September 7, 1984, 25 pages. Submitted to J. Comput. Phys. This paper considers the solution of hyperbolic systems of conservation laws on discontinuous grids. In particular, we consider what happens to conservation at grid interfaces. A procedure is presented to derive conservative difference approximations at the grid interfaces for two- dimensional grids which overlap in an arbitrary configuration. The same procedures are applied to compute interface formulas for grids which are refined in space and/or time, and for continuous grids where a switch in the scheme causes the discontinuity. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [39] Osher, S. and S. Chakravarthy Very high order accurate TVD schemes ICASE Report No. 84-44, September 10, 1984, 61 pages. Submitted to SIAM J. Numer. Anal. A systematic procedure for constructing semi-discrete families of 2m-1 order accurate, 2m order dissipative, variation diminishing, 2m+1 point bandwidth, conservation form approximations to scalar conservation laws is presented. Here m is any integer between 2 and 8. Simple first-order forward time discretization, used together with any of these approximations to the space derivatives, also results in a fully discrete, variation diminishing algorithm. These schemes all use simple flux limiters, without which each of these fully discrete algorithms is even linearly unstable. Extensions to systems, using a nonlinear field-by-field decomposition are presented, and shown to have many of the same properties as in the scalar case. For linear systems, these nonlinear approximations are variation diminishing, and hence convergent. A new and general criterion for approximations to be variation diminishing is also given. Finally, numerical experiments using some of these algorithms are presented. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [40] Elcrat, A. R. and L. N. Trefethen Classical free-streamline flow over a polygonal obstacle ICASE Report No. 84-45, September 10, 1984, 61 pages. Submitted to J. Comput. Appl. Math. In classical Kirchhoff flow, an ideal incompressible fluid flows past an obstacle and around a motionless wake bounded by free streamlines. Since 1869 it has been known that in principle, the two-dimensional Kirchhoff flow over a polygonal obstacle can be determined by constructing a conformal map onto a polygon in the log-hodograph plane. In practice, however, this idea has rarely been put to use except for very simple obstacles, because the conformal mapping problem has been too difficult. This paper presents a practical method for computing flows over arbitrary polygonal obstacles to high accuracy in a few seconds of computer time. We achieve this high speed and flexibility by working with a modified Schwarz-Christoffel integral that maps onto the flow region directly rather than onto the log-hodograph polygon. This integral and its associated parameter problem are treated numerically by methods developed earlier by Trefethen for standard Schwarz-Christoffel maps. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [41] Krause, Egon Review of some vortex relations ICASE Report No. 84-46, September 12, 1984, 8 pages. Submitted to Computer and Fluids. The evaluation of the circulation from numerical solutions of the momentum and energy equations is discussed for incompressible and compressible flows. It is shown how artificial damping directly influences the time rate of change of the circulation. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [42] Tal-Ezer, Hillel A pseudospectral Legendre method for hyperbolic equations with an improved stability condition ICASE Report No. 84-48, September 14, 1984, 46 pages. Submitted to J. Comput. Phys. A new pseudospectral method is introduced for solving hyperbolic partial differential equations. This method uses different grid points than previously used pseudospectral methods: in fact the grid points are related to the zeroes of the Legendre polynomials. The main advantage of this method is that the allowable time step is proportional to the inverse of the number of grid points 1/N rather than to 1/N**2 (as in the case of other pseudospectral methods applied to mixed initial boundary value problems). A highly accurate time discretization suitable for these spectral methods is discussed. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [43] Bayliss, A., C. I. Goldstein, and E. Turkel The numerical solution of the Helmholtz equation for wave propagation problems in underwater acoustics ICASE Report No. 84-49, September 17, 1983, 29 pages. Submitted to J. Comput. Math. Appl. The Helmholtz Equation with a variable index of refraction, and a suitable radiation condition at infinity serves as a model for a wide variety of wave propagation problems. A numerical algorithm has been developed and a computer code implemented that can effectively solve this equation in the intermediate frequency range. The equation is discretized using the finite element method, thus allowing for the modeling of complicated geometries (including interfaces) and complicated boundary conditions. A global radiation boundary condition is imposed at the far field boundary that is exact for an arbitrary number of propagating modes. The resulting large, non-selfadjoint system of linear equations with indefinite symmetric part is solved using the preconditioned conjugate gradient method applied to the normal equations. A new preconditioner is developed based on the multigrid method. This preconditioner is vectorizable and is extremely effective over a wide range of frequencies provided the number of grid levels is reduced for large frequencies. A heuristic argument is given that indicates the superior convergence properties of this preconditioner. The relevant limit to analyze convergence is for K increasing and a fixed prescribed accuracy level. The efficiency and robustness of the numerical algorithm is confirmed for large acoustic models, including interfaces with strong velocity contrasts. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [44] Burns, John A., Ito, Kazufumi, Powers, Robert K. Chandrasekhar equations and computational algorithms for distributed parameter systems ICASE Report No. 84-50, September 20, 1984, 23 pages. Proc. of 23rd Conference on Decision and Control, December 12-14, 1984, Las Vegas, NV. In this paper we consider the Chandrasekhar equations arising in optimal control problems for linear distributed parameter systems. The equations are derived via approximation theory. This approach is used to obtain existence, uniqueness and strong differentiability of the solutions and provides the basis for a convergent computation scheme for approximating feedback gain operators. A numerical example is presented to illustrate these ideas. Submitted by: emily@icase.csnet Obtainable from: Ms. Barbara Kraft (as above) --------------- [45] Petter E. Bjorstad and Olof B. Widlund Iterative Methods for the Solution of Elliptic Problems on Regions Partitioned into Substructures Finite element problems can often naturally be divided into subproblems which correspond to subregions into which the region has been partitioned or from which it was originally assembled. A class of iterative methods is discussed in which these subproblems are solved by direct methods,while the interaction across the curves or surfaces which divide the region is handled by a conju- gate gradient method. A mathematical framework for this workis provided by regularity theory for elliptic finite element problems and by block Gauss elimination. A full development of the theory,which shows that certain of these methods are optimal, is given for Lagrangian finite element approxi- mations of second order linear elliptic problems in the plane.Results from numerical experiments are also reported. Submitted by: Olaf Widlund Obtainable from: Olaf Widlund Courant Institute 251 Mercer St. N.Y., N.Y. 10012. (WIDLUND@NYU-ACF1.ARPA) --------------- [46] Ron S. Dembo and Ulrich Tulowitzki Local Convergence Analysis for Successive Inexact Quadratic Programming Methods SOM Working Paper Series B #78 Yale School of Organization and Management October, 1984 Successive quadratic programming (SQP) methods for the solution of constrained nonlinear optimization problems are attractive because they converge rapidly from any sufficiently good initial solution. However, solving the quadratic subproblems at each stage can be expensive, particularly if the number of unknowns is large and may be not justified when far away from an optimal solution. Therefore, we consider a class of successive inexact quadratic programming (SIQP) methods that solve the subproblems only approximately. We characterize the rate of convergence in terms of the relative error incurred in the subproblems in a manner that does not assume that the set of active constraints remains constant. This leads to practical termination criteria for truncating various iterative algorithms applied to the quadratic subproblems. Submitted by: Ron Dembo Obtainable from: Ron Dembo Yale University School of Organization and Management P.O. Box 1A New Haven, Conn. 06520 --------------- [47] Ron S. Dembo and Ulrich Tulowitzki Sequential Truncated Quadratic Programming Methods To appear in the Proceedings of the SIAM Conference on Numerical Optimization, Boulder, Colo., June, 1984 In a sequential quadratic programming (SQP) method for nonlinear optimization it is possible to truncate an iterative procedure, applied to each quadratic subproblem, prior to reaching a solution, without affecting the asymptotic rate of convergence. We describe some practical termination criteria which ensure that an SQP method, executed without exact solution of the QP subproblem, inherits the rate of convergence of its (exact) SQP counterpart. Numerical experiments on linearly-constrained problems of up to 2230 variables indicate that substantial savings can be achieved by inexact solution of the QP subproblems with little or no adverse effect on the convergence rate. Submitted by: Ron Dembo Obtainable from: Ron Dembo Yale University School of Organization and Management P.O. Box 1A New Haven, Conn. 06520 --------------- .