================================================== NUMERICAL ANALYSIS TITLES -- Volume 1, Number 2 September, 1983 ================================================== [1] J.J. Dongarra and C.B. Moler, EISPACK - A Package for Solving Matrix Eigenvalue Problems, Argonne National Laboratory, Mathematics and Computer Science Division, ANL/MCS-TM-12, August 1983. This is a two part paper on the software package EISPACK. The first part describes the development and usage of EISPACK and is intended as an introduction to the package. The second part describes changes made to the package for the current release and how to install the package. EISPACK is a systemized collection of subroutines that compute the eigenvalues and eigenvectors of different classes of matrices. Submitted by: Jack Dongarra Obtainable from: Jack Dongarra Mathematics and Computer Science Division Argonne National Laboratory Argonne, Illinois 60439 --------------- [2] ESTIMATION OF SPARSE HESSIAN MATRICES AND GRAPH COLORING PROBLEMS Thomas F. Coleman and Jorge J. More' Large scale optimization problems often require an approximation to the Hessian matrix. If the Hessian matrix is sparse then estimation by differences of gradients is attractive because the number of required differences is usually small compared to the dimension of the problem. The problem of estimating Hessian matrices by differences can be phrased as follows: Given the sparsity structure of a symmetric matrix A, obtain p vectors d(1), ..., d(p) such that Ad(1), ..., Ad(p) determine A uniquely with p as small as possible. We approach this problem from a graph theoretic point of view and show that both direct and indirect approaches to this problem have a natural graph coloring interpretation. The complexity of the problem is analyzed and efficient practical heuristic procedures are developed. Numerical results illustrate the differences between the various approaches. Submitted by: Jorge J. More' Obtainable from: Jorge More' Mathematics and Computer Science Division Argonne National Laboratory Argonne, Illinois 60439 --------------- [3] SOFTWARE FOR ESTIMATION OF SPARSE JACOBIAN MATRICES Thomas F. Coleman, Burton S. Garbow, and Jorge J. More' In many nonlinear problems it is necessary to estimate the Jacobian matrix of a nonlinear mapping F. In large scale problems the Jacobian of F is usually sparse, and then estimation by differences is attractive because the number of differences can be small compared to the dimension of the problem. For example, if the Jacobian matrix is banded then the number of differences needed to estimate the Jacobian matrix is, at most, the width of the band. In this paper we describe a set of Fortran 77 subroutines whose purpose is to estimate the Jacobian matrix of a mapping F with the least possible number of function evaluations. Submitted by: Jorge J. More' Obtainable from: Jorge More' (address above) --------------- [4] THE MINPACK PROJECT Jorge J. More', Danny C. Sorensen, Burton S. Garbow, and Kenneth E. Hillstrom The MINPACK project is a research effort whose goal is the development of a systematized collection of quality optimization software. In this paper we provide an overview of the MINPACK project. We describe the circumstances that led to the project and the various changes that occurred during the next four years. We also describe the techniques we have used to produce reliable, easy-to-use, transportable software. We discuss those topics that are relevant to the development of software optimization libraries: scale invariance, robustness, convergence testing, user interface and documentation standards. Submitted by: Jorge J. More' Obtainable from: Jorge J. More' (address above) --------------- [5] A Nonlinear Version of Gauss's Minimum Variance Theorem with Applications to an Errors-in-the-Variables Model G. W. Stewart TR-1263, April 1983 This paper consists of two parts. In the first, a theorem of Gauss, commonly known as the Gauss- Markov theorem, is generalized and extended to apply to nonlinear least squares estimation. The result justifies the use of nonlinear least squares under the classical assumptions that the errors have mean zero and equal variances, with the additional proviso that the variance is suffi- ciently small. In the second part of the paper the theory developed in the first is applied to an errors-in-the-variables model to justify the use of a form of latent root regression to estimate regression coefficients. However, it is further shown that in terms of the theory ordinary least squares is equally good, which suggests that the latter is to be prefered on grounds of computa- tional simplicity. Submitted by: G. W. Stewart Obtainable from: G. W. Stewart University of Maryland Department of Computer Science College Park, MD 20742 U.S.A. --------------- [6] On the Asymptotic Behavior of Scaled Singular Value and QR Decompositions. G. W. Stewart TR-1307, July 1983 Asymptotic expressions are derived for the singu- lar value decomposition of a matrix some of whose columns approach zero. Expressions are also derived for the QR factorization of a matrix some of whose rows approach zero. The expressions give insight into the method of weights for approximat- ing the solutions of constrained least squares problems. Submitted by: G. W. Stewart Obtainable from: G. W. Stewart (address above) --------------- [7] A Jacobi-like Algorithm for Computing the Schur Decomposition of a Non-Hermitian Matrix G. W. Stewart TR-1321, August 1983 (Dedicated to Peter Henrici on his sixtieth birthday.) This paper describes an iterative method for reducing a general matrix to upper triangular form by unitary similarity transformations. The method is similar to Jacobi's method for the symmetric eigenvalue problem in that it uses plane rotations to annihilate off-diagonal elements, and when the matrix is Hermitian it reduces to a variant of Jacobi's method. Although the method cannot com- pete with the QR algorithm in serial implementa- tion, it admits of a parallel implementation in which a double sweep of the matrix can be done in time proportional to the order of the matrix. Submitted by: G. W. Stewart Obtainable from: G. W. Stewart (address above) --------------- [8] On Lipschitzian Proximity Maps J. R. Respess and E. W. Cheney CNA-174, July 1981 [No abstract] Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis R. L. Moore Hall, 13.150 University of Texas Austin, Texas 78712 (At the time the report is sent, an invoice in the amount of $1 per copy to cover duplication and postage will be included.) --------------- [9] The Characterization of Best Approximations in Tensor Product Spaces W. A. Light and E. W. Cheney CNA-175, September 1981 Given compact Hausdorff spaces S and T, a subspace W of C(SxT) is defined by W = G*C(T) + C(S)*H where G and H are finite dimensional subspaces of C(S) and C(T) respectively, and "*" represents the tensor product. Necessary and sufficient conditions are developed for a function in C(SxT) to have a best approximation in W. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [10] Generalized Conjugate Gradient Acceleration of Iterative Methods Kang Chang Jea CNA-176, February 1982 Acceleration of basic iterative methods is considered for solving large sparse systems of linear equations which are ei- ther not symmetrizable or for which no symmetrization matrix is conveniently available. Work on developing a method which will work as well as Chebyshev acceleration but requires no eigenvalue estimates is described. Algorithms are analyzed and numerical re- sults given. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [11] Adapting ITPACK Routines for Use on a Vector Computer David R. Kincaid, Thomas Oppe, and David M. Young CNA-177, August 1982 A description of recent work involving vectorization of the ITPACK package of iterative algorithms for the solution of large sparse systems of linear equations is given along with nu- merical results from runs on the CDC CYBER 203 and 205 computers. A more complete vectorization involving, in some cases, total re- design of algorithms is projected. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [12] ITPACK on Supercomputers David R. Kincaid and Thomas Oppe CNA-178, September 1982 Results of preliminary testing of a vector version of ITPACK are presented. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [13] The Best Approximation of Bivariate Functions by Separable Functions M. von Golitschek and E. W. Cheney CNA-179, December 1982 [No abstract] Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [14] The ITPACK Project: Past, Present, and Future David R. Kincaid and David M. Young CNA-180, March 1983 The objectives of the ITPACK project are reviewed, pro- gress to date is summarized, and plans for future work are out- lined. The present packages for use on scalar and vector compu- ters are described. An overview is given of developmental work on other software involving preconditioners and nonsymmetric proce- dures. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [15] Accelerating Nonsymmetrizable Iterative Methods David M. Young, Kang Chang Jea, and David R. Kincaid CNA-181, March 1983 We discuss recent work done at the University of Texas and elsewhere on accelerating basic iterative methods for the solution of systems of linear equations which have a nonsym- metrizable coefficient matrix. Approaches discussed include that of Concus and Golub and of Widlund as well as the use of normal equations, Chebyshev acceleration, and generalized conjugate gra- dient procedures. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [16] The ITPACK Software Package David M. Young and David R. Kincaid CNA-182, June 1983 We discuss iterative methods for the solution of sys- tems of linear equations in general and their implementation in ITPACK. Future modifications of the package including vectoriza- tion and modularization are considered. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [17] The Embedding of Proximinal Sets Carlo Franchetti and E. W. Cheney CNA-183, June 1983 Given Banach spaces Y < X < Z (where "<" denotes the subset relation) such that Y is proximinal in X, we discuss con- ditions under which Y remains proximinal when considered as a subspace of Z. Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [18] Minimal Projections in Tensor Product Spaces Carlo Franchetti and E. W. Cheney CNA-184, July 1983 [No abstract] Submitted by: David Kincaid Obtainable from: Center for Numerical Analysis (address above, $1 charge) --------------- [19] Splines in Interactive Computer Graphics Richard H. Bartels (Invited presentation, Dundee Conference, 1983) Computer graphics, particularly interactive computer graphics, is not, as the name might imply, concerned with drawing graphs, but rather with the broadest issues of manipulating, transforming, and displaying information in visual format. It is interactive in so far as operations can be carried out in real time -- which requires algorithms of high computational efficiency and low com- plexity. Splines are a valuable tool in graphics, but they are often applied in a way not used by the mathematician. This difference raises computational issues which the numerical analyst might otherwise never see. This talk will provide a brief introduction to such issues and follow with a study of two current developments. We begin with a review of the graphics en- vironment, mentioning the modelling and display process and pointing out some of the costly issues. The novel use of splines in interactive graphics comes through the construction of sur- faces as weighted averages of selected points, called control vertices in which B-splines are taken as the weighting functions. Some examples will illustrate the characteristics of this use of B-splines. With this background we consider two recent develop- ments. The first is the control-vertex recurrence of Riesenfeld, Cohen, and Lyche; the second is Barsky's work on geometric vs. mathematical continuity, and his introduction of Beta-splines. We will close with some results on current research concerned with a synthesis of these two developments. Submitted by: Richard Bartels Obtainable from: Richard Bartels University of Waterloo Department of Computer Science Waterloo, Ontario Canada N2L 3G1 --------------- [20] NUMERICAL DECOMPOSITION OF A CONVEX FUNCTION Mike Lamoureux Henry Wolkowicz Department of Mathematics Department of Mathematics Stanford University University of Alberta Given the n by p orthogonal matrix A and the convex function f: R(n) to R, we find two orthogonal matrices P and Q such that f is 'almost' constant on the convex hull of the columns of P and -P, f is 'sufficiently' nonconstant on the column space of Q, and the column spaces of P and Q provide an orthogonal direct sum decomposition of the column space of A. This provides a numerically stable algorithm for calculating the cone of directions of constancy, at a point x, of a convex function. Applications to convex programming are discussed. Submitted by: Henry Wolkowicz Obtainable from: Henry Wolkowicz Department of Mathematics University of Alberta Edmonton, Canada T6G 2G1 --------------- .