IML - Integer Matrix Library

[What is IML?] - [What is new] - [Timings] - [Download] - [Reporting Bugs] - [Reference] - [Authors] - [Related Work]

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

[top]

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[64] and MinGW[64].

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]

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.

Inverse of a nonsingular mod p matrix, where p is about 20-bit long
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

Determinant of a mod p matrix, where p is about 20-bit long
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

[top]

Download

Click the following links to download the source codes for different versions.

IML 1.0.5 iml-1.0.5.tar.bz2 Size: 392K Released on: 2015-12-07 New!
IML 1.0.4 iml-1.0.4.tar.bz2 Size: 396K Released on: 2014-07-30
IML 1.0.3 iml-1.0.3.tar.gz Size: 392K Released on: 2008-07-28
IML 1.0.2 iml-1.0.2.tar.gz Size: 388K Released on: 2007-09-14
IML 1.0.1 iml-1.0.1.tar.gz Size: 385K Released on: 2006-11-26
IML 0.1.0 iml-0.1.0.tar.gz Size: 370K Released on: 2004-09-24

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.

ATLAS can be obtained from http://math-atlas.sourceforge.net.
GMP can be obtained from http://gmplib.org.

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]

Last updated: 30 July 2014