J. Symbolic Computation (2002) 11, 1–000

Computing Zero-Dimensional Schemes ^{†}

J. ABBOTT^{∗}, M. KREUZER^{∗∗}, L. ROBBIANO^{∗}

∗Department of Mathematics, University of Genova, Italy ∗∗ Fakultät für Mathematik, Universität Regensburg, Germany

(Received 31 July 2002)

This paper is a natural continuation of Abbott et al. (2000) further generalizing the Buchberger-Möller algorithm to zero-dimensional schemes in both affine and projective spaces. We also introduce a new, general way of viewing the problems which can be solved by the algorithm: an approach which looks to be readily applicable in several areas. Implementation issues are also addressed, especially for computations over ℚ where a trace-lifting paradigm is employed. We give a complexity analysis of the new algorithm for fat points in affine space over ℚ. Tables of timings show the new algorithm to be efficient in practice.

1. Introduction

Nowadays it is common knowledge that Gröbner bases and Buchberger’s Algorithm are key ingredients in Computational Commutative Algebra, and are hence fundamental tools for applications in several fields both inside and outside Mathematics (see Buchberger (1985)). It is also well-known that the computation of a Gröbner basis can be time consuming due to its intrinsic complexity. Therefore many attempts have been made in recent years to find special situations in which the usual computational scheme of Buchberger’s Algorithm can be improved.

For instance, in a recent paper (see Abbott et al. (2000)) we addressed the problem of computing the vanishing ideal of a set of reduced K -rational points, where K is a field. In particular, we studied the case K = ℚ. Our investigation was based on the Buchberger-Möller Algorithm (BM-algorithm) which improves the traditional scheme for computing intersections of ideals of points considerably (see Buchberger and Möller (1982)).

The first question we want to address now is the following. Is there a more general computational problem one of whose specializations is solved by the classical BM-algorithm? For this we let P = K[x_{1}, …, x_{n}] be the polynomial ring in n indeterminates over a field K, we let M be a P -module, and we let φ : P ⟶ M be a homomorphism of P -modules. The task is to compute Ker(φ) efficiently.

Let us see how this general setting specializes to the case treated by the classical BMalgorithm. Let p_{1}, …, p_{s} ∈ 𝔸_{K}^{n} and 𝔪_{1}, …, 𝔪_{s} be their associated maximal ideals. Let M = ⊕_{i=1}^{s}P/𝔪_{i} ≅ K^{s}, and let φ : P ⟶ M be defined by φ(f) = (f(p_{1}), …, f(p_{s})).

  † abbott,robbiano@dima.unige.it   martin.kreuzer@mathematik.uni-regensburg.de

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 2002 Academic Press Limited

Then the problem of computing Ker(φ) is exactly the problem of computing ⋂_{i=1}^{s} 𝔪_{i}, and indeed a good solution is the BM-algorithm.

A more general instance of the above computational problem is the computation of the vanishing ideal of a zero-dimensional scheme. Let 𝔪_{1}, …, 𝔪_{s} be maximal ideals in P, and for each i let 𝔮_{i} be an 𝔪_{i} -primary ideal. Then I = 𝔮_{1} ∩ ⋯ ∩ 𝔮_{s} is the vanishing ideal of some zero-dimensional subscheme 𝕏 ⊆ 𝔸_{K}^{n}. It is also the kernel of the canonical P -linear map π : P ⟶ ⊕_{i=1}^{s}P/𝔮_{i}. In this case the methods based on Buchberger’s Algorithm tend to be rather inefficient in practice and faster methods are needed.

If the ideals 𝔮_{1}, …, 𝔮_{s} are described by the vanishing of certain “dual functionals”, a suitable adaptation of the BM-algorithm was given in Marinari et al. (1993). But to find those functionals from systems of generators of 𝔮_{1}, …, 𝔮_{s} does not seem easy, especially if K has finite characteristic. A more direct approach was suggested in Lakshman (1991), but the cost of computing local normal form vectors and the problem of the growth of coefficients in the case K = ℚ were ignored. The related problem of computing minimal generators has been studied in Cioffi (1998) and Cioffi and Orecchia (2001).

To get a better grip on this situation, and in order to put it in a suitable general framework, we start in Section 2 by studying K -linear, surjective maps φ : P ⟶ K^{μ}, where μ ≥ 1; this was partly inspired by some ideas given in Mourrain (1999), and is further extended in Robbiano (2001). We show that Ker(φ) is a zero-dimensional ideal in P if and only if φ maps a polynomial to its normal form vector with respect to a tuple of polynomials whose residue classes are a K -vector space basis of P/ Ker(φ). The important case is when φ is explicitly computable. For instance, if P/ Ker(φ) is generated by the residue classes of the terms in the complement of some leading term ideal and if φ is constructed using the normal form map, it is explicitly computable. But we shall also see that there are cases where φ is explicitly computable, but not of this type. The “change of basis” between two such maps having the same kernel is achieved by a generalization of the well-known FGLM-algorithm.

Then we present our first generalization of the BM-algorithm in Section 3. It computes the vanishing ideal of a zero-dimensional scheme 𝕏 ⊆ 𝔸_{K}^{n} as above. The zero-dimensional ideals whose intersection we want to compute are represented by normal form vector maps. To compute the local normal form vectors more efficiently, we show how to use a method similar to the one introduced in Faugère et al. (1989): the ideals I_{k} are represented by the image of 1 in the basis of P/I_{k} ≅ K^{μ_{k}} and by the matrices representing the multiplications by x_{1}, …, x_{n} in this basis. Then we exploit the fact that the algorithm operates only on terms of the form t = x_{j}t′ for which the local normal forms of t′ are already known.

As in Abbott et al. (2000), we are also able to extend the method to the computation of the vanishing ideal of a zero-dimensional scheme 𝕏 ⊆ ℙ_{K}^{n}. Here we have to intersect one-dimensional homogeneous saturated ideals in K[x_{0}, …, x_{n}]. By proceeding degree by degree, we can reduce the problem to computations involving finite dimensional vector spaces. The problem is then to find a good stopping criterion which says that the result is complete after we have reached a certain degree. For the case of zero-dimensional subschemes of ℙ_{K}^{n}, we give two stopping criteria and the projective version of the BMalgorithm in Section 4.

As mentioned above, if we consider the problem of computing the vanishing ideal of 𝕏 ⊂ 𝔸_{K}^{n} over the base field K = ℚ, we run into the additional problem of coefficient growth. This problem is addressed in Section 5, where we present a version of the general BM-algorithm using an approach a bit like the method of Gröbner traces. The brunt of the computation becomes the solving of some linear systems over ℚ, a well-studied problem for which efficient algorithms already exist.

One case which is particularly important for applications in Algebraic Geometry is the case of schemes containing fat points: a fat point is a point in Supp(𝕏) whose local ideal is a power of the associated maximal ideal. We examine this situation in Section 6. We exhibit particularly efficient normal form vector maps for this case, and proceed to analyse the complexity of the algorithm of Section 5 assuming use of these maps. We find that for simple points the new algorithm matches the complexity of the less general modular algorithm given in Abbott et al. (2000).

Although we are not going to address them directly in this paper, we mention that for the general computational problem described above there are other cases where suitable generalizations of the BM-algorithm appear feasible. For instance, if we view M = P′ = K[y_{1}, …, y_{m}] as a P -module via a K -algebra homomorphism φ given by φ(x_{i}) = f_{i}(y_{1}, …, y_{m}) for i = 1, …, n, then the general task specializes to the implicitization problem. Again it is known that the general implicitization problem is hard, but there are special cases which can be treated more directly. For instance in the case of toric ideals, an ad hoc approach was used in Bigatti et al. (1999) to tame the intrinsic difficulties of elimination theory.

All algorithms described in this paper are implemented in the system CoCoA which is available from http://cocoa.dima.unige.it (see Capani et al. (1998)). Some experimental data based on our implementations are reported in Section 7.

2. Theoretical Preliminaries

In this section we describe some material which forms the theoretical background of our algorithms. For an extended presentation of this material we refer to Robbiano (2001). Throughout we assume that P = K[x_{1}, …, x_{n}] is a polynomial ring over a field K and that 𝕋^{n} is the monoid of terms (power products) of P. At various points it will be handy to refer to a basis for K^{μ}, so let e_{1}, …, e_{μ} be one with the convention that (a_{1}, …, a_{μ}) ∈ K^{μ} refers to the vector ∑_{i} a_{i}e_{i}.

Example 2.1. Let I ⊂ P be a zero-dimensional ideal, let μ = dim_{K}(P/I), let σ be a term ordering on 𝕋^{n}, and let O_{σ} = (t_{1}, …, t_{μ}) be a tuple whose components are precisely the terms in 𝕋^{n} which are not contained in the leading term ideal LT_{σ}(I). By the Macaulay Basis Theorem (see for instance Kreuzer and Robbiano (2000), Thm. I.5.7), the tuple (\overline{t}_{1}, …, \overline{t}_{μ}) of the residue classes of the elements of O_{σ} is a K -basis of P/I.

Let G be a σ -Gröbner basis of I. For every polynomial f ∈ P, the Division Algorithm with respect to G yields its normal form NF_{σ,I}(f) = ∑_{i=1}^{μ} a_{i}t_{i}, where a_{1}, …, a_{μ} ∈ K. The canonical surjective map π : P ⟶ P/I satisfies π(f) = ∑_{i=1}^{μ} a_{i}\overline{t}_{i}. Our choice of basis for P/I also fixes a canonical isomorphism P/I ⟶ K^{μ}, and combining this with π we obtain a K -linear, surjective map NFV_{O_{σ}} : P ⟶ K^{μ} sending f ↦ (a_{1}, …, a_{μ}) and whose kernel is precisely the ideal I.

Example 2.2. Let {(0, 0), (0, −1), (1, 0), (1, 1), (−1, 1)} ⊂ 𝔸_{2}(ℚ), let I ⊂ P = ℚ[x, y] be the vanishing ideal of this set of points, and let O = (1, x, y, x^{2}, y^{2}). Since the evaluation matrix of those terms at the given points has determinant −4, we conclude that the tuple (\overline{1}, \overline{x}, \overline{y}, \overline{x}^{2}, \overline{y}^{2}) is a ℚ-basis of P/I. Therefore, as before, there is a K -linear, surjective map NFV_{O} : P ⟶ K^{5} which sends every polynomial f to the uniquely defined tuple (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) such that the residue class of f in P/I is a_{1} + a_{2}\overline{x} + a_{3}\overline{y} + a_{4}\overline{x}^{2} + a_{5}\overline{y}^{2} .

But the map NFV_{O} is not induced by a map of the form NF_{σ,I}, since the components of O do not form a set 𝕋^{2} \LT_{σ}(I) for some term ordering σ. To prove this, consider the polynomial f = x^{2} +xy −x− \frac{1}{2}y^{2} − \frac{1}{2}y. It is in I, since it vanishes at the five points. For any term ordering σ, we have x^{2} >_{σ} x and y^{2} >_{σ} y. If x >_{σ} y, then x^{2} >_{σ} xy >_{σ} y^{2} . And if y >_{σ} x, then y^{2} >_{σ} xy >_{σ} x^{2} . This means that there are only two possibilities for the leading term of f: either it is x^{2} or y^{2} . In either case we have that LT_{σ}(f) is both a component of O, and an element of LT_{σ}(I).

For instance, examples of this second type, which do not come from Gröbner bases, arise in the study of Design of Experiments — see Caboara and Robbiano (2001). As has already been noted by Stetter, and more recently recalled in Mourrain (1999), such non-Gröbner examples are also important for symbolic-numeric solving. These situations motivate the following definition.

Definition 2.3. Let I be a zero-dimensional ideal in P, let π : P ⟶ P/I be the canonical map, let μ = dim_{K}(P/I), and let O = (t_{1}, …, t_{μ}) be a tuple of polynomials such that \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space. The vector (a_{1}, …, a_{μ}) ∈ K^{μ} such that π(f) = a_{1}\overline{t}_{1} + ⋯ + a_{μ}\overline{t}_{μ} is called the normal form vector of f with respect to O and is denoted by NFV_{O}(f). The corresponding map NFV_{O} : P ⟶ K^{μ} is called the normal form vector map with respect to O. To ease notation the dependence of NFV_{O} on the ideal I is not written out.

Clearly for actual computations we shall need explicit normal form vector maps, i.e. ones given by concrete algorithms. The next step is to characterize zero-dimensional ideals via normal form vector maps.

Proposition 2.4. Let μ ≥ 1, and let φ : P ⟶ K^{μ} be a K -linear, surjective map. The following conditions are equivalent.

a) The kernel of φ is a zero-dimensional ideal in P.

b) The map φ is a normal form vector map, i.e. φ = NFV_{O} for some choice of I and O.

c) The map φ is the composition of a normal form vector map NFV_{O_{σ}}, where O_{σ} is the complement of some leading term ideal, with a linear base change K^{μ} ⟶ K^{μ}.

Proof. First we show that a) ⇒ b). For every i = 1, …, μ we select a polynomial t_{i} ∈ P such that φ(t_{i}) = e_{i} ∈ K^{μ}. Hence we define a K -linear map ψ : K^{μ} ⟶ P such that φ ∘ ψ is the identity on K^{μ}. Let us write I for the zero-dimensional ideal Ker(φ). Since P = I ⊕ ψ(K^{μ}), every polynomial f can be uniquely represented as f = g + ∑_{i=1}^{μ} a_{i}t_{i}, where g ∈ I and a_{1}, …, a_{μ} ∈ K. Thus we get φ(f) = φ(g) + ∑_{i=1}^{μ} a_{i}φ(t_{i}) = ∑_{i=1}^{μ} a_{i}e_{i}, and therefore φ = NFV_{O} for O = (t_{1}, …, t_{μ}).

Now we prove that b) ⇒ c). Assume there exist an ideal I and a tuple O = (t_{1}, …, t_{μ}) of polynomials for which \overline{O} = (\overline{t}_{1}, …, \overline{t}_{μ}) is a basis of P/I as a K -vector space. Let σ be a term ordering on 𝕋^{n}, and let O_{σ} = (τ_{1}, …, τ_{μ}) be a tuple whose components are the terms in 𝕋^{n} \LT_{σ}(I). As already pointed out in Example 2.1, the tuple \overline{O}_{σ} of the residue classes (\overline{τ}_{1}, …, \overline{τ}_{μ}) of the elements of O_{σ} is a K -basis of P/I. Therefore \overline{O} = \overline{O}_{σ} · M for some invertible matrix M. Hence by their definitions NFV_{O}(f) = M · NFV_{O_{σ}}(f) for every f ∈ P; that is φ is the composition of NFV_{O_{σ}} with the change of basis given by the matrix M.

Now we prove that c) ⇒ a). Assume c). Clearly the kernel of the composition is the kernel of NFV_{O_{σ}}. This latter is precisely the ideal implicit in the normal form vector map, which is a zero-dimensional ideal. ⊓ ⊔

This proposition allows us to represent a zero-dimensional ideal in our later algorithms by a normal form vector map. Given two normal form vector maps corresponding to the same zero-dimensional ideal, we can change from one to the other as follows.

Remark 2.5. Let I ⊂ P be a zero-dimensional ideal, and let O = (t_{1}, …, t_{μ}) be a tuple of polynomials whose residue classes form a basis of P/I as a K -vector space.

a) Given an explicit NFV_{O}, if we have a tuple O_{σ} = 𝕋^{n} \ LT_{σ}(I) for some term ordering σ, we can calculate NFV_{O}(t) for all components t of O_{σ}, and we obtain the matrix M in the proof of Proposition 2.4. Thus we can compute NFV_{O_{σ}}(f) for all f ∈ P without having to find a σ -Gröbner basis of I.

b) Given an explicit NFV_{O} and a term ordering σ, but no corresponding tuple O_{σ}, we can still find such a tuple without resorting to Buchberger’s Algorithm. Namely, we can apply the Algorithm GBM of Theorem 3.1 in the case s = 1. We get a Change of Base Algorithm which generalizes the standard FGLM-algorithm (see Faugère et al. (1989), Section 3), because it does not require a Gröbner basis as input.

We conclude with two results we shall need in the next section where we show how to represent a zero-dimensional ideal using commuting matrices. These results are inspired by Mourrain (1999).

Proposition 2.6. Let μ ≥ 1, let φ : P ⟶ K^{μ} be a K -linear, surjective map whose kernel is a zero-dimensional ideal I in P, and let w = φ(1). Then there exist uniquely defined, pairwise commuting matrices M_{1}, …, M_{n} in Mat_{μ}(K) such that

a) φ(x_{i}f) = M_{i} · φ(f) for all f ∈ P and all i = 1, …, n.

b) φ(f) = f(M_{1}, …, M_{n}) · w for all f ∈ P.

Proof. We explain how to construct the matrices M_{i}; the rest of the proof is simple algebra. Let g_{1}, …, g_{μ} be polynomials such that φ(g_{k}) = e_{k} ∈ K^{μ} for k = 1, …, μ. We define M_{i} to be the matrix whose columns are the vectors φ(x_{i}g_{1}), …, φ(x_{i}g_{μ}). ⊓ ⊔

Definition 2.7. The pairwise commuting matrices M_{1}, …, M_{n} described in the above proposition are called the multiplication matrices of φ.

Here is a sort of converse to Proposition 2.6

Proposition 2.8. Let μ ≥ 1, let w ∈ K^{μ} be a non-zero vector, and let M_{1}, …, M_{n} be pairwise commuting matrices in Mat_{μ}(K).

a) There exists a unique map φ : P ⟶ K^{μ} with the following properties: a_{1}) φ(1) = w, a_{2}) φ is K -linear, a_{3}) φ(x_{i}f) = M_{i}φ(f) for all f ∈ P and each i = 1, …, n.

b) We have φ(f) = f(M_{1}, …, M_{n}) · w for all f ∈ P.

c) The kernel of φ is a zero-dimensional ideal.

Proof. The first part of the proof is straightforward algebra with the observation that the commutativity of the matrices M_{i} is necessary for φ to be well-defined.

To show that Ker(φ) is an zero-dimensional ideal, let f ∈ Ker(φ). For any x_{i} we have φ(x_{i}f) = M_{i}φ(f) = 0. By induction and the K -linearity of φ, we deduce that gf ∈ Ker(φ) for any g ∈ P. Now it is clear that Ker(φ) is an ideal; it is zero-dimensional because P/I is a finite-dimensional K -vector space. ⊓ ⊔

3. The Generalized BM-Algorithm

In Section 2 we established a correspondence between zero-dimensional ideals and normal form vector maps. In particular, we showed how knowledge of the Gröbner basis of such an ideal enabled us to determine a corresponding normal form vector map NFV_{O}. In this section we present a generalization of the BM-algorithm which determines directly a Gröbner basis for the intersection of a finite number of zero-dimensional ideals where each ideal is represented by a normal form vector map.

In the following, let K be a field, let P = K[x_{1}, …, x_{n}], let s ≥ 1, and for i = 1, …, s let NFV_{O_{i}} : P ⟶ K^{μ_{i}} be a normal form vector map representing a zero-dimensional ideal I_{i} ⊆ P. Recall that this means μ_{i} = dim_{K}(P/I_{i}) and I_{i} = Ker(NFV_{O_{i}}), and that O_{i} is a set of polynomials whose residue classes form a K -basis of P/I_{i}.

Our goal is to compute a Gröbner basis of the ideal I = ∩_{i=1}^{s} I_{i}. We present here the generalized BM-Algorithm: in outline, we consider all power products in increasing order (according to the term-ordering), for each power product we seek a linear dependency of its normal form vector on those of smaller power products, if there is a dependency then we get a new Gröbner basis element, otherwise we place the power product in the quotient basis for use in finding future linear dependencies.

Theorem 3.1. (Algorithm GBM) Let σ be a term ordering on 𝕋^{n}. Consider the following instructions. GBM1 Start with empty lists G = [ ], O = [ ], a list L = [1], and a matrix M = (m_{ij})

over K with μ = μ_{1} + ⋯ + μ_{s} columns and initially zero rows. GBM2 If L is empty, return the pair [G, O] and stop. Otherwise choose the power

product t = min_{σ}(L) and remove it from L. GBM3 Compute the vector v = NFV_{O_{1}}(t) ⊕ ⋯ ⊕ NFV_{O_{s}}(t) ∈ K^{μ}. GBM4 Reduce v against the rows of M to obtain

v^{∗} = v − ∑_{i} a_{i}m_{i} with a_{i} ∈ K

where m_{i} = (m_{i1}, …, m_{iμ}) is the i^{th} row of the matrix M.

GBM5 If v^{∗} = 0, then append the polynomial t − ∑_{i} a_{i}t_{i} to the list G, where t_{i} is the

i^{th} power product in the list O. Continue with step GBM2. GBM6 Otherwise v^{∗} ≠ (0, …, 0), so append the vector v as a new row to M. Append

the corresponding term t to the list O. Add to L those elements of {x_{1}t, …, x_{n}t} which are neither multiples of an element of L nor of {LT_{σ}(g) | g ∈ G}. Continue with step GBM2.

This is an algorithm which computes a pair (G, O) such that G is a list of polynomials in P forming the reduced σ -Gröbner basis of I = ∩_{i=1}^{s} I_{i} and O is a list whose components

are precisely the elements of 𝕋^{n} \ LT_{σ}(I).

Proof. In Algorithm GBM the reduced Gröbner basis is accumulated into the variable G; in the main loop G contains those elements whose leading term is smaller than t. A quotient basis of power products in accumulated into (O), it contains only power products known not to be reducible by any Gröbner basis element; at the end of the algorithm is contains all such power products. The list L helps identify quickly the next power product to consider in step GBM2.

First we exhibit termination. In each iteration either step GBM5 is performed or step GBM6. By its construction the matrix M always has linearly independent rows, and hence step GBM6, which adjoins a row to M, can be performed only finitely many times (at most μ times). By Dickson’s lemma step GBM5 can be performed only finitely many times; the noetherianity of P implies this too. Thus the algorithm performs only finitely many iterations, and each iteration clearly involves only a finite amount of computation.

To exhibit correctness we use induction on the iterations of the algorithm: we shall show that if the values of G and O are correct at the start of an iteration then they are still correct at the end of the iteration. Let B denote the reduced Gröbner basis for the intersection, and Q = 𝕋^{n} \ LT_{σ}(I) be the set of all power products not divisible by the leading term of some element of B.

If L is not empty then it contains a minimal element t. So at the start of the iteration we have that the list G contains all elements of B whose leading term is σ -smaller than t, and the list O contains all elements of Q which are σ -smaller than t.

We must show that in each iteration the power product t is either added to O or gives a new reduced Gröbner basis element as appropriate. The case t = 1 is trivial. Now consider the case t > 1. In step GBM5, if the vector v^{∗} is zero then the polynomial t−∑_{i} a_{i}t_{i} is an element of I_{i} for each i, and thus also of their intersection. Consequently B contains an element whose leading term divides t, but by definition of L no element of G does this. Hence B must contain an element whose leading term is exactly t; and this element is added to G in step GBM5.

Should we reach step GBM6 then t is an element of Q because any element of B whose leading term divides t would have to have leading term exactly t (by definition of L), and so such element would necessarily be of the form t − ∑ b_{i}t_{i} which would correspond to a linear relationship between v and the rows of the matrix M, and yet the reduction to a non-zero vector in step GBM4 proved that no such relationship exists.

We affirm that the list L is updated in such a way that its σ -smallest element is always the σ -smallest power product greater than t and not divisible by the leading term of some element of G. ⊓ ⊔

Now we know how to compute the intersection of the kernels of finitely many explicit K -algebra homomorphisms. For instance, the theorem applies when we have Gröbner bases of two zero-dimensional ideals I_{1} and I_{2} with respect to different term orderings. It also applies when we have quotient bases which are not of type 𝕋^{n} \LT_{σ}(I_{i}) but which do yield a normal form vector map NFV_{O_{i}} such as in Example 2.2.

Remark 3.2. Our presentation of Algorithm GBM favoured simplicity over efficiency. In reality it is better to build the matrix M in triangular form by appending the vector v^{∗} in step GBM6 and maintaining a list O^{∗} to which we append t − ∑_{i} a_{i}t_{i} rather than just t in step GBM6. The elements of the list O are then merely the leading terms of the corresponding elements in O^{∗}. In this way step GBM4 runs faster.

In the last part of this section we describe an optimization of Theorem 3.1 which is based on the following remark (also noted in Faugère et al. (1989)).

Remark 3.3.

In step GBM3 the power product t is either 1 or of the form t = x_{j}t′ for some power product t′ ∈ O. By storing NFV_{O_{i}}(t′) for each t′ ∈ O as the algorithm proceeds, we may compute the vector v cheaply by concatenating the images of each NFV_{O_{i}}(t′) under the linear transformation on K^{μ_{i}} which corresponds to the multiplication by x_{j} on P/I_{i}. This is simple if each I_{i} is represented by a vector w_{i} and multiplication matrices M_{i1}, M_{i2}, …, M_{in}. Here the commutativity of the multiplication matrices given in Proposition 2.6 is crucial. GBM3bis If t = 1 then put v = w_{1} ⊕ ⋯ ⊕ w_{s}. Otherwise t = x_{j}t′ for some indeter-

minate x_{j} and some t′ ∈ O, in which case put v = M_{1j}v′_{1} ⊕ ⋯ ⊕ M_{sj}v′_{s} where

v′_{1} ⊕ ⋯ ⊕ v′_{s} is the vector stored when processing t′.

4. The General Projective BM-Algorithm

In this section we shall develop along another direction the material explained in Section 2. In order to use it to compute intersections of homogeneous ideals, we shall need to extend those methods to the following general setting. Note that throughout this section all ideals are implicitly saturated and of algebraic dimension one (i.e. corresponding to geometrical objects of projective dimension zero).

Let K be a field and P = K[x_{0}, …, x_{n}]. Let P = ⊕_{d∈ℕ}P_{d} be standard graded, i.e. graded by deg(x_{0}) = ⋯ = deg(x_{n}) = 1, and let I ⊆ P be a homogeneous ideal. For every d ∈ ℕ, let O_{d} = (t_{d1}, …, t_{dμ_{d}}) be a tuple of homogeneous polynomials of degree d such that the residue classes \{\overline{t}_{d1}, …, \overline{t}_{dμ_{d}}\} under the canonical map π_{d} : P_{d} ⟶ P_{d}/I_{d} form a basis of P_{d}/I_{d} as a K -vector space.

As in Section 2, we introduce the notion of the normal form vector NFV_{O_{d}}(f) for f ∈ P_{d} and the map NFV_{O_{d}} : P_{d} ⟶ K^{μ_{d}}. The tuple (NFV_{O_{d}})_{d∈ℕ} will be called a graded normal form vector map. Clearly, such maps must be explicit if we are to perform calculations with them.

The next proposition generalizes Proposition 2.4 and can be proved in the same way (with the obvious changes).

Proposition 4.1. For every d ∈ ℕ, let μ_{d} ≥ 1 and let φ_{d} : P_{d} ⟶ K^{μ_{d}} be a K -linear, surjective map. The following conditions are equivalent.

a) The set ⊕_{d∈ℕ} Ker(φ_{d}) is a homogeneous ideal in P.

b) The tuple (φ_{d})_{d∈ℕ} is a graded normal form vector map, i.e. there is a homogeneous ideal I and tuples O_{d} such that for every d ∈ ℕ the map φ_{d} = NFV_{O_{d}}.

c) For every d ∈ ℕ, the map φ_{d} is the composition of a map NFV_{O_{σ,d}}, where O_{σ,d} is the degree d part of the complement of some leading term ideal, with a linear base change K^{μ_{d}} ⟶ K^{μ_{d}}.

Let us see an example of a graded normal form vector map.

Example 4.2. Let P = K[x, y, z], and let I ⊂ P be the ideal generated by G = {x^{2} − 4xz + 4z^{2}, xy − xz − 2yz + 2z^{2}, y^{2} − 2yz + z^{2}}, which is also the reduced Lex-Gröbner basis of I. Macaulay’s Basis Theorem tells us that the residue classes of

O = 𝕋^{3} \ LT_{Lex}(I) = {z^{d} | d ∈ ℕ} ∪ x · {z^{d} | d ∈ ℕ} ∪ y · {z^{d} | d ∈ ℕ}

form a K -basis of P/I. Therefore, if we let O_{d} = (z^{d}, xz^{d−1}, yz^{d−1}) for all d ∈ ℕ, we get a graded normal form vector map (NFV_{O_{d}})_{d∈ℕ} where NFV_{O_{d}} : P_{d} ⟶ K^{3} is given by NFV_{O_{d}}(f) = (a, b, c) such that NR_{G}(f) = az^{d}+bxz^{d−1}+cyz^{d−1} is the normal remainder returned by the Division Algorithm (see Kreuzer and Robbiano (2000), Section 1.6).

Now we examine the case when we have a finite number of graded normal form vector maps as before. Let s ∈ ℕ be a positive integer, and I_{1}, …, I_{s} be homogeneous ideals in P. For each ideal I_{i} we have a collection of tuples O_{i,d} the residue classes of whose components form a K -vector space basis of P_{d}/(I_{i})_{d}. Furthermore, we assume that (NFV_{O_{i,d}})_{d∈ℕ} is an explicit graded normal form vector map for i = 1, …, s.

This is the setting for a generalized projective BM-algorithm. The main difference with the affine case is that we need an extra piece of information for the termination of the algorithm. Abstractly speaking, what we need is a stopping criterion.

Definition 4.3. For a computation which proceeds degree by degree, a stopping criterion is a logical condition which depends only on the data obtained in the computation up to the current degree d, and which, if satisfied, guarantees that the complete result has been attained.

For the computation of the homogeneous vanishing ideal of a zero-dimensional scheme in ℙ_{K}^{n}, the following simple stopping criterion can be used. Recall that the Hilbert function of a standard graded K -algebra R is the map HF_{R} : ℕ ⟶ ℕ defined by i ↦ dim_{K}(R_{i}). The basic properties of the Hilbert function HF_{P/I} for one-dimensional saturated homogeneous ideals I ⊂ P needed in the proof below can be found in (Kreuzer, 1994).

Proposition 4.4. (Naive Stopping Criterion) In the setting of the generalized projective BM-algorithm, if the ideals I_{1}, …, I_{s} are one-dimensional and saturated, then writing μ_{i} = mult (P/I_{i}) for each i, we can stop the computation of I = I_{1} ∩ ⋯ ∩ I_{s} after we have finished computing its homogeneous generators of degree ≤ μ_{1} + ⋯ + μ_{s}.

Proof. The multiplicity of the ring P/I is μ ≤ μ_{1} + ⋯ + μ_{s}. Since the ideals I_{1}, …, I_{s} are saturated, the ring P/I is Cohen-Macaulay and its Hilbert function increases strictly until it reaches the value μ in some degree d. From there on it is constant, i.e. we have dim_{K}(P/I)_{i} = μ for i ≥ d. In particular, it is clear that HF_{P/I}(i) = μ for i ≥ μ−1. Since HF_{P/I} = HF_{P/ LT_{σ}(I)} for every term ordering σ, it follows as in the proof of (Abbott et al., 2000), Prop. 3.2, that LT_{σ}(I) is generated in degrees ≤ μ. After we have finished computing the homogeneous generators of I of degree ≤ μ, the ideal J = (I_{≤μ}) which they generate has therefore the leading term ideal LT_{σ}(J) = LT_{σ}(I), and we conclude J = I. ⊓ ⊔

In the paper (Abbott et al., 2000) we presented a stopping criterion which is usually much better and which can be used in our situation, too. For completeness we restate it here. We recall that two power products t, t′ are connected if there exist indeterminates x, x′ such that x′t = xt′.

Theorem 4.5. (Projective Stopping Criterion) In the setting of the generalized projective BM-algorithm, let σ be a term ordering on 𝕋^{n+1} and let I = I_{1} ∩ ⋯ ∩ I_{s} where the homogeneous ideals I_{1}, …, I_{s} are onedimensional and saturated. Moreover, suppose we have computed homogeneous polynomials, each one lying in the intersection and whose leading terms generate (LT_{σ}(I)_{≤d}) for some degree d ≥ 1, and also that the following conditions hold:

a) HF_{P/ LT_{σ}(I)}(d) = mult(P/I_{1}) + ⋯ + mult(P/I_{s}) or d > 0 and HF_{P/ LT_{σ}(I)}(d) = HF_{P/ LT_{σ}(I)}(d − 1)

b) For each i = 0, …, n, every power product in the connected component of x_{i}^{d} in

(𝕋^{n+1} \ LT_{σ}(I))_{d} is divisible by x_{i}. Then the homogeneous polynomials computed so far are a σ -Gröbner basis of I.

Now we are ready to prove the main result of this section: the Generalized Projective BM-Algorithm.

Theorem 4.6. (Algorithm PBM)

In the above setting, let σ be a term ordering on the monoid 𝕋^{n+1} of terms of P = K[x_{0}, …, x_{n}]. Assume that there exists a function StoppingCriterion(G) which returns TRUE if the set G computed so far is a σ -Gröbner basis of I = I_{1} ∩ ⋯ ∩ I_{s}, and FALSE otherwise.

Consider the following sequence of instructions. PBM1 Start with empty lists G = [ ], H = [ ], a list L = [1], and d = 0. PBM2 Apply the function StoppingCriterion(G). If it returns TRUE, return the list G

and stop. Otherwise increase d by one, set M = (m_{ij}) to be a matrix over K with zero rows and ℓ = ∑_{i=1}^{s} #(O_{i,d}) columns, and let L be the list of all terms of degree d which are not multiples of any element of {LT_{σ}(g) | g ∈ G}.

PBM3 If L = ∅, go to step PBM2. Otherwise choose the term t = min_{σ}(L) and remove

it from L. PBM4 Compute the vector v = (NFV_{O_{1,d}}(t) ⊕ … ⊕ NFV_{O_{s,d}}(t)) ∈ K^{ℓ} and reduce it

against the rows of M to obtain

v^{∗} = v − ∑_{i} a_{i} (m_{i1}, …, m_{iℓ}) with a_{i} ∈ K

PBM5 If v^{∗} = (0, …, 0), then append the polynomial t − ∑_{i} a_{i}h_{i} to the list G, where

h_{i} is the i^{th} element of the list H. Continue with step PBM3. PBM6 Otherwise v^{∗} ≠ 0, so append v^{∗} as a new row to M and t − ∑_{i} a_{i}h_{i} as a new

element to H. Continue with step PBM3. This is an algorithm which returns the reduced σ -Gröbner basis G of the ideal I = I_{1} ∩ ⋯ ∩ I_{s}.

Proof. This can be shown in the same way as Thm. 3.12 in (Abbott et al., 2000). We note that v = (0, …, 0) is equivalent to f = t−∑_{i} a_{i}h_{i} ∈ I_{d}, since the Chinese Remainder Theorem yields that f ∈ I_{d} if and only if NFV_{O_{1,d}}(f) = ⋯ = NFV_{O_{s,d}}(f) = 0. ⊓ ⊔

Remark 4.7. Let σ be a term ordering on 𝕋^{n+1} , let 𝕏 ⊂ ℙ_{K}^{n} be a zero-dimensional subscheme, let Supp(𝕏) = {P_{1}, …, P_{s}}, and, for i = 1, …, s, let I_{i} ⊂ P be the vanishing ideal of 𝕏 at P_{i}. Then the reduced σ -Gröbner basis of the homogeneous vanishing ideal I_{𝕏} ⊂ P of 𝕏 can be computed as follows.

1) For i = 1, …, s and d ∈ ℕ, find a tuple O_{i,d} of homogeneous polynomials of degree d and a map NFV_{O_{i,d}} : P_{d} ⟶ K^{μ_{i,d}} such that (NFV_{O_{i,d}})_{d∈ℕ} is an effective graded normal form vector map with kernel I_{i}. (For instance, one can compute a σ_{i} -Gröbner basis G_{i} of I_{i} for some term ordering σ_{i} and use the normal remainder map NR_{σ_{i},G_{i}} as in Example 4.2 to define NFV_{O_{i,d}}.)

2) Apply algorithm PBM to this situation using the stopping criterion of Theorem 4.5.

Remark 4.8. As is well known 𝔸_{K}^{n} can be readily embedded into ℙ_{K}^{n}, thus Algorithms GBM and PBM are closely related. We may use Algorithm GBM instead of Algorithm PBM if the chosen ordering σ is degree compatible and all the points associated to the input ideals have non-zero coordinate corresponding to the σ -smallest indeterminate. In such special cases Algorithm GBM computes its answer doing less arithmetic than Algorithm PBM.

5. Modular Techniques

When we work over the base field K = ℚ, algorithms for computing Gröbner bases like our algorithm GBM may perform poorly due to the problem of coefficient growth. In a previous paper Abbott et al. (2000) we presented some modular methods to overcome this difficulty in the BM-algorithm. More precisely, we presented a version of this algorithm which computes the desired Gröbner bases modulo different primes and then reconstructs the solution over ℚ using Chinese Remaindering techniques. The analogous development of algorithm GBM is impeded by the lack of a good criterion for checking the correctness of the reconstructed basis.

Therefore we shall now present a different way of exploiting modular methods in algorithm GBM — an idea similar in spirit to the method of Gröbner traces. The same idea applies equally to algorithm PBM, but we shall leave it to the interested reader to work out the details.

So, let K = ℚ, let n ≥ 1, let σ be a term ordering on P = K[x_{1}, …, x_{n}], let s ∈ ℕ be a positive integer, and for i = 1, …, s let the zero-dimensional ideal I_{i} ⊂ P be given by the vector w_{i} ∈ K, and the multiplication matrices M_{i1}, …, M_{in} as described in Definition 2.7. Moreover, let μ_{i} = dim_{K}(P/I_{i}) for i = 1, …, s and μ = μ_{1} + ⋯ + μ_{s}.

Theorem 5.1. (Modular Version of the General BM-Algorithm) In the above situation, consider the following sequence of instructions. MBM1 Pick a prime number p ∈ ℕ which does not divide the denominator of any entry

in the matrices M_{ij} or in the vectors w_{i} — so that reductions modulo p exist. MBM2 Apply algorithm GBM over the field 𝔽_{p} to the modular reductions of the ma-

trices M_{ij} and of the vectors w_{i}. From the result we use only the tuple of power products O = (t_{1}, …, t_{ν}), and Ĝ = (ĝ_{1}, …, ĝ_{r}), the tuple of the leading power products of the computed Gröbner basis.

MBM3 Construct a ν × μ matrix M over ℚ: each element t_{i} ∈ O gives one row being

NFV_{O_{1}}(t_{i}) ⊕ ⋯ ⊕ NFV_{O_{s}}(t_{i}) MBM4 Similarly construct a matrix R of size r × μ over ℚ whose i^{th} row is the

concatenated normal form vectors of ĝ_{i} ∈ Ĝ. MBM5 Now solve the linear systems LM = R over ℚ to obtain a matrix L = (λ_{ij}) of

size r × ν. MBM6 If the system in step MBM5 admits no solution then go back to step MBM1.

Otherwise form the polynomials g_{i} = ĝ_{i}−∑_{j=1}^{ν} λ_{ij}t_{j} for each power product ĝ_{i} ∈ Ĝ, and check whether λ_{ij} = 0 for all indices j having t_{j} >_{σ} ĝ_{i}. If this is not the case, go back to step MBM1. Otherwise let G = {g_{1}, …, g_{r}}, and return the pair (G, O).

This is an algorithm which returns a list O whose components are precisely the elements of 𝕋^{n} \LT_{σ}(I) together with the reduced σ -Gröbner basis G of the ideal I = I_{1} ∩⋯∩I_{s}.

Proof. The basic idea behind this proof is to consider running two copies of algorithm GBM, one on the inputs over ℚ, the other on the modular images in 𝔽_{p}. If the two runs follow the same path then the final modular result is just the modular reduction of the result over ℚ. Otherwise we consider the point where the two runs first differ, and then deduce how to detect when the modular result is not good.

Let G_{0} and O_{0} denote the result algorithm GBM would produce over ℚ; similarly let G_{p} and O_{p} denote the result over 𝔽_{p}. We shall also refer to M_{0} , the final value of the matrix M used during the run of algorithm GBM over ℚ. To simplify later arguments we shall suppose that all entries in M_{0} are integer, this being achieved by multiplying each row by its least common denominator — this assumption clearly does not affect the run of algorithm GBM over ℚ. Further note that the rows of M_{0} are linearly independent by construction, and so rank(M_{0}) = ν where ν is the number of rows.

Of those primes satisfying the conditions in step MBM1 we shall say that a prime p is good if O_{p} = O_{0} , and otherwise the prime is bad. For a bad prime p we shall be interested in the “first difference” between O_{p} and O_{0} , i.e. the σ -smallest power product t which appears in one but not both. In fact, we claim that t ∈ O_{0} and t ∉ O_{p}. For suppose instead that t ∉ O_{0} . This means that the row comprising the concatenated normal form vectors of t is ℚ-linearly dependent on the rows corresponding to those elements of O_{0} which are σ -less than t, equivalently there is a polynomial with rational coefficients t − ∑_{i} μ_{i}t_{i} lying in the intsersection where each t_{i} <_{σ} t and t_{i} ∈ O_{0} . Now p does not divide the denominator of any coefficient μ_{i} since otherwise, multiplying by the least power of p to remove all factors of p from the denominators would yield an 𝔽_{p} -linear dependency among the rows corresponding to those elements of O_{0} which are σ -less than t; yet O_{p} and O_{0} contain the same elements up to t, which means there can be no 𝔽_{p} -linear dependency.

Now these preliminaries are over our proof has three parts: (i) there are only finitely many bad primes, (ii) if the prime chosen in step MBM1 is bad then the checks in step MBM6 will detect this, and (iii) if the prime chosen in step MBM1 is good then the checks in step MBM6 will pass and the correct result will be returned.

(i) We first show that there are only finitely many bad primes. Suppose that O_{p} ≠ O_{0} , and let t be the σ -smallest element of O_{0} not in O_{p}. Thus over 𝔽_{p} the normal form vector of t is linearly dependent on the normal form vectors of those elements of O_{0} smaller than t. So in particular there is a linear relation modulo p between the rows of M_{0} , so M_{0} is not of full rank modulo p. Thus all bad primes must divide the determinants of all ν × ν minors of M_{0} , and hence the bad primes are only finite in number.

(ii) Now we show that if the prime chosen in step MBM1 is bad then we discover this in step MBM6. So assume that p is bad. If this leads to an insoluble linear system in step MBM5 we detect this in step MBM6, and start anew with a different prime. Otherwise a solution was found in step MBM5; if there are multiple solutions we may pick any one. Let t be the σ -smallest element of O_{0} not in O_{p}. The solution obtained in step MBM5 has represented the normal form vector of t as a linear combination of the rows of M. Now, the rows of M and M_{0} differ only by a non-zero scalar multiple, so we also have a representation as a linear combination of the rows of M_{0} involving the same rows. Since t ∈ O_{0} we know its row cannot be represented as a linear combination of those rows of M_{0} corresponding solely to power products σ -smaller than t. Hence the linear combination obtained for t must involve at least one row corresponding to a power product σ -greater than t. And this is what we check for in step MBM6.

(iii) Now suppose that the prime chosen in step MBM1 is good. Thus we have O_{p} = O_{0} at the end of step MBM2. The set O_{p} uniquely determines Ĝ which, by its uniqueness, must also be the set of leading power products of G_{0} . Hence the linear systems in step MBM5 admit a solution: the coefficients of the elements of G_{0} give one solution. Moreover these solutions are unique since the matrix M is of full rank: M is the same as M_{0} up to multiplication of rows by non-zero scalars. This unique solution clearly satisfies the test in step MBM6, and so the correct result is returned. ⊓ ⊔ Remark 5.2. Here we make some observations directed at potential implementers.

(a) If step MBM1 is executed several times (because the tests in step MBM6 fail) then on each occasion we must pick a prime p different from those previously chosen.

(b) In step MBM2 the number of elements of O may be less than μ (e.g. if the input ideals are not pairwise comaximal).

(c) In step MBM3 in our implementation we exploit the idea expounded in Remark 3.3; the same idea can be used to compute the rows of R cheaply from the rows in M.

(d) In step MBM5 a sophisticated linear system solver will, in its turn, exploit modular techniques (e.g. Hensel methods). Indeed the Gröbner basis discarded in step MBM2 could be used here, though this is unlikely to produce a measurable improvement in speed.

(e) The order of the rows of the matrices M and R constructed in steps MBM3 and MBM4 is quite unimportant so long as the interpretation in step MBM6 is consistent. Their rows are indexed by power products, and we can order these power products in any convenient manner (the use of tuples in step MBM2 is intended to indicate this).

6. Complexity on Fat Points

In Section 3, we saw how one can compute the vanishing ideal of a zero-dimensional subscheme 𝕏 of an affine space 𝔸_{K}^{n} if we are given the zero-dimensional ideals defining 𝕏 at the points of its support. Suppose some point p = (p_{1}, …, p_{n}) ∈ Supp(𝕏) is K -rational. Let 𝔪 = (x_{1} − p_{1}, …, x_{n} − p_{n}) be the corresponding maximal ideal of K[x_{1}, …, x_{n}], and let I ⊆ 𝔪 be the ideal defining 𝕏 at p. The following situation occurs frequently.

Definition 6.1. The point p is called a fat point of 𝕏, if I = 𝔪^{d} for some d ≥ 1. The number d is called the order of the fat point p. We say that 𝕏 is a scheme of fat points if Supp(𝕏) is K -rational and every point of Supp(𝕏) is a fat point of 𝕏 (of some order).

Remark 6.2. Reduced points are fat points of order one. Not all non-reduced points are fat points; for instance, in 𝔸^{2} the point (0, 0) could be associated to the ideal I = (x, y^{2}) which is not a power of (x, y).

If the input ideals are ideals of fat points we can make step GBM3bis even faster. First we consider fat points located at the origin (0, …, 0), then we observe that a simple change of coordinates allows us to handle any fat point in much the same way. In fact, the ideal of a fat point located at (0, …, 0) is a monomial ideal, and the observations here apply to any monomial ideal.

Remark 6.3. Let I be a monomial ideal, then a natural K -vector space basis for P/I is given by the set O of all power products x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}} not divisible by any monomial generator of I; if I is the ideal of a fat point of order d then the quotient basis is generated by all power products of degree < d. For this choice of basis the map NFV_{O} : P ⟶ K^{μ} is particularly easy to compute.

Furthermore, in step GBM3bis we compute NFV_{O}(x_{j}t′) directly from NFV_{O}(t′) by matrix multiplication. Now, using the natural quotient basis for a monomial ideal we have a special structure which permits us to replace the matrix multiplication by a simpler process. Indeed v = NFV_{O}(x_{j}t′) may be obtained from v′ = NFV_{O}(t′) merely by changing the position of some coordinates and setting the rest to zero: the entries of a normal form vector are indexed by the power products in O, so the entry of v indexed by t is zero if t is not divisible by x_{j}, otherwise it is equal to the entry of v′ indexed by t/x_{j}. The necessary coordinate shifts can be effected optimally, in linear time, after a simple preprocessing phase (with complexity O(nμ^{2})).

Remark 6.4. To handle a fat point located away from the origin at (p_{1}, …, p_{n}) we use the change of coordinates x_{i} ↦ x_{i} + p_{i}. Note that this coordinate change affects step GBM3bis: the new normal form vector is now obtained by multiplying by x_{j} + p_{j}. We can do this multiplication in linear time by using coordinate shifts to multiply by x_{j}, and then adding p_{j} times NFV_{O}(t′) to the result.

Remark 6.5. In general, for a fat point of order d located at (p_{1}, …, p_{2}), we have that NFV_{O}(x_{1}^{α_{1}} ⋯ x_{n}^{α_{n}}) comprises exactly the coefficients of all terms of degree < d in the polynomial (x_{1} + p_{1})^{α_{1}} ⋯ (x_{n} + p_{n})^{α_{n}}.

The normal form vector map described in Remark 6.4 is sufficiently well specified that we are able to analyse the complexity of Algorithm MBM in the special case of ideals of fat points with disjoint support with integer coordinates. If all the points are in fact simple then we obtain the same expected complexity as the algorithm in Abbott et al. (2000).

We shall express the complexity in terms of the following parameters:

μ the sum of the multiplicities of the input ideals; n the number of variables (i.e. the dimension of the ambient affine space); r the number of elements in the Gröbner basis; X a bound on the coordinates of the points supporting the ideals.

Note that since the fat points have disjoint support we know that the multiplicity of the intersection is equal to the sum of the multiplicities of the input ideals; in general, the sum is an upper bound.

Running Algorithm GBM over the finite field 𝔽_{p} has the same complexity as the classical Buchberger-Möller algorithm: the only difference is the way in which each vector v is computed, but the cost of reducing each vector exceeds the cost of creating it. We recall from Abbott et al. (2000) that the complexity is O(μ^{2}(r +μ)(log p)^{2} +μ^{2}n^{2}) where the cost of an arithmetic operation in 𝔽_{p} is O((log p)^{2}).

Lemma 6.6. Let p_{1}, …, p_{n} ∈ ℝ and τ_{1}, …, τ_{n} ∈ ℕ. Put τ = τ_{1} + ⋯ + τ_{n} and f = ∏(x_{i} + p_{i})^{τ_{i}}. Then the coefficient in f of any term of degree d has magnitude bounded by B_{d} the coefficient of x^{d} in (x + B)^{τ} for any B ≥ max{|p_{1}|, …, |p_{n}|}. In particular, we have B_{d} ≤ (B + 1)^{τ} whenever τ > 0.

Proof. Let t be any power product. Then the magnitude of the coefficient of t in f is clearly bounded by the coefficient of t in ∏_{i=1}^{n}(x_{i} + |p_{i}|)^{τ_{i}}, and this in turn is clearly bounded by the coefficient of t in g = ∏_{i=1}^{n}(x_{i} + B)^{τ_{i}}. For any degree d it is an elementary induction on n to show that the coefficient of x^{d} in (x + B)^{τ} is the sum of all coefficients of terms of degree d in g. Finally, every coefficient in (x + B)^{τ} is non-negative and the sum of these coefficients is (B + 1)^{τ}, and therefore obviously an upper bound. ⊓ ⊔

Theorem 6.7. Let I_{1}, I_{2}, …, I_{s} be ideals in ℚ[x_{1}, …, x_{n}] of fat points with disjoint support at points with integer coordinates bounded by X. Let the multiplicity of each I_{j} be μ_{j}, and put μ = ∑ μ_{j}. Supposing that the ideals are presented using the bases of Remark 6.4 then Algorithm MBM has expected bit complexity:

O(μ^{5}(r + μ) log^{2}(X + 1) + μ^{2}n^{2}).

Furthermore, for “generic” fat points with the DegRevLex ordering, Algorithm MBM has bit complexity

O(μ^{4}d(r + μ) log^{2}(X + 1) + μ^{2}n^{2})

where d is such that \binom{n+d−1}{d} = r + μ; this is better than the general expected complexity by a factor of about μ/d.

Proof. Recall from the proof of Theorem 5.1 that a prime is bad if and only if it divides a certain determinant whose value is independent of the choice of prime. Consequently, the probability of returning to step MBM1 at least n times is bounded above by 2^{−n} (an upper bound for the probability that the determinant is divisible by each of the n primes chosen). Furthermore for a fixed input and a given prime p the cost of an iteration is in O(log^{2} p). Thus provided the primes chosen do not vary wildly in size the expected cost is bounded by a constant times the cost of a single iteration. Our proof is completed by assuming the prime chosen in step MBM1 is good and then showing that each step of Algorithm MBM has cost not exceeding the complexity claimed above.

Steps MBM1 and MBM6 have negligible cost. The cost of the computation over 𝔽_{p} in step MBM2 is also dominated by the claimed complexity provided log p ≤ μ\sqrt{μ} log X, i.e. we must not pick huge primes.

We now estimate the cost of steps MBM3 and MBM4. We first estimate the cost of creating a single row of M (or R). Using the method of Remark 6.4 we do at most μ multiplications between an integer of size O(log X) and another of size at most O(log(X^{μ})), giving a total cost of O(μ^{2} log^{2} X) per row. Altogether there are r + μ rows, so their combined cost remains less than the claimed complexity.

Finally, we estimate the cost of solving the linear systems in step MBM5. We use Remark 6.5 to bound the size of the entries of the matrices M and R which are necessarily integer. The entries in M come from normal form vectors of power products of total degree not exceeding μ − 1; similarly for the entries in R except that the degree may be as high as μ. We shall use Cramer’s rule and Hadamard’s bound on determinants to estimate the size of solutions to the linear system.

To use Hadamard’s bound we need to calculate the Euclidean length of each row in M and in R. Consider a row corresponding to a power product t of degree τ > 0. By Remark 6.5 and Lemma 6.6 the normal form vector of t with respect to any of the ideals I_{j} contains entries of magnitude at most (X + 1)^{τ}. Hence the Euclidean length of the entire row is at most (X + 1)^{τ} \sqrt{μ}. For a row in M we can take τ = μ − 1, and a for a row in R we take instead τ = μ.

By Cramer’s rule every coordinate of any solution vector in the system solved in step MBM5 has numerator bounded by \sqrt{μ^{μ}}(X + 1)^{μ^{2}−μ+1} ∈ O((X + 1)^{μ^{2}}), and denominator bounded by \sqrt{μ^{μ}}(X + 1)^{μ^{2}−μ} ∈ O((X + 1)^{μ^{2}}). Hence the system can be solved using Chinese Remaindering techniques in time O(μ^{5}(r + μ) log^{2}(X + 1)) which is bounded by the claimed complexity.

In the generic case with the ordering DegRevLex we can take advantage of the fact that the highest degree power product appearing in the algorithm is typically far smaller than μ. In fact, we need to go only as far as degree d where d is the smallest integer for which \binom{n+d}{d} ≥ r + μ. The reasoning above then allows us to reduce the complexity by a factor of d/μ, except for the contribution μ^{2}n^{2} (arising from the generation of power products within the call to Algorithm GBM). ⊓ ⊔

Remark 6.8. The worst case complexity is max(X^{2}, μ^{2}) times the expected complexity, but is realised with exceedingly low probability. The product of the first k primes clearly exceeds k! whose logarithm lies in O(k log k). Hence there can be at most max(X^{2}, μ^{2}) bad primes.

Remark 6.9. A more general analysis is difficult to manage because of the freedom of choice of the representation of an ideal using a normal form vector map. However, the formula of Theorem 6.7 still applies in the case where the ideals are given by integer vectors w_{i} of bounded length, and multiplication matrices M_{ij} with integer entries and all of whose rows have 1-norm bounded by X + 1. This is because the crucial part of the proof is the estimation of the sizes of the entries in the matrices M and R, and we can easily obtain the same estimates in this case.

7. Implementation Issues and Timing

Here we comment briefly on the differences between the new algorithm MBM and the old algorithm M we gave in Abbott et al. (2000). Foremost, the new algorithm is more general than the old one since it can be applied to any intersection of zero-dimensional ideals. Another notable difference is that in the new algorithm the “lifting” of the modular result is implicit in the process of solving the linear systems in step MBM5 whereas the “lifting” was an integral part of the old algorithm. Furthermore, the new algorithm is able to benefit directly and immediately from any improvement to algorithms for solving linear systems; instead the old algorithm could benefit only if such improvements can be fitted into its scheme.

The following tables give the timings for computing the intersections of various random ideals of non-simple points. The times reported are in seconds and represent averages of ten cases run on a 433 MHz Digital Alpha with 192Mb RAM; the code was compiled with gcc -O2. The timings reported in the tables below are a small selection; there are too many parameters to give comprehensive results. We have arbitrarily fixed the term ordering to be DegRevLex, the ambient spaces were chosen to be 𝔸_{ℚ}^{3} and ℙ_{ℚ}^{3} , and the coordinates of the points are random integers between −99 and 99.

We do not give a table comparing the new implementation in the reduced case with that described in Abbott et al. (2000) since on all examples tried the times were virtually identical.

The table rows labelled “Order 2” give times for computing the intersection of ideals of fat points of order 2; those labelled “Order 3” give times for computing the intersection of ideals of fat points of order 3; and the row labelled “non-monomial” gives the times for computing the intersection of non-monomial zero-dimensional ideals of multiplicity 10 (the same multiplicity as for a fat point of order 3). The last column gives the size of the largest coefficient in the resulting Gröbner basis for the intersection of 15 ideals. In all cases the time spent constructing the multiplication matrices was excluded.

The Affine Case

DegRevLex 5 pts 10 pts 15 pts  15 pts
Order 2 0.1 s 1.3 s 5.5 s 330 digits
Order 3  1.4 s 28 s 140 s 1100 digits
non-monomial  3.4 s 43 s 210 s 1250 digits

The Projective Case

DegRevLex 5 pts 10 pts 15 pts  15 pts
Order 2 0.6 s 4.2 s 15.3 s 500 digits
Order 3  3.9 s 68 s 340 s 1600 digits

In section 6 we observed that the ideal of a fat point is a monomial ideal under some change of coordinates. The non-monomial ideals used in these tests are ideals which cannot be obtained by applying a change of coordinates to a monomial ideal.

References

Abbott, J., Bigatti, A., Kreuzer, M., Robbiano, L. (2000) Computing Ideals of Points. J. Symb. Comput.,

30: 341–356. Bigatti, A., La Scala, R., Robbiano, L. (1999) Computing Toric Ideals. J. Symb. Comput., 27: 351–365. Buchberger, B. (1985). Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, In Bose,

N.K., editor, Multidimensional Systems Theory , pp. 184–232. Dordrecht. D. Reidel Publishing Co. Buchberger, B., Möller, H. M. (1982). The construction of multivariate polynomials with preassigned ze-

ros. In Calmet, J., editor, Proceedings of the European Computer Algebra Conference (EUROCAM ’82), Lecture Notes in Comp. Sci., Vol. 144, pp. 24–31. Springer.

Caboara, M., Robbiano, L., (2001) Families of Estimable terms Proceedings of ISSAC 2001, pp.56–63,

ACM Press Capani, A., Niesi, G., Robbiano, L. (1998). CoCoA, a system for doing Computations in Commutative

Algebra. Available via anonymous ftp from cocoa.dima.unige.it, version 4 Cioffi, F. (1998) Minimally generating ideals of points in polynomial time using linear algebra. Ricerche

di Matematica, XLVII fasc. 2 (1998) Cioffi, F., Orecchia, F. (2001) Computation of Minimal Generators of Ideals of Fat Points. Proceedings

of ISSAC 2001, pp.72–76, ACM Press Faugère, J. C., Gianni, P., Lazard, D., Mora, T. (1989). Efficient computation of zero-dimensional

Gröbner bases by change of ordering. J. Symb. Comput. , 16(4): 329–344. Kreuzer, M. (1994). On the canonical module of a 0-dimensional scheme. Can. J. Math., 46: 357–379. Kreuzer, M., Robbiano, L. (2000) Computational Commutative Algebra 1. Heidelberg. Springer. Lakshman, Y. (1991). A single exponential bound on the complexity of computing Gröbner bases of

zero dimensional ideals. In Mora, T., Traverso, C., editors, Proceedings of MEGA-90 (Castiglioncello/Italy), Progress in Math., Vol. 94, pp. 227–234, Boston. Birkhäuser.

Marinari, M., Moeller, H., Mora, T. (1993). Gröbner bases of ideals defined by functionals with an

application to ideals of projective points. Appl. Alg. in Eng., Comm. and Comp., 4(2): 103–145. Mourrain, B. (1999). A new criterion for normal form algorithms. In Fossier, M., Imai, H., Lin, S.,

Poli, A., editors, Proceedings of the 13th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, Lecture Notes in Comp. Sci., Vol. 1719, pp. 439–443. Springer.

Robbiano, L. (2001). Zero-dimensional ideals or the inestimable value of estimable terms. Preprint.