Balanced Truncation Model Reduction of Large-Scale Dense Systems on Parallel Computers

Model reduction is an area of fundamental importance in many modeling and control applications. In this paper we analyze the use of parallel computing in model reduction methods based on balanced truncation of large-scale dense systems. The methods require the computation of the Gramians of a linear-time invariant system. Using a sign function-based solver for computing full-rank factors of the Gramians yields some favorable computational aspects in the subsequent computation of the reduced-order model, particularly for non-minimal systems. As sign function-based computations only require efficient implementations of basic linear algebra operations readily available, e.g., in the BLAS, LAPACK, and ScaLAPACK, good performance of the resulting algorithms on parallel computers is to be expected. Our experimental results on a PC cluster show the performance and scalability of the parallel implementation.     

Simultaneous multidiagonalization for the CS decomposition

When an orthogonal matrix is partitioned into a two-by-two block structure, its four blocks can be simultaneously bidiagonalized. This observation underlies numerically stable algorithms for the CS decomposition and the existence of CMV matrices for orthogonal polynomial recurrences. We discover a new matrix decomposition for simultaneous multidiagonalization, which reduces the blocks to any desired bandwidth. Its existence is proved, and a backward stable algorithm is developed. The resulting matrix with banded blocks is parameterized by a product of Givens rotations, guaranteeing orthogonality even on a finite-precision computer. The algorithm relies heavily on Level 3 BLAS routines and supports parallel computation.     

Sparse matrix multiplication package (SMMP)

Routines callable fromFortran and C are described which implement matrix-matrix multiplication and transposition for a variety of sparse matrix formats. Conversion routines between various formats are provided.The algorithms and routines described here were developed while both authors were visiting the Center for Applied Mathematics, Department of Mathematics, Purdue University. This research was supported in part by the Office of Naval Research, Grant No. N00014-895-1440.     

Partitioned quasi-Newton methods for nonlinear equality constrained optimization

We derive new quasi-Newton updates for the (nonlinear) equality constrained minimization problem. The new updates satisfy a quasi-Newton equation, maintain positive definiteness on the null space of the active constraint matrix, and satisfy a minimum change condition. The application of the updates is not restricted to a small neighbourhood of the solution. In addition to derivation and motivational remarks, we discuss various numerical subtleties and provide results of numerical experiments.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the US Department of Energy under grant DE-FG02-86ER25013.A000, and by the US Army Research Office through the Mathematical Sciences Institute, Cornell University.     

Parallel sparse Gaussian elimination with partial pivoting

In this article, we consider the factorization of a sparse nonsymmetric matrix using Gaussian elimination with partial pivoting on a multiprocessor having a globally-shared memory. The parallel algorithm makes use of a static data structure developed by George, Liu and Ng in [17]. Some numerical experiments on a Sequent Balance 8000 are presented to demonstrate the efficiency of the parallel implementation.Research supported in part by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc.     

Convergence properties of trust region methods for linear and convex constraints

We develop a convergence theory for convex and linearly constrained trust region methods which only requires that the step between iterates produce a sufficient reduction in the trust region subproblem. Global convergence is established for general convex constraints while the local analysis is for linearly constrained problems. The main local result establishes that if the sequence converges to a nondegenerate stationary point then the active constraints at the solution are identified in a finite number of iterations. As a consequence of the identification properties, we develop rate of convergence results by assuming that the step is a truncated Newton method. Our development is mainly geometrical; this approach allows the development of a convergence theory without any linear independence assumptions.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by the National Science Foundation grant DMS-8803206 and by the Air Force Office of Scientific Research grant AFSOR-860080.     

A block algorithm for computing antitriangular factorizations of symmetric matrices

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.     

Computing theCS decomposition of a partitioned orthonormal matrix

Summary This paper describes an algorithm for simultaneously diagonalizing by orthogonal transformations the blocks of a partitioned matrix having orthonormal columns.This work was supported by the Air Force Office of Scientific Research under Contract No. AFOSR-82-0078     

On optimal triangular meshes for minimizing the gradient error

Summary Construction of optimal triangular meshes for controlling the errors in gradient estimation for piecewise linear interpolation of data functions in the plane is discussed. Using an appropriate linear coordinate transformation, rigorously optimal meshes for controlling the error in quadratic data functions are constructed. It is shown that the transformation can be generated as a curvilinear coordinate transformation for anyC data function with nonsingular Hessian matrix. Using this transformation, a construction of nearly optimal meshes for general data functions is described and the error equilibration properties of these meshes discussed. In particular, it is shown that equilibration of errors is not a sufficient condition for optimality. A comparison of meshes generated under several different criteria is made, and their equilibrating properties illustrated.This work was supported by the Natural Sciences and Engineering Research Council of Canada, by the Information Technology Research Centre, which is funded by the Province of Ontario, by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy under contract DE-AC05-84OR21400 with Martin Marietta Energy Systems, Inc., and through an appointment to the U.S. Department of Energy Postgraduate Research Program administered by Oak Ridge Associated Universities     

Analysis of switched linear systems in the plane,part 1: Local behavior of trajectories and local cycle geometry

This paper investigates the problem of control of switched linear systems evolving inR ². The concept of an opposition point is introduced, and its properties related to the existence of closed trajectories in the phase plane are investigated. The geometry of cycles in a neighborhood of an opposition point is also studied.This research was supported by the Office of Naval Research, ONR Contract No. N0013-80-C-0199, and the United States Department of Energy, DOE Contract No. DE-AC01-79-ET-29363.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

The empirical behavior of sampling methods for stochastic programming

We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various ways. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant 9726385. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grant DMS-0073770. Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the National Science Foundation under Grants 9726385 and 0082065.     

The equivalence of strict convexity and injectivity of the gradient in bounded level sets

It is shown that Lipschitzian functions are strictly convex if and only if their generalized gradients are disjoint at distinct interior points of a given bounded level set.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38.     

Optimal design of pitched laminated wood beams

The optimal design of a pitched laminated wood beam is considered. An engineering formulation is given in which the volume of the beam is minimized. The problem is then reformulated and solved as a generalized geometric (signomial) program. Sample designs are presented.This research was partially supported by the Office of Naval Research under Contracts Nos. N00014-75-C-0267 and N00014-75-C-0865; by the US Energy Research and Development Administration Contract No. E(04-3)-326 PA-18; and by the National Science Foundation, Grant No. DCR75-04544 at Stanford University. This work was carried out during the first author's stay at the Management Science Division of the University of British Columbia and the Systems Optimization Laboratory of Stanford University. The authors are indebted to Mr. S. Liu and Mrs. M. Ratner for their assistance in performing the computations.     

Computing mountain passes and transition states

The mountain-pass theorem guarantees the existence of a critical point on a path that connects two points separated by a sufficiently high barrier. We propose the elastic string algorithm for computing mountain passes in finite-dimensional problems and analyze the convergence properties and numerical performance of this algorithm for benchmark problems in chemistry and discretizations of infinite-dimensional variational problems. We show that any limit point of the elastic string algorithm is a path that crosses a critical point at which the Hessian matrix is not positive definite.This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

Interior point methods for optimal control of discrete time systems

We show that recently developed interior point methods for quadratic programming and linear complementarity problems can be put to use in solving discrete-time optimal control problems, with general pointwise constraints on states and controls. We describe interior point algorithms for a discrete-time linear-quadratic regulator problem with mixed state/control constraints and show how they can be efficiently-incorporated into an inexact sequential quadratic programming algorithm for nonlinear problems. The key to the efficiency of the interior-point method is the narrow-banded structure of the coefficient matrix which is factorized at each iteration.This research was supported by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38.     

On the solution of large,structured linear complementarity problems: The block partitioned case

This paper delineates the underlying theory of an efficient method for solving a class of specially-structured linear complementarity problems of potentially very large size. We propose a block-iterative method in which the subproblems are linear complementarity problems. Problems of the type considered here arise in the process of making discrete approximations to differential equations in the presence of special side conditions. This problem source is exemplified by the free boundary problem for finite-length journal bearings. Some of the authors' computational experience with the method is presented.Research partially supported by the Office of Naval Research under contract N-00014-67-A-0112-0011; U.S. Atomic Energy Commission Contract AT (04-3)-326 PA No. 18.Research partially supported by U.S. Atomic Energy Commission Contract AT(04-3)-326 PA No. 30; and National Science Foundation Grant GJ 35135X.     

On the solution of concave knapsack problems

We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject to linear constraints, and use this characterization to show that although the problem of determining a global minimizer of the concave knapsack problem is NP-hard, it is possible to determine a local minimizer of this problem with at most O(n logn) operations and 1+[logn] evaluations of the function. If the function is quadratic this algorithm requires at most O(n logn) operations.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by a Fannie and John Hertz Foundation graduate fellowship.     

Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices

The sum of the largest eigenvalues of a symmetric matrix is a nonsmooth convex function of the matrix elements. Max characterizations for this sum are established, giving a concise characterization of the subdifferential in terms of a dual matrix. This leads to a very useful characterization of the generalized gradient of the following convex composite function: the sum of the largest eigenvalues of a smooth symmetric matrix-valued function of a set of real parameters. The dual matrix provides the information required to either verify first-order optimality conditions at a point or to generate a descent direction for the eigenvalue sum from that point, splitting a multiple eigenvalue if necessary. Connections with the classical literature on sums of eigenvalues and eigenvalue perturbation theory are discussed. Sums of the largest eigenvalues in the absolute value sense are also addressed.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.The work of this author was supported by the National Science Foundation under grants CCR-8802408 and CCR-9101640.The work of this author was supported in part during a visit to Argonne National Laboratory by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under contract W-31-109-Eng-38, and in part during a visit to the Courant Institute by the U.S. Department of Energy under Contract DEFG0288ER25053.