Now for computing integer solutions
of rational equations you might
want to keep in mind that Gauss reduction
suffers from exponential
growth of the entries because every
row operation on the matrix
can---and usually does---double the
number of bits in the numbers.
For this reason, Gaussian elimination
and simple Hermite NF algorithms
are only useful if the number of equations
is very low (<< 10, say).
Otherwise, you need to use more advanced
algorithms (e.g. solving
several "mod m" images of
the equation and reconstructing using the
Chinese Remainder Theorem), but I am
not aware of any 'off the shelf'
implementation of this functionality
in Ocaml.
As an entry point for the algorithms
consider this page from the manual
of the computer algebra system Magma:
----
Dr. Sebastian Egner
Senior Scientist
Philips Research Laboratories
Prof. Holstlaan 4 (WDC 1-051, 1st floor, room 51)
5656 AA Eindhoven
The Netherlands
tel: +31 40 27-43166
fax: +31 40 27-44004
email: sebastian.egner@philips.com
Thomas Gazagnaire <thomas.gazagnaire@irisa.fr>
Sent by:
caml-list-bounces@yquem.inria.fr
29-11-2005 19:46
To
caml-list@yquem.inria.fr
cc
Subject
[Caml-list] Integral solutions of rational
linear equations
Classification
Hello,
in my one of my Ocaml programs, I need to find all integers solutions of
a rational equation systems. This algo uses Gauss reduction and Hermite
normal form, and need to know if a rational is an integer or not (ie. I
don't want to use numerical approximation : (1/3) * 3 is an integer but
0,333333*3 we don't know). I didn't find any integer algebra package for
ocaml, so I tried to implement Gauss elimination (easy) and Hermite
normal form (more difficult...). But I didn't implement optimized
version of these algorithms...
So my question is : do you know if exists a native ocaml module or an
interface with a C library which is able to do integer/rational matrix
manipulation (essentialy the Hermite normal form) in an efficient way ?