================================================== NUMERICAL ANALYSIS TITLES -- Volume 2, Number 1 March, 1984 ================================================== [1] Daniel Szyld: A Two-level Iterative Method for Large Sparse Generalized Eigenvalue Calculations We present a method for the solution of the generalized symmetric eigenvalue problem. The matrices in the pencil are assumed to be too expensive to factor. The outer level of iteration is a step of either Inverse or Rayleigh Quotient iteration. The choice is made at each step to guarantee superlinear convergence to an eigenvalue in (or close to) a prescribed interval. The indefinite linear system is solved at each step with the conjugate gradient type method SYMMLQ, for which a variational formulation and error bounds are presented. Submitted by: Daniel Szyld Obtainable from: Daniel B. Szyld Institute for Economic Analysis New York University 269 Mercer Street, Second Floor New York, NY 10003 --------------- [2] Daniel Szyld: Preliminary Results in Implementing a Model of the World Economy on the Cyber 205: A Case of Large Sparse Nonsymmetric Linear Equations presented at the Cyber 200 Applications Seminar, Oct.10-12, 1983, NASA Godard Ctr. Md. A brief description of the Institutes' Model of the Wrold Economy is presented, together with our experience in converting the software to vector code.Includes running times. Submitted by: Daniel Szyld Obtainable from: Daniel B. Szyld (address above) --------------- [3] G. W. Stewart A Generalization of the Eckart-Young Approximation Theorem TR-1325 Department of Computer Science University of Maryland at College Park September 1983 The Eckart-Young theorem solves the problem of approximating a matrix by one of lower rank. How- ever, the approximation generally differs from the original in all its elements. In this paper it is shown how to obtain a best approximation of lower rank in which a specified set of columns of the matrix remains fixed. The paper concludes with some applications of the generalization. Submitted by: G. W. Stewart Obtainable from: G. W. Stewart Department of Computer Science and Institute for Physical Science and Technology The University of Maryland at College Park College Park, Maryland 20742 --------------- [4] Dianne P. O'Leary and G. W. Stewart DATA-FLOW ALGORITHMS FOR PARALLEL MATRIX COMPUTATIONS In this work we develop some algorithms and tools for solv- ing matrix problems on parallel processing computers. Operations are synchronized through data-flow alone, which makes global synchronization unnecessary and enables the algorithms to be implemented on machines with very simple operating systems and communications protocols. As exam- ples, we present algorithms that form the main modules for solving Liaponuv matrix equations. We compare this approach to wavefront array processors and systolic arrays, and note its advantages in handling missized problems, in evaluating variations of algorithms or architectures, in moving algo- rithms from system to system, and in debugging parallel algorithms on sequential machines. Submitted by: G. W. Stewart Obtainable from: G. W. Stewart (address above) --------------- [5] GENE H. GOLUB AND DAVID MAYERS THE USE OF PRE-CONDITIONING OVER IRREGULAR REGIONS Some ideas and techniques for solving elliptic pde.'s over irregular regions is discussed. The basic idea is to break up the domain into subdomains and then to use the pre-conditioned conjugate gradient method for obtaining the solution over the entire domain. The solution of Poisson's equation over a T-shaped region is described in some detail and a numerical example is given. Submitted by: Gene H. Golub Obtainable from: Gene H. Golub Computer Science Department Stanford University Stanford, California 94305 --------------- [6] Robert Schreiber Computing Genrealized Inverses and Eigenvalues of Symmetric Matrices Using Systolic Arrays. Manuscript NA-83-03. Stanford NA Project New systolic arrays methods are presented for tridiagonalization of a dense, symmetric n x n matrix in O(n**3/2) time, tridiagonalization of a matrix of bandwidth b in O(bn) time, and finding the eigenvalues of a symmetric tridiagonal matrix in O(n) time. Systolic arrays for implementing an iterative method for the generalized inverse are given. They allow computation of the generalized inverse of an m x n matrix in O(m) time. Submitted by: Gene Golub Obtainable from: Gene Golub (address above) --------------- [7] Rodrigo Fontecilla Technical Report 1370 Department of Computer Science University of Maryland at College Park January 1984 In solving nonlinear equality constrained optimization prob- lems using secant methods we often have to solve two or three linear systems of equations at each iteration. We use the theory developed by Dembo, Eisenstat and Steihaug in inexact Newton methods to solve at least one of the linear system inexactly. We analyze the case when the number of constraints is much smaller than the number of variables. In this case we solve the smallest linear system (the one used to find the multipliers) exactly while solving the bigger system (the one giving the step on the variables) inexactly at each iteration. Algorithms using the DFP and the BFGS secant updates are proposed. Conditions on the residual are given in order to allow the user the possibility of a trade- off between the rate of convergence (q-superlinear) and the amount of work per iteration. Submitted by: Rodrigo Fontecilla Obtainable from: Rodrigo Fontecilla <rod%umcp-cs@csnet-cic> Department of Computer Science and Institute for Physical Science and Technology University of Maryland College Park, Maryland 20742 --------------- [8] Richard H. Bartels and John J. Jezioranski On Least Squares Fitting Using Orthogonal Multinomials Forsythe (1) has given a method for generating basis polynomials in a single variable which are orthogonal with respect to a given inner product. Weisfeld (2) later demonstrated that Forsythe's approach could be extended to polynomials in an arbitrary number of variables. In this paper we sharpen Weisfeld's results and present a program for computing weighted, multinomial, least squares approximations to discrete data. ----- (1) G. E. Forsythe (1957), Generation and Use of Orthogonal Polynomials for Data-Fitting with a Digital Computer, J. SIAM 5, 74-87. (2) M. Weisfeld (1959), Orthogonal polynomials in Several Variables, Numer. Math. 1, 38-40. Submitted by: Richard H. Bartels Obtainable from: Richard H. Bartels University of Waterloo Department of Computer Science Waterloo, Ontario Canada N2L 3G1 --------------- [9] Ulrich Tulowitzki Inexact Successive Linearization Methods for Variational Inequality Problems We extend the inexact Newton rate of convergence characterization of Dembo, Eisenstat and Steihaug to variational inequality problems. Our characterization theorem is expressed in terms of the relative error in the solution of a linearized subproblem and does not require the set of active inequalities to remain constant. An immediate consequence of our theorem is a practical termination criterion for truncating an iterative procedure applied to the subproblems in successive quadratic programming algorithms for nonlinear optimization. Submitted by: Ulrich Tulowitzki Obtainable from: Ulrich Tulowitzki <Tulowitzki@YALE.ARPA> Yale University School of Organization and Management Box 1-A New Haven, CT 06520 --------------- [10] Ron S. Dembo and Siddhartha Sahi A Convergent Framework for Constrained Nonlinear Optimization Working Paper, Series B #69 School of Organization and Management Yale University September, 1983 We describe a simple, practical algorithmic framework for constrained nonlinear optimization. Any algorithm that may be expressed in this framework, and most existing algorithms can, will converge to a local minimum from an arbitrary feasible starting point. The framework is particularly suitable for the analysis and development of algorithms for large-scale optimization, since it permits radical changes in the active set to occur at each step and can be implemented in terms of quantities that are easily computed. Submitted by: Ron Dembo Obtainable from: Ron Dembo Yale University School of Organization and Management Box 1-A New Haven, CT 06520 --------------- .