 |
|
|
|
|
 |
 |
|
Half-GCD, Fast Rational Recovery, and Planar Lattice Reduction
|
|
|
|
|
|
| Organization: | Wolfram Research, Inc. |
|
|
|
|
|
|
ISSAC 2005
|
|
|
|
|
|
Beijing, China
|
|
|
|
|
|
This is an extended version of work presented at ISSAC 2005, Beijing, July 2005.
Abstract
Over the past few decades several variations on a "half GCD" algorithm for obtaining the pair of terms in the middle of a Euclidean sequence have been proposed. In the integer case algorithm design and proof of correctness are complicated by the effect of carries. This paper will demonstrate a variant with a relatively simple proof of correctness. We then apply this to rational recovery for a linear algebra solver. After showing how this same task might be accomplished by lattice reduction, albeit more slowly, we proceed to use the half GCD to obtain asymptotically fast planar lattice reduction.
|
|
|
|
|
|
|
|
|
|
|
|
integer gcd, subquadratic arithmetic, rational recovery, planar lattice reduction
|
|
|
|
|
|
http://www.mmrc.iss.ac.cn/issac2005/
|
|
|
 |
|
|
| HGCD_and_planar_lattices.pdf (113.1 KB) - PDF Document | | ISSAC2005_HGCD_slides.pdf (722.2 KB) - PDF Document | | HGCD_and_planar_lattices.nb (192.6 KB) - Mathematica Notebook | | ISSAC2005_HGCD_slides.nb (211.2 KB) - Mathematica Notebook |
|
|
For the newest resources, visit Wolfram Repositories and Archives »
