Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Half-GCD, Fast Rational Recovery, and Planar Lattice Reduction
Author

Daniel Lichtblau
Organization: Wolfram Research, Inc.
Conference

ISSAC 2005
Conference location

Beijing, China
Description

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.
Subjects

*Mathematica Technology > Programming > Symbolic Computation
*Mathematics > Number Theory
Keywords

integer gcd, subquadratic arithmetic, rational recovery, planar lattice reduction
URL

http://www.mmrc.iss.ac.cn/issac2005/
Downloads Download Wolfram CDF Player

Download
HGCD_and_planar_lattices.pdf (113.1 KB) - PDF Document
Download
ISSAC2005_HGCD_slides.pdf (722.2 KB) - PDF Document
Download
HGCD_and_planar_lattices.nb (192.6 KB) - Mathematica Notebook
Download
ISSAC2005_HGCD_slides.nb (211.2 KB) - Mathematica Notebook