Solving a linear diophantine equation with lower and upper bounds on the variables

Aardal, Karen; Hurkens, Cor A.J.; Lenstra, Arjen K.

Solving a linear diophantine equation with lower and upper bounds on the variables

Conference paper (1998)

Authors

Karen Aardal Universiteit Utrecht

Cor A.J. Hurkens Eindhoven University of Technology

Arjen K. Lenstra Citibank

Affiliation

External organisation

Diophantine Equation Feasibility Problem Basis Reduction Convex Body Initial Basis

To reference this document use:

http://resolver.tudelft.nl/uuid:3e55969a-bfa0-4b22-8827-9c9029ce5027

More Info

expand_more

Published Date

1998

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

Abstract

We develop an algorithm for solving a linear diophantine equation with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction, and first finds short vectors satisfying the diophantine equation. The next step is to branch on linear combi- nations of these vectors, which either yields a vector that satisfies the bound constraints or provides a proof that no such vector exists. The research was motivated by the need for solving constrained linear dio- phantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good result on real-life data.