Perturbation and error analyses for block downdating of a Cholesky decomposition

A new perturbation result is presented for the problem of block downdating a Cholesky decompositionX ^T X = R ^T R. Then, a condition number for block downdating is proposed and compared to other downdating condition numbers presented in literature recently. This new condition number is shown to give a tighter bound in many cases. Using the perturbation theory, an error analysis is presented for the block downdating algorithms based on the LINPACK downdating algorithm and stabilized hyperbolic transformations. An error analysis is also given for block downdating using Corrected Seminormal Equations (CSNE), and it is shown that for ill-conditioned downdates this method gives more accurate results than the algorithms based on the LINPACK downdating algorithm or hyperbolic transformations. We classify the problems for which the CSNE downdating method produces a downdated upper triangular matrix which is comparable in accuracy to the upper triangular factor obtained from the QR decomposition by Householder transformations on the data matrix with the row block deleted.Dedicated to Ji-guang Sun in honour of his 60th birthdayThe work of the second author was supported in part by the National Science Foundation grant CCR-9209726.     

Rank-k modification methods for recursive least squares problems

In least squares problems, it is often desired to solve the same problem repeatedly but with several rows of the data either added, deleted, or both. Methods for quickly solving a problem after adding or deleting one row of data at a time are known. In this paper we introduce fundamental rank-k updating and downdating methods and show how extensions of rank-1 downdating methods based on LINPACK, Corrected Semi-Normal Equations (CSNE), and Gram-Schmidt factorizations, as well as new rank-k downdating methods, can all be derived from these fundamental results. We then analyze the cost of each new algorithm and make comparisons tok applications of the corresponding rank-1 algorithms. We provide experimental results comparing the numerical accuracy of the various algorithms, paying particular attention to the downdating methods, due to their potential numerical difficulties for ill-conditioned problems. We then discuss the computation involved for each downdating method, measured in terms of operation counts and BLAS calls. Finally, we provide serial execution timing results for these algorithms, noting preferable points for improvement and optimization. From our experiments we conclude that the Gram-Schmidt methods perform best in terms of numerical accuracy, but may be too costly for serial execution for large problems.Research supported in part by the Joint Services Electronics Program, contract no. F49620-90-C-0039.     

Accurate downdating of a modified Gram-Schmidt QR decomposition

A new algorithm for downdating a QR decomposition is presented. We show that, when the columns in the Q factor from the Modified Gram-Schmidt QR decomposition of a matrixX are exactly orthonormal, the Gram-Schmidt downdating algorithm for the QR decomposition ofX is equivalent to downdating the full Householder QR decomposition of the matrixX augmented by ann ×n zero matrix on top. Using this relation, we derive an algorithm that improves the Gram-Schmidt downdating algorithm when the columns in the Q factor are not orthonormal. Numerical test results show that the new algorithm produces far more accurate results than the Gram-Schmidt downdating algorithm for certain ill-conditioned problems.This work was partially supported in part by the National Science Foundation grants CCR-9209726 and CCR-9509085.     

RankRev: aMatlab package for computing the numerical rank and updating/downdating

The numerical rank determination frequently occurs in matrix computation when the conventional exact rank of a hidden matrix is desired to be recovered. This paper presents a Matlab package RankRev that implements two efficient algorithms for computing the numerical rank and numerical subspaces of a matrix along with updating/downdating capabilities for making adjustment to the results when a row or column is inserted/deleted. The package and the underlying algorithms are accurate, reliable, and much more efficient than the singular value decomposition when the matrix is of low rank or low nullity.     

On choices of formulations of computing the generalized singular value decomposition of a large matrix pair

For the computation of the generalized singular value decomposition (GSVD) of a large matrix pair (A,B) of full column rank, the GSVD is commonly formulated as two mathematically equivalent generalized eigenvalue problems, so that a generalized eigensolver can be applied to one of them and the desired GSVD components are then recovered from the computed generalized eigenpairs. Our concern in this paper is, in finite precision arithmetic, which generalized eigenvalue formulation is numerically preferable to compute the desired GSVD components more accurately. We make a detailed perturbation analysis on the two formulations and show how to make a suitable choice between them. Numerical experiments illustrate the results obtained.

     

Alternating direction splitting for block Angular parallel optimization

We develop and compare three decomposition algorithms derived from the method of alternating directions. They may be viewed as block Gauss-Seidel variants of augmented Lagrangian approaches that take advantage of block angular structure. From a parallel computation viewpoint, they are ideally suited to a data parallel environment. Numerical results for large-scale multicommodity flow problems are presented to demonstrate the effectiveness of these decomposition algorithmims on the Thinking Machines CM-5 parallel supercomputer relative to the widely-used serial optimization package MINOS 5.4.This material is based on research supported by the Air Force Office of Scientific Research, Grants AFORS-89-0410 and F49620-1-0036, and by NSF Grants CCR-89-07671, CDA-90-24618, and CCR-93-06807. The work of the second author was supported partially by Grant 95.00732.CT01 from the Italian National Research Council (CNR).     

An efficient rank detection procedure for modifying the ULV decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The problem of adding and deleting rows from the ULVD (called updating and downdating, respectively) is considered. The ULVD can be updated and downdated much faster than the SVD, hence its utility. When updating or downdating the ULVD, it is necessary to compute its numerical rank. In this paper, we propose an efficient algorithm which almost always maintains rank-revealing structure of the decomposition after an update or downdate without standard condition estimation. Moreover, we can monitor the accuracy of the information provided by the ULVD as compared to the SVD by tracking exact Frobenius norms of the two small blocks of the lower triangular factor in the decomposition.     

Computing the optimal commuting matrix pairs

A matrix can be modified by an additive perturbation so that it commutes with any given matrix. In this paper, we discuss several algorithms for computing the smallest perturbation in the Frobenius norm for a given matrix pair. The algorithms have applications in 2-D direction-of-arrival finding in array signal processing. The work of first author was supported in part by NSF grant CCR-9308399. The work of the second author was supported in part by China State Major Key Project for Basic Researches.     

Nonmonotone curvilinear line search methods for unconstrained optimization

We present a new algorithmic framework for solving unconstrained minimization problems that incorporates a curvilinear linesearch. The search direction used in our framework is a combination of an approximate Newton direction and a direction of negative curvature. Global convergence to a stationary point where the Hessian matrix is positive semidefinite is exhibited for this class of algorithms by means of a nonmonotone stabilization strategy. An implementation using the Bunch-Parlett decomposition is shown to outperform several other techniques on a large class of test problems.The work of this author was based on research supported by the National Science Foundation Grant CCR-9157632, the Air Force Office of Scientific Research Grant F49620-94-1-0036 and the Department of Energy Grant DE-FG03-94ER61915.These authors were partially supported by Agenzia Spaziale Italiana, Roma, Italy.     

Path problems in skew-symmetric graphs

We study path problems in skew-symmetric graphs. These problems generalize the standard graph reachability and shortest path problems. We establish combinatorial solvability criteria and duality relations for the skew-symmetric path problems and use them to design efficient algorithms for these problems. The algorithms presented are competitive with the fastest algorithms for the standard problems.This research was done while the first author was at Stanford University Computer Science Department, supported in part by ONR Office of Naval Research Young Investigator Award N00014-91-J-1855, NSF Presidential Young Investigator Grant CCR-8858097 with matching funds from AT&T, DEC, and 3M, and a grant from Powell Foundation.This research was done while the second author was visiting Stanford University Computer Science Department and supported by the above mentioned NSF and Powell Foundation Grants.     

The union of balls and its dual shape

Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in ℝ ^d . These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in ℝ³ where unions of finitely many balls are commonly used as models of molecules. This work is supported by the National Science Foundation, under Grant ASC-9200301, and the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the view of the National Science Foundation.     

Approximating disjoint-path problems using packing integer programs

In a packing integer program, we are given a matrix $A$ and column vectors $b,c$ with nonnegative entries. We seek a vector $x$ of nonnegative integers, which maximizes $c^{T}x,$ subject to $Ax \leq b.$ The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.     

A globally convergent Newton method for convex SC1 minimization problems

This paper presents a globally convergent and locally superlinearly convergent method for solving a convex minimization problem whose objective function has a semismooth but nondifferentiable gradient. Applications to nonlinear minimax problems, stochastic programs with recourse, and their extensions are discussed.The research of the first author is based on work supported by the National Science Foundation under Grants DDM-9104078 and CCR-9213739. This research was carried out while he was visiting the University of New South Wales. The research of the second author is based on work supported by the Australian Research Council.     

Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

Modified predictor-corrector algorithm for locating weighted centers in linear programming

In certain applications of linear programming, the determination of a particular solution, the weighted center of the solution set, is often desired, giving rise to the need for algorithms capable of locating such center. In this paper, we modify the Mizuno-Todd-Ye predictor-corrector algorithm so that the modified algorithm is guaranteed to converge to the weighted center for given weights. The key idea is to ensure that iterates remain in a sequence of shrinking neighborhoods of the weighted central path. The modified algorithm also possesses polynomiality and superlinear convergence.The work of the first author was supported in part by NSF Grant DMS-91-02761 and DOE Contract DE-FG05-91-ER25100.The work of the second author was supported in part by NSF Cooperative Agreement CCR-88-09615.     

The primal douglas-rachford splitting algorithm for a class of monotone mappings with application to the traffic equilibrium problem

We apply the Douglas-Rachford splitting algorithm to a class of multi-valued equations consisting of the sum of two monotone mappings. Compared with the dual application of the same algorithm, which is known as the alternating direction method of multipliers, the primal application yields algorithms that seem somewhat involved. However, the resulting algorithms may be applied effectively to problems with certain special structure. In particular we show that they can be used to derive decomposition algorithms for solving the variational inequality formulation of the traffic equilibrium problem. This research was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science and Culture, Japan.     

Modifying the forrest-Tomlin and saunders updates for linear programming problems with variable upper bounds

The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Fonest—Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted. Research supported in part by a fellowship from the Alfred P. Sloan Foundation and by NSF Grant ECS82-15361.     

On the convergence rate of Newton interior-point methods in the absence of strict complementarity

In the absence of strict complementarity, Monteiro and Wright [7] proved that the convergence rate for a class of Newton interior-point methods for linear complementarity problems is at best linear. They also established an upper bound of 1/4 for the Q ₁-factor of the duality gap sequence when the steplengths converge to one. In the current paper, we prove that the Q ₁ factor of the duality gap sequence is exactly 1/4. In addition, the convergence of the Tapia indicators is also discussed.This author was supported in part by NSF Coop. Agr. No. CCR-8809615 and AFOSR 89-0363 and the REDI Foundation.This author was supported in part by NSF Coop. Agr. No. CCR-8809615, AFOSR 89-0363, DOE DEFG05-86ER25017 and ARO 9DAAL03-90-G-0093.Visiting member of the Center for Research on Parallel Computations, Rice University, Houston, Texas, 77251-1892. This author was supported in part by DOE DE-FG02-93ER25171.     

Weighted median algorithms for L1 approximation

The weighted median problem arises as a subproblem in certain multivariate optimization problems, includingL ₁ approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariateL ₁ approximation.This work was supported in part by National Science Foundation Grant CCR-8713893 and in part by a grant from The City University of New York PSC-CUNY Research Award program.     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.