IML is a free library of C source code which implements algorithms for computing exact solutions to dense systems of linear equations over the integers. IML is designed to be compiled with a CBLAS library (e.g., ATLAS/BLAS) and the GMP bignum library.
Written in portable C, IML can be used on both 32-bit and 64-bit machines. It can be called from C++.
Currently, IML provides the following functionality:
In addition, IML provides some low level routines for a variety of mod p matrix operations: computing the row-echelon form, determinant, rank profile, and inverse of a mod p matrix. These mod p routines are not general purpose; they require that p satisfy some preconditions based on the dimension of the input matrix (usually p should be prime and should be no more than about 20 bits long).[top]
2015-12-07 The current release is 1.0.5. This version incorporates a new functions kernelLong and kernelMP into the library interface for computing a right kernel basis of an integer matrix of type long and filled with GMP bignums, respectively. The kernel basis returned can be optionally reduced using lattice basis reduction. Unlike functions nullspaceLong and nullspaceMP which only compute a basis for the rational nullspace, functions kernelLong and kernelMP produce an integer basis for the sublattice of all integer vectors in the right kernel of the input matrix.
2014-07-30 The current release is 1.0.4. This version can now be built as a dynamic library under Cygwin and MinGW.
2008-07-28 The current release is 1.0.3. This version incorporates a new function nullspaceMP into the library interface which computes an integral basis for the right rational nullspace of an integer matrix filled with GMP bignums.
2007-09-14 The current release is 1.0.2. This version corrects several bugs.
2006-11-26 The current release is 1.0.1. This version corrects several bugs as well as incorporates a new function nullspaceLong into the library interface which computes an integral basis for the right rational nullspace of an integer matrix with type long.
2004-09-24 The current release is 0.1.0. This version modifies the implementation of p-adic lifting algorithm and gains 30 to 50 percent speedup on the functions without reducing the solution size such as nonsingSolvMM . Considerable speedup is also gained from other functions for system solving. For example, let A be a 2000 x 3000 integer matrix and let b be a 2000 x 1 integer vector. Entries in A and b are randomly chosen from -7 to 7. If the solution size is not reduced, the new version spends 7 minutes certified solving the system Ax=b while the old version spends 10 minutes.
2004-07-30 The current release is 0.0.0, namely the first release. If you find any bugs, please report to us referring to the reporting bugs.[top]
The following two tables list some timings for system of linear equations with small entries and large entries respectively. For input systems with a nontrivial nullspace, lattice reduction may optionally be used to attempt to reduce the size of the solution at an increase in running time. The dimension of input matrix is listed in the first column. All the square input systems in the table are nonsingular.
CPU: Itanium2 1.3GHz, memory: 50Gb, platform: GNU/Linux 2.4.21-sgi240rp0405180810074, compiler & linker: icc 8.0, GMP 4.1.3, ATLAS 3.6.0
The following tables list the timings for computing inverse
and determinant of a mod p matrix.
The testing environment is
CPU: PentiumM 1.6GHz, memory: 1Gb, platform: GNU/Linux 2.4.26-20040424-patch2.4.26, compiler & linker: gcc 3.3.3, GMP: 4.1.3, ATLAS 3.6.0.
|Time||0.08 s||0.29 s||2.03 s||14.73 s||48.35 s||3.61 m||15.08 m|
|Time||0.03 s||0.11 s||0.73 s||5.13 s||16.65 s||1.23 m||5.31 m|
Click the following links to download the source codes for different versions.
After download the source code, unzip the file using command
tar xjvf iml-1.0.5.tar.bz2
and compile and install the library by following the installation instructions in the INSTALL file inside the iml-1.0.5 directory.
To install this software, you need to pre-install the ATLAS library and GMP library.
The compilation is tested in the following hosts: i686-pc-linux-gnu using gcc 3.3, ia64-unknown-gun-linux using gcc 3.3 and icc 8.0, sparc-sun-solaris2.6 using gcc 3.2, and i686-pc-cygwin using gcc 3.3.[top]
If you find any bugs or come across installation problems, please send email to Arne Storjohann firstname.lastname@example.org.[top]
Z. Chen and A. Storjohann, A BLAS based C library for exact linear algebra on integer matrices. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC'05), ACM Press, 2005, pp. 92-99.[top]
Zhuliang Chen, principle author, David R. Cheriton School of Computer Science, University of Waterloo
Arne Storjohann, David R. Cheriton School of Computer Science, University of Waterloo
Cory Fletcher, University of Waterloo
Project Finite field linear algebra subroutines/package (FFLAS-FFPACK) provides a suite of Basic Linear Algebra Subroutines over finite fields.[top]