|
|
Название: |
The euclidean algorithm in dimension n |
|
| Автор: |
Pottier L. (Загрузил Denis aka Rock Lee) |
| Категория: |
Информатика. Компьютеры
|
| Дата добавления: |
23.02.2009 |
| Скачиваний: |
21 |
| Рейтинг: |
|
| Описание: |
Introduction
Definition:
We present in this paper an algorithm which is a natural extension in dimension n of the Euclidean algorithm computing the greatest common divisor of two integers.
Let H be a sub-group of Zn, given by a system of generators. This algorithm computes the union of bases of all monoids obtained as intersection of H with the 2" orthants of Zn.
As a consequence, this algorithm can be used for example to compute minimal solutions of linear Diophantine systems, the basis of the monoid of integer points of a rational sim-plicial convex cone (called the Hilbert basis of the monoid), the Hilbert serie of a graded algebra, or integer points of a rational simplex.
This is a completion algorithm, i.e. similar to Buchberger algorithm (Grobner bases), and to Knuth-Bendix algorithm (canonical rewriting systems), also parent with the Euclide algorithm.
In dimension 2, it is different of the Gaussian algorithm (see for example [3]).
The Euclide algorithm in Z
The Euclide algorithm makes successive Euclidean divisions :
«i = qiu2 + аз, в2 = дгаз + й4, ,... ,an-i = qn-io,n
giving finally the gcd an of a,\ and аг-
More generally, given gi,... ,gn generating a sub-group H of Z, divide them with each other, replacing them by remainders of divisions, while it is possible. Then we obtain a basis of H, i.e. the gcd of the дг. Remark that this gcd is, in absolute value, a basis of the monoid H П N.
The Euclide algorithm appears then as a completion algorithm, as Buchberger algorithm, which makes divisions on multivariate polynomials.
Generalization to Zn
Naturally, let us generalize the Euclidean division to vectors of Zn :
Permission to make digital/hard copies of all or part of this material for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage, the copyright notice, the title of the publication and its date appear, and notice is given that copyright is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires specific permission and/or fee. ISSAC'96, Zurich, Switzerland; ©1996 ACM 0-89791-796-0/96/07. ..$3.50
a non zero vector v divides a vector v' iff for all i £ [1; n], Viv'i > 0 and \vi\ < \v't\.
The remainder of the division of v' by v is v' — qv, where q is the greatest natural number such that qv divides v' if v divides t/, else q = 0.
Note that the remainder is in the same orthant of Zn than v', and also than v if q is not zero.
The remainder R{v, F) of the division of a vector v by a family F of vectors is obtained by successive divisions by vectors of F or by their opposites. This remainder cannot be divided by any vector of F U — F but it is not unique in general, and depends on the order in which vectors of F are used.
In other words, the division by F is not a confluent relation in general. To make it confluent, it is necessary to complete F, according to the principle shared by algorithms of Buchberger and Knuth-Bendix.
The Euclide algorithm in dimension n
From a generating system G of a sub-group H of Zn, we build incrementally a family F of vectors in H, by adding at each step the non zero remainders of divisions by F of sums and differences of vectors of F (sums and differences are analog to S-polynomials of Buchberger and critical pairs of Knuth-Bendix). A last step divides vectors between them.
- Procedure Completion(G)
- F:=GU-G
- SD := {v + v'\v, v' € F} - {0}
- While SD ф 0
let veSD
SD := SD - {v, -v]
v:=R(v,F)
if v ф 0 then
SD := SD U {г/ + v\v' € F} U {v1 ~ v\v' G F}
F := F\J{v,-v}
- Return F
- Procedure Reduction(F)
- While there exists v and v in F, not equal, v' dividing v
- F:=F-{v, -v} U {R(v, {„'}), -Д(„, {„'})}
- Return F
40 |
|
|
|
