Comparison of theoretical complexities of two methods for computing annihilating ideals of polynomials

COMPARISON OF THEORETICAL COMPLEXITIES OF TWO METHODS FOR COMPUTING ANNIHILATING IDEALS OF POLYNOMIALS J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ Abstract. Let f1,...,fpbe polynomials in C[x1,...,xn] and let D=Dn be the n-th Weyl algebra. We provide upper bounds for the complexity of computing the annihilating ideal of fs=fs1 1 ···fsp pin D[s] = D[s1,...,sp]. These bounds provide an initial explanation on the differences between the running times of the two methods known to obtain the so-called Bernstein- Sato ideals. 1. Introduction Fix two integers n≥1, p ≥1 and two sets of variables (x1, . . . , xn) and (s1, . . . ,sp). Let us consider f1, . . . , fp∈C[x] = C[x1, . . . , xn] and let D=Dnbe the n-th Weyl algebra. A polynomial b(s)∈C[s] = C[s1, . . . , sp] is said to be a Bernstein-Sato polynomial associated to f1, . . . , fpif the following functional equation holds for a certain P(s)∈D[s]: b(s)fs=P(s)fs+1, where fs=fs1 1· · · fsp pand 1= (1,...,1). These polynomials form an ideal called the Bernstein-Sato ideal, noted Bfor simply Bif no confusion arises. Analogous functional equations with respect to vectors different from 1yield other versions of Bernstein-Sato ideals (see for example [Bahloul(2001)]). In [Lichtin(1988)] it is proved that Bis not zero. This fact is a generalization of the classical proof of Bernstein ([Bernstein(1972)]) in the algebraic setting for the case p= 1, in which Bis generated by the so-called Bernstein-Sato polynomial noted bf(s). The analytical case was covered in [Bj¨ork(1973)] for p= 1 and [Sabbah(1987a)] and [Sabbah(1987b)] for p > 1 (an interesting new proof using the Gr¨obner fan has been given in [Bahloul(2005)]). The roots of bf(s) encode important algebro-geometrical data (see [Malgrange(1974)], [Hamm(1975)] or [Budur-Saito(2003)] to mention only a few) and a complete understanding of all roots for a general fis open. The case p > 1 seems to be much more complex and there are conjectures on the primary decomposition of B, on the conditions over f for Bto be principal, etc. (see for example [Maynadier(1996)]). Until [Oaku(1997)] there were no algorithms to find the Bernstein-Sato polynomial. Since then, alternative methods have been proposed to obtain Bin the general case (see [Oaku and Takayama(1999)], [Bahloul(2001)] and [Brian¸con and Maisonobe(2002)]). These methods have a feature in common: their first step is the computation of the annihilating ideal of fsin D[s], AnnD[s]fs. In [Castro-Ucha(2004)] some experimental evidences were given in favor of the method of Brian¸con-Maisonobe (BM) Key words and phrases. Complexity, Poincar´e-Birkhoff-Witt algebras, Bernstein-Sato ideals. All authors partially supported by MTM2004-01165 and FQM-333. 1 2 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ to compute AnnD[s]fswith respect to the method of Oaku-Takayama (OT), but no clues about which facts support this advantage were provided. Our work is a first step in order to compare theoretically both methods. We give upper bounds for the complexity of computing AnnD[s]fs, the previous requirement for both algorithms. To obtain these bounds we use the techniques and results of [Grigoriev(1990)] on the complexity of solving systems of linear equations over rings of differential operators. These extend the classical polynomial case treated in [Seidenberg(1974)]. In particular, we show that Grigoriev’s construction can not be directly generalized to the algebra proposed by Brian¸con-Maisonobe. We prove that the complexity of computing AnnD[s]fsusing the method BM is that of the calculation of a Gr¨obner basis in the n-th Weyl algebra with some extra p commutative variables, so 2n+pvariables at most. On the other hand, in the case of the method OT the calculation of such a basis is made in a (n+p)-th Weyl algebra with some extra 2pvariables, so 2n+ 4pvariables altogether. It is an open problem to know whether the bound proposed in this work is reached `a la Mayr-Meyer ([Mayr-Meyer(1982)]), that is to say, whether an example with this worst complexity can be explicitly obtained. Such an example would mean a complete answer to the question of which is the complexity of computing AnnD[s]fs, proposed by Professor N. Takayama. 2. Preliminaries In this section we just remind briefly some details of the methods of Brian¸con- Maisonobe and Oaku-Takayama. 2.1. Method of Brian¸con-Maisonobe. In this case the computations are made in the non-commutative algebra1 R=D[s, t] = D[s1, . . . , sp, t1, . . . , tp], an extension of the n-th Weyl algebra Din which the new variables s, t satisfy the relations [si, tj] = δijti.It is a Poincar´e-Birkhoff-Witt (PBW) algebra: Definition 1. A PBW algebra Rover a ring kis an associative algebra generated by finitely many elements x1, . . . , xnverifying the relations Q={xjxi=qjixixj+pji,1≤i<j≤n}, where each pji is a finite k-linear combination of standard terms xα=xα1 1· · · xαn n and each qji ∈kverifying the two following conditions: (1) There is an admissible2ordering ≺on Nnsuch that exp(pji)≺exp(xjxi) for every 1 ≤i<j≤n. (2) The standard terms xα, with α∈Nn, form a k-basis of Ras a vector space. It is possible to compute Gr¨obner bases in PBW algebras. The book [Bueso et al.(2003)] is a good introduction to the subject of effective calculus in this fairly general family. The following algorithm computes B, starting from I:= AnnR(fs) = hsj+fjtj, ∂i+X j ∂fj ∂xi tj,1≤i≤n, 1≤j≤pi. 1It is, in fact, the ring introduced in classical works by Malgrange and Kashiwara for p= 1. 2Here admissible means a total ordering among the elements of Nnwith 0as smallest element. COMPLEXITY OF AnnD[s]fs3 Algorithm 2.1.(1) Obtain J=AnnDn[s]fs=hG1∩Dn[s]iwhere G1is a Gr¨obner basis of Iwith respect to any term ordering where variables tjare greater than the others (that is, an elimination ordering for the tj.) (2) B= (hG2i+hf1, . . . , fpi)∩C[s]i, where G2is a Gr¨obner basis of Jwith respect to any term ordering with xi, ∂jgreater than sl, for all i, j, l. 2.2. Method of Oaku-Takayama. All the computations are made in Weyl algebras. More precisely, we start from I0=htj−fj, p X j=1 ∂fj ∂xi ∂tj+∂i, i = 1, . . . , n, j = 1, . . . , pi Algorithm 2.2.(1) Obtain J0=I0TC[t1∂t1, . . . , tn∂tn]hx, ∂xi. (2) J=AnnDn[s](fs) = J00, where J00 denotes the ideal generated by the generators of J0after replacing each ti∂tiby −si−1. (3) B= (hG2i+hf1, . . . , fpi)∩C[s]i, where G2is a Gr¨obner basis of Jwith respect to any term ordering with xi, ∂jgreater than sl, for all i, j, l.. Remark 1.The second step above is, as in Algorithm 2.1, the elimination of all the variables but (s1, . . . , sp). Often the bottleneck to obtain the Bernstein-Sato ideal is this step. As far as we know, the example for p= 2 with f1=x2+y3, f2=x3+y2 is intractable for the available computer algebra systems. The computation of I0∩C[t1∂t1, . . . , tn∂tn]hx, ∂xi uses 2n+ 4pvariables, as new variables uj, vjfor 1 ≤j≤pare introduced. More precisely, the main calculation is an elimination of these new variables for the ideal htj−ujfj, p X j=1 ∂fj ∂xi uj∂tj+∂i,1−ujvj,1≤i≤n, 1≤j≤p, i. 3. Complexity In [Grigoriev(1990)] a bound for the degree of the solutions of a general system of linear equations over the Weyl algebra is given, with a procedure somewhat similar to the one of [Seidenberg(1974)]. In this section we shall see how much of the work of Grigoriev is applicable to our PBW algebra Rof 2.1. The construction has two different steps. In the first, the given system is reduced to another system in a diagonal form. In the second, it is shown how to normalize the new system in order to eliminate, successively, the variables. We need a technical lemma to reduce the system to a diagonal form. This lemma comes from Grigoriev’s paper (see [Grigoriev(1990), Lemma 1]), but we will write it in a more general way. Here deg means the total degree of a term, that is, the sum of the exponents of all of its variables. Lemma 1. Let Abe a (m−1)×mmatrix with entries in a Poincar´e-Birkhoff-Witt algebra Swith a basis of pelements. If deg(aij)≤d, there exists a nonzero-vector f= (f1, . . . , fm)∈Smsuch that Af = 0 and deg(f)≤2p(m−1)d=N. Proof. Consider the linear space T⊂Smof vectors c= (c1, . . . , cm)∈Smsuch that deg(c)≤N. We have dim(T) = N+p pm. For any vector c∈Tit 4 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ is clear that deg(Ac)≤N+d. If we consider now the vector space γof vectors e= (e1, . . . , em−1)∈Sm−1such that deg(e)≤N+d, we have dim(γ) = N+d+p p(m−1). We prove that dim(γ)<dim(T). N+d+p p/N+p p= N+d+p N+p N+d+p−1 N+p−1· · · N+d+ 1 N+ 1 ≤N+d+ 1 N+ 1 p . It is enough to see (N+d+1 N+1 )p<1 + 1 m−1. This inequality follows from: 1 + 1 m−11 p >1 + 1 p(m−1) +1 2 1 p1 p−1 1 m−12 > >1 + 1 2p(m−1) >1 + d N+ 1  If we work in a noetherian domain (not necessarily commutative), we can always define the rank of a finite module as in [Stafford(1978)]. Given a square matrix in a Poincar´e-Birkhoff-Witt algebra we say that it is non-singular if it has maximal rank. In this case we can obtain a left quasi-inverse with the previous lemma: Lemma 2. Given a m×mnon-singular matrix Bover a PBW algebra Sas in Lemma 1, it has a left quasi-inverse matrix Gover S, such that deg(G)≤N. Proof. There is no vector b6= 0, in Rmsuch that bB = 0. If we consider the matrix B(i)obtained from Bdeleting its i-th column, using Lemma 1 we obtain a vector gi6= 0 such that giB(i)= 0 and deg(gi)≤N, so the matrix Gwhich has gias its i-th row, for i= 1, . . . , m, is a left quasi-inverse of B. Lemma 3. Given a system of linear equations over a PBW algebra defined by a m×smatrix Aof rank rwith its elements deg(aij)≤d, we can always construct a matrix Cthat defines an equivalent system, and such that (1) CA =C10 C2EA=     a10 ... 0ar ? 0 0      where Eis the identity matrix. Proof. C1is the left quasi-inverse of the submatrix of Aof maximal rank r(after reordering the rows or columns of Aif it were necessary). C2is constructed with the requirement on the left lower corner to be zero. The right lower corner is zero by the definition of rank.  Thanks to this lemma, we can assume that our system is equivalent to a system in diagonal form: akVk+X r+1≤l≤s ak,lVl=bk,1≤k≤r, deg(ak),deg(ak,l),deg(bk)≤2pmd. COMPLEXITY OF AnnD[s]fs5 Once the system is in diagonal form, we need to normalize it. To do this, we construct some syzygies, applying Lemma 1 to the submatrix of the first rcolumns and the column l > r. There always exist h(l), h(l) 1, . . . , h(l) rsuch that: akh(l) k+ak,lh(l)= 0,1≤k≤rdeg(h(l)),deg(h(l) i)≤4p2m2d The result that gives the normalization in the Weyl algebra is the following one: Lemma 4 ([Grigoriev(1990)], Lemma 4).Given g1, . . . , gt∈Da family of elements, there is a nonsingular linear transformation of 2n-dimensional space with basis x1, . . . , xn, ∂1, . . . , ∂nunder which: xi→Γxi= n X j=1 γ(1,1) i,j xj+ n X j=1 γ(1,2) i,j ∂j; ∂i→Γ∂i= n X j=1 γ(2,1) i,j xj+ n X j=1 γ(2,2) i,j ∂j such that the following relations hold: ΓxiΓ∂i= Γ∂iΓxi−1; ΓxiΓxj= ΓxjΓxi; Γ∂iΓ∂j= Γ∂jΓ∂i; Γ∂iΓxj= ΓxjΓ∂i, i 6=j, and if we denote by Γgithe transformed of giwith the indicated linear transformation, we have Γgi=∂deg(gi) n+f Γgi. Remark 2.The main fact in the proof of Lemma 4 is that the matrices of the linear transformations defined by the relations in the Weyl algebra are a transitive group. Let us see why we can not assure the existence of such a normalization lemma to every PBW algebra. If we consider the PBW algebra defined by Brian¸con and Maisonobe for p= 1, that is R=C[s, t, x1, . . . , xn, ∂1, . . . , ∂n], a general linear transformation as the one appearing in Lemma 4 has the form: s→Γs=α1s+β1t+Pn j=1 γ(s,1) jxj+Pn j=1 γ(s,2) j∂j t→Γt=α2s+β2t+Pn j=1 γ(t,1) jxj+Pn j=1 γ(t,2) j∂j xi→Γxi=α(1) is+β(1) it+Pn j=1 γ(1,1) i,j xj+Pn j=1 γ(1,2) i,j ∂j ∂i→Γ∂i=α(2) is+β(2) it+Pn j=1 γ(2,1) i,j xj+Pn j=1 γ(2,2) i,j ∂j and it has to verify the following relations: (1) ΓsΓt= ΓtΓs+ Γt; (2) ΓsΓxi= ΓxiΓs; (3) ΓsΓ∂i= Γ∂iΓs; (4) ΓtΓxi= ΓxiΓt; (5) ΓtΓ∂i= Γ∂iΓt; (6) ΓxiΓ∂i= Γ∂iΓxi−1; (7) ΓxiΓxj= ΓxjΓxi; (8) Γ∂iΓ∂j= Γ∂jΓ∂i; (9) ΓxiΓ∂j= Γ∂jΓxi From relation (1), we obtain α2=γ(t,1) j=γ(t,2) j= 0 for all j, so Γt=β2t. The transformation must be nonsingular, so we must have β26= 0,and again using (1) we deduce that α1= 1. Using (4), we obtain that α(1) i= 0 for all i. This, together with (5) implies that α(2) i= 0 for all i. 6 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ From relation (2) (Γscommutes with Γxi) we have β(1) i= 0, and relation (3) gives β(2) i= 0. Due to relations (6) to (9) (between Γxiand Γ∂j) we have that the submatrix γ(1,1) i,j γ(1,2) i,j γ(2,1) i,j γ(2,2) i,j ! verifies the relations of Lemma 4, and in addition, from the relations with Γsit verifies Xγ(s,1) iγ(1,2) i,i =Xγ(s,2) iγ(1,1) i,i Xγ(s,1) iγ(2,2) i,i =Xγ(s,2) iγ(2,1) i,i . So it is clear that we can not normalize with respect to the variables in R. Thus we can not repeat the second step of the process to a general PBW algebra in the way that it appears in [Grigoriev(1990)]. It is an open problem to obtain a general bound for the solutions of a general linear system over any PBW algebra or, at least, to give such a bound for R. We give up on this general problem at this point: with the aim of obtaining a bound for the complexity of the annihilating ideal of fs, we will treat only the particular case of one equation of the type produced by the definition of the ideal Iin section 2.1 or I0in section 2.2. In both cases we want to measure the complexity of computing Gr¨obner bases (in different rings) and we will do it by considering the equivalent problem of computing the syzygies of the generators of our respective ideals. Remark 3.In OT algorithm the calculations are computed in a Weyl algebra of 2n+ 4pvariables, or more precisely in a commutative polynomial ring with n+ 3p, (x, u, v, t) commutative variables extended with n+p, (∂x, ∂t) “differential” variables. Let us denote by Athis algebra. The complexity of computing the annihilating ideal of fsis bounded by the complexity of computing a Gr¨obner basis in A. Recall that the complexity in the Weyl algebra is given by the following theorem: Theorem 1 (Th. 6,[Grigoriev(1990)]).Given a solvable system in the Weyl algebra Dn:X 1≤l≤s uk,lVl=wk,1≤k≤m with deg(uk,l),deg(wk)≤d. There exists a solution with deg(Vl)<(md)2O(n) As we said before in the Brian¸con-Maisonobe ring Rwe can not construct a similar algorithm to bound the degree of a solution for a system in general. But in our very special case, our problem is equivalent to computing the solutions of the equation: (s1+f1t1)V1+. . . + (sp+fptp)Vp+ (∂1+X j ∂fj ∂x1 tj)Vp+1 +. . . + (∂n+X j ∂fj ∂xn tj)Vp+n= 0 To simplify notation we write the precedent equation as PlQlVl= 0. Theorem 2. Given f= (f1, . . . , fp), the computation of the annhilating ideal of fs in the Brian¸con-Maisonobe algebra R=D[s1, . . . , sp, t1, . . . , tp]can be reduced to the computation of the syzygies of the generators ∂i+Pj ∂fj ∂xitjin the Weyl algebra D[t1, . . . , tp]. COMPLEXITY OF AnnD[s]fs7 Proof. Trying to repeat Grigoriev’s ideas, the first step is the reduction of the system to one in diagonal form. Due to the fact that we have only one equation this step is done. Then, we need to compute h(l) 1, h(l)for 2 ≤l≤n+psuch that: (s1+f1t1)h(2) 1+ (s2+f2t2)h(2) = 0 . . . (s1+f1t1)h(p) 1+ (sp+fptp)h(p)= 0 (s1+f1t1)h(p+1) 1+ (∂1+Pj ∂fj ∂x1tj)h(p+1) = 0 . . . (s1+f1t1)h(p+n) 1+ (∂n+Pj ∂fj ∂xntj)h(p+n)= 0 It is easy to see that [si+fiti, sj+fjtj]=0 [si+fiti, ∂j+X l ∂fl ∂xj tl] = si(X l ∂fl ∂xj tl) + fiti∂j−∂jfiti−(X l ∂fl ∂xj tl)si= =tisi ∂fi ∂xj +ti ∂fi ∂xj +X l6=i tlsi ∂fl ∂xj +tifi∂j−tifi∂j−ti ∂fi ∂xj −X l ∂fl ∂xj tlsi= 0 and we obtain h(l)=s1+f1t1for all l≥2. These are the elements we need to normalize, and they are almost in normal form with respect to the variable s1. This form is required to make the division of the solutions Vl,l≥2 by h(l)with respect to a lexicographical ordering with leading term s1. We obtain a remainder ¯ Vlsuch that degs1(¯ Vl)<degs1(h(l)) = 1, so s1does not appear in ¯ Vl. So Vl=h(l)¯ ¯ Vl+¯ Vl, and adding the relation Q1h(l) 1+Qlh(l)= 0 multiplied by −¯ ¯ Vlto our initial equation, we obtain: Q1¯ V1+Q2¯ V2+· · · +Qn+p¯ Vn+p= 0 with Qi,¯ Viwithout s1for i≥2, so ¯ V1= 0, where ¯ V1=V1−h(2) 1¯ ¯ V2−· · ·−h(n+p) 1¯ ¯ Vn+p. We have then the new equation: Q2¯ V2+· · · +Qn+p¯ Vn+p= 0 in a Brian¸con-Maisonobe algebra C[s2, . . . , sp, t1, . . . , tp, x, ∂]. Repeating the process for Q2, . . . , Qp, we reduce our problem to solving: (∂1+X j ∂fj ∂x1 tj)Vp+1 +. . . + (∂n+X j ∂fj ∂xn tj)Vp+n= 0 in the Weyl algebra D[t1, . . . , tp].  Remark 4.As a consequence of Theorem 2, the bound for the complexity of computing the annihilating ideal of fsin Ris bounded by the complexity of computing a Gr¨obner basis in a Weyl algebra with 3pvariables less that the one required by OT method. Although the complexity of computing these objects in any case is known to be double exponential (with respect to the number of variables and the total degree of the generators of the ideal) by Theorem 1, it is clear that the reduction of 3pvariables in BM method is a significant advantage, both theoretically and in practice as it is shown in the examples (see [Castro-Ucha(2004)]). 8 J. GAGO-VARGAS, M.I. HARTILLO-HERMOSO, AND J.M. UCHA-ENR´ IQUEZ Table 1. CPU times for the computation of Annfs fBrian¸con-Maisonobe’s method Oaku-Takayama’s method x3+xy2+z2<0.01s 0.39s x4+y3+z2<0.01s 0.39s yx3+y3+z20.06s 3.97s x3+y2+z2<0.01s 0.02s x5+y2+z2<0.01s 4.66s x7+y2+z2<0.01s 298.56s x4+y5+xy40.56s E(>12h) Table 2. CPU times for the computation of Annfs1 1fs2 2 f1f2Brian¸con-Maisonobe’s method Oaku-Takayama’s method x3+y2x2+y30.72s 6363.97s x5+y3x3+y53.53s E(>6h) x7+y5x5+y711.84s E(>6h) x3+y2xz +y < 0.01s 9.73s x5+y2xz +y < 0.01s 1568.59 s x11 +y5xz +y3s E(>6h) Table 3. CPU times for the computation of Annfs1 1· · · fsp p f1f2f3Brian¸con-Maisonobe’s method Oaku-Takayama’s method x+y x −y x2+y < 0.01s29.46s x+y x2+y x +y22.64s E x+y x2+y x2+y3116.24s E x+y x2+y x3+y21728.41s E 4. Appendix: Experimental Data In the tables we give some examples for which it is clear the superiority of Brian¸con-Maisonobe’s method. They have been tested3using Singular::Plural 2.1 (see [Greuel et al.(2003)]) in a PC Pentium IV, 1Gb RAM and 3.06GHz running under Windows XP. Singular::Plural 2.1 is a system for non-commutative general purpose, so the calculations in our algebras are not supposed to be optimal. We present the following data only for the sake of comparing both methods in the same system. In the case of [Brian¸con and Maisonobe(2002)] method we have used a pure lexicographical ordering, while for [Oaku and Takayama(1999)] we have used typical elimination ordering. These are the orderings with best results for each case. References [Bahloul(2001)] Bahloul, R. Algorithm for computing Bernstein-Sato ideals associated with a polynomial mapping. Journal of Symbolic Computation 32, 643–662, 2001. 3The CPU times must be considered as approximations: as it is explained in the Singular::Plural 2.1 Manual, the command timer is not absolutely reliable due to the shortcomings of the Windows operating system. COMPLEXITY OF AnnD[s]fs9 [Bahloul(2005)] Bahloul, R. D´emonstration constructive de l’existence de polynˆomes de Bernstein- Sato pour plusieurs fonctions analytiques. Compositio Math. 141, no. 1, 175–191, 2005 (to appear). [Bernstein(1972)] Bernstein, I.N. The analytic continuation of generalized functions with respect to a parameter. Funct. Anal. 6273–285, 1972. [Bj¨ork(1973)] Bjork, J.E. Dimensions over Algebras of Differential Operators. Preprint, 1973. [Brian¸con and Maisonobe(2002)] Brian¸con, J. and Maisonobe, Ph. Remarques sur l’id´eal de Bernstein associ´e `a des polynˆomes. PUMA, 650 (preprint). 2002. [Budur-Saito(2003)] Budur, N. and Saito M. Multiplier ideals, V-filtration and spectrum. arXiv:math.AG/0305118, 2003. [Bueso et al.(2003)] Bueso, J.L. Gom´ez-Torrecillas, J. and Verschoren, A. Algorithmic methods in non-commutative algebra. Applications to quantum groups. Mathematical modelling. Theory and applications 17, Kluwer Academic Publishers. 2004. [Castro-Ucha(2004)] Castro-Jim´enez, F.J. and Ucha-Enr´ıquez, J.M. On the computation of Bernstein-Sato ideals. J. Symbolic Comput. 37(5), 629–639. 2004. [Greuel et al.(2003)] G.-M. Greuel, V. Levandovskyy, and H. Sch¨onemann. Singular::Plural 2.1. A Computer Algebra System for Noncommutative Polynomial Algebras. Centre for Computer Algebra, University of Kaiserslautern (2003). http://www.singular.uni-kl.de/plural. [Grigoriev(1990)] Grigoriev, D. Complexity of solving systems of linear equations over the rings of differential operators. In Effective methods in algebraic geometry (Castiglioncello, 1990), Progr. Math., 94. Birkhauser Boston, MA 195–202. 1991. [Hamm(1975)] Hamm, H.A. Remarks on asymptotic integrals, the polynomial of I.N. Bernstein and the Picard-Lefschetz monodromy. In Several complex variables (Proc. Sympos. Pure Math. Vol XXX, Part 1, Williams Coll., Williamstown, Mass. 1975), 31–35. Amer. Math. Soc., Providence, R.I. 1977. [Kashiwara(1976)] Kashiwara, M. B-functions and holonomic systems. Rationality of roots of B- functions. Invent. Math. 38 (1) 33–53. 1976. [Lichtin(1988)] Lichtin, B. Generalized Dirichlet series and b-functions. Compositio Math 65 81– 120. 1988. [Malgrange(1974)] Malgrange, B. Le polynˆome de Bernstein d’une singularit´e isol´ee. In Fourier integral operators and partial differential equations (Colloq. Internat., Univ. Nice, Nice, 1974). Lecture Notes in Math. 459 Springer–Verlag, New York 98–119. 1975. [Maynadier(1996)] Maynadier, H. Equations fontionnelles pour une intersection complete quasihomog`ene `a singularit´e isol´ee et un germe semi-quasi-homog`ene, Th`ese, Nice-sophia Antipolis, 1996. [Mayr-Meyer(1982)] Mayr, E.W. and Meyer, A.R. The complexity of the word problems for commutative semigroups and polynomial ideals. Adv. in Math. 46(3), 305–329. 1982. [Oaku(1997)] Oaku, T. An algorithm of computing b-functions. Duke Math. J. 87 115–132 1997. [Oaku and Takayama(1999)] Oaku, T. Takayama, N. An algorithm for de Rham cohomology groups of the complement of an affine variety via D-module computation. Journal of Pure and Applied Algebra 139 201–233 1999. [Sabbah(1987a)] Sabbah, C. Proximit´e ´evanescente I. La structure polaire d’un D-Module. Apendice en collaboration avec F.J. Castro Jim´enez. Compositio Math. 62, 283–328. 1987. [Sabbah(1987b)] Sabbah, C. Proximit´e ´evanescente II. Equations fonctionelles pour plusieurs fonctions analytiques. Compositio Math. 64, 213–241. 1987. [Seidenberg(1974)] Seidenberg, A. Constructions in algebra. Trans. Amer. Math. Soc. 197 273– 313. 1974. [Stafford(1978)] Stafford, J. T. Module structure of Weyl algebras. J. London Math. Soc. (2) 18, no. 3, 429–442. 1978. Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected] Depto. de Matem´ aticas, Universidad de C´ adiz. Apdo. 40, E-11510 Puerto Real (Spain) E-mail address:[email protected] Depto. de ´ Algebra, Universidad de Sevilla. Apdo. 1160, E-41080 Sevilla (Spain) E-mail address:[email protected]