Unsafe features
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20051130 (08:34) 
From:  Sebastian Egner <sebastian.egner@p...> 
Subject:  Re: [Camllist] Integral solutions of rational linear equations 
Thomas, Ocaml comes with a library for arbitraryprecision rational arithmetics; the library is called 'Num' and its documentation can be found from here: http://caml.inria.fr/pub/docs/manualocaml/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 canand usually doesdouble 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 1051, 1st floor, room 51) 5656 AA Eindhoven The Netherlands tel: +31 40 2743166 fax: +31 40 2744004 email: sebastian.egner@philips.com Thomas Gazagnaire <thomas.gazagnaire@irisa.fr> Sent by: camllistbounces@yquem.inria.fr 29112005 19:46 To camllist@yquem.inria.fr cc Subject [Camllist] 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 _______________________________________________ Camllist mailing list. Subscription management: http://yquem.inria.fr/cgibin/mailman/listinfo/camllist Archives: http://caml.inria.fr Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/camlbugs