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 32bit and 64bit 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 rowechelon 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]20151207 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.
20140730 The current release is 1.0.4. This version can now be built as a dynamic library under Cygwin[64] and MinGW[64].
20080728 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.
20070914 The current release is 1.0.2. This version corrects several bugs.
20061126 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.
20040924 The current release is 0.1.0. This version modifies the implementation of padic 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.
20040730 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.
Testing environment:
CPU: Itanium2 1.3GHz, memory: 50Gb, platform: GNU/Linux 2.4.21sgi240rp0405180810074, 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.2620040424patch2.4.26, compiler & linker: gcc 3.3.3, GMP: 4.1.3, ATLAS 3.6.0.
Dimension  300  500  1000  2000  3000  5000  8000 
Time  0.08 s  0.29 s  2.03 s  14.73 s  48.35 s  3.61 m  15.08 m 
Dimension  300  500  1000  2000  3000  5000  8000 
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 iml1.0.5.tar.bz2
and compile and install the library by
following the installation instructions in the INSTALL
file inside the iml1.0.5 directory.
To install this software, you need to preinstall the ATLAS library and GMP library.
The compilation is tested in the following hosts: i686pclinuxgnu using gcc 3.3, ia64unknowngunlinux using gcc 3.3 and icc 8.0, sparcsunsolaris2.6 using gcc 3.2, and i686pccygwin using gcc 3.3.
[top]If you find any bugs or come across installation problems, please send email to Arne Storjohann astorjoh@uwaterloo.ca.
[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. 9299.
[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 (FFLASFFPACK) provides a suite of Basic Linear Algebra Subroutines over finite fields.
[top]