Publication

Solving a system of linear diophantine equations with lower and upper bounds on the variables

Arjen Lenstra
2000
Article
Résumé

We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first finds a short vector satisfying the system of diophantine equations, and a set of vectors belonging to the null-space of the constraint matrix. Due to basis reduction, all these vectors are relatively short. The next step is to branch on linear combinations of the null-space 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 diophantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good results on real-life data, and on instances from the literature

À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Concepts associés (39)
Espace vectoriel
vignette|Dans un espace vectoriel, on peut additionner deux vecteurs. Par exemple, la somme du vecteur v (en bleu) et w (en rouge) est v + w. On peut aussi multiplier un vecteur, comme le vecteur w que l'on peut multiplier par 2, on obtient alors 2w et la somme devient v + 2w. En mathématiques, plus précisément en algèbre linéaire, un espace vectoriel est un ensemble d'objets, appelés vecteurs, que l'on peut additionner entre eux, et que l'on peut multiplier par un scalaire (pour les étirer ou les rétrécir, les tourner, etc.
Vecteur isotrope
En mathématiques, un vecteur isotrope pour une forme bilinéaire f est un vecteur x tel que f(x, x) = 0. Soient E un espace vectoriel et f une forme bilinéaire symétrique sur E. On dit qu'un vecteur x de E est isotrope (pour f, ou pour la forme quadratique associée) si f(x, x) = 0. L'ensemble des vecteurs isotropes est appelé le cône isotrope. Il contient le noyau de f. Au cône isotrope, on associe une quadrique projective. La forme bilinéaire est dite définie — et la forme quadratique est dite anisotrope — si 0 est son seul vecteur isotrope.
Vecteur euclidien
En mathématiques, et plus précisément en géométrie euclidienne, un vecteur euclidien est un objet géométrique possédant une direction, un sens et une norme. On l'utilise par exemple en physique et en ingénierie pour modéliser une force. On parle aussi parfois de vecteur géométrique dans le plan euclidien (deux dimensions) et de vecteur spatial dans l'espace à trois dimensions. Vecteur#HistoireVecteur En physique et en ingénierie, on travaille souvent dans l'espace euclidien.
Afficher plus
Publications associées (50)

The ABCD of topological recursion

Nicolas Gerson Orantin

Kontsevich and Soibelman reformulated and slightly generalised the topological recursion of [43], seeing it as a quantisation of certain quadratic Lagrangians in T*V for some vector space V. KS topological recursion is a procedure which takes as initial da ...
San Diego2024

Get the Best of Both Worlds: Improving Accuracy and Transferability by Grassmann Class Representation

Haoqi Wang, Zhigang Li

We generalize the class vectors found in neural networks to linear subspaces (i.e., points in the Grassmann manifold) and show that the Grassmann Class Representation (GCR) enables simultaneous improvement in accuracy and feature transferability. In GCR, e ...
Ieee Computer Soc2023

Short homology bases for hyperelliptic hyperbolic surfaces

Given a hyperelliptic hyperbolic surface S of genus g >= 2, we find bounds on the lengths of homologically independent loops on S. As a consequence, we show that for any lambda is an element of (0, 1) there exists a constant N(lambda) such that every such ...
Jerusalem2023
Afficher plus
MOOCs associés (18)
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 1)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Algèbre Linéaire (Partie 2)
Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.
Afficher plus