SPEX Cholesky, SPEX LDL, and SPEX Backslash are software packages for exactly solving sparse linear systems, \(A\mathbf{x}=\mathbf{b}\) . SPEX Cholesky, used for symmetric positive definite (SPD) systems, computes an integral Cholesky factorization to solve the system \(A\mathbf{x}=\mathbf{b}\) in time proportional to arithmetic work—to date the only algorithm for SPD linear systems with this property. SPEX LDL extends SPEX Cholesky for symmetric negative definite and symmetric indefinite matrices with exclusively non-zero leading principal minors. SPEX Backslash is a general-purpose exact solver that automatically determines the best ordering and factorization to exactly solve the system \(A\mathbf{x}=\mathbf{b}\) . Computationally, we test the accuracy of MATLAB sparse backslash, the state-of-the-art collection of sparse matrix solvers, revealing it is near perfect for 87% of the tested instances. In addition, we show that SPEX Cholesky outperforms alternate exact solvers in runtime; specifically, SPEX Cholesky outperforms the exact solver Linbox and exact LU factorization on 70% and 92% of tested instances, respectively. Each of SPEX Cholesky, SPEX LDL, and SPEX Backslash is implemented in C and is accompanied by easy-to-use Python and MATLAB interfaces. They are distributed via GitHub, as a component of the SPEX software package, and as component of SuiteSparse.

SPEX Left LU is a software package for exactly solving unsymmetric sparse linear systems. As a component of the sparse exact (SPEX) software package, SPEX Left LU can be applied to any input matrix, A , whose entries are integral, rational, or decimal, and provides a solution to the system \( Ax = b \) , which is either exact or accurate to user-specified precision. SPEX Left LU preorders the matrix A with a user-specified fill-reducing ordering and computes a left-looking LU factorization with the special property that each operation used to compute the L and U matrices is integral. Notable additional applications of this package include benchmarking the stability and accuracy of state-of-the-art linear solvers and determining whether singular-to-double-precision matrices are indeed singular. Computationally, this article evaluates the impact of several novel pivoting schemes in exact arithmetic, benchmarks the exact iterative solvers within Linbox, and benchmarks the accuracy of MATLAB sparse backslash. Most importantly, it is shown that SPEX Left LU outperforms the exact iterative solvers in run time on easy instances and in stability as the iterative solver fails on a sizeable subset of the tested (both easy and hard) instances. The SPEX Left LU package is written in ANSI C, comes with a MATLAB interface, and is distributed via GitHub, as a component of the SPEX software package, and as a component of SuiteSparse.

Exact solving of systems of linear equations (SLEs) is a fundamental subroutine within number theory, formal verification of mathematical proofs, and exact-precision mathematical programming. Moreover, efficient exact SLE solution methods could be valuable for a growing body of science and engineering applications where current fixed-precision standards have been deemed inadequate. This article contains key derivations relating, and computational tests comparing, two exact direct solution frameworks: roundoff-error-free (REF) LU factorization and rational arithmetic LU factorization. Specifically, both approaches solve the linear system Ax = b by factoring the matrix A into the product of a lower triangular (L) and upper triangular (U) matrix, A = LU . Most significantly, the featured findings reveal that the integer-preserving REF factorization framework solves dense SLEs one order of magnitude faster than the exact rational arithmetic approach while requiring half the memory. Since rational LU is utilized for basic solution validation in exact linear and mixed-integer programming, these results offer preliminary evidence of the potential of the REF factorization framework to be utilized within this specific context. Additionally, this article develops and analyzes an efficient streamlined version of Edmonds’s Q-matrix approach that can be implemented as another basic solution validation approach. Further experiments demonstrate that the REF factorization framework also outperforms this alternative integer-preserving approach in terms of memory requirements and computational effort. General purpose codes to solve dense SLEs exactly via any of the aforementioned methods have been made available to the research and academic communities.

Multiresolution metrology devices coexist in today's manufacturing environment, producing coordinate measurements complementing each other. Typically, the high-resolution (HR) device produces a scarce but accurate data set, whereas the low-resolution (LR) one produces a dense but less accurate data set. Research has shown that combining the two data sets of different resolutions makes better predictions of the geometric features of a manufactured part. A challenge, however, is how to effectively match each HR data point to an LR counterpart that measures approximately the same physical location. A solution to this matching problem appears a prerequisite to a good final prediction. We solved this problem by formulating it as a quadratic integer program, aiming at minimizing the maximum interpoint distance difference among all potential correspondences. Due to the combinatorial nature of the optimization model, solving it to optimality is computationally prohibitive even for a small problem size. We therefore propose a two-stage matching framework capable of solving real-life-sized problems within a reasonable amount of time. This two-stage framework consists of downsampling the full-size problem, solving the downsampled problem to optimality, extending the solution of the downsampled problem to the full-size problem, and refining the solution using iterative local search. Numerical experiments show that the proposed approach outperforms two popular point set registration alternatives, the iterative closest point and coherent point drift methods, using different performance metrics. The numerical results also show that our approach scales much better as the instance size increases, and is robust to the changes in initial misalignment between the two data sets.

In the Hamiltonian p-median problem (HpMP), the target is to find p cycles that partition a given undirected graph with the objective of minimizing the total sum of the costs of these p cycles. Even though this problem has several applications, the current state-of-the-art algorithms are only able to solve instances with up to 100 nodes. In this paper, we devise a branch-and-price algorithm that is able to solve instances with up to 318 nodes. To achieve this, we modified the set partitioning formulation of HpMP—a minor modification yet with significant algorithmic and computational advantages. Furthermore, our computational results demonstrate that the practical complexity of HpMP and the performance of the algorithms to solve it strongly depend on the value of p. In addition, to solve the pricing problem, we make contributions on a couple of problems that are important on their own right: (1) we develop a new efficient algorithm to find the least-cost cycle in undirected graphs with arbitrary edge costs and no negative cycles; and (2) we develop an algorithm to find the most negative cycle in undirected graphs with arbitrary edge costs. Finally, we prove that for every value of p, HpMP is NP-hard even when restricted to Euclidean graphs.

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundoff-error-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients’ maximum word length—i.e., the maximum number of digits required for expression—is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries’ word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented.

Computing the degree of redundancy for structured linear systems is proven to be NP-hard. A linear system whose model matrix is of size n×p is considered structured if some p row vectors in the model matrix are linearly dependent. Bound-and-decompose and 0-1 mixed integer programming (MIP) are two approaches to compute the degree of redundancy, which were previously proposed and compared in the literature. In this paper, first we present an enhanced version of the bound-and-decompose algorithm, which is substantially (up to 30 times) faster than the original version. We then present a novel hybrid algorithm to measure redundancy in structured linear systems. This algorithm uses a 0-1 mixed integer feasibility checking algorithm embedded within a bound-and-decompose framework. Our computational study indicates that this new hybrid approach significantly outperforms the existing algorithms as well as our enhanced version of bound-and-decompose in several instances. We also perform a computational study that shows matrix density has a significant effect on the runtime of the algorithms.

A hitting set for a collection of sets is a set that has a nonempty intersection with each set in the collection; the hitting set problem is to find a hitting set of minimum cardinality. Motivated by instances of the hitting set problem where the number of sets to be hit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting set problem the collection of sets to be hit is typically too large to list explicitly; instead, an oracle is provided which, given a set H, either determines that H is a hitting set or returns a set that H does not hit. We show a number of examples of classic implicit hitting set problems, and give a generic algorithm for solving such problems optimally. The main contribution of this paper is to show that this framework is valuable in developing approximation algorithms. We illustrate this methodology by presenting a simple on-line algorithm for the minimum feedback vertex set problem on random graphs. In particular our algorithm gives a feedback vertex set of size n–(1/p) log np(1 − o(1)) with probability at least 3/4 for the random graph Gn,p (the smallest feedback vertex set is of size n − (2/p) log np(1 + o(1))). We also consider a planted model for the feedback vertex set in directed random graphs. Here we show that a hitting set for a polynomial-sized subset of cycles is a hitting set for the planted random graph and this allows us to exactly recover the planted feedback vertex set.