From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@yquem.inria.fr Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id E2112BB9C; Wed, 30 Nov 2005 09:34:01 +0100 (CET) Received: from gw-eur4.philips.com (gw-eur4.philips.com [161.85.125.10]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id jAU8Y1Fk014702; Wed, 30 Nov 2005 09:34:01 +0100 Received: from smtpscan-eur5.philips.com (smtpscan-eur5.mail.philips.com [130.144.57.168]) by gw-eur4.philips.com (Postfix) with ESMTP id D238849732; Wed, 30 Nov 2005 08:33:58 +0000 (UTC) Received: from smtpscan-eur5.philips.com (localhost [127.0.0.1]) by localhost.philips.com (Postfix) with ESMTP id E2EB96BFB; Wed, 30 Nov 2005 08:33:57 +0000 (GMT) Received: from smtprelay-eur2.philips.com (smtprelay-eur2.philips.com [130.144.57.171]) by smtpscan-eur5.philips.com (Postfix) with ESMTP id 7BA956C33; Wed, 30 Nov 2005 08:33:56 +0000 (GMT) Received: from ehvrmh02.diamond.philips.com (ehvrmh02-srv.diamond.philips.com [130.139.27.125]) by smtprelay-eur2.philips.com (Postfix) with ESMTP id DAB7B44; Wed, 30 Nov 2005 08:33:55 +0000 (GMT) In-Reply-To: <438CA20C.2080200@irisa.fr> To: Thomas Gazagnaire Cc: caml-list@yquem.inria.fr, caml-list-bounces@yquem.inria.fr Subject: Re: [Caml-list] Integral solutions of rational linear equations MIME-Version: 1.0 X-Mailer: Lotus Notes Release 6.0.3 September 26, 2003 Message-ID: From: Sebastian Egner Date: Wed, 30 Nov 2005 09:32:12 +0100 X-MIMETrack: Serialize by Router on ehvrmh02/H/SERVER/PHILIPS(Release 6.5.3FP1HF291 | September 19, 2005) at 30/11/2005 09:32:16, Serialize complete at 30/11/2005 09:32:16 Content-Type: multipart/alternative; boundary="=_alternative 002F0C57C12570C9_=" X-Miltered: at concorde with ID 438D63F9.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 ocaml:01 gaussian:01 ocaml:01 algebra:01 eindhoven:01 irisa:01 caml-list:01 integers:01 algebra:01 beginner's:01 beginners:01 bug:01 gaussian:01 eindhoven:01 X-Spam-Checker-Version: SpamAssassin 3.0.3 (2005-04-27) on yquem.inria.fr X-Spam-Level: X-Spam-Status: No, score=0.1 required=5.0 tests=HTML_40_50,HTML_MESSAGE autolearn=disabled version=3.0.3 This is a multipart message in MIME format. --=_alternative 002F0C57C12570C9_= Content-Type: text/plain; charset="US-ASCII" Thomas, Ocaml comes with a library for arbitrary-precision rational arithmetics; the library is called 'Num' and its documentation can be found from here: http://caml.inria.fr/pub/docs/manual-ocaml/manual036.html 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: http://magma.maths.usyd.edu.au/magma/htmlhelp/text602.htm#5489 Sebastian. ---- 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 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 ? Thomas _______________________________________________ Caml-list mailing list. Subscription management: http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs --=_alternative 002F0C57C12570C9_= Content-Type: text/html; charset="US-ASCII"
Thomas,

Ocaml comes with a library for arbitrary-precision rational arithmetics;
the library is called 'Num' and its documentation can be found from here:

        http://caml.inria.fr/pub/docs/manual-ocaml/manual036.html

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:

        http://magma.maths.usyd.edu.au/magma/htmlhelp/text602.htm#5489

Sebastian.

----
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 ?

Thomas


_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs
--=_alternative 002F0C57C12570C9_=--