Which algorithm(s) does FindIntegerNullVector[]
- To: mathgroup at smc.vnet.net
- Subject: [mg122414] Which algorithm(s) does FindIntegerNullVector[]
- From: Simon <simonjtyler at gmail.com>
- Date: Fri, 28 Oct 2011 05:32:49 -0400 (EDT)
- Delivered-to: l-mathgroup@mail-archive0.wolfram.com
- Reply-to: comp.soft-sys.math.mathematica at googlegroups.com
I only just noticed that Mathematica 8 introduced the new function FindIntegerNullVector. It is a integer relation function (http://mathworld.wolfram.com/IntegerRelation.html) but the documentation and a Trace[..., TraceInternal -> True] gives no hint to what class of algorithms it belongs to. Mathematica has for a long time had a variant of the LLL lattice reduction algorithm which can be used to generate integer relations. I've got some simple code based off Paul Abbott's (http://forums.wolfram.com/mathgroup/archive/2005/Jan/msg00254.html) which seems to perform better than the new FindIntegerNullVector, i.e. it needs less precision to find the correct relation in the cases I'm interested in. So my question is: Is FindIntegerNullVector based on LatticeReduce or does it use some other (more efficient) algorithm such as PSQL? ---------------- For those that are interested, here's my version of Paul's code: TranscendentalRecognize[num_Real, basis_List, ord_Integer] := Module[{vect, mat, lr, ans}, vect = Round[10^(ord - 1) Join[{num}, N[basis, ord]]]; mat = Append[IdentityMatrix[Length[vect]], vect]; lr = LatticeReduce[Transpose[mat]]; ans = First[lr[[1]]]^-1 Most[Rest[lr[[1]]]].basis; Sign[N@ans] Sign[num] ans] TranscendentalRecognize[num_Real, basis_List] := TranscendentalRecognize[num, basis, Precision[num] // IntegerPart]