# IML - Integer Matrix Library

## What is IML?

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:

• Nonsingular rational system solving: compute the unique rational solution X to the system AX=B, where A and B are integer matrices, A nonsingular.
• Compute the right nullspace or kernel of an integer matrix.
• Certified linear system solving: compute a minimal denominator solution x to a system Ax=b, where b is an integer vector and A is an integer matrix with arbitrary shape and rank profile.

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).

## What is New?

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.

## Timings

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.21-sgi240rp0405180810074, compiler & linker: icc 8.0, GMP 4.1.3, ATLAS 3.6.0

Small entries: entries in the input systems are 1-decimal digit long
Dimension Typical solution Size Reduced solution
n x m # of solution
decimal digits
time # of solution
decimal digits
time
<= 10 seconds <= 20 seconds
1000 x 1000 1905 7 s
400 x 1000 1141 6 s 116 9 s
500 x 600 1354 9 s 137 15 s
500 x 1000 1445 9 s 146 16 s
<= 30 seconds <= 50 seconds
1500 x 1500 2989 20 s
700 x 1500 2138 22 s 216 38 s
750 x 2000 2363 28 s 238 49 s
800 x 1000 2344 29 s 236 50 s
<= 1 minute <= 1.5 minutes
2000 x 2000 4110 42 s
900 x 1000 2628 40 s 264 70 s
950 x 2000 3024 50 s 304 85 s
1000 x 2000 3097 52 s 311 89 s
Dimension Typical solution Size Reduced solution
n x m # of solution
decimal digits
time # of solution
decimal digits
time
<= 15 minutes <= 20 minutes
6000 x 6000 13761 15 m
2000 x 4000 6980 7 m 700 11 m
2500 x 3000 8506 12 m 852 18 m
2500 x 5000 8965 13 m 899 20 m
<= 30 minutes <= 50 minutes
7000 x 7000 16288 23 m
3000 x 6000 10995 22 m 1102 33 m
3400 x 4000 11991 27 m 1200 42 m
3400 x 7000 12674 30 m 1269 47 m
>= 1 hour >= 2 hours
10000 x 10000 24044 1 h
5000 x 10000 19434 1.7 h 1945 2.4 h
6000 x 8000 22967 2.6 h 2298 3.9 h
6000 x 10000 23451 3.3 h 2347 4.8 h

Large entries: entries in the input systems are 100-decimal digits long
Dimension Typical solution Size Reduced solution
n x m # of solution
decimal digits
time # of solution
decimal digits
time
<= 10 seconds <= 1.5 minutes
100 x 100 9990 5 s
30 x 60 3005 3 s 301 29 s
40 x 100 4013 6 s 402 53 s
50 x 200 5030 9 s 504 87 s
<= 30 seconds <= 5 minutes
200 x 200 20008 30 s
70 x 200 7045 18 s 705 3 m
80 x 200 8053 24 s 806 4 m
80 x 400 8067 28 s 808 4 m
<= 1 minute <= 10 minutes
250 x 250 25021 44 s
90 x 100 8988 34 s 899 6 m
100 x 200 10068 41 s 1008 7 m
110 x 200 11076 50 s 1109 9 m
Dimension Typical solution Size Reduced solution
n x m # of solution
decimal digits
time # of solution
decimal digits
time
<= 15 minutes <= 3.5 hours
1000 x 1000 100386 13 m
200 x 400 20196 4 m 2021 43 m
300 x 400 30345 9 m 3036 2.1 h
350 x 500 35426 13 m 3544 3.2 h
<= 30 minutes <= 9 hours
1200 x 1200 120508 23 m
400 x 800 40510 18 m 4053 4.5 h
450 x 900 45596 23 m 4561 6.3 h
500 x 600 50593 29 m 5061 8.4 h
>= 1 hour >= 30 hours
2000 x 2000 201071 1.3 h
800 x 2000 81308 1.5 h 8133 30.5 h
1000 x 1500 101575 2.7 h
1500 x 2000 152559 7.9 h

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.

 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

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.

## Reporting Bugs

If you find any bugs or come across installation problems, please send email to Arne Storjohann astorjoh@uwaterloo.ca.

## Reference

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.

## Authors

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

## Related Work

Project Finite field linear algebra subroutines/package (FFLAS-FFPACK) provides a suite of Basic Linear Algebra Subroutines over finite fields.  Last updated: 30 July 2014