Name
Abstract | ||
|---|---|---|
The HJLS and PSLQ algorithms are the de facto standards for discovering non-trivial integer relations between a given tuple of real numbers. In this work, we provide a new interpretation of these algorithms, in a more general and powerful algebraic setup: we view them as special cases of algorithms that compute the intersection between a lattice and a vector subspace. Further, we extract from them the first algorithm for manipulating finitely generated additive subgroups of a euclidean space, including projections of lattices and finite sums of lattices. We adapt the analyses of HJLS and PSLQ to derive correctness and convergence guarantees. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2465506.2465936 | ISSAC |
Keywords | Field | DocType |
special case,real number,euclidean space,pslq algorithm,finite sum,additive subgroup,new interpretation,convergence guarantee,powerful algebraic setup,non-trivial integer relation,new view,lattice,integer relation | Integer,Discrete mathematics,Combinatorics,Algebraic number,Algebra,Tuple,Computer science,Correctness,Integer relation algorithm,Euclidean space,Linear subspace,Real number | Conference |
Citations | PageRank | References |
4 | 0.48 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jingwei Chen | 1 | 60 | 11.58 |
| Damien Stehlé | 2 | 1269 | 73.95 |
| Gilles Villard | 3 | 565 | 48.04 |