9512.net
甜梦文库
当前位置:首页 >> >>

A New Efficient Algorithm for Computing Grbner bases (F4


A new ef?cient algorithm for computing Gr¨ bner bases ( o
Jean-Charles Faug` re e LIP6/CNRS Universit? Paris VI e case 168, 4 pl. Jussieu, F-75252 Paris Cedex 05 E-mail: jcf@posso.lip6.fr January 20, 1999
1

Abstract This paper introduces a new ef?cient algorithm for computing Gr¨ bner bases. To avoid o as much as possible intermediate computation, the algorithm computes successive truncated Gr¨ bner bases and it replaces the classical polynomial reduction found in the Buchberger o algorithm by the simultaneous reduction of several polynomials. This powerful reduction mechanism is achieved by means of a symbolic precomputation and by extensive use of sparse linear algebra methods. Current techniques in linear algebra used in Computer Algebra are reviewed together with other methods coming from the numerical ?eld. Some previously untractable problems (Cyclic 9) are presented as well as an empirical comparison of a ?rst implementation of this algorithm with other well known programs. This comparison pays careful attention to methodology issues. All the benchmarks and CPU times used in this paper are frequently updated and available on a Web page. Even though the new algorithm does not improve the worst case complexity it is several times faster than previous implementations both for integers and modulo computations.
?

1 Introduction
In view of the progress already achieved and the promising potential of current and planned algorithms, polynomial solving could become one of the more attractive application of Computer Algebra: practical problems can be solved, the algorithms are competitive with numerical methods. The main conclusion to be drawn from practice and experience of solving polynomial systems coming from various ?elds (industrial [Fau98b] problems, pure mathematics [Fro96]) is the following: ?rst of all, even though the computation of a Gr¨ bner basis is a crucial point it o must be emphasized that it is only one step in the full solving process (change of ordering, triangular systems, real or numerical roots are complementary tools); secondly classical Buchberger algorithms [Buc65, Buc70, Buc85] must be improved since even the best implementations often do not succeed to compute Gr¨ bner bases from big problems. This paper is concerned with o describing a new algorithm (whose name is ) for computing Gr¨ bner basis. Even if the algoo rithm works for any admissible ordering, the algorithm has been designed to be ef?cient for a degree reverse lexicographical ordering (DRL); computing ef?ciently a lexicographical Gr¨ bner o basis from an already computed Gr¨ bner basis being the task of another algorithm. Paradoxio cally, if the Buchberger algorithm without optimizations is very simple to describe it becomes much harder to understand how to improve a real implementation. By and large, however, it may
1

Work partially supported by EEC project FRISCO LTR 21.024.

1

? ?

)

¤ ?

¤ ?

eventually be possible to suggest two improvements: since of the times is spent computing zero it would be useful to have more powerful criterion to remove useless critical pairs [Buc79] (a powerful theoretical criteria exists but it is too costly); this crucial aspect of the problem is not studied in this paper, but is implemented in another algorithm ( [Fau98a]). The second improvement is concerned with strategies: during a Gr¨ bner computation, several choices can be o made (select a critical pair, choose a reductor) and even if strategies have been proposed ([Gio91] or even [Ger95]) the heuristics which they rely on could not be satisfactorily explained. So it is dif?cult to be convinced that they are optimal optimizations. Another bad consequence is that it is very dif?cult to (massively) parallelize the Buchberger algorithm because the sugar (for instance) strategy imposes a strong sequential ordering. The primary objective of this paper is to propose a more powerful reduction algorithm. For that purpose we will reduce simultaneously several polynomials by a list of polynomials by using linear algebra techniques which ensure a global view of the process. The plan of the paper is as follows. The main Section 2 is devoted to presenting the new algorithm. This section has been divided into several parts: ?rst (2.1), we review the necessary mathematical notations (we make the choice to use the same notations as in the book [Bec93]) and in 2.2 we establish the link between linear algebra (matrices) and polynomial algebra. Then we present (2.3) a basic version of the algorithm without any criteria to eliminate useless pairs. A improved version of the algorithm including the Buchberger criteria is then given in 2.4. We close this section in 2.5 by motivating the choice of a good selection strategy (it seems that selecting all critical pairs with a minimal exponent is a good strategy). Since the algorithm relies heavily on linear algebra, Section 3 contains a short survey of linear algebra techniques we have implemented. A ?rst version of this algorithm has been implemented in C in a new small system called FGb (for Fast Gb). In Section 4 we report an experimental evaluation of this ?rst implementation. The best Gr¨ bner bases programs are compared on a set of well known o benchmarks and industrial problems. Finally, in Section 5 we outline the main features of the algorithm along with a list of possible related works and open issues. The name of this algorithm is simply algorithm number . In the rest of this paper stands for this algorithm.
¤ ?
?

2 Description of the
2.1 Standard notations

algorithm

We use the notations of [Bec93] for basic de?nitions: is the ground ring, is the polynomial ring. We denote by , or simply by , the set of all terms in these variables. We choose an admissible ordering on . If , then the total degree of is de?ned as . Now let , , so that (where are elements of ). Then we de?ne the set of monomials of as . The set of terms of is . The total degree of is de?ned as . We de?ne the head term , the 2
§  ?      ? ?? 6 ? ¨1  0    )      ? )  2 5  @ ? " 9 ¨1 ¤  !  ? ¨ 0 § ?? § ?? ?   ? ¤ ¤ ¤ 6 ?  !  ? "  ¨ ¨1 0   )      ? )  2 5  ?   ?   )      ? )  2 4  6    )      ? )  2 ' ) ¤   ?      ? ?  0  ?  !  ? ('   " &  5 ¨ ¨ ?   ? 4   % $ # 4     % $ # 0   3 ¨  ? 8 0   !  ? 0 7   ¨  0 0  % $ # ?   ?   )      ? )  2    0  0   3 & ? ¨ ¨1 0 0

?

? ? ?

?

? ?

head monomial , and the head coef?cient of w.r.t. as follows: , , and the coef?cient of . If is a subset of we can extend the de?nition , and ; denotes the ideal generated by . Let with , and let be a ?nite subset of . Then we say that
 ¨ 

.
¨§

is the re?exive-transitive closure of
¤

.

2.2 Linear algebra and polynomials.
De?nition 2.1 By convention if is a matrix, is th element of the th row of . If an ordered set of terms, let be the canonical basis of , we consider the linear map (where is the submodule of generated by ) such that . The reciprocal function will be denoted by . The application allows to interpret vectos of as polynomials. We note by a matrix with such an interpretation.
7 3

):
( 
    



'& ' E 

E

We note

the matrix

. 3



# $ HG F

¨



#

E

7     

7

B

% 

¨

¤

B

¨

)

 §

(? D

  §

3

)? #  Q $ P I

¨

)

7 '& ' E



)



 R 5& D 

3 

D



@"A

where nomials and
D
  $

is the -th row of (an element of ). Conversely, if is a list of polyan ordered set of terms we can construct an matrix (where ,

6 ? 4

C

6



    

B

1

¨

)5

 

)



3 

@ " A 6 5 9

4

¨

7

% 



0

 

3 



 @"

0

 

De?nition 2.2 If the set of polynomials:
¤ 3 

is a

matrix with such an interpretation, then we can construct

1

¤

¤

 

¤



§ ??

)





 

¤

¤

0 

65 9











0

 

7 2

#

3 



0 

(

$  §

1&3 3 3 & ?

'& '

3

658

0

('

 



'

2

¤







 

0 

7

1

0 

% 



¤





¨§



7 2



658 7

¤

3

#



¤ $ 

65 4

0

The S-polynomial of
¨ 

and

is de?ned as





¤

@

9

¤

¨§

0

§ ??

¤

"

¤



is top reducible modulo
 0  @

if there exists

such that

¤

¨§

0

§ ??

¤

"

¤



is reducible modulo

if there exists

such that

¤

¨? §

0

§ ??

¤

"

¤

is reducible modulo if there exists
?

such that

. . and



"

?

¤

¨? §

0

¤

¨§

0



'

2

¨



'

 

§

¤

¤

reduces to

modulo

(notation

), if

for some

?



8

?     ?    §

1

 0 

65 4

     ? ?

#" ?

0

¤

¨



¨! §

¤

and
0

where is the coef?cient of in . .

?



  



"





0 



"





¤

¨? §

0

reduces to modulo (notation
? ¤

), if

,

such that

6

¨

?



"

0 

0 5

@

9



0 

?

?

9 4



0 

¨

?


? ? ?

9



§ ??

9

¤

6

?

0

"

0 5



0 



0 

?

9

¨

@



9 4

0 

¨

?

9 

?

?

@

9

  

? ? ?

0 

?

3  ? 8 ¨1 6

?

?

7

"



¨

0 

0 5

§ ??

 0 

?

 0 

¤

9

?

"

 4

9

? ¤

  ¨

 0



0 

?
¨ 9 0 0 0 0 0

HG F

§ ??

  ? 8 

0

?

?

?

?

?

?

?

¨

¤

65 9



0

7

7 

. . .
0 0 ¨ 3

. . .

. . .

. . .

De?nition 2.3 Let be a matrix, and new variables. Then is a set of equations, so we can compute a reduced Gr¨ bner basis of for a o lexicographical ordering such that . From this basis we can reconstruct a matrix . We called the (unique) row echelon form1 of . We say also that is a row echelon basis of .
¨

where denotes a possibly non zero element. In the case of polynomials we have a similar de?nition:


Elementary properties of row echelon matrices are summarized by the following theorem:


1

In some computer algebra system, this is the only way to compute a row echelon form !

4

%



?

@

9

"1



¤



@



9 5



3   @ "

?



 ? C ?

"

¤$

¤

¨

¨

¨

& ?



?

,

. We de?ne





3 

 @"

¤

¨

?

§

1 

     ?

?

¨



?

7

3

% 

Theorem 2.1 Let be a the row echelon form of
3

matrix, and

new variables,

? !



E



E



?

    # 5&   § ?? ¤

E

¨

7

E



 

6

?

"

 

0 5

?

De?nition 2.4 Let to be
 0   

be a ?nite subset of and an admissible ordering. We de?ne , and the row echelon form of . We say that is the row echelon form of w.r.t. .



?

?

?

. . .

%

%

?

%

...

?

?

?

        ?

1

§

%

%

1 

3

      ?
     ?



?

?

?



%

%

%

?

?



¨

¤

% % % % %


B

?

?

?

?





1  

?

% % % % %



  

  

? 

% %

% ? ? % ? ? ? ? ? % ?
  

? ?

B

?

?

?

?







§ ? ?'

? ?'

?



¨'

?'

? 

'

B

?

?

?

?



0 0 0 7

(1)

?

? ? ? ? ? ? ? ? ? ?



% 
§R ' R'


?'

'

'

0

0

0

0

0

3

¨

3

3

? !

?

E   @ "

 4  



  &   %





A" "

3 

E

¤

 @"
¨ ¨

3 3 ?

¤

(2)

,

For any subset of such that and , then is a triangular basis of the module generated by . That is to say, for all there exist elements of and elements of such that , and . Proof Since the head terms of are pairwise distinct, is linearly independent. We claim that it is also a generating system of . Suppose for a contradiction that there exists such that . By de?nition of a Gr¨ bner basis, o , consequently is top
? 0

It is well known that during the execution of the Buchberger algorithm, one has a lot of choices:
?

select a critical pair in the list of critical pairs. choose one reductor among a list of reductors when reducing a polynomial by a list of polynomials.

Buchberger[Buc65] proves that these choices are not important for the correctness of the algorithm, but it is well known that these choices are crucial for the total time computation. Moreover the best strategies [Gio91] inspect only the leading terms of the polynomials to make a choice. Consider the case where all the input polynomials have the same leading term. In that case, all the critical pairs are equal and it is not possible to take a decision. In some sense this problem can be corrected in a simple and surprising way: we make no choice. More precisely instead of choosing one critical pair at each step, we select a subset of critical pairs at the same time. So, in fact, we are delaying the necessary choices in a second step of the algorithm, the linear algebra part of the algorithm
§ ?? ¤

5

%



 

%

'

§ ??

0 

@

¤

9  

%

'

0 



@

9 

7 2

#

¨



' 0 '



'

@

0 

9

'

0 

De?nition 2.5 A critical pair of two polynomials such that
 ' 0 '   @ 9 ¨

is an element of

?

¨

''



'

7 2

0 

#

'

¨



'

 

0 

'

'

 

0 

''

'

0 

7 2

A)

#

8





¨

?

2.3 The

algorithm



0 

@

9

08

¨

"

 ?

¤

0

. For all ,
@ 9

¨



?

@

9

¨



&

?

 ¤

@

?

¤

9

For all subset of such that size( )=size( ) and is a triangular basis of the module generated by elements of and elements of such that .

& ¨  0

, then there exist and

?

?

%



?

@

9

?

"1

@



9

¤

@



9 5

?

?

§ &

?

¤

¨

Corollary 2.1 Let be a ?nite subset of form of w.r.t. . We de?ne
¤$
¨

and

an admissible ordering, and

the row echelon





@

9

¨



&

?

@

9

reducible modulo top-reducible modulo . This is a contradiction. We can transpose immediately the theorem for polynomials:
?

, so that

08

 ¤

¤

"





? 0

0

?

&

@

¨

9

0

?

¨



&

?

?

@

9

?

?

 ¨! §

 

? 0

?





@

?

?

08

9  ? ? @

   ¤
9

)

¨

§

¨



& ? 



§ &

¤

?

 ?

¤

@

? ?

"

  ¤

9

)

08

?



@



08

?

9

?





?

@

  ¤



9

 ¤

 

¨

?

¤ 

@

?



?

? 

9

?

¨1

&

@

 ?

&

?

?

¤

? 0

?

9

  ¤

 0 



¨!? §

&

@

@

7

?

7 2

9



9

08 '
0

?

0 

#



¨

?

&



'

?


 ?

?

"

0 

 ¤

¤

 

?

A)

?

0

¨

@

@



8

?

¤ 

?

9 9

is

,



We have now the tools needed to present the basic version of our algorithm. All the matrices occuring in following algorithms are the representation of a list of polynomials through the set of all their terms, as explained in De?nition 2.2.
P F F
? ? §   ? ¨ § ?

return

We have now to describe the main function of our algorithm, that is to say the consruction of the “matrix” . This subalgorithm can be viewed as an usual reduction of all the considered polynomials if we replace the standard arithmetic by: let , then , , and . So this is really a symbolic preprocessing. 6
B
¨

%



?

Remark 2.1 By Lemma 2.1, we will see that an equivalent (but slower) de?nition of be .
%
?



?

¤

"

%

¨1

?  ?

¨1

?

$ 

$

¤ G

B

I

¨

?

# $

?

# #G



?

"

P

?

05

?

?

¨

?

?

"





?

return




?

Reduction to Row Echelon Form of
%




?





?



Symbolic Preprocessing

"1  0  

?

§ ??

¤

Output: a ?nite subset of
¨ ¨

(possibly an empty set). w.r.t.

§ ??

¤



P

?

$

F

 ?

 5 ?

F

$

?

G

? ¨ §

"

0

$

?

Input:
7 ?

§ ??

¤

%





P

?

$

F

 ?

F

$

?

G

? ¨ §

?

0

¨

?

Reduction

§ ??

¤

We have to extend the reduction of a polynomial modulo a subset of a subset of modulo another subset of :
§ ?? ¤ § ?? ¤

6

?

"

¤

5



¤



?



A)

8

6



?

4

4

?

?

?



"

¨

¨

7

7

?

?

for
?

do











?

?



¤)

 ?

¤



?

!

")





 2







 ?  ??

 0 ?



B

C 

  



¤

?

¨1

?

¨

¨

¨

?

$

7

7

¨



while
7 ?


do

6

¤

¨1

0

?



) @

§ ??

?

? ¨

¤

Output: a ?nite subset of , and
7 ?
"

.

, to the reduction of



¨1

#

G 

¨1



#

 

Input:
?

? §  ?



I

?

F



 A)

8

  )

?

¨



 A)

§ ??

8

 )

¤



?

?

$

?

¤

 ?

PG ? I

 0 5

$



?

?

G

¤

 0 

¨

7

A)





?

8

? ?

Algorithm

could



' 0  '   ¨ 7  '& ' ?   ? ¤ ) ¤ '& ' ?  ¤ ? ?  ' 0  ' 0  A ) 8 


De?nition 2.6 We say that the degree of the critical pair . We de?ne the two projections and If then we note the evaluated product .
? 
 ¨  ' 0 

,

, is .

'& ' ?
'



¨

7



'& ' ? 

 0 ?

?

 

?

  

?¤ ? ?

§ ??

¤

?

%







7

7

?



¨

4

'& ' 7


?  7 ?

B

"

 ?



¨

¨

¨

7

?





7 2

7



7

¨

?

# ¤? ?
?



%

 



?

Symbolic Preprocessing
§ ?? ¤

return F

Remark 2.3 The symbolic preprocessing is very ef?cient since its complexity is linear in the size of its outout if ) is smaller than the ?nal size of tf which is usually the case.
%

?

Proof Let the set computed by the algorithm Symbolic Preprocessing . Assume for a contradiction that such that . Hence divides for some . So is in and is top reducible by , hence is inserted in by Symbolic Preprocessing (or another product with the same head term). This . contradicts the fact that The following lemma is useful to proof the correctness of the algorithm.
%


Proof Apply the Corollary 2.1 to the set generated by Symbolic Preprocessing . Clearly is a subset of , but it is obvious that is a subset of , so that is a subset of . Hence any ful?lling the hypothesis of Theorem 2.1 is a subset of . This conclude the proof of the lemma since the module generated by is a submodule of the module generated by .
7

where is the reduction which is used in Buchberger algorithm. The reason for that is that the result of depends on many choices (strategies). 7
7

A" ?#

8

7

A" §

?

¨!? §

0

A" ?#

§ ??

8

¤

Remark 2.4 Let
? ¨1 
?

be a ?nite subset of
A" §
7

. It is possible that

but that



?





?

? ?

?



?





?

?



? ?

?

§

¤

7

?

A" ?#

§



?

?

8

&

?



7

?

? ?

 § ¨ ?§ ? !

A" §

?

?

?

0

generated by ,
?

§

¤

0

?¤ ? ?



?



? ?

?

§ ??

¤

Lemma 2.2 Let
")
 2

be ?nite subset of , be the image by of a ?nite subset of . Then is a subset of . Moreover for all in the
 ?

?

¤   ? ?¤ ?

and module



?



¤



@

?

¤

9



?



 



?¤ ? ?

@

 

9 

?

? ?



@

"1

9 



?

? ?



@

"

9





?



?

?





@

"

?

9

§

?

?

§ ??

¨





? 

?



¤







?

"1







?

?









?

?







?

"



!



?

")

?







 2

Lemma 2.1 Let and
?
?

be ?nite subset of , . Then for all

be the image by ,

of a ?nite subset of .

?



Remark 2.2 It seems that the initial values of Done should be function the result is in fact the same with less iterations.
?





?

"



?

7

?

"

0

6

0

 0 



?

@

7 4

9

 ? ?



?

?

?

?

!

?

)

7

?

¨

¨

7

?

?

¤

?

7

?

7

if

top reducible modulo then for some

?

?

!

"

C

6



7 4

?

@

an element of
?

?

?

?

!

"

!

"

?

¨1



¨

7

?

?

@

while
"
?
7

do

§ ??

¤

Output: a ?nite subset of
6



P

?

$

F

?

 ?

"

F



$

?

0    5



G

?

? ¨ §

?

@

0

9

?

Input:

.

§ ??

¤

%





P

?

$

F

 ?

F

$

?

G

? ¨ §

?



?

¨

 4

7
!

?

¨

"

?



¨ ¤

!

?



7 ¤ "


?

¨

? ?

?

? §
 0 

and some

but in all application of this



?
¤

?

Proof Termination: Assume for a contradiction that the while-loop does not terminate. We see of natural numbers such that for all . Let that there exists an ascending sequence
B  )
  ' § ??

for all such that . The ?rst claim is an immediate consequence of the ?rst part of Lemma 2.2. For the second one, if , this means that has been selected in a previous step (say ) by the function . Hence and are in , so is an element of the -module generated by hence by Lemma 2.2 . Remark 2.5 If In that case the for all then the algorithm is the Buchberger algorithm. function correspond to the selection strategy in the Buchberger algorithm.
¤ ?

¨1 ¨ 

Example 2.1 One might wonder why in the proof of the termination of the algorithm we consider only one element of and not the whole . If for a lexicographical ordering, and identity, we ?nd and so that . So contrarily to Buchberger Algorithm this not true that after each operation , we have .

In order to obtain an ef?cient algorithm we need to insert into the previous algorithm the Buchberger Criteria. Since it is not the subject of this paper to improve the Buchberger Criteria we will use a standard implementation of these criteria such as the Gebauer and Moller installation [GM88]: Buchberger Criteria
FG¤
#

§ ??

¤

Output: a ?nite subset of

and a list of critical pairs.

8

§ ??

¤



P F #G

§ " ¤ §

IG ?G# I



P   

§ ??

?

¤

$

F

"

$

?

?

G

? ¨ §

Input:

 ?

  "

§

?

$ $

F FGF

§  ¤ §

$ #

G

#

? § ?

G

§ " ¤ §

§ ??

¤

IG ?G# I

0

"

D

?



P

?

$

?

? §

$

F

#

 ?

"

F



Speci?cation:
$



?



D

?





D



?

?

2.4 Buchberger criteria. Improved

algorithms

Bec93

§

?

§

?

%

?

¨!? §

%



? ¤

4

¤

 ?

 ?

%



¨

¤ A )

 

? ¤

¨



?

 ?

?

¤

0 

8

¤ # " ? 



B

?



?

@

6 

¤

? ?

9 

¤

0  ? 0 

 

? ?

¨

?



?





0 

? ? ?

A)

@

?

B

&

9 

8

'

?



?



? ? ?

¤

 

?

?



%

¤

?

0 

'

?

"1

?

  ?

¨

?

0 

6

?

? 0?

? ¤

?

A)



 ?

?

8

@

¨

?  ?

¤



9 

4

 

?

? ?

?

?

0  ? 0 

 ?  8



'



?

?



? ? ?

¤



A)

§ ??

? ¤

#

 ? ?   &

?

8

"1

 ?

6

¤



'

%

¤ # " ? 

¨

6

§

?

4

4

6

7

? ¤



?



¨

¨

?

4

?

 ?

B

¨§

 

?

?

¨

¤

¨? § !

¨



 

4



? ?

 

?

?





#

¨§

 ?

¨

'

? ¤

?

7

 

@



?

 ?



? 9 

?





?

¤ # " ? 

 ? ?



? ?

?

? ¤?

 

?

G

)

? ¨ § 

?

? ¤  ?

¨1

?  ?

?

  ?

"

?

?







¤

? ¤

"



%

 ?  

¨

 ?

'

6



?

say that
¨

(hence can be any element in ). Let be for and . By Lemma 2.1 we have . This contradicts the fact that is noetherian. Correctness: We have . We claim that the following are loop invariants of the is a ?nite subset of such that , and while-loop:
 ? 

)

?

?



¨1

?  ?



§ ??

¤





'

?

¤ ?

Theorem 2.2 The algorithm .


computes a Gr¨ bner basis o

in

such that

?

?

and



? ? ?

B

¨

 

¤

?& ?

?

 %



?

?

¤ 

7 2







? ?
?

? 

#

?

?

In the previous version of the algorithm we used only some rows of the reduced matrix (the sets ), rejecting the rows which were already in the original matrix(the sets ). In the new version of the algorithm we keep these useless rows, and we try to replace some products occuring in the rows of the “matrix” by a new “equivalent” product with . This is the task of the function . The third argument of is the list of all the already computed matrices. A complete description of this function will be given below.
?

Improved Algorithm


Input:

return

The new Reduction function is identical to the previous version except that there is a new argument and that it returns also the result of Symbolic Preprocessing: Reduction Input:



?





?

return

9



?

Reduction to Row Echelon Form of
%






?





?



Symbolic Preprocessing

"1  0  

§

?

§ ??

¤

Output: two ?nite subsets of
¨ ¨

.

w.r.t.

§ ??

¤



P

?

$

F

 ?

F

$

?G ? ¨

FG  ?

§ ??

$

#

¤

$

§ ??

 ?

%



?

¤







?







P



P

&

?

 &333& ? (    ?  F  ?F $ ?G ? ¨

?

?

$

 ?  8

$

F

 ?

 5 ?

? ? ?

F

$

?G ? ¨ §

¨

"

7



¨

§

?

0



$



?

"

? 

§





¨

?

?

for


do

  ?

&

 &333& ?

(





'

?



?









 ?





?

!

¤)

")

 2

¤

?

?



?



¤









¨

 0 ?



B

7

C 

  







?

¨1

?

?

¨

¨

?



7

¨



while
7 ?


do

§ ??

 0 

?

¨

¤

7 ?

Output: a ?nite subset of and and while do

 ¨

.

 §

Bec93

0



 $

7

? ? " ?

?

7



?

¨1

PI P

§ ??

#

7

G 

?

¤

?



F #G

%

¨1

§ "



? 0



#

¨§

$



 

 ? ?

?

7

  § ??

I

? § ?

$

¤

$

F

¤   ?

?





?G

I

IG

?

?

 ?

?

F

 



 A)

" )



?  ?G #

" 

8

 )

P

?

P

? ?G #

%

%

¤ § #

§ ??

?

$ %

P

¨

¤

%

#

¤ §



$

%

 A)

 

$

§ ??



 ?

I

?

8

7

? ¤ 

  )

$

¤

$G¤ " ?G ?

?G¤ §G #



P

P



?

? # § "

?

$



F

$

?

?

?G #

 ?

PG? I

 ?  8

?

$

F

I

 ?

$

$

? ? §    ? ?G ? ¨ § ??

? ? ?

 ?

$G¤ " ?

$

? §

?  A)

6

7

%

0 4

#

?



¨

GF



"

C ?

7

G?

?

¨1





 ? ?

0



¨

?

7

¨

7

¨







7

7

?  7 ?

7

 ? 

7

 ?

?

¨

?

?





0





7

?

?



?

@

9

¨



&

?

@

9

' ?



0





@

9

¨

 ? 0 

@

9

(

¨





0



 

@

9

 ?



0 

@

9

¨





0





@

9

Proof Termination: constructs a sequence such that , and except perhaps for the last step. is noetherian, this implies that the algorithm stops after steps. Correctness: The ?rst part is obvious since so that . The proof is by induction on the step number. So we suppose , and , for some with . The set can be supplemented by other elements of such that and
' ?
"
? 0

0

¨



0



¨









0 







§
 0

?

  ?#  §
 @ 9 ¨

?"

7

§ 

¤ @

" 9

A

¤

"

¤

¨1

?

?

&

 &333& ?

(

   ?  

§



0  



? B



§



?  ?? ?



$G¤ " ?G ?



¨1



0





@

9

¨



?

@

9

? '

"



' ?


' ?

"

0





?



( ? B



§ ??

¤



P

?

$

F

 ?

?

6
?

7 4

?

?

!

"

?

 6

?

?

@

9

¨

7
4

?

"



0 

7  5

 

§ ??

¤



P

?

$

F

 ?

F

$

?G ? ¨

FG  ?

$

#

$

 ?
§ ??

 ¤ 

?
 

&

§ ??

¤

%

P

?

$

F

 ?

F

$

?G ? ¨ §

?

? 

Symbolic Preprocessing



Input:

P

 &333& ? (    ?  F  ?F $ ?G ? ¨ ?
$

Output: a ?nite subset of

§ ??

§

 0  ¤

7 

$G¤ " ?

G ?
¨

?¤ ? ?

§

§

while

?

an element of

!

"

C



?

@

?
¨1

¨

7

?

!

"

!

"



?

@

?

if

top reducible modulo then for some

do

.

and some



"

?

Output: a non evaluated product, i.e. an element of for list of divisors of do if ( ) such that then is the row echelon form of w.r.t. there exists a (unique) such that if then return else return return

§ ??

¤

%



F

$

?G ? ¨

FG  ?

$

#

$

 ?



?
?

&

¨ "  "

?#

$

? §

  

6   7

§

 0  ? "

7  0

$G¤ " ?G ?



?¤ ? ?
@

4 9

? ?

?
7

¨

7

?

 0 



¨

7 7

?

Input:

¤ §

G

P

? $¤

 &333& ? (    ?  P " § § ?? ¤

Lemma 2.3 If if denotes

return F

is the result of there exist .

then , and



 ? 0

?  



 0   

$G¤ " ?G ?

 ? 0  ?  

with

10
6 0 4 ¨

&

?

' ?

"

0



??

¨

? 

B

¨ 

A

 ?



0 ?





@

9

¨

 ?



0

? ?? ?

@

9

A









?





$ G¤ " ?G ?



0



 

@

9





A

@

9

A



? 0?  ¤

¨

0 

  §

.

. Moreover such that

' ? (
"

§
0

$ G¤ " ?G ?

?

7

!

"

¨

7

?

?

Remark 2.6 Experimental observation establishes that the effect of is to return, in of the cases, a product where is a variable (and frequently the product ). This technique is very similar to the FGLM algoritm for computing normal forms by using matrix multiplications. For the veri?cation of the improved version of the algorithm we recall the following de?nition and theorem([Bec93], p. 219): De?nition 2.7 Let be a ?nite subset of , , and . Suppose with monomials and not necessarily pairwise different . Then we say that this is a -representation of w.r.t. , if for all .
" ¨ 0  "  § ?? ¤ " 0 ¨1 ? § ?? ¤ ? ? ? 

11

§

?& ?

7 2

#



    ?

A

@

9  

A

@

9  ? 8

7

¨

? 

has a -representation for
? 

?& ?

7 2

#



  ?

A

@

9  

A

@

9  ? 8

7





? ?

?



?

"

?

AA

with
 ?

such that

. Hence

¨

 ?

¤?



@

9

¨

 ? ?

 ?

? ¤ ??  § ? ¤ ?

¤ ??  

@

9







? ¤?



§

?

?

A

¤?









?

0  ? 0 

 ?

¤ ?  § ?? ¤ ??   ?? ¤ ??  § ?? ¤ ?? 



#" ?

?



'

¤





'

A

 

¨

¨

¨

%

 ?

? ¤ ??  

0

)# ?

§

 ?

? ¤

7

 ? ?

@

) "

  ? ?  §

9

¤ # " ? 

¨



 ? '

? ¤?

¤

 ?   '

Proof Let
9 ¨

be

. By Lemma 2.3 we have so that (we suppose that all the polynomial are monics):

?& ?

7 2

#



? 

?

? 

§



? ¤

 ?

¤ # " ? 

Then the -polynomial
"

has a -representation w.r.t.

with

 

?

0 

@

9   ? 0 

@

9 

7 2

#





?





?

0  ? 0 



@



? ¤

#" ?

(iv)

has a -representation w.r.t.





B

¨

)

 



'

¤



'

 

$G¤ " ?

G?

?¤ ? ?

¨

'

0

(iii)

for

. with . .

 ?

 ?



B § ?

§

    

B

¨

?

?

   ? 

(ii)

for

(

being as usual the row echelon of

? %



?¤ ? ?

?

 ?

(i)

is the image by

of a ?nite subset of

 ?

?

&





&333& ?

"

?   ?   ?& ?   ?

(

¨

7 2

#

§ ??

¤



? ¤?

  ?

¤

 ?  

?& ?

7 2

#

¨

?



Theorem 2.4 Let ,
? ¤
 ?

be a ?nite subset of

, with

, where is ?nite subset of such that the following hold:

)

  ?

¤

@

? ¤

9 

 ?

7 2

¤

#

Theorem 2.3 Let be a ?nite subset of with . Assume that for all either equals zero or it has a -representation w.r.t. for some . Then is a Gr¨ bner basis. o
 
?

?



?

?

 ? 



'

?

?

'

¨1

7 

? )

@

$ G¤ " ?G ?



9



?





 ¤

0

@

 ? 0 

?



9

"1

"



@

 ? 0 

?

9

'

?



@



A

§

9

§ ??

§ ??

@

9

¤



¤

 ? 0 



"

'

?

@

'

A

7

9



¨

0

¨1

 ?

? )



?

¤

?

¨

'

@

? 

? 0

9

§



?

A? 

 ¤
?

 

?

)

0

?     

§



¤ A )

 ?



? 0 ? 



&

'

? ¤

?'

? )

8

 

¨

¨

 ?

 



?

7 ? ('



? ¤

? 0

?

?& ?



¤ # " ? 

¤ # " ? 

B

¤

that ,
¨

and . Hence .

. We can apply Corollary 2.1 we ?nd , , such and for . By construction of with , consequently and we have
  ' ? 
?

&

?

"

 ¤

¤

"





) 

 

?

@

9  ? ?

)

¨



&

?

§ ??

? B

? ?



7 2

@

¨

&

)
& ¤

0  9 

?

)

,

#

2.5 Selection strategy
The choice of a good selection strategy, that is to say the choice of the function , is very important for the performance of the algorithm. Computing Gr¨ bner bases for a degree ordering is very frequently the most dif?cult step in o the solving process (other steps are elimination or decomposition of the ideal). One reason for with no mathematical structure. We that is that the input of the algorithm is only a subset of want to give some structure to these polynomials at the beginning of the computation: we use the concept of -gr¨ bner bases: o De?nition 2.8 If is the result of the Buchberger algorithm truncated to the degree (that is to say we reject all critical pairs whose total degree (De?nition 2.6) are ), then we call a (truncated) -Gr¨ bner basis of . o The following theorem give a structure to this list when the polynomials are homogenenous.
 
?

An effective Nullstellensatz may give an estimate of ; from a theoretical point of view such an explicit bound for the degrees reduces the problem of ?nding the polynomials to the resolution of a system of linear equations. This reduction to linear algebra of the computation Gr¨ bner bases has been used for a long time for analysing the complexity of Buchberger o algorithm [Laz83]. For practical computation this does not work well since: is often over estimated.
?

the linear system is huge: the matrix which is generated is frequently larger that really needed. the matrix of the linear system has a generalized sylvester structure and solving ef?ciently such a system is not a well known task. 12

?

?

¨





?



?

?

Moreover, there exists a such that for all We note by the number .
 

,

is the Gr¨ bner basis of . o

? ?

  

¤

¤

?

@

?

9  

0 

?

@

9 

?

7 2

#

% $ #



¤

?

 0

for

in

such that

? ?



0  % $ #

?

0

is well de?ned for polynomials
¨! ?§ ? ? ? ?  ?

such that

.

D

0      ? 0

Theorem 2.5 ([Laz83], [Bec93] p. 471) For homogeneous polynomials ner basis “up to degree ” that is to say:
? ¨! ?§
?

,

is a Gr¨ bo

?

 

?

? 

§ ??

¤

?

?

?

?

¨

?



?

% $ #  



¨! ?§

?

?



?

¤

 0 

?

?

"

#" ?



?

?

?

? ? ? ? ? ?

Other algorithms are also closely related to linear algebra [Laz79, Laz81, Att96, Ger95, Lom98]. In fact the Buchberger algorithm and the algorithm give incremental methods to solve this systems. The new algorithm will compute from . Thus the algorithm transforms a mathematical object ( is unique) into another object with a stronger structure. In fact the Buchberger algorithm is also incremental since it computes one polynomial after another but in our case we compute a whole new truncated basis.
¨§
?

Unfortunately Theorem 2.5 is false for non homogeneous polynomials. One solution to overcome this dif?culty is to homogenize the list of polynomials but it is not ef?cient for big systems since parasite solutions are also computed (solutions at in?nity can be of greater dimension); a better method is to consider the sugar degree [Gio91] of each polynomial: we add a “phanof a polynomial is the degree of the tom” homogenization variable and the sugar degree polynomial if all the computations were performed with the additional variable: where

 7     

The weak point of this approach is that contains polynomials with various degrees and that near to the end of the computation . We give now some possible implementation of . These results are not discussed in detail as they will been reported in a more technical paper. The easiest way to implement is to take the identity ! In that case we really reduce all the critical pairs at the same time. The best function we have tested is to take all the critical pairs with a minimal total degree: Sel(P) Input: a list of critical pairs Output: a list of critical pairs
6 

We call this strategy the normal strategy for . If the input polynomials are homogeneous, we already have a Gr¨ bner basis up to degree o and selects exactly all the critical which are needed for computing a Gr¨ bner basis up to degree . o 13
?
 

B § ?

¤ ?





return

?

% $ #

 

?

 ?





?

?

C

? % $ #

?    ?

?

? % $ #

6

?



¨

 

 

"

?

?

  

% $ #

7 2

?

#

% $ # 5

7 2

#

% $ # 4



"

!

?4

)



? 

De?nition 2.10 whose is
? % $ #

is the result of the Buchberger algorithm when we reject all critical pairs . (We replace by is the De?nition 2.8)



?



? % $ #

"



7  % $ #

B

? 

¨



)

De?nition 2.9 For the initial polynomials: , for all polynomials occurring in the computation have the following forms or a term. We de?ne and We say that is the “sugar” of .
¨ 

?  ?

? 

7  ? % $ #





'

0  % $ #

?



?

¨§

? % $ #

 

¨



?

?



?

'

? % $ #  



¨§

0  ? % $ #

?

¤ ?

?

¨§ ?

? % $ # 

?

?

? 8

¨§

7

¨

?

?



?  ?

¨§



?



? % $ #

?

. The is .

 ?



?

7

?



¨

? % $ #

7

¨

7 ?





? ?

2.6 Example
The reader should be aware that it is impossible to fully appreciate the ef?ciency of the algorithm for small examples. We consider the cyclic problem. We choose a total degree reverse lexicographical ordering and the normal strategy.
§

At the beginning and so that . We enter now in Symbolic Preprocessing ; , and , we pick an element in , for instance , but is top reducible by ; we have , and . Since the other elements of are not top reducible by , Symbolic Preprocessing returns . Or in matrix form:
6  6

that is to say and since we have and now . In the next step we have to study , thus and . In Symbolic Preprocessing we ?rst try to simplify and with . We see that and that is the unique polynomial in such that , hence . Now and . We pick wich is reducible by but again we can replace this product by . After several steps we ?nd
6 ¨ 6

14

?

?

?

?

§

2 



?2? ?

?? 

?

8

6 

¨



¤

2 8 

0  2



?

¤ 0 ?

§

? 0

?

??

?

?

¨

8 

 

@

§

?

?

0 

9

0 

2



?

¤

?

? ¤ ¤ ¤ ¤ ¤ ¤ ¤

¨

B

 2

0  2

? § ?? §

?

 4

6



?

§

?

?

?

?

?

?

?

8 4

0 

0 

¨

? ¤ ¤

?

¤

B

?

?

?

?

@

?

0 4

¨

?

?

?

?

9

B §



2

B



?

?

?

¨

? ?

B §

?

?

B

B

0 

?

 ?

B



?



?

?

B

6 

B

?

?

8

¤

B

?

?

?

?

0 

¨

B §

?

B



?

6

?

?

B §

0 

0 

B

B

B

?

?

0 2 

A)

?

6

B

?

?

?

§

8

B

B

?

?

?

?

0 4



0 4



B

?

?

4

?

B

B

?

?

?

¨

2

¨

B

6

?

?

¨

 ? ?

?



B

B

?

?

?

? ?

0 2 

? 

B

?

?

??

¤ 0? ?

B

?

?

?

?

?

? ? ?

?

0  ? 0



B

B

¨

?

?

?

?

?

?

? ? ? ? ? ? ? ?

8

?

?

E

E

the row echelon form of

is

?

?

?

¤

?



8

0 

4

6

2

?

?

?

8 4

 ?

 

 ?

¤

?

?



¨

0 

8



8

''


B

 ?

 4

7 2 ¨ ¨

?

? 0 

#

 ?

@

¨

? % $ #

?

9

?

?

2

?



¨



?

?

?

8

!

!

"

"

6

? ¤ ¤



?

?

¤ 0?

?

2

?

C

?

?

?

?  ?

 ?

6 

4

?

?

¤

?

B

?

?

?

0 

?

8

¨



¤

?

B

B

?

0 

¨

?

¨

A)

?

B

B

?

?

0 

?

?

8



?

B

B

?

?2?





4



  6

B

B

?

?

?

'



¨

8 

 ?

0 

?

B

?

?

?

'

?

2 8

?

0  

8 4



B

B

?

A)



?

? ? ?

¨

8

??


 ?
?

¨

8

!

6

% $ #

?

?

"

¤



0 4

6

E

?



2

?



?



2 

¨

?

§

8

¨

¨

0  2 

 ?

0

??

? 0 4

?

? E

¨

 ? 0 2 4

?

 2

?

¤

0 

?

@

¨

¨



?

9

B § ?2?

?

0

?



?

?

? 

¨

"

§

?

? ?



8 

?

¤

8 

0  2

?

6

8

?

8 4

??

¤ 0?  ¤ 0 ?  ¤

8

? $ G¤ " ?G ?

¨

8

?

¨

¤

?

0?

 ?

"

6 ?

?
¨

We can also change the to be the sugar degree, (see De?nition 2.6). In our experiments, this variant of the algorithm was less ef?cient.

?

¤0?

?

0 4

?
 4

, and . In the next step we have , and we call recursively the function Simplify: . We have . Notice that cannot be simpli?ed, but very often we have only a polynomial multiplied by a variable. After several steps in Symbolic Preprocessing we ?nd and , , , , . Note that the rank of is only . This means that there is a reduction to zero.

2.7 Conclusion
So we have transformed the degree of freedom in the Buchberger algorithm into strategies for ef?ciently solving linear algebra systems. This is easier because we have constructed a matrix (the number of rows in is a little overestimated by the symbolic prediction) and we can decide to begin the reduction of one row before another with a “good reason”. For integer coef?cients it is a major advantage to be able to apply an iterative algorithm on the whole matrix ( -adic method). Some negative aspects are that the matrix is singular and that is often huge. A good compression algorithm for the matrix reduces the storage requirements by a factor greater than (see Section 3.4).
E ? E E E
?

3 Solving sparse linear systems
Compared with naive linear algebra approach we have reduced dramatically the size of matrices which are involved. Despite this reduction, the matrices that we have to solve during the program execution are very big sparse matrices (see p. 22): say to give an idea (the record is for a very sparse matrix). To give a comprehensive review of all useful linear techniques is far beyond the scope of this paper and we give only some references to the original papers. It should be observed that we have to solve sparse matrices in a computer algebra system. It is therefore not surprising that we have to merge techniques coming from sparse linear algebra (possibly designed initially for ?oating point coef?cients) and techniques coming from computer algebra (for big integer computations for instance). But ?rst we establish the link with the main algorithm: 15
? ? ? ? ?



6 ?  ??  ¤ ¤ B § ?2?8 ¨

??

? §

6

0 

¤?

?

0 

?? § ?2?

§

¨

0 



¤

?

??



0 4

? 0

? ? ? ?

0 

¨

¤

?



? 

%

?

??

¨

0



)# ?

8

?

?

¤

0 ? § ?? § ? 2 ¤ ? ? ¤ ??   ? 2 § ? 2 ? ? ? ?

¨

6 

7

6

? ? 0

) "

¤

¤?

? §

0 

¨

?

? ?



? ?? § ? 2 ? ?? 

%

 

?



0 

§

? ? ? ? ?

0 

?

2 

2   

%

0





¨



)# ?

¤

§

??

0 

? ? 0 4

0

2

?

?

7

?

2

? 2 ?

2

) "

¨

¨

¨

¨

¤?



  ? 0 

?

¨

? 0

? 0

¤ ?

0

, ,

,

¤

?

? ¤ ¤ ¤ ¤ ¤ ¤ ¤

?
? ? ? ? ?

B §

B §

B B
¤

?

B §

B
? ? ?

?

B §

B §

B

?



B §

B B
? ?

? ? ? ?

B §

B B
? ?

B
? ? ? ? 

¤

¤

B B
?
? ? ? 0 

?

?

B

?

 4



2

? 2 ?



B

? ? ? ? 6

?  ?2 § ??  ? 2 § ?2? § ¤ ¤ ? ? ? ¤ ?  ¤? 0?  ¤? 0 ?  § 0 2  ? ? 0?  ? 0 4 ?



?

6



¨

? 0

?

¤?

B

?

? ? ? ?

%

?

2

?

¤

0

0

2

§

)# ?

?

?

B

? ? ? ? 



?

§

? ? ? ? ? ? ? ? ?

??

0

7

?2?

?

) "

2 

¨



¤ ?

? ? 0?

? E


?

?

?

2

2 8

 ? 0 4

? ? ? ? ?

§ ?2? §
¨
?

¨

?

0 4

%

¤ ?

2

? ? ? ? ?

?

¨

8

? ?

B

¨ ¨

¨

?

??
§

¤ ?

? 0

0

3.1 Solving a matrix and reduction to row echelon
In the main algorithm we have to reduce (?nd a basis of the image of the correspon?ng linear map) sparse matrices which are singulars and not square. On the other hand, linear algebra techniques are often described for solving linear systems of equations . One way to connect the two approaches is to ?rst extract a square sub matrix and to put the remaining columns into the right hand side. For instance if we want to reduce:
?
¨ 2 ?

We ?rst try to ?nd the rank of the matrix using a fast algorithm mod and we ?nd that the second column is deffective. So we extract a square matrix and a right hand side:
?
?

Hence the system of equation can be rewritten:
?

so we have to solve the linear system
?

and the reduced form of the matrix
?
?

3.2 Solving sparse linear systems
Solving sparse linear systems has been studied for a very long time for numerical computations, there are mainly two types of methods: iterative methods (computing successively if is a matrix) and decomposition methods. The methods wich are useful in our context are the following: 16
'

%

E

¨

?

'

%





A & E   ?

B

?

?

?

E

?

B

?

?

?

? ¤ ¤

8 

?

?

? ? 8

 

§



 ?



2

B



?
? ? ?
¨

?

B

B ? ?

B

8

?

?

¨

?

B B


?

? 
? ?

?

A

2

?

? 0

¤

8

? ?

?

?

?

0

0

?   

? ¤ ¤

?

?

8 ¨ ¨

B





A"

?

?

?

B B

B ? ?
? 

8

B

B







2



?

A ?

B

?

?

?

?



?

? 0

B

B

B

¤
? ?

0 0 8 

?

? ? ?

?

B

?

?

?

§

¨ ¨

¨

?





E


E
?
?



8

? ?

?
2

? ?

B

B ? ?

B

8

? ? ?
8

?

?

? 0

¤

E
0 0

!

%

!

E

3.2.1
?

Iterative solvers


After steps we obtain an exact solution (up to rounding errors). This is the case of conjugate gradient method or the Lanczos algorithm [Mon95] since after steps the result is exact. Another well known iterative algorithm is the Wiedemann algorithm [Wie86, Kal91], which uses the ef?cient Berlekamp and Massey algorithm [L.69] to recover the solution. Note that there exists a more ef?cient version of the Wiedemann algorithm: the Wiedemann algorithm by blocks (but we have not implemented this version yet). . It is very easy to implement The key operation in these algorithms is the multiplication this operation ef?ciently to take advantage of the sparsity of and to obtain a complexity of for computing where is the number of non zero elements in ; thus the global complexity for solving the system is instead of . When the matrix has a regular pattern it is possible to apply even more ef?cient techniques (for Toeplitz matrices for instance [Bin94]). These methods can not be applied in our case since the pattern of the generated matrices is not regular enough. A signi?cant drawback of these methods is that there is no speedup if we try to solve simultaneously several linear systems with the same left hand side.
E
%

3.2.2

Factorization methods
?

The classical LU decomposition try to decompose the input matrix into a product where (resp. ) is a lower (resp. upper) triangular matrix. For sparse LU decomposition [Geo81, Rei71, Ros72, Duf84, Geo81, Geo93] there is an additional constraint: the number of non zero elements in and minus the number of non zero elements in must be as smallest as possible (this number is called the number of “?ll-ins”). The sparse LU decomposition starts with a symbolic preprocessing very similar to our. It aims is to avoid to spend time time for computing coef?cients the vanishing of which is predictable. The interest of this method is that both preprocessing may be done simultaneously. A large number of implementation for these methods are available (mainly in C/C++ or Fortran) [Dav95] or even in Matlab. Unfortunately these programs and some algorithms are not very robust: very often the input matrix must be non singular or square or positive de?nite. On the other hand, parallel algorithms and parallel implementations exist [Van93, Hea, Don, Alv, Pey]. We have modi?ed the smms [Alv93] program in order to work with modulo coef?cients in order to evaluate the costs of different algorithms. Solving large linear equations modulo a small prime number has been studied in cryptology [LaM91, Mon95] for factoring integers or computing discrete logarithms (very often in that case). These authors use a combination of structured Gaussian elimination and other iterative algorithms. In the current implementation of the algorithm we use by default the structured Gaussian elimination. Note that in an ideal implementation the program should ?rst analysed the shape of the matrix and then decided which algorithm should be applied. 17

¨

?

? ?

?

E

 E

E

!



¤ ?

¤

!



?

E

5

E5

E

!



5

?

E5

%

 E

?

!



?

5

E5

?



?

3.3 Computer Algebra methods for solving linear systems with integer coef?cients.
Very speci?c methods have been developed in Computer Algebra for solving linear equations when the coef?cients are integers. First we recall that the Bareiss algorithm is better than the classical Gauss algorithm but is very inef?cient for big systems. The best way of solving linear systems with integer coef?cients is to use -adic computations: we choose a prime , and we compute (very often a sparse decomposition is more appropriate). Then we de?ne
? ?
?

Theorem 3.1 (Dixon [Dix82])
 1 1 ?
?? ?
? ¨

In fact the iteration may be stopped when becomes stable (see [S.R71] for multi modular methods which may be generalized to adic method). The global complexity [Knu81] of this algorithms is
? 

Bareiss method multi modular method -adic method
?

Note that the -adic method is also an iterative algorithm (in fact this is a Newton algorithm) and that we have previously noticed that this kind of algorithm is less ef?cient for solving simultaneous systems . If it is probably better to use a multi modular approach: we compute for different primes and we apply the Chinese remainder theorem to ?nd the solution modulo .

3.4 Matrix compression
When the matrices are big it is necessary to adopt fairly complicated storage schemes to compress matrix with non zero elements (this is the matrix in memory: consider a the case in Cyclic for instance); even if only one byte is allocated for each coef?cients (an optimistic assumption since some coef?cients have hundred digits); the matrix requires bytes to be stored ! In our implementations we do not duplicate coef?cients (relying on the fact that some rows in the matrix are just term multiples of others); thus we have only to compress the position of the non zero elements; we have experimented the following techniques: 18
?
? ?

1

?

B 

? ?

?



 1

?

B

?

'

?

E

!

 

¤

 1

?

?

¨ ! ¤"#

B

?

?

%



?

?





?

¤

§ ?

'

?



?' 

¨ ! ¤"#

¨ ! ¤"#

B

¨ ! ¤"#  !

¨

?

'



?

?

?? ?

?

¤

E

!

!







?

?

?

?

?

 ?

& E

¤



?

!



¨ ! ?

¨

?

?

?

%

E

?



! 

?

¨

If
7

is upper bound of the coef?cients of and it is suf?cient to compute for and then to apply the extended Euclidean algorithm to and to recover the value in .

?

?

?? ?

?

& E

&( '   1 ? '  ' ? 1 ? ¨ ? ? § ?? &  ?  1 ¤ ? ¤ ?? $ ¨ % ? ? ?  1

¨

??

?

$

%

?



¨

&

?

?

E

¨

¨

  1 ? ? ? ?   
?

?

? §

 1

?

E

? ?

(i) No compression: inef?cient both for CPU time and memory usage. (ii) Bitmap compression: each row of the matrix contains zero and non zero elements: x 0 0 x x 0 0 0 x ... denote the indexes of the non zero elements (here ), then is the bitmap compression (for the example ) . This method is ef?cient but consumes a substantial amount of memory. This is the prefered way to implement the compression when the coef?cients are in
    ¨

(iii) Distributed representation: the row is represented by the array

using bytes when (this occurs very frequently). This method is most ef?cient in memory than the previous one and a little slower ( ). (iv) Apply a standard compression tool (gzip for instance) to one of the previous representation. Very ef?cient in memory but rather slow. For the moment our prefered methods are (ii) and (iii) (depending on the ground ?eld), but the compression algorithms should be seriously improved in future versions.
? ?

4 Experiments
The quality of the computer implementation of Gr¨ bner bases computations may have a drao matic effect on their performance. The theoretical results on complexity (even for homogeneous systems, the complexity is in most cases and in some very pathological cases) cannot throw light on the practical behavior of effective implementation. Thus, while ”paper and pencil” analysis of polynomial solving algorithms are important, they are not enough. Our view is that studying and using programs which implement these algorithms is an essential component in a good understanding of this area of Computer Algebra. To this end, we provide some experiments and comparison with similar programs. This section should be considered as the validation of our algorithm. Thus it plays the same role as its proof for theorems.

4.1 Methodology
Empirical analysis means that we have to pay particular attention to the development of methodologies in the ?eld of benchmark for linear system solving. We adopt the following points: 19

?

B

?(B
?



¨

¨

?



?

(





B

 ?

¤





?

B

?( § ¤(

!

?



?

( § ?(

? ?

?

(





?

&

( § (



¤

?

    ?

&

?'

 

?(

 ?

&

(

1. We compare the new algorithm with state of the art Gr¨ bner bases implementation (namely o Magma [Can98], PoSSo/Frisco Gr¨ bner engine [Tra97], Macaulay 2 [Sti89, Gra97], Sino gular [Gre97], Asir [Tak96], Cocoa, Axiom, Maple [Cha91] and Gb [Faub]). It is also crucial to compare the implementation of the new algorithm with the Buchberger algorithm implemented by the same person (in this case the author). In our opinion it is also important to compare low-level implementation of the algorithms to avoid parasite interactions with a high level language/compiler. has been implemented in and most of the competitors are implemented in C/C++. 2. The list of examples is also a crucial issue: the examples can be easily accessed [Faua] (the web site contains pointers to the Frisco test suite). The list is composed of classical benchmarks (Cyclic , Katsura ) but also of industrial examples (coming from signal theory, robotics). We have removed from the list all the toy examples since nothing can be concluded with them. Of course the toy concept is relative to current computers. For us, an example is toy if it takes less than 1 sec on a PC. 3. This section contains two timing tables: the ?rst one corresponds to modular computations, the second one corresponds to big integers computations. All the computations are done several times on equivalent computers to prevent as much as possible interactions with other programs. For each timing the program was run several times. This was necessary to eliminate ?uctuations in the measurements stemming from some other programs running on the same computer. Of course the timings are rounded. 4. We rigorously use the last version of all the programs and use an appropriate computer to execute them. 5. An even more convincing proof of the ef?ciency of a new algorithm is to solve previously untractable problems. So we should test the algorithm on very dif?cult problems. In our case, solves Cyclic and Cyclic . 6. The same strategy is used for all the programs. For instance if we homogenize the input polynomials for one program we try the same strategy with all other programs. This is the reason why we give the timing for cyclic and homogeneous cyclic . Some systems (Singular for instance) allow the user to customize the internal strategy; we try several parameters and we retain the best method. 7. The outputs of the different programs are checked to be equal. 8. Last, and it is the more dif?cult, we compare the algorithm with other methods: triangular sets (Moreno/Aubry), homotopies (J. Verschelde), Bezoutian (Mourrain) and sparse resultant (Emiris). The task is more dif?cult since the outputs are very different (quasi component, ?oating point approximations).
?
! !
? ?

Triangular methods (Wu, Wang, Lazard, Kalkebrenner). On one hand triangular methods seem to be less ef?cient than lexico Gr¨ bner bases computation (the curo rent limit is Cyclic and Katsura ) but on the other hand the quality of the output is
?
?

20

$

¤ ?

!

!

¤ ?

better. So we think that these methods are useful to simplify lexicographical Gr¨ bner o bases.
?

Mixed volume is extremely fast to estimate the number of isolated roots (up to Cyclic’ ) but with our experience it is not so ef?cient for other systems (and the number of solution is often over estimated).
B

4.2 Modular Computations
Modular computations are very useful in Computer Algebra because they give a fast result (with a very high probability) and information on the number of solutions (Hilbert function). Moreover, since big integer computations could be done by means of -adic or multi modular arithmetics it means that the cost of an integer computation is roughly
F Q$ PI ?
? ? "? ?

So it is also very important to have an ef?cient solver modulo a prime . The computer is a PC Pentium Pro 200 Mhz with 128 Meg of Ram. We consider only non homogeneous systems, but in the following we give because Singular and Macaulay are often very slow for non homogeneous system. Note that the PoSSo library uses generic coef?cient to implement but the other softwares implement inlined modular arithmetic. In other words the overhead of function calls is heavier in the PoSSo library. With a better implementation one can probably divide timings by a factor between and . Table 1 Academic Examples mod FGb Gb PoSSo Singular Mac 2 Asir 0.8 s 3.2 s 46 s 10 s 12 s 56 s 4.1 s 29 s 9m58s 1m47s 1m55s 30 s 3m48s 1h25m 17m41s 17m11s 4m13s 36m23s 3h6m 30m29s Cyclic 7 4.6 s 1m15s 9m3s 2m34s 2m0s 6m51s Hom 5.2 s 1m02s Cyclic 8 1m55s 26m17s 4h38m 1 h 56 m 1 h 33m 3h54m Hom 184.4s 39m17s Cyclic 9 4 h 32 m Hom 11 h 10 m a
a
 ?

11 h 9 min 40 s on a 500 Mhz Alpha workstation with 1Go of RAM.

21



?



? ? 

?

G

?

¨

?

?

?

?

?

?

?

?

?

?

P

$

?

?

?

 ? 

P

$

HGF 

?

?

?

?

PG

? § ? ? " ?

?

?

?

PI

# §¤ ?

?

#

?

?

P

? 

P

$

?

?G?

7 ?

 ?



?

 ?

? ?
§
? ?

Homotopy methods. J. Vershelde reports timings (Cyclic on a Sparc-Server 1000 in ) which are less ef?cient than Gr¨ bner bases techniques. It is dif?cult to o handle over constrained systems.



$

$

$

? ?



?

§

?

?

?



§

§

§

§

§

?

¤



¤ ?

. ..... ...... . ..... .. ..... ...... .... . . ... .... . .... ........ .. .. . . ............. .. .. . . . . .... ... . .. .. . ..... ..... . ... .... . .. ...... .. . .. ........... ..... . . . ..... .. ....... . ....... . . .. ...... .. .. ...... .... . .... . . ... . . . .... . . . ... . ..... . ... .. ....... .. ... ........... . ..... ... . ...... .. .... ...... .............................. .. . . .. .. . . .. . . ... .. ... . .. ... . . . . . ..... ..... . ... ........ . .. ...... .. . .. ........... ..... . . ... . ..... .. . ..... . .. .... .. .. . . ......... ..... . . . . ........... . ............ . . . .. .. . . ...... .... . .... . . .. ... . . .. . .... . . ..... .... ..... ..... . ..... ... . ... .. ....... .. . .. ...... .. .... ...... ........... ............. ..... . .... ... .. . .. ... . . ... . . . . . . ...... . . . . . .. .... .. ... . . ... . . . . . .... . .. . ..... . ...... .. . . ... . ........ .............. . . ...... .. .. ...... .... . .... . . ... ... . . . ..... ... .. .. .. ....... . ....... .... ...... .. ........ .............. .................. ... .... . .... . . . .. ....... .. ..... ... . ... .. . . .. ...... .. .... ...... ...... .... . ........ .... . .... . . .... ... .. . .. ... . . ... . . . . .. . ... . . . ....... . . . . .... .. .. .. . .... .. ...... .. ...... .. ...... .. ................................. .. . . . .. .. . .... .. .............. ... . . .... ... . ... . . ... . . . .. .. .... ... . . ..... ... ... . . ... . . . .. ... . .... .. .... .. .. . ... .. . . ... . . . . . ..... .... ........ . ... .... . ... .. . .. ........... ..... . .. .. . .. .. .. .. . ....... . .. . . ............... .... .... ...... .. .. .. ... ......... ............. . ... .... . . .......... . . . .......... . . ......... ...... .. .. . .. .. .. .. . .... . .. . . .... . .............. . . . ..... ... . ........... . . ....... .. ... .. . .... . . ..... . . . .... . . . . ...... .... .. . .. . ...... .... . .... . . .. ... . . .. . ... . ..... .... ..... ..... . ..... ... . ... .. ....... .. . .. ...... .. .... ...... ........... ............. ..... . .... ... .. . . ... .. ... . . . . . ... .. ... .. .. . ...... . . ....... . .. ... . . . ....... . .... . .. . ............. ............................ .. ........... ............................. ..... ...... .................................. ..... .. . ........ ....... .. . ... . .. . ..... ...... .......................... .. ............. ............................ ............................................... ...... . ..... ..... .. .. . ... .. .. . ............. .......................... .. ............ ............................ ............................................. ...... ... . .... .... . ............. ........ .. . .... .. .. . ............ ........................... .. ............. ............................. ................................................ . ...... . .. ......... . .... ... ... .......... .... . ......................................... . ....... . . ........ .. . .... .. .. ... ......... ... ............... .. . ......... .. .... ....................... ... ....................................... .. . . ............. ............. .. .. ........... .... . . . . ....... ............................................... . .. . . ..................... .. . ........ ..... ... .................... ... . . .. . . . ....... .. ..... .. ..... . ...... . . . . .. . .... .... . . . . .. ..... . . .......... .... . ... . .. .............. ....... .... ...... .. .. ............ ......................... ................................................ .. ....... . .............. ..... .. .... .. .. .. ...... . .............. ... .... . ............ ..... . ... ... . . .. ....... .. .... . . . ... .. . . ...... ... . .. ...... .. .... ...... ...... .... . ........ .... . .... . . . .. . .. ... ... . .. ... .. .. .. . ... . . .... .. .. .. . .... .. .............. ...... .. ........ .. ............. .............. ..... . . .. .. . . .. ... ... . . . ... ... ... . . ... . . . .... ... . ... .. . .. .... .. .. .... .... .. .... .. ... . . .... ... . ... . . ... . . . .. . ... .. . . .. ... .... . ..... .. . .. ... . ..... .. .... ... ..... . ........... ..... . . ..... . . ... .. . . ... .. . ... .. ..... .. .. . .. .. ..... . ....... . .. . ...... . .. .. .... .. . . .. .. . . ........ ..... . . . .................. ................ . . ... . .. . ...... .. . . . . .. .... . .... . .... .... . . . .... .. ...... .... . . . .. .. . . .. . .... . ... .. . ............. ............ ....... .. . .... ...... ... ................... ... ...................... ............... . . .. .... .. .. . .. . . ... ... .. ............. ...... .. ...... .. .. .. .... ..... .. ........... . ........ ... .. .. .. . ......... .. ........ .... ............................ .. .............. ............................. ................................................ .... .. ...... . ......... .... . ....... .... . .... . . ... . .. ....... .. .... . .... . . .... ... . ... . . .. ...... .. .... ...... ...... .... . ........ .... . .... . . .. . ... .. . .. ... ... ..... ... .. .. ... .. .. .. .. .... .. .. .. ........... .... . .. . ... .. .... .............. .... ........ ....... .. .... ............ ............................. .............................................. ... .... .. .. . . . .. .............. ...... .. ..... .. .. . . .. ... ... . .. ... ... . ........ .... . ......... .... . .... . . ... . . ... . . . .... ... . ... .. . .. .... .. .. .... .... .. .... .. ... . . .... ... . ... . . ... . . . .. . ... .. . . .. ... .... . ..... .. . .. ... . ..... .. .... ... ..... . ........... ..... . . ..... . . ... .. . . ... . . ... . . . . .... . . .... . ... .. .. . .... . ... ............ .... . ... ... . . . . ....... .... . . .... .... . ... . . ..... .... . ... . . ... . . . . ..... ..... . ... ........ . .. ...... .. . .. ........... ..... . . . . .. . . .... . ...... . ... .. . ............. ............................ . ............. .... ....................... ... ...................... ................ . ........ ... . . . ........ .... .. ........ ........................... .. .......... . ..... . . . ....... . .... . ............ ... ......... ..... . .. ............. ............................. ................................................ ...... .... .. . ......... ....... .. ... .. . . .. . .. .... .... . ........... ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ ...... ... .. . . .. . .. .... .... . ........... ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ .. ....... ....... .. ... .. . . .. . .. .... .... . .. .. ............................. . . . ........... . .... ............... ............................. .. ............... ............................. ................................................ ........... ........... ... ......... ............. ...... ... ....... ....... .. .. . ...... .. .. ... .... . .............. .. ............... ............................. ................................................ . . .............. . . . .... .... . . . ....... ....... ... .. . . .. . .. .... .... . .. .. ............................. . . . ........... . .... ............... ............................. ........... . .... . .. . .... . . .......... . . . ......... . . . .. .... . ....... . ... .. ... .. . .... . . ..... . .. . . .... . . . . ...... . . . ..... .. . . ..... ..... . ..... .. . .. . ...... .... . .... . . .. ... . . . ... . ..... .... ..... ..... . ..... ... . ... .. ....... .. . .. ...... .. .... ...... ........... ............. ..... . .... ... .. . .. ... . . . . ... . ... . . . ...... . . ....... . .. ... . . . ... .. . . .. . .. .... .... . ........... . .. ... . . . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ ...... .. ....... ....... .. ....... .. ... .. . . .. . .... ....... .. . ............. ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ............................................... .......... .... . ........... ............................. . . ....... ....... .. . ........................... .. ........... ..... ...... .............. .............. ..... . . .. ....... .. .... .. .... . . ........... ............. .... .. . .... .. .. ............ ........................... .. ............. ............................. ................................................ . . ............. ............................. . . ....... ..... .. .. . . ............................ ............. ..... . .. ... . . .. . ... ....... .. . ..... ...... ............................. . . . ........... . .... . ............. ............................ .. ............... ............................. ................................................ ........... .. .. .... .... . ........... .......................... .... ........... ........................... ............................. ...... .. . ....... ....... .. ... . . . .. . ....... . . ............. ............. ....... .. . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ ...... .......... ........ .. .... . .. . . ... ....... .. . ............. ............................. .. .............. ............................. ................................................ ..... .. .. . . ........ ....... .. . ... .. .. . ............. .......................... .. ............. ............................ .......................... ............. ..... . .... . .. .... . .... .. . .. .. .... . . ............. ............ ....... .. . .... .. .. . ............ ..................... .. .. ............. ............................. ................................................ . . ............. . ...... . . .... .. .. . ............. .... .................... .. .......... .. ............................. ................................................ . ... . .......... .... . ........ . . ... ......... ............. ..... .. .. ........... ............................ ... ...... .. .. . .. ... ......... ........ . ... .... . ......... .... . . . ............................ . . . .............. ....... .. .... . . ......... .... . ... . .. .. . . .. . ............. ....... .... . . .... . ... ..................... .................... .. . .. . .. .. . .... . . ....... .. ..... .. . . . .. . . . ...... ..... . . . ....... . . .. . ..... ........ . . . ............. ......... .. .... . ...... . .. . .. . . . .... .. . ... . . .......... .... . .. . ....... . . ............ .............. ....... .. . . . ........... . .. . ............. ............................. .. ............... ............................. ............................................... . .... . . .. . .. .... . .... . . . . ... . . .. .. . . .......... .... . .. ........... ..... .. .. ............. ............................ .. . . ... .. . . .. . ... ....... ... ...... ... . ............................. . . . . ........... . ... ..... . ............................. ... ............... ............................. . . . .............. ... ...... .. ... . . ...... .. .. .... .............. .............. ... . . .... ............ ......................... ... . .. ....... ....... .. . ..... ... . ... . . ... . ..... ... . ............ ................................................ ... . . .. . . . .. .. . .... ... . .. .. . .... . ..... ... . . .. . .. . .. .. ... .... .. ....... .... ...... .. ... . . . .... . ...... . .............. . . . . ... . ... . . . . .. . ... . . . . . ...... ... . . . . .. ... . . . .. . ....... ... ... . .. . . .. .. . ..... ... . .... ... . ... .... . .. . . ... . ..... ... . ......... . . . ..... ... . ......... . . . .. . .. ... . . ... . . . . .... ... . .. .. ... ... ..... . ... . . .. .. . ..... ..... .... ... . ... ..... . . .. . . ... . ..... ..... ... ..... .. . . ..... ... . ... ..... .. . . .. . . .... . . ... . . . . .... .... . . .. ...... . . . ...... . . . .. . ..... ...... . . ... .. .. ... .. . . . ... . . . ........... .. . . . ... .. . . .. . ... .. . . . . . . ... . . .. .... .. .. . .. . . ... . . ... .... ... . . . . .. . .. . . . .. . ..... .. . . . ... . . . ... . . . . .. . ... .. . . . . . . ... . . .. ... . . . ... . . . .... .. .. .. .... .. .............. ...... .. ........ . ............. .............. ..... . .. . . ... ... . . . ... ... ... . . ... . . . .... ... . ... .. . .. .... .. .. .... .... .. .... .. ... . . .... ... . ... . . ... . . . .. . ... .. . . .. ... .... .. . . ..... .. . .. ... . ..... .. .... ... ..... . ........... ..... . . . . ..... . . ... . . ... .. . ... . . . .. .. . ... . ....... .... . .. .......... . ............... . ........ . .... . . . ........... . ............... . ......... . .... . . ....... ....... .. . .... .. .. . ............. . .............. .............. ....... .. .. ........... .. ............... ............................. .. ............. ............................. ................................................ ... . .. ..... ...... ......... .... . ......... .... . .... . . .. .......... .... . . .. ......... . ............ .............. ....... .. . . ........... .. . ............. ............... ............. .. ............... ............................. ................................................ . ...... . ..... ........ .. .. . ... . .............. ......... .... . ........ .... . .... . . .. .. . . ....... ........ .. ... .. .. . . .. . ............. .... ............... ............................. . .. ............ . .... .............. ............................. .. ............... ............................. ................................................ .... ....... . .. . .. .... .... . ........... ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ .. . .... ........... ....... .... . . . ........... . ............. ......... .... . ...... . . . ....... . .. . ............. .. . ........ ....... .. . ... .. ... .............. ....... .... . .. ............. .............. ......... .... . ............ ......... .... . ........ .... . .... . . .... . . .. .... .. . .......... .... .. ....... . ............ .... ... . ... . . . .... . .. ..... ... .. ..... ... . ... . . .. .... .. ..... ... . ... . . ..... ... . ... . . ... . . . . ..... .. ... ... . .. . .... .. .. . .... ......... . ..... ..... ... . .............. ....... .. .. ...... .... .. ...... ............... ........................... ..... ............. ............................. ............................................... .. . . . . .. . .. .. ...... . ...... .. . . . . . ........ ..... . . .... . ............. . .......... ..... . . . .. ..... ... ... ... .. .... .. .... .. . .. .. .. ... .... . . . ..... ..... ... .. ..... ..... ... .. ......... .. ... .. .. .. ...... ...... ... ...... ..... ... .. ..... ... .. ... .. .. ..... .... .. . ..... ... .. .......... ..... ... .. .......... ...... .. ... ...... .. .. .. . . ... ......... ..... ............. .. ..... ... .. ...... .. .... . .. ... ..... ... .. .... ... ... ..... .............. .............. ..... .............. ..... ..... ..... ... ... .. ... ........ .. .. . ...... .... ........ .............. ... . . . ..... ... .. ... ....... . .. . ..... ... . . . ..... ..... ... . ..... ..... ... . .. .. ... ...... .... .. ...... ................... ..... ... . ..... ... . ... ..... ...... .... .. ..... ... . ... ..... ...... ... . ... . . .... . . .. . . . . . . .. . . .. .. ....... ... ......... . .. . . . .. . .. . . .. . . . ..... . ............. ..... ..... ......... .. .. ...... . . .. ...... ... . .. . ...... . ... ............ ................. ..... ..... ... . ..... . . ... . . ..... ............... . ........ . ... . . . .. ... . ... ... ... .. . . . .. . . . ... . ...... . . .. . ... . . . . .. .. . ........... . .... . . . .. . .. . ........ . ........... ..... ..... ... .... ............. .... .......... ............ ...... . ... ... ....... ......... ............ ..... ... ....... .......... ...... ..... .. ..... .......... ....... ... .... .. .. . ..... . . ... . .... .. ... . ..... ..... ... .. ... ...... . ..... ..... ... . ..... ... ..... ... ..... ... ..... ..... ..... ..... .. ..... ... ... . ...... .. ...... . ..... . . .. . . ... . . . .. . . .. .. . . ..... ..... ... . ..... ..... ......... .. .. ..... . . .. ...... ..... .. .... . ..... ............ ... ..... . . . . . ..... ... . ..... ... ..... . . ..... . . . ... . . ... . . . ... . . . . . .... ... ... . .. . ........ ...... . ... . . . ..... . . . ... .. . . ..... ..... ... ... ..... ..... ... . .. .. .. . ... . ..... ...... ..... .... ............. ... .. ..... ... . ... . . . ........ ... . ..... ... . ... . . ..... . . . ... . . ... . . . ... . . . . . ............. . .......... .. ....... . ............. ............ ....... .. ... .... .. .. .. .. .... .. .. . .. .... ............. .............. ...... . ..... ... . ............................. ............. ............................. ................................................ ... ..................... ............. ..... . ... .. .. . .... . . ... ...... ... . ..... ...... .. . ............................ .. .... ..... .. .... .............. ............................. ..... ..... ... . ............................ ..... ... . .............. ... ..... .. ..... . .... .. ... ................... ... . . ..... ... . ... . . .. .. .. .. . .... ... ..... .. ........... . ........ ... ... .... .. ............. .. .. . . . .. ... ... . .............. ...... . .... .. .. .. ......... .. ....... .... ...... .. ....... .... . .... . . ... . . .. ....... .. ... .... . .... . . .. . . . ...... .. .... ...... ...... .... . ........ .... . .... . . ... ... .. . .. ... ... ... ... .. .. ... .. .. .. .. .... .. .. .. ........... .... . .. . ... .. .... .............. .... ........ ....... .. ... .... .. .... ............ ............................. .......................... .............. ..... . .. . . . . .. .. .. .............. ...... .. ..... ... . ........ .... . ......... .... . .... . . .. . . ... ... . .. ... ... . . ... . . . .... .. . ... .. . .. .... .. .. .... .... .. .... .. ... . . .... ... . ... . . ... . . . .. . ... .. . . .. ... .... . ..... .. . .. ... . ..... .. .... ... ..... . ........... ..... . . ..... . . ... ... ... . . . . ... . . . ... .. .... . ... ....... .... . ... ... . . . . ..... ... .... .... . ... . . .... .... . ... . . . .... .. .. .. ..... ... . . . ..... ..... . ... . . . .. . ... ...... . . . .. . . .. ... . .. . . . ... . ....... .... ..... . . . .... . ........... ..... . . ..... ..... . .... . . ....... ........ .. . . .......... . . .. ............. .... . ........... ............................. . . ................ .... ............... ............................. .. ............... ............................. ................................................ .. . ...... .. . .. . .. ...... .. . . . . . .. .... . . .... .... .... . . . ...... .. .. ...... .... . .... . . .. .. . . ... ... .. . ... . . .............. ............ ....... .. . .............. ... ... ...... ......... .... . ... ........ ........ .... . . .... .... . .... . . .... . . .. . . .. .... .. ........... . ........ ... ... ... .. .. ....... .... ............. ............... ......... ... . .. .... ... . ............... ........ .... . .............. ......... .... . ......... .... . .... . . .. .. .. .... ..... .. .. .. . ......... .... .. ...... .. ...... ......... .... . ....... .... . .... . . . .. ....... .. .... . .... . . ..... ... . ... . . .. ...... .. .... ...... ...... .... . ........ .... . .... . . .... ... .. . .. ... . . ... . .. .. .... .. .... .. .. ........... .... . .... . ... .. ... .. .... ........ .. .............. .... ..... ....... .. .... ........ .. .............. ... . . .. .. . . .. . .. . ... . .. .... .. .. . .... .............. ...... ............. ..... ... .. .. . . .. ...... ............ ...... ............... .............. ....... .. ..... .............. .............. ...... .. .............. ....... .. ....... .. .. ... . . . . ... . ..... ........ ....... .. ... . . ... . ....... .. . .. .... .. .. .. ..... ... . . ..... .. . .. ...... ..... .. .... ... . . .. .. . .... .. ... ... ... ... . ... ... .. ... ..... .. ... . . . ..... ..... ... .. ...... ..... ...... ..... ... . .. . . .. ...... ..... . . . ...... ..... ... .. ..... ... .. ... . . ..... ..... ... .. ..... ... .. ... . . ..... ... .. ... . . ... . . . ... . . . .... .... .. .. . .. . . . . .. ..... ... . . ..... .. . .. .. ... .. ... ..... .. ..... .. . . ..... ..... ...... ...... ..... ... ....... ... .... . . .. ...... ....... ........... ..... ... ....... ... ..... . . ..... ..... ... ....... ... ..... . . ..... ... ..... . . ... . . . ... . . . . ....... .. . . .. ..... ...... . ..... .. . .... .... .... ... .... . ... ... .. . ... .. ... .... . ..... .. . .. ... . ..... .. .... ... ..... . ........... . ..... . ..... . . ... .. . .. . ... . . ... . . . . . .... .. .. . ... .... ..... .. .. .. . .... ... . ... .... ............ .... . .... .... .... . ... ... . . . . .... ............ ... ...... ..... .... . ..... ... . ... . . ..... ..... .... . ..... ... . .. . ..... ... . ... . . ... . . . . ... ..... ... .. ....... . . . . . ........... . .... . ............. ............................. .. ............... ............................. ................................................ ....... ....... .. ... .. . . .. . ... ........ .... . ............ ............................. ...... .. ... . ........... ... ......... ..... . . ............. .... ....................... ... ..................... . .......... ..... . . ... . . . ........ .... .. ........ ........................... .. .......... . ..... . . . ....... . .... . ............. ............................ .. ............. ............................. ............................ .............. ..... . ..... . ......... .... .... . . ....... ... .. . . .. . .. .... .... . ........... ............................. ............................ .............. ..... . . ..... .. ....... .. .. ....... ... ........ ..... . . ... .. . . .. . ........... . .... . ............. ............................. . ... . ........... . .. ............... ............................. .. ............... ............................. ................................................ ........... . . . ........... . .... . ............. ............................. .... . ............. ............................. ... .. . . .. . .. .... .... . ........... ............................. . . . .. .... .... . ........... ............................. .. ............... ............................. ............................ .............. ..... . ..... . .. ....... ....... .. ....... .... ... .. . . .. . .. .... .... . ........... ............................. ............................ .............. ..... . . ...... .. ....... .. . ... .. . . .. . ........... . .... . ............. ............................. . ... . ........... . .. ............... ............................. .. ............... ............................. ................................................ ........... . . . ........... . .... . ............. ............................. .... . ............. ............................. ... .. . . .. . .. .... . .... ....... ............................. .... ........... .............. ...... . . . . .. .... .... .. ........... ............................. .. ............... ............................. ............................ .............. ..... . ..... . .. ....... ....... .. .. .... . .. . .... . . . ...... . . . ..... .. . . ..... ..... . . .. . . ...... .. ...... .... . .... . . . . ..... . . . ... .. . ..... .... ..... ..... . . ... .. ....... .. . ..... ... . ...... .. .... ...... ........... ............. ..... . .. . . ... . . . .. .. . . ........ ....... .. .. . ... .. ... . . . ... .. . . .. . .. .... .... . ........... ............................. ............................ .............. ..... . . .. ....... ....... .. ... .. . . .. . ........... . .... . ............. ............................. . . . ........... . .. ............... ............................. .. ............... ............................. ................................................ ........... . . . .. .... .... . ........... ............................. .... . ............. ............................. . ....... .... ... .. . . .. . ........ .... . ........... ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ............................ ............. ..... . ..... . .. ....... .. ....... .. .. .. . . ........... ............. .... .. . .... .. . . ............. ........................... .. ............. ............................. ............................ .............. ..... . . ....... ....... .. ... . . . .. . .. .... .... . ........... ............................. . . . ........... . .... . ............. ............................. .. ............... ............................. ............................ .............. ..... . ..... . .. . ....... .... ... .. . . .. . ....... .... . ............. ............. ....... .. ........... ........................... . . . ........... . .... . ............. ............................. .. ............... ............................. ............................ .............. ..... . ..... . ...... .......... ........ .. .. .. .... . . ... ....... ............. ......... .... . .............. ......... .... . ........ ... ... . . . . . .... .... .......... . ............... ......... ... . . ....... . .... . ............. .. ............... ............................. .. ............. .. ............... ............................. .............. ............................ ....................... ......... .. .... . .. ......... .... . .... . . .... .... . ......... .... ....... .. .. .. . .. .... . ............. ......... .... . . ............. . . ... .. . . .. . .. .... .... . ........... . ............... ............ ....... .. . . . ........... . .... . .... .. .. . ............ ..................... .. ............... ............................ ......... .... . .. ............... .. ............. ............................. ............... ............................. ......... .... . .............. ............................ ....................... ......... .. .... . .. ......... .... . .... . ..... . . . . ............. . ...... . . .... .. .. . ............. .......... .. ......... .... . . ....... .. ... .. . . .. . .. .... .... . ........ . . ............... ............. ..... .. . . . ........... . .... . ............. .. ............... .... ......... .... . .. ............... .. ............... ............................ .............. ............................ ....................... .... .. . .... . .. ......... .... . .... . ... ....... ....... .. .... . ........... ... ......... ......... .... . ........... .................... . . ....... .. ... .. . . .. . .. .... .... . .. . ........... ............... ......... .... . . . . ........... . .... . ............. ............... ... ......... .... . .. ............... ............... .. ......... .... . .............. ....................... ......... ........ .... .. . .... . . .... . .. ....... . . . ............. ......... .. . .. . ......... .... . .. ... .. . . .. . .. .... .... . ........... ............... . ....... .... . . . . ........... . .... . ............. ............... . ..................... .. ............... ............... .................... ......... ........ .... . .............. ...................... ......... ......... .... . . .... . . .... . . .. ....... . ....... .. . ...... .. . .... .. . ... .. . ... . . . . ... . .... .. ..... ... ...... ..... ... . ..... ... . .. . ... . . . .... ... . .... . .... ..... ... . ..... ..... ... . ......... . .... . . .. ...... ..... .. ...... ..... ... . ..... ... . .... . . ..... ..... ... . ..... ... . ... ...... ..... ... . ... . .. ... . . . ... . . . . . ....... . . .. . . .......... .... . .. . ....... . . ............ .............. ....... .. . . . ........... . .. . ............. ............................. .. ............... ............................. ........................... .............. ..... . . .... .... .. . . .. . . . . . ... . .... .. ..... ... ...... ..... ... . ..... ....... .. .. ... .. . . ..... .. . . .... ..... ..... ... . ..... ..... ... . ..... .......... ... .. ...... ..... .. ...... ..... ... . ..... ... . ... ... ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . . ...... . . . .. ... . ..... . .. .. . ... . ... ... .. .... .......... ... ....... ..... ... ........ ... .. .. .. . . . ...... .. . . .. ..... ..... ..... ... .. ..... ..... ... ....... ... ...... .... .......... ..... .. ....... ..... ... ....... ... ..... .... ..... ..... ... ....... ... ..... .... ..... ... ..... .... ... .... .. ... .... .. . ............. ... ..... .. .... ... .. ... .... . ..... ... ...... ..... ... ..... ... ... .. . .... ..... .... . .... ..... ... ...... ............ ......................... ..... ... ..... ... ... ...... ..... ... ...... ..... ... ..... ... ... ..... ..... ... ..... ... .............. ..... ... ... ..... ... . ... ... . .......... ... . .. .............. .............. ..... .. ............................ . .. ..... . ... ... .. . .. .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... . ..... ... . ... .. . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... .. ..... ... . ... . . .. ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . ...... ... ... .... ..... ... ...... ..... ... ..... ... .... . .... ..... .... . .... ..... ... ...... ........ . ..... ... ... ... ...... ..... ... ...... ..... ... ..... ... ... ..... ..... ... ..... ... ... ..... ... ... ... ... .. ........ .. . ... ....... ... ..... ..... .... ... . . ... . .... ... .. .... . .......... ... ........ ..... ... ....... ... .............. . . . ............ .... . ........... ..... ... ........ ..................... ... ..... .... .......... ..... ... ........ ..... ... ....... ... ..... .... ..... ..... ... ....... ... ..... .... ..... ... ..... .... ... .... .. ... .... .. . . .. ... ... . . .... ............. ... .. .. ... . .... ... ........... .... ............. ..... ... . ... . . .. ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . . ... ....... . . ... . ... .. . . .. . .. ... . ...... .. ...... .. .... ...... ...... ....... ............................. . . . .... ..... .. . ...... .... ...... .. ..... ...... ...... ... . ............................. .. . ...... ...... ... . . ...... ...... ... . ............................. ..... ............... ............................. ................................................ ... ............ .. ..... ... . ... . . .. .. ... .. . .. ... . .. .... ... . ....... .... ...... .. .... ........... ..... ... . ... . . . . . ........... .... . ............. ............................. .. ............... ............................. ............................ .............. .. .. . ... . ....... . ....... .. .. ... ... ..... ... . ... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... .. ................ ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . .......... ... . ... . . .... . ...... . ... . . . . ... ... ... . . ............ . . ... ... ... . .. . ..... .. .... ..... .... ... .. .... .. .. ..... ... .. ...... ..... ... . ..... ... . ... . . . . . .... ..... .. . .... . .... ..... ... . ...... ..... ... . ..... ... . ... . . .. ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . .. ..... ... . ... . . ... . .. . ... . . . . .. . ... ... .... .. ..... ... ...... ..... ... .. ......... .. ....... ... . .. ... ....... .... .. .. .. .... ...... .. ... .. .... .. .. ..... ... .. ...... ............. ..... ... .. ... ...... .. .. ..... ..... .. .. .... ..... ..... ... .. ...... ..... ... .. ..... ... .. ... ......... ...... ..... ... .. ...... ..... ... .. ..... ... .. ... ............ ..... ... .. ..... ... .. ... .. ........ ... .. ... .. .. ... .. .. .. ... .. .. .. ... ... .. .. .. ... .... .. ..... ... ...... ..... ... ..... ... ... ..... ..... .. .... ..... ..... ... ...... ..... ... ..... ... ..... .. ...... ..... ... ...... ..... ... ..... ... ..... ..... ..... ... ..... ... ... ..... ... ... ... ... .... .... ... . .. . ... ... ..... . ... .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ..... ..... ... . ... . . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ..... ... . . ... ...... ..... ... . ...... ..... ... . ..... ... . ... . . ...... ..... ... . ..... ... . ... . . ...... ... . ... . . ... . . . ... . . . ... ........ . . ... . .... ...... ...... . ... ...... . . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... . ..... ... . ........ . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ................ .. ...... ..... ... . ...... ..... ... . ..... ... . ........ ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . ... .. . . .. .. . ... . .. . .. ... ... . ... .. . ... . ... ...... .... .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ...... ..... ... ..... ..... . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... ..... ... .. ...... ..... ... . ...... ..... ... . ..... ... . ... ... ..... ..... ... . ..... ... . ... . .......... ... . ... . . .... . . . ... . . . . .... .. .... .............. . . ..... .............. .. ... . . .. . . ... ... . ...... ... ... ............. ... . . ... . . . . ... .. . ...... ... . .. .... .. .. .... .... .. .... .. ... . . .... ... . ... . . ... . . . . .. ....... .. . . ....... .. ... .. . . .. . .. .... .... . ........... . ............... ............ ..... . . . . ........... . .... . ............. .. ............... ............ ..... . .. ............... .. ............... ......... ..... . .............. ......... .... . ......... .... . .... . . .... . . .. . ....... .. .... .. ... . . ..... ... . ..... ... . ... . . ............. . ........... ............. ..... ... . ... . . . ... ....... ... . ... ... . . . ... ... .. . . .... .. . . ....... .... . .... ............... ...... ............... .............. ....... .. . . .. .... ...... .. . ...... .... ...... ... . ...... ...... ... . ............................. .. ...... ............... ...... ............. ............................. ..... ..... ... . ............................ ........................... ............ ... ....... .. ... .. .. ... . .. ..... ... . ..... ... . ... . . ... . . ... . ....... .. . .. . . ....... .. . ......... .... . ........... .... . ............. .. ............... ............... ............. .. ..... ... . .. ............... ............................. .............. .............. ....... .. .. .......... .... . .. ........... . ............ .............. ....... . . . ........... . ............. ......... .... . ............... ......... .... . ............................ .. ...... ... ... .. .. .. ... ... .... . .. ..... ............... ........ .. ..... ... ... .. ... . ... ..... ..... .. .... ..... ..... ... ...... ..... ... ..... ... ... .. ...... ..... ... ...... ..... ... ..... ... ... ..... ..... ... ..... ... ... ..... ... ................. ..... . ... .. . ... .. .. ..... ... ... ... .. ........ .. .. .. .. .... ...... ............ ....... .. ..... ... .......... ..................... ... .. ... .. .. .. .. ..... ..... .. .. .... ........... ... .. ...... ..... ... .. ..... ... .. ... .. .. .. ...... ..... ... .. ...... ..... ... .. ..... ... .. ... .. .. ..... ..... ... .. ..... ... .. ... .. .. ..... ... .. ... .. .. ... .. ....... .... .. ....... . .. .. ....... . ... .. .. . . .... . ........... . .... . ............. ............................. ....... ....... ... . . . .. . .. .... .... . ........... .... . ............. ............................. ............... ......... .... . . . . ........... . .... . ............. ............... ......... .... . ......... .... . .. ............... .. ............... ............................. ............... ......... .... . ......... .... . .............. ............................ ....................... .... . . ......... .... . .... . .. .. . ....... ........ .. ... . . .. . ....... .. .. .... .... . ........... . . ......... .... . . . . ... ....... . . ........... . .. . ............. . ............. ............... ......... .... . .. ............... .............. ......... .... . ......... .... . .... . . .... . . ......... .... . ...... ........... .... . .. .. .............. .. ............... ............................. ............... ......... .... . .............. ............................ ....................... ......... .. ......... .. .... . . . . ....... ........ .. ... .. . . ... . ............. .... ............. ............................. .. .... .... ........... ....... .. . . . ........... . .... ............... ............................. . ............. ............... . .. .... .. . .......... .... . .... .. .. ............. ..... ... . ... . . .. ..... ... . ..... ... . ... . . ........................... ... ... . ... ... . . . ... .. . . .. . ... ... . .... . .. ......... . ...... ..... ... . ........... ... . . . . . .... ..... .. . .... . .... ..... ... . ...... ...... ... . ........................... .. ...... ..... ... . ...... ............. ............................. ..... ..... ... . ..... ... . .... . . ..... .. . .............. ... ...... .. ... . . .. .. ... . . ............ .............. ....... .. ... . ... . . . .. . .. ...... . . . . . ........ ..... . .... ............. .......... . ........... . ... .. ... ... . . . .. . .. . . . . . . ......... . .... . .. ..... ..... ...... ..... ... .. ..... ... . ... .... . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... .. ..... ... . ... . .. .. ...... ..... ... . ...... ..... ... . ..... ... .. ......... ..... ..... ... . ..... ... . ......... ..... . . . .............. . .... ... . . . . . .. ... . .... . . ... ... ... .... . ... ......... ...... ............. ..... ..... ... .. ..... ... ..... ... ... . .... ..... .... . .. ........... ...... .... ........ .............. ....... .... ..... ... ..... ... ... . ...... ..... ... ...... .............. .............. ... . ..... ..... ... .............. ..... ..... ... ..... ... ..... ... ... ... ... . ........... . ... ... ... .. .... ..... ... ... . . ... . .... ...... .... . .......... ... ........ ..... ... ....... ... ..... .... . . . ...... ..... .... . ..... ..... ..... ... ........ ..... ... ....... ... ..... ................. ..... ... ........ ..... ... ....... ... ..... ............ ..... ... ....... ... ..... ........... . . ..... .......... ....... ... .... .. . . .. . .. ............. . .. . ... .. ... . .... ... . . . ... .. . . .. . .. ... . .... . .. ..... ... . . .... . ....... ..... ... .. ... . . . . . .... ..... .. . .... . .... ..... ... . ...... . ....... .............. ... . . .. ...... ..... ... . ...... ............ .............. ... . . ..... ..... ... . .............. ... . . ..... ... . ... . . ... . . . ... . . . ..... ...... ... . . ..... ... . ... . ... . ... . .. . .... ... . . . .. . ... .. ... ... . . . .. . . . . . . . .. ... . .... . .. ..... ... . ...... ..... ... . ..... ... ...... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... . .. ..... . . ............ .. ...... ..... ... . ...... ..... ... . ..... . ............ ..... ..... ... . ..... ... . ......... ..... ... . ... . .. ... . . . ... . . . ... ... . ... . . . .... .. . ... ............ . ... . ... ....... . . . .. . .. . . . . . .... ... . .... . .. ..... ... ........ ..... ... . ..... ... . ... .... . . ........... .. . .... ..... ..... ... . ...... ..... ... ....... ... . ... ..... ... ...... ..... ... . ...... ..... ... . ..... ... . ... ..... ...... ..... ... . ..... ... . ... ..... ...... ... . ... ..... .... ..... .. . ... . . . . . . .. . . .............. ....... ............... ... . .. ............... ............... ... . ............. ... . .. . ... . . ... ... . . . .. . .. . . . . . . ....... .... . . ..... ... . . .... ..... ............ ... ..... . . . . . ..... .. . .... . .. ..... ... . ...... ..... ............ ............ . . .. ...... ..... ... . ...... ..... ... . ..... ............ . . ..... ..... ... . ..... ............ . . ..... ............ . . ... . . . ... . . . .. ... . .. . ............ ..... . ........... ..... . ............. ... .... .. .. . ... ... . . . . .... .... ..... ... .. ..... ... . ... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... .. ..... ... ...... . . .. ...... ..... ... . ...... ..... ... . ..... ... ...... . . ..... ..... ... . ..... ... .. ... . . ..... ... .. ... . . ... . . . ... . . . . .. . .. . . . . . ... ... . .... . .. ..... ... . .... ............. .............. ...... .. .... . ...... . .......... .... .. ....... . ............. ... .... .. .... ..... .. ............................. ............. .. ............. ............................. ............................ .............. ..... . . .. .... .. .. . .. . .... ... . ... ................... ......... ..... . ... . .... ..... ....... .. .. ....... .. .. . . .... . . .. .... . ... ...... ... . ..... ............... ............ ....... .. ..... .. . .. .. . . . ... . . ..... ... . ... ..................... ... . . ... . . .... . . .. ... .. . .. .... ........... . . . ........... .. ..... ...... .. .... ............... .............. ...... . .... ............. .. ............... ..... ............... .............. ....... .. .............. .............. ....... .. ......... ....... . .... .. . .... . . . .. . .... .. .. .. .. .... .. ....... .... ......... .... . ...... .. ... ... . ......... .... . ....... .... . . .. .. . .. . . .. ... ... . .. .. ........... .... . . ... ..... ... . ...... ............ ............. ... . . . . . .... ..... .. . .... . .... ..... ... . ...... ............ ............................. .. ...... ..... ... . ...... ..... ... . ..... ....... ... .. . ..... ..... ... . ..... ... . .............. ..... ... . ... ...... ... . .. . ... . . . ... .. .... .............. .... ... . ....... .. .... ........ . ..... ....... ... .. . .......................... .. . ... ... . . . ... .. . . .. . .. ... . .... .. .... .. .. ... . ... . . ....... .. . .. .... .. .. .............. ...... .. ..... ... . ........ .... . ......... .... . .. . . . . .. ... ... ... ... ... .. ..... ... ... . . . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... .. ..... ...... ... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... .. ... .. . .. ...... ..... ... . ...... ..... ... . ..... ... .. ... .. . ..... ..... ... . ..... ... . ... .. . ..... ... . ... . . ... . . . ... . . . .... . .. ...... .. ... . .. .. ... ....... . . . .. . .. . . . . . . .... ... . .... . .. ......... . ...... ..... ... . ..... ... . ... .... . . ........... .. . .... ..... ..... ... . ...... ......... . ..... ... . ... ..... ... ...... ..... ... . ...... ..... ... . ..... ... . ... ..... ...... ..... ... . ..... ... . ... ..... ...... ... . ... ..... .... ..... .. . ... . . . . . . . . . . ....... .. . . . ............. .............. ....... .. . ........... .. . ............. ............... ......... .... . .. ............. ............... ......... .... . .............. ......... .... . ......... .... . .... . . ... .... .......... .... . .. .. ......... . ............ .............. ....... ............... ......... .... . ........ .. ............... ............... ......... .... . .............. ......... .... . ......... .... . .... . . . ....... ........ .. ... . . .. . ......... .. .. .... .. .... ........... ............... ......... .... . . . . ........... . ........... . .. . ............. .... . ............. ............... ......... .. ............... ............... ......... .... . ......... .............. ......... .... . ......... .... . ......... . .. . . ....... ........ .. ... .. . . .. . ........ .... . ........... ............... ......... .... . . . . .... .. . . ........... . .. . ............. .... . ............. ............... ........ .... . .. ............... ............... ......... .... . .............. ........ .... . ......... .... . .... . . .... . . . .......... .... . . . ............ .............. ....... .. .............. . ..... .... . .. ............. ............... ........ .... . .............. . ..... .... . ......... .... . .... . . .... . . .. . . .. .. ...... . ...... .. .. . . . . ....... . .... . ... . .......... .... . .. ... . . .. . ... ... . .... ... . . . ... .... . . . .. .. ... ......... .... . .. ............. ...... ..... ..... ..... ... .. ... . . . . . .. ........... . .... . .... .... ........ ...... .............. ..... ....... ... .. . .. ...... .............. ...... .............. ..... ....... ... .. . ..... .............. ..... ....... ... .. . ..... ...... ... .. . ... .. . . ... . . . .. ... . ..... ... . ... . . .... ..... .. . ............ ... . . ............ ... . . ... . . . .. .. . .. . .. . .. ... ... . ......... .. ... . .. ............... ............................. ......... ... . ......... ............................ ... . .................. ...... . ..... . .. .. . ....... ........ .. . .............. . . .. .. ....... .... . ........... ............................. .......... .. ..... . . ................ .... . ............. ............................. .. . ...... . .... . .. .. .. ........ .. . ... ... .. .... . ... ..... .. .... ..... .... ... .. .... .. .. ..... ... .. ...... ..... ... ........ ... .. ... .. .. .. .. ..... ..... .. ...... ..... ..... ...... ...... ..... ............ .......... ..... .. ...... ..... ... .. ...... ..... ...... ..... .......... .. .. ..... ..... ... .. ..... .......... ..... ..... ... .. ... ..... ... .. .. .. ... .. .. .. . .. . .... ... ... . .... .. ..... ... ...... ..... ... . ..... ... ... . .... ..... .. .... . .... ........ . ...... ........ . ..... ..... ... .. ...... ..... ... ...... ........ ..... ..... ... ..... ..... ... ..... ..... ... ..... ... ... ... ... .... .. . ... ... ... .. . ... . . ... ... . . . .. . .. . . . . . .. ... ... .... . .. ..... ... . ...... ..... ... . ...... ... . ... . . . . ..... ..... .. . .... ..... ..... ... ........ ..... ... . ...... ... . ... . . .. ...... ..... ... . ...... ..... ... . ...... ... . ... . . ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . .... .. . . .... . .. ..... ............. ..... ... . ..... ... . ... . . . . ..... ..... .. . .... ..... ..... ............. ..... ... . ..... ... . ... . . .. ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . .. . ... . . ... ... . . . .. . .. . . . . . .. ... . . .. .. . . . . . ... ............ . ... ...... . . . .. . .. . . . . . . ............ .... . .. ..... ... . ...... ..... ... . ..... ... . ... .... . . ..... ..... .. . .... ..... ..... ....... ...... ..... ... . ..... ... . ... . . ... ...... ..... ... . ...... ..... ... . ..... ... . ... . . ...... ..... ... . ..... ... . ... . . ...... ... . ... . . .... . . .. ... . . . .. . .. ... .. . ....... .... ............. ............ ....... . ... ... . .... ............ ........ .... ...... ... ....... ........ .... ........ . .... .... .... . .... .... .. .. .. .... .. ...... .. .... . .... . . ... . . .. ....... .. ... .... . .... . . .. . . . ...... .. .... ...... ...... .... . ........ .... . .... . . ... ... .. . .. ... . . ... . . . ... .. .. .. .. . .... .... .. .. .. . .. ... ..... ... .... .... ........ .. ..... ..... ..... ... ... . . ... ... .... .. .... . .... ........ .. ...... ..... ..... ..... ... . ... . . .. ...... ..... .. ...... ..... ..... ..... ... . ... . . ..... ..... ... . ..... ... . ... . . ..... ... . ....... .. ... . .. . . . .. . .... . .... .............. .... ... ... ....... .. .. .. ........... .. . .... . . ... ..... ... .. ..... ..... ... ... . .. .... ........ . ....... .. .. .... ..... .. .. . .. . . .... .... ............ ..... ............... ........... .... . ..... ..... ... . ..... .............. ............ ... . ..... ... . ............ ..... . ... ... ... . . . ... . . . . .... .. . ... . .... ..... ..... ... . .... .... ... . ... ... . . . .. . ... . .. .. .. .. .... ..... .. .. .. . ... ... .. .... ..... ..... .. ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . .. . ..... ... . ... . . ... . . . .. .. . . ... ... . . .. ... ... . .. ... ... . . .. .. ..... . .. .. . ... .. ...... . . . ....... . ...... .. .. . . . ..... . . .... . ........ .... . . ..... .... . .... . . .. .. . ... . ....... ........ .. . . .......... . . .. .. .. .... . .... . ........... ............... ......... .... . . . ............... . .... ............... ............... ......... .... . .. ............... ............... ......... .... . .............. ......... .... . ......... .... . .... . . .... . . ...... .. . .. .... . .... .... . . .. .. .. .... .. .. . .... . . ............. ............ ....... .. . ........ . .. .......... ........ .... . ... ......... ........ .... . . .... .... .... . .... . . .. . .... .. .. .. ... .. .. ...... .. . ... ... . .... ... . . . . . ... ..... .. . . .. . ....... .... . .... . .. ..... ... . ...... ..... ... . ..... ... . ... . . . . . .... ...... . . .... . .... .............. ...... ..... ....... ..... ... .. ... . . .. ...... ..... ....... ...... ..... ....... ..... ... .. ... . . ..... ..... ....... ..... ... .. ... . . ..... ... .. ... . . ... . . . ... . . . .. ....... ... . ..... ... . ....... . .. ....... . .. .. .... . . .. . .. .. ..... . . . ...... .......... ...... . . .. .. . ... . . ... ... . . . . ... . ..... .. . . . . . .. ... . . .... . .. ..... ............. ..... ... ....... ... . ... . . . . ..... ..... ......... .... ..... ..... ............. ..... ... ....... ... . ... . . .. ...... ..... ............. ..... ... ....... ... . ... . . ..... ..... ... ....... ... . ... . . ..... ... . ... . . ... . . . ... . . . .. ... . . . ... . ... ... . . .. . .. . ... . . ... ... . ....... .. . ... . ..... .... . . . . . ............. ....... .. ..... ... .......... ..................... ... . ... . . . . ..... ..... ... ... .... ........... ... ........ ..... ... . ..... ... . ... . . .. ...... ..... ... ........ ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . ...... .... . ...... . . . . ....... ...... . .. . .. . .... . ... . ............................. . . ........... . . ............. .... ....................... .... . ............. ............................. .. ............... ............................. ............................ .............. . . .... . .. ........ ............... . ... ......... ..... . ... ..................... . .......... ..... . ........... . ... .. . . .. . ... ........ .... . ............ ............................. . ... . ........... . .... . ............. ............................. .. ............... ............................. ............................ .............. ..... . ..... . ...... .. .. . ... .......... .... .. ............................ . ... .. . . .. . .. .... .... .. ........... ............................. ........... . .... . . . ...... . ... . ........... . .... . ............. ............................. .. ............... ............................. ............................ .............. ..... . ..... . .. . .... . ..... .. ....... ....... .. ... .. . . .. . ... ........ . . .... . ........... .... . ........... ............................. ......... .... . . . . ........... . . . ............. ............... . .......... ..... .. .. ............... .. ............... ............................. ............... .......... ..... . .............. ............................ ....................... ......... .. ......... .. ......... ......... . .... .. . . . ....... ....... .. .. . .... ........ . ............... ........................... . .... . ........... . .... . ............. ............................. .. ....... ...... .. .... . . .................................. . . ... ....... .. . ............. ............................. .. ............. ............................. ............................ .............. ..... . . . .. ....... . .............................. . ............. .. .............. ............................. ............................ .............. ..... . . ..................... . .. ....... . . .................................. . .... .. .. . ............ ..... ... . ... . . .. ............. ............................. ............................ .............. ..... . . . . .... . .. ... . . ... ... . . ...... . .. ... .. . . .. . .. ... . .... . . ..... ... . ...... ...... ... . ............................ . . . .... ..... .. . .... . .... ..... ... . ...... .......... .. ............................. .. ...... ..... ... . ...... ..... ... . ............................ ..... ..... ... . ..... ... . .............. ..... ... . ... ...... ... . .. . ... . .. . .. .... .. .. . ............. ..................... .. ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . . .. .. .... ............. .. ............... .... ....... ... ... ............... ... . . .. ............... ............... ... . ......... .............. ... . . . . .. . ... ... ........ ..... . .. .. ... .. . . . . . .. . ....... .... . ......... ... . ...... ..... ... . ..... .................... . . . ........ .. . .... . ......... ... . ...... ..... ... . ..... .................. .. ...... ..... ... . ...... ..... ... . ..... ............................ ..... ... . ..... .................... ..... ............................ .. ......... .. .. . . .. .. . .. . ........... .. ........... .... .................. ..... . ........... ..... . ............. ... . . . ... . . . . ... . ............ . ... ... .. .... ... ............................. ............................ . . .............. . . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... ....... ... . ... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... . ... . . .. ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... . .......... ... . ... . . .... . . . ... . . . . .. ............. ....... . . .. ... ......... ..................... .................... ......... .... . .. ....... .............. ...... .. ...... .. . ... .. . . .. . .. .... .... . ........... ............... . . . . ..... . . ... . ........... . .... . ............. ............... .. .......... ........ .... . .. ............... ............... ...................... ......... . .............. ......... .... .. ......... .... . .... . . .... . . . .... .. . .. . ... . . ....... . .. . ....... . . ................................... . . . ........... . .. . ............. ............................. .. ............... ............................. ........................... .............. ..... . . .... . . .............. .. . .. .... . .... . . . .. .. . . . ... . ... ... . ... ................................... . ... .. . . .. . .. ... . .... . .. ..... ... . ...... ............ ......................... . ... . .... ..... .. . .... . .... ..... ... . ...... ..... ... . ..... ... . ... . . .. ...... ..... ... . ...... ..... ... . ..... ... . .............. ..... ..... ... . ..... ... . ... ...... ..... ... . ... . .. ... . . . ... . . . ... . .. ....... .. . ... . . .. ............................ . . . .............. ..... ... . ... . . ... . . . .. ... .. ........ .. .. . .... ... . ... .. . . .. . .. .... .... ...... ... . ............................. ........... ... ... . .............. . ... . ........... . .... . ............. ............................. .. ............... ............................. ............................ .............. ..... . ..... . .. .. .... ........................... .. ............ . ... . .. ...... .. ........ .. .. .... .... ... .. ..................... .. ..... .. .... ..... .... ... .. .... .. .. ..... ... .. ...... ..... ... .. ..... ... .. ... .. .. .. ... ..... ..... .. ...... ..... ..... ... .. ...... ..... ... .. ..... ... .. ... .. .. .. ...... ..... ... .. ...... ..... ... .. ..... ... .. ... ............ ..... ... .. ..... ... .. ... .. ........ ... .. ... .. .. ... .. .. .. ... .. .. .. . ... . ..... ... ....... .. .. . .. . ... .. . ... .... .. ..... ... ...... ..... ... ........ ... ... ... . .... ..... .. .... . .... ..... ... ...... ..... ... ..... ... ... .. ...... ..... ... ...... ..... ... ..... ... ... .. ..... ..... ... ..... ... ... ..... ... ... ... ... ........ ..... ...... ....... . .. .. . ... . .. . ........... . ... . ... . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... . ..... ..... ... ..... . . ... ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... . ... ..... ... ...... ..... ... . ...... ..... ... . ..... ... . ... . . ...... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . . . . ... ..... ... .. ...... .. .... ..... .. . . .. . ... . .... ..... ...... ... ...... ...... . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... . ..... ................. . ... ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... ... . ......... .. ...... ..... ... . ...... ..... ... . ..... ... . ... . .. ..... ..... ... . ..... ... . ... . . ..... ... . ... . . ... . . . ... . . . ... .. .. . ... . ... .. .. .. .. .. . .. ... . . ... . . ... . .. . . .. . . ... . ... ... .. .. ...... ....... . . . .... . ... . .... ..... ... . ... .. .... ......... . .................................... . .. . .. .. . . . .... .... ... .... .... . ......................... ..... ... . ..... ... . ... ..... . . ... ........... .. . .... ..... ..... ... . ...... ..... ... . ..... ... . ... ..... ... ...... ..... ... . ...... ..... ... . ..... ... . ... ..... ...... ..... ... . ..... ... . ... ..... ...... ... . ... ............ ..... ... . ... ..... ... . . ........... .. . ............. ............................. .. ............. ............................. ............................ .............. . ....... ....... ... . .. .... . ........... .. . ............. ............... ............. . . ........... . .... . ............. .. ............... ............................. ............... ......... .. ............... ............... ............................ ......... .............. ....................... ......... ..... . . .............. .. . .. ......... . ................................... . . .... .. .. ............... ......... . . .. . .............. .. ....... . . .... .. . . . ................................... . .. ..... ... ..... ... . ... . . ........................... ... . ... .. . . .. . .. ... . .... . .. ..... ... . ...... ............... ........................... . . . .... ..... .. . .... . .... ..... ... . ...... ............. ............................. .. ...... ..... ... . ...... ..... ... . ..... ... . .... . . ..... ..... ... . ..... ... . .............. ..... ... . ... ...... ... . .. . ... . .. . ..... . . . . ........... . .. ... ..... ... ..... ... . .. . . .. .. . ... .. .. ...... .. ...... . ... .. ..... ... .. ... . . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... .. ..... ...... ............... ...... ..... ... . ...... ..... ... . ..... ... . ... . . ..... ..... ... . ..... ... . ... ............ ... . ... . ...... . . . ... . . . . ... ... . . .......... . .. . ......... ... .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ........ ......... ... .. ........... . .... ....... .. .... . .... . . ........ . . ... .. . ..... .. ............. .... .... .............. ......... .... ......... .... . . . .. . .. . . . . . .. ... . .... . .. ..... ... . ...... ..... ... ....... .......... ..... . . . ..... ..... .. . .... ..... ..... ... . ...... ..... ... . ..... .......... ..... ... ...... ..... ... . ...... ..... ... . ..... ... . ... ..... ...... ..... ... . ..... ... . ... .... ...... ... . ... . . .... . . . ... . . . . . . .. . .. .............. . ...... . . .. . . .. ....... . . ................ .. ... .... .. .... ............... ............................. .. ............. ............................. ............................ .............. ..... . . .. .. .. .. .... .. .. . .. .... ...................................

We give the shape of some generated matrices. The matrices can have a very different structure and the number of non zero elements varies greatly. Upper left ?gure: From Matrix ( non zero) Upper right ?gure: application example: from [Fau98b] matrix ( non zero) Lower left ?gure: Example: engineering problem (Nuclear) matrix ( non zero)
? ? ?

22

%

%

%

E

E

E

$

The conclusion of Table 1 is that the old Gb is still faster than other systems, and that FGb Gb.

The following ?gure shows the performance results for the homogenization strategy and the af?ne strategy (the quotient “time to solve homog Cyclic ” divided “time to solve non homog Cyclic ” is plotted).
Comparison Homegeneous/ Non homogeneous
! !

We conclude that for small systems the difference is small but for big systems like Cyclic there is a huge difference (you add several components of dimension and ). For Cyclic the algorithm generates a matrix and it is times slower!
Cyclic n - Modulo p - DRL Groebner basis
6 h 10 m
? ?

PoSSo Asir Cocoa
1 h 50 m

Singular Macaulay 2 Gb

Maple 5.5
20 min

Magma

10 s C9

C6

C7

C8

23

?



 

? ? ?

?

B  % B

? ?



?



?

1000%

100% Cyclic 6 Cyclic 7 Cyclic 8 Cyclic 9 F 855

FGb

4.3 Integers
In the following table, we have included a special version of the the classical PoSSo Gr¨ bner o engine called “Rouil”, this version has been optimized by Fabrice Rouillier2. In the table we remove the Singular entry because Singular and Macaulay2 seem very close and very slow for big integers. Size is the size in digits of the biggest coef?cient in the output. Table 2 Academic Examples Z FGb Gb Singular 2.9 s 42 s 23 s 10m21s 3m3s 5h35m 31m24s Cyclic 6 0.3 s 3.2 s 5.3 s Hom 54.2s 1h32m 10h35m Cyclic 7 39.7s 5h17mb Cyclic 8 24m4s Cyclic 9 18 daysd
a b
? ? ? ? ? ?

5.4 s 25ma
? ?

134 Mbyte of data when stopped. Estimated from an original time of 24h26m40s on Sparc 10 with Lazard s algorithm. c 162 Mbyte of data when stopped. d The size of the result in binary is 1 660 358 088 bytes. Run on 512 Meg RAM PC.
22d 11h

Maple 5.5

Cyclic n - Big Integer - DRL Groebner Basis
FGb

8d 5h

1d 2h

Singular

Asir 3h 30m 30m 10s Axiom Cocoa Gb Magma

Macaulay 2

6
2

Posso (Rouillier)

7
?

8

The algorithm uses a prime to avoid syzygies. Then the algorithm checks that the result was correct. At the present state the implementation sometimes does not detect bad primes.

24

?

?

?

8s 2h50m 2hc
? ?

19.5 s

?

Rouil 50 s 8m23s 1h31m
?

Asir 3m28s 8m37s
?

Mac 2 Magma 10m56s 2h17m
?

2.6 s 2202s =

Size 53 102 133 192 96 96 96 202 800

?

?



?



§

$



§

?

?

?

§ § §

§

9

We observe that Magma is very ef?cient for big integers (in fact the Magma version for alpha workstations is even times faster). Cyclic- for big integers is an example of huge computation; we use: 3 Processors PPro 200 Mhz 512 Meg RAM + 1 Alpha 400 Mhz 570 Meg Total sequential CPU time: 18 days Size of the ?le of coef?cients in the output (binary): 1660 Meg The result contains: 1344 polynomials with 1000 monomials and 800 digits numbers !
?
?

This success is also a failure in some sense: the size of the output is so big that we cannot do anything with this result. That is to say we are now near to the intrinsic complexity of Gr¨ bner o bases. On the other side, the output is very big because the coef?cients are big and ?oating point computation would not suffer from this exponential growth. We conclude that for all these examples FGb Gb and that it faster than other systems.

5 Final remarks
The conclusion is that is at least one order of magnitude faster than all previously implemented algorithms. We recall the main features of this algorithm are: Replace all the previous strategies (sugar([Gio91]), . . . ) by algorithms for (sparse) linear algebra. It explains why the usual strategies in Buchberger algorithm could not be optimal. Faster for all kind of arithmetic (modular computation, integers, “generic” computation) In some sense it is as fast as possible for big integers coef?cients or coef?cients with parameters ( ) because the practical complexity is almost linear in the size of the output coef?cients: in the case of homogeneous polynomials the complexity of is where is the size of othe result and is the time needed for modular computation which is generally much smaller. For homogeneous systems the algorithm generate reduction to zero or non zero polynomials (completely reduced) which are all in the ?nal Gr¨ bner basis. So the algorithm does o not generate “parasite” intermediate data. Very good experimental behavior for non homogeneous systems (several times faster than the corresponding homogeneous system). Parallel versions of the algorithm can be implemented (we have done a ?rst implementation). 25
¤ ?
3 
?

?



%

     ?

¤ ?

%

 ?

3



? ?

?



? ? ? ? ? ? ? ? ? ?

A lot of work remains to do in the linear algebra part to apply less naive algorithms to the generated matrices and to compress more ef?ciently those matrices. Considerable works must also be done to compare the algorithm with different possible strategies (sugar and homogenizing, multi-weight in the case of multi-homogeneous ideals might reduce the size ot the matrices (as suggest by D. Lazard and one anonymous referee)). How to use the symmetry of the problems to handle more ef?ciently the matrices is also an open problem. Even if the algorithm presented in this paper is heavily connected with the Buchberger algoritm (use the same criteria for useless pairs), we think that an interesting work would be to use Mandache [Man94, Man96]’s technique to check that is not a Buchberger algorithm in the sense that the Buchberger algorithm cannot simulate the new algorithm for any strategy. When the normal strategy is used, we can plot the function ; we obtain an increasing function for homogeneous systems but in the af?ne case we obtain different curves:
 

Cyclic – Total degree of critical pairs
?

El – Total degree of critical pairs An open issue is to understand deeply the shape of this curves.

Acknowledgements
We would like to thank Daniel Lazard and one anoymous referee for their comments on drafts of this paper. I also want to acknowledge M. Stillman and D. Bayer for helpful suggestions and encouragement. We would like to thank the UMS 658 Medicis.

References
[Alv] Alvarado F.L. and Pothen A. and Schreiber R. Highly Parallel Sparse Triangular Solution. preprint.

[Alv93] Alvarado F.L. The Sparse Matrix Manipulation System User and Reference Manual. University of Wisconsin, May 1993. 26

?

§

?

§

? ?



  A)

?

§

0 

¤? ?

¤ ?

¨§ ?

? ?

The algorithm is easier to implement (no polynomial arithmetic is required, do not need an ef?cient power product (exponents) implementation). It can solve previously intractable problems: we are now able to compute easily three new records: Cyclic for modular coef?cients (4h30), Cyclic for big integers coef?cients (25 mins) and the very challenging Cyclic for bignum coef?cients (18 days of CPU time).

[Att96]

Attardi G. and Traverso C. Homogeneous Parallel Algorithm. Journal of Symbolic Computation, 1996.

[Bec93] Becker T. and Weispfenning V. Groebner Bases, a Computationnal Approach to Commutative Algebra. Graduate Texts in Mathematics. Springer-Verlag, 1993. [Bin94] Bini D. and Pan V. Polynomial and Matrix Computations, volume 1 of Progress in theoretical computer science. Birk¨ user, 1994. Fundamental Algorithms. a

[Buc65] Buchberger B. Ein Algorithmus zum Auf?nden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck, 1965. [Buc70] Buchberger B. An Algorithmical Criterion for the Solvability of Algebraic Systems. Aequationes Mathematicae, 4(3):374–383, 1970. (German). [Buc79] Buchberger B. A Criterion for Detecting Unnecessary Reductions in the Construction of Gr¨ bner Basis. In Proc. EUROSAM 79, volume 72 of Lect. Notes in Comp. Sci., o pages 3–21. Springer Verlag, 1979. [Buc85] Buchberger B. Gr¨ bner Bases : an Algorithmic Method in Polynomial Ideal Theory. o In Reidel, editor, Recent trends in multidimensional system theory. Bose, 1985. [Can98] Cannon J. The Magma Computational Algebra System 2.20-7, Feb 1998. http://www.maths.usyd.edu.au:8000/u/magma/. [Cha91] Char B. and Geddes K. and Gonnet G. and Leong B. and Monagan M. and Watt S. Maple V Library Reference Manual. Spinger-Verlag, 1991. Third Printing, 1993. [Dav95] Davis T. Users’ Guide for the Unsymmetric-pattern MultiFrontal Package. Computer and Information Sciences Department University of Florida, January 1995. Technical Report TR-95-004. [Dix82] Dixon J.D. Exact solution of linear equations using p-adic expansions. Numer.Math., 40:137–141, 1982. [Don] Dongarra J. and Lumsdaine A. and Niu X. and Pozo R. and Remington K. A Sparse matrix Library in C++ for High Performance Architectures. preprint.

[Duf84] Duff I.S. and Reid J.K. The multifrontal solution of unsymmetric sets of linear equations. SIAM J. Sci. Statist. Comput., 5(3):633–641, 1984. [Faua] [Faub] Faug` re J.C. e Benchmarks for polynomial solvers. http://posso.lip6.fr/?jcf/benchs.html. Faug` re J.C. e On line documentation of Gb. http://posso.lip6.fr/?jcf. 27 avalaible on the WEB avalaible on the WEB

[Fau98a] Faug` re J.C. Computing Gr¨ bner Basis without reduction to zero (F5). Technical e o report, LIP6 report, 1998. in preparation. [Fau98b] Faug` re J.C. and Moreau de Saint-Martin F. and Rouillier F. Design of nonseparable e bidimensional wavelets and ?lter banks using Gr¨ bner bases techniques. IEEE SP o Transactions on Signal Processing, 46(4), 1998. Special Issue on Theory and Applications of Filter Banks and Wavelets. [Fro96] Fronville A. Singularit? r? siduelle et Probl` me du centre. PhD thesis, Universit? Paris e e e e 6, D? cembre 1996. e

[Geo81] George A. and Liu J. W. H. Computer solution of large sparse positive de?nite systems. Englewood Cliffs, N.J. : Prentice-Hall, 1981. [Geo93] George A. and Gilbert J.R. and Liu J. W. H. Graph theory and sparse matrix computation. New York : Springer-Verlag, 1993. [Ger95] Gerdt V.P. Involutive Polynomial Bases. In PoSSo on software. Paris, F, 1995. [Gio91] Giovini A. and Mora T. and Niesi G. and Robbiano L. and Traverso C. One sugar cube, please, or Selection strategies in the Buchberger Algorithm. In S. M. Watt, editor, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation. ISSAC’ 91, ACM Press, 1991. [GM88] R. Gebauer and H.M. M¨ ller. On an Installation of Buchberger’s Algorithm. Journal o of Symbolic Computation, 6(2 and 3):275–286, October/December 1988. [Gra97] Grayson D. and Stillman M. Macaulay http://www.math.uiuc.edu/Macaulay2/. 2 User Manual, 1997.

[Gre97] Greuel G.-M. and P?ster G. and Schoenemann H. SINGULAR 1.0.2, July 1997. http://www.mathematik.unikl.de/?zca/Singular/Welcome.html. [Hea] [Kal91] Heath M.T. and Raghavan P. Distributed Solution of Sparse Linear Systems. preprint. Kaltofen E. On Wiedemann’s Method of Solving Sparse Linear Systems. LNCS, 539:29–38, 1991. AAECC-9.

[Knu81] Knuth D.E. The Art of Computer Programming, volume 2. Addison Wesley, 2 edition, 1981. [L.69] Massey J. L. Shift-register synthesis and bch decoding. IEEE Trans. on Information Theory, 15(1):122–127, January 1969.

[LaM91] LaMacchia B.A. and Odlyzko A.M. Solving Large Sparse Linear Systems Over Finite Fields. LNCS, 537, 1991. Advances in Cryptology, CRYPTO’90. 28

[Laz79] Lazard D. Systems of Algebraic Equations. In EUROSAM 79, pages 88–94, 1979. [Laz81] Lazard D. Resolution des systemes d’equations algebriques. Theor. Comp. Science, 15:77–110, 1981. [Laz83] Lazard D. Gaussian Elimination and Resolution of Systems of Algebraic Equations. In Proc. EUROCAL 83, volume 162 of Lect. Notes in Comp. Sci, pages 146–157, 1983. [Lom98] Lombardi H. Un nouvel algorithme de calcul d’une Base de Gr¨ bner. Technical report, o Equipe de Math? matiques de Besan? on, Janvier 1998. e c [Man94] Mandache A.M. . The Gr¨ bner Basis Algorithm and Subresultant Theory. In Proceedo ings of ISSAC’94, pages 123–128. Oxford, UK, ACM press, July 1994. [Man96] Mandache A.M. A note on the relationship between involutive bases and Gr¨ bner o bases . Mega 96, 1996. [Mon95] Montgomery P. A Block Lanczos Algorithm for Finding Dependencies over GF(2). LNCS, pages 106–120, May 1995. [Pey] [Rei71] Peyton B.W. and Pothen A. and Yuan X. Partitioning a Choral Graph into Transitive Subgraphs for Parlallel Sparse Triangular Solution. preprint. Reid J.K. Large Sparse Sets of Linear Equations. Academic Press . London and New York, 1971.

[Ros72] Rose D. and Willoughby R.A. Sparse Matrices and their applications. Plenum Press, 1972. [S.R71] S.R. Petrick, editor. Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation. ACM Press, March 23-25 1971. [Sti89] Stillman M. and Bayer D. Macaulay User Manual, 1989. available via anonymous ftp on zariski.harvard.edu.

[Tak96] Takeshima T. Risa/Asir. FUJITSU LABORATORIES LIMITED, 1996. Vers 950831. available from ftp://endeavor.fujitsu.co.jp/pub/isis/asir. [Tra97] Traverso C. Groebner Engine. Rel. http://janet.dm.unipi.it/posso\_demo.html. 2.0, 1997.

[Van93] Van der Stappen A.F. and Bisseling R.H. and Van de Vorst J.G.G. Parallel Sparse LU Decomposition on a mesh network of transputers. SIAM J. Matrix ANAL. APPL., 14(3):853–879, July 1993. [Wie86] Wiedemann D. Solving Sparse Linear Equation Over Finite Fields. IEEE Transaction on Information Theory, IT-32(1), January 1986.

29


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图