Back to the homepage of Dan Steffy
Tools for Symbolic Linear AlgebraThis page contains software and test problems developed to solve systems of linear equations exactly over the rational numbers. Solvers are provided for both sparse and dense systems. We also provide BasisLIB, a large test set of sparse linear systems arising from linear programming applications, and a script to generate several classes of dense matrices. Sparse Rational SolversThis following software for solving sparse rational systems of equations was developed as part of the following computational study:Solving Very Sparse Rational Systems of Equations. William Cook and Daniel Steffy. To appear in ACM Transactions on Mathematical Software. A poster presentation based on this project is also available. Exact Computation of Basic Solutions for Linear Programming (Poster Presentation) This computational study contains a detailed description of each of the implementations and of the origins of the test set BasisLIB. The software contained on this page was developed by David Applegate, William Cook, Sanjeeb Dash, Daniel Espinoza, and Daniel Steffy. Here we provide source code for the rational solvers. Each solver is written in C for the Linux/UNIX environment and relies on the GNU Multiple Precision Arithmetic Library. Each code contains basic documentation.
This code may be used under the terms of the GNU General Public License (Version 2.1 or later) as published by the Free Software Foundation. Alternatively, use is granted for research purposes only. It is your choice of which of these two licenses you are operating under. BasisLIBBasisLIB is a test set of 276 sparse linear systems arising for linear programming applications. Each problem is a square non-singular system of rational linear equations. Click below to download the entire library, including a problem list and format description.[Download BasisLIB 14 mb] The linear systems here are all basis systems from linear programming problems. The basis recorded for each problem is either the optimal basis, or the final basis encountered after 24 hours of solve time as encountered within QSopt_ex. A full description of how the problems were generated can be found in the paper. The linear programming problems from which this test set was generated come from the following linear programming test sets. NETLIB MIPLIB 3.0 MIPLIB 2003 Meszaros LP Test Set Mittelmann LP Test Set TSPLIB Many of the instances can also be found in the GAMS Performance Library Dense Rational SolversThe dense rational solvers provided here were implemented to perform tests for the following study on output sensitive lifting:Exact solutions to linear systems of equations using output sensitive lifting. Daniel Steffy. To appear in ACM Communications in Computer Algebra. Detailed description of the methods can be found in this paper, and documentation is included with each code. The dense Dixon solver uses C++ and requires the FFLAS-FFPACK package. The iterative-refinement method is written in C. Both also require a BLAS installation.
We also provide scripts which can be used to generate the test matrices used in our paper. They will generate a some Hadamard, Random, Hilbert, Vandermonde and Lehmer matrices. [Download Generation Scripts] These are written in python and include documentation. Links to Related ProjectsGNU Multiple Precision Arithmetic LibraryGMP is a high performance multiprecision arithmetic library. Each of our codes relies on this library. ATLAS: Automatically Tuned Linear Algebra Software A project that provides automatically tuned BLAS routines and a subset of LAPACK. Our dense solvers require BLAS/LAPACK. FFLAS-FFPACK A fast library for performing BLAS and some LAPACK routines over finite fields. Our dense Dixon solver relies on this. QSopt_ex QSopt_ex is a start of the art solver for solving linear programming problems exactly. The LU based solvers used in the above codes are all derived from code in QSopt and QSopt_ex. QSopt QSopt is a linear programming solver. Sparse Integer Matrices Collection A nice collection of integer and rational matrices coming from many different applications put together by Jean-Guillaume Dumas. BasisLIB is included here in both rational and scaled integer formats. LinBox A C++ template library for exact, high-performance linear algebra computation with dense, sparse, and structured matrices over the integers and over finite fields. IML - Integer Matrix Library A library for finding exact solutions to dense integer systems of equations. This BLAS based library is developed by Z. Chen and A. Storjohann. ContactThis page is maintained by Dan Steffy (desteffy@gatech.edu). Contact me with questions or bugs. |