Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 37 (1996), No. 2, 309-328.

On the Complexity of Parametrizing Curves

Michal Mňuk,^{1} J. Rafael Sendra,^{2} and Franz Winkler^{1}

1Research Institute for Symbolic Computation, Johannes-Kepler University, A-4040 Linz, Austria

2Departamento de Matemáticas, Universidad de Alcalá, Spain

Abstract. Given a rational algebraic plane curve C in implicit representation we analyze the bit complexity of an algorithm to describe C by parametric equations. Estimates for subalgorithms for computing the standard decomposition of singularities and the genus are also obtained.

1. Introduction

Rational parametrization of algebraic curves is one of the basic computational problems in constructive algebraic geometry. A completely symbolic approach to this problem has been published in [11] and it has been implemented in the program system CASA ([4, 9]). The main goal of this paper is to give a thorough theoretical worst case complexity analysis of this parametrization algorithm.

In the first part we limit the complexity analysis to the case in which the curve has rational coefficients and only ordinary singularities, i.e. no blowing up is necessary to resolve them. In the Section 4 we discuss questions related to the presence of neighboring points.

Since the main steps of the parametrization algorithm consist of solving systems of algebraic equations in two variables, solving linear systems, and computing gcd’s and resultants of polynomials of two or three variables, it is easy to see that the complexity is polynomial in the size of the input. In this paper we give a precise analysis in terms of bit complexity of the parametrization problem and some of its important subproblems.

1Supported by the “Fonds zur Förderung der wissenschaftlichen Forschung” under project number P8573-PHY and the “EC Project POSSO” No. 6846.

2Partially supported by DGICYT A.I. Spain–Austria HU-007 and ÖAD Int. Akt. 16.

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix} 1996 Heldermann Verlag, Berlin

Section 2 contains a summary of complexity bounds for basic integer and polynomial arithmetic algorithms (gcd, polynomial remainder sequences, etc.). Section 3 is dedicated to the computing time analysis of the parametrization problem. In Subsection 3.1, description and analysis of an algorithm for the decomposition of the set of singularities is given. Subsection 3.2 is devoted to the main algorithm for parametrization. A brief description of and a detailed analysis in terms of bit complexity are provided. In order to obtain tighter bounds for special cases we distinguish whether coordinates of all singularities are rational or not. In Subsections 3.2.1 and 3.2.2 we give the analysis for both cases. Section 4 discusses the complexity of algorithms designed so far in the case when the input curve possesses neighboring singularities.

2. Complexity of integer and polynomial arithmetic

In this section we briefly recall complexity bounds for basic algorithms for integers and polynomials. For some of them we give also short proofs to make the methods used here more transparent. Throughout this paper we use classical algorithms for both integers and polynomials. Even though this will not yield the best possible estimate of the complexity the main goal of this paper is to reveal computationally expensive parts of the parametrization algorithm. For detailed description of algorithms in this section we refer to [6, 7], etc. For elementary introduction the reader may refer to [2].

2.1. Integer arithmetic

The computational complexity of operations over integers is measured in terms of length of input, i.e. the number of bits needed to store the input into the memory. By length(a), a ∈ ℤ we denote ⌊log_{2}(|a|)⌋ + 2 (we take the most significant bit as sign bit).

Remark 2.1. Throughout this paper all logarithms are taken to the base 2.

The following proposition summarizes classical results on integer arithmetic.

Proposition 2.2. Let a, b ∈ ℤ and l_{a}, l_{b} be the length of a and b, respectively. Then it holds:

(i) The worst case complexity for adding a and b is bounded by O(max{l_{a}, l_{b}}) and

length(a + b) = O(max{l_{a}, l_{b}})

(ii) The worst case complexity for multiplying a and b is bounded by O(l_{a}l_{b}) and

length(ab) = O(l_{a} + l_{b})

(iii) The worst case complexity for computing a^{n} is bounded by O((n l_{a})^{2}). (iv) The worst case complexity for computing a mod b (|a| > |b|) is bounded by

O(l_{b}(l_{a} − l_{b} + 1)).

(v) The worst case complexity for computing the greatest common divisor of a and b is bounded by O(l_{a}(l_{b} − l_{c} + 1)), where l_{c} is the length of the gcd.

2.2. Polynomial arithmetic

Before we start to give complexity analysis of polynomial arithmetic we need to define some measures for the size of polynomials. Let a = a_{n}x_{r}^{n} + ⋯ + a_{0} be a multivariate polynomial in ℤ[x_{1}, …, x_{r−1}][x_{r}] with a_{i} ∈ ℤ[x_{1}, …, x_{r−1}]. The complexity of various operations with a is determined by the degree of a (regarded as a univariate polynomial in x_{r}) and by the size of its coefficients. In the sequel, we recall three well-known notions of a norm. In order to obtain an estimate of the size of coefficients we define the max-norm of a by

∥a∥_{max} := max_{i=0,...,n}{∥a_{i}∥_{max}}.

However this norm does not comprise any information on the degree of the polynomial. Hence numerous complexity estimates are given in terms of the 1-norm defined by

∥a∥_{1} := ∑_{i=0}^{n} ∥a_{i}∥_{1}

or the 2-norm defined by

∥a∥_{2} := (∑_{i=0}^{n} ∥a_{i}∥_{2}^{2})^{1/2}.

For a ∈ ℤ we define

∥a∥_{max} = ∥a∥_{1} = ∥a∥_{2} = |a|.

We have obvious relations among these norms. For a ∈ ℤ[x_{1}, …, x_{r}] it holds

∥a∥_{max} ≤ ∥a∥_{1}  (1)
∥a∥_{max} ≤ ∥a∥_{2}  (2)
∥a∥_{1} ≤ n^{r} ∥a∥_{max}  (3)
∥a∥_{2} ≤ n^{r/2} ∥a∥_{max}  (4)

Throughout this paper, for a ∈ ℤ[x_{1}, …, x_{r}], we will use L_{max}(a) and L_{1}(a) to abbreviate length(∥a∥_{max}) and length(∥a∥_{1}), respectively.

Proposition 2.3. Let A, B ∈ ℤ[x_{1}, …, x_{r}], n = max{deg_{x_{i}}(A)| i = 1, …, r}, m = max{deg_{x_{i}}(B)| i = 1, …, r}, and L_{A} = L_{max}(A), L_{B} = L_{max}(B). Then we have:

(i) The worst case complexity for adding A and B is O(k^{r}L) where k = max{m, n}, L = max{L_{A}, L_{B}}.

(ii) The worst case complexity for multiplying A and B is bounded by O(L_{A}L_{B}n^{r}m^{r}). (iii) The worst case complexity for computing the pseudoquotient and pseudoremainder of A

and B w.r.t. x_{r} (deg_{x_{r}}(A) ≥ deg_{x_{r}}(B)) is

O(n^{r} m^{r−1}(n − m + 1)((n − m + 2)L_{B} + L_{A})L_{B}).

Furthermore, for univariate polynomials the length of the max-norm of quotient and remainder is dominated by O((n − m + 1)L_{B} + L_{A}).

Proof. First two assertions are obvious. Let n_{r} := deg_{x_{r}}(A), m_{r} := deg_{x_{r}}(B). Computation of pseudo-quotient and pseudo-remainder can be described by the following recurrence relation:

A^{(0)} ← A
A^{(k)} ← lc(B)A^{(k−1)} − x_{r}^{deg_{xr} (A^{(k−1)})−m_{r}+1} lc(A^{(k−1)})B

where k = 1, …, deg_{x_{r}}(A) − m_{r} + 1. We see that

∥A^{(i)}∥_{max} = O(2^{i}∥A∥_{max} ∥B∥_{max}^{i}).

Each loop of the above recurrence requires O(n) multiplications of (r−1)-variate polynomials with lengths of max-norms O((n−m+1)L_{B} +L_{A}) and L_{B}. Combining these results together we get a bound as stated in the theorem.

Corollary 2.4. Let A, B be univariate polynomials over a field, n ≥ max{deg(A), deg(B)}, e ∈ ℕ, L_{A} = L_{max}(A), L_{B} = L_{max}(B). The worst case complexity for computing C ≡ A^{e} mod B is bounded by

O(n^{2} log e(eL_{A} + n log eL_{B})^{2})

Moreover, L_{max}(C) = O(eL_{A} + n log eL_{B}).

Proof. Without loss of generality we may assume e = 2^{k}. We use the well-known algorithm for exponentiation based on repeated squaring. See Algorithm 1.

Exppoly(A, B, e)

Input: univariate polynomials A, B, and e ∈ ℕ, e = ∑_{i=0}^{k} e_{i}2^{i} Output: A^{e} mod B

1. S_{0} ← 1; T_{0} ← A; for i = 0 to k do

2. if e_{i} = 1 then S_{i} ← S_{i−1}T_{i−1} mod B

3. T_{i} ← T_{i−1}^{2} mod B

end Algorithm 1:

Let us estimate the length of T_{i} in step 3. We easily obtain L_{max}(T_{i−1}^{2}) = O(log n + 2L_{max}(T_{i−1})). Using results of Proposition 2.3 we conclude L_{max}(T_{i}) = O(2L_{max}(T_{i−1})+nL_{B}). By induction L_{max}(T_{i}) = O(2^{i}L_{A} + niL_{B}). Hence upon termination

L_{max}(A^{e} mod B) = O(eL_{A} + n log eL_{B}).

When counting bit operations we may restrict the analysis to step 3. In the i-th loop, the multiplication costs O(n^{2}(2^{i}L_{A} + niL_{B})^{2}) and computing residuum O(n^{2}(nL_{B} + 2^{i}L_{A} + niL_{B})L_{B}). The overall complexity is then

O(n^{2} log e(eL_{A} + n log eL_{B})^{2}).

We will often need estimates of norms of polynomial divisors. The following lemma can be found in [8].

Lemma 2.5 (Landau-Mignotte-bound). Let A and C be univariate polynomials with integral coefficients. Moreover let C = AB for some B ∈ ℤ[x]. Then

(i) ∥B∥_{max} ≤ O(2^{n}∥C∥_{2}) = O(2^{n}n^{1/2}∥C∥_{max}) = O(2^{n}∥C∥_{max}) (ii) L_{max}(B) = O(n + L_{max}(C)) where n = deg(C).

In the next proposition, we summarize some basic results on polynomial remainder sequences, resultants, polynomial gcd’s and on solving linear systems (cf. [1] and others).

Proposition 2.6. Let A, B ∈ ℤ[x_{1}, …, x_{r}], n the maximum degree in any variable of A and B, and L_{max} := max{L_{max}(A), L_{max}(B)}. Then the following holds:

(i) The worst case complexity of the subresultant chain algorithm over ℤ[x_{1}, …, x_{r−1}][x_{r}] is bounded by O(n^{2r+2}(r log n + L_{max})^{2}). Furthermore, the subresultant coefficients are bounded in length by O(n(log n + L_{max})), and the degree of the k-th subresultant is at most k.

(ii) The worst case complexity of Brown’s modular gcd algorithm is

O(n^{2r+1}(r log n + L_{max})^{2}).

(iii) The worst case complexity of Collins’ modular resultant algorithm is

O(n^{2r+1}(r log n + L_{max}) + n^{2r}(r log n + L_{max})^{2}) =
O(n^{2r+1}(log n + L_{max}) + n^{2r}(log n + L_{max})^{2})

(iv) The worst case complexity of Bareiss’ algorithm for a linear system over ℤ[x_{1}, …, x_{r}] is bounded by O(k^{2r+5}n^{2r}L^{2}), where k is the order of the matrix of the system, L is the maximum length of 1-norms of its entries, and n bounds the degrees.

In the course of parametrization we will have to compute primitive part of polynomials in ℤ[x_{1}][x_{2}]. Thus, we will need bounds for computing the gcd of several polynomials in ℤ[x_{1}].

Corollary 2.7. Let G = {g_{1}, …, g_{s}} be a set of univariate polynomials over ℤ, Γ := max{∥g_{i}∥_{max} |g_{i} ∈ G}, L := length(Γ), and n := max{deg(g_{i})|g_{i} ∈ G}. The worst case complexity for computing gcd(g_{1}, …, g_{s}) is

O(sn^{3}(n^{2} + nL + L^{2})).

Moreover, the max-norm of gcd(g_{1}, …, g_{s}) is bounded by

∥ gcd(g_{1}, …, g_{s})∥_{max} = O(2^{n}Γ)
L_{max}(gcd(g_{1}, …, g_{s})) = O(n + L)).

Proof. Without loss of generality we may assume s = 2^{k} for some k. We will proceed by divide-and-conquer. Using the following recurrence

S_{j}^{(0)} ← g_{j}, j = 1, …, 2^{k}
S_{j}^{(i)} ← gcd(S_{2j−1}^{(i−1)}, S_{2j}^{(i−1)}), j = 1, …, 2^{k−i}, i = 1, …, k.

Upon termination the element S_{1}^{(s)} will contain the result. In the i-th step 2^{k−i} gcd’s of pairs of polynomials are computed. From Lemma 2.5 we see that the max-norm of polynomials in the i-th step is bounded by O(2^{n}Γ) (as they all divide some of g_{i}’s). Using Proposition 2.6 we may bound the number of bit-operations by

O(∑_{i=1}^{k} \frac{s}{2^{i}} n^{3}(n + L)^{2})).

Evaluating the closed form of this sum at k = log s we get the assertion of the corollary.

3. Parametrization algorithm

In this section we briefly describe an algorithm for parametrizing plane curves, that we will analyze in next subsections. For further details we refer to [11].

Basically, the parametrization process consists of two parts. First, the standard decomposition of singularities (including the neighboring ones, in general) is determined. In this step, the set of all singularities is decomposed according to their multiplicities. In the course of this process the genus is determined yielding a decision of rationality of the curve. Second, using these informations a rational parametrization is computed.

In the sequel, algorithms corresponding to the two steps from above are outlined. For this purpose, we will assume that the given curve is rational and therefore the algorithm will not compute the genus. The curve is supposed to be in regular position (i.e. no line parallel to axes cut the curve in more than one singularity). This can always be achieved by a suitable change of coordinates (cf. [10]).

3.1. Standard decomposition of singularities

Let K be a field of characteristic zero in which all the field operations can be carried out effectively. For two univariate polynomials A, B over a field, let res(A, B) denote the resultant of A and B, subres(A, B, x) the subresultant with respect to x, and A′ the derivative of A. The Algorithm 2 on the next page yields the standard decomposition of the set of singularities.

Remark 3.1. Some steps in the above algorithm have to be clarified theoretically and computationally. In step 5.3. the polynomials Ā_{i} defining the families of singularities are obtained. The x_{1} coordinates of all the corresponding (i + 1)-fold affine points of C are exactly the roots of Ā_{i}. Then, in step 5.5. x_{2}-coordinates of singularities are computed. Let p be an irreducible factor of Ā_{i}. As the curve is supposed to be in regular position, for each α with p(α) = 0 there is exactly one β such that (α : β : 1) is a singular point of F. Hence in each

M. Mňuk et al.: Complexity of Parametrizing Curves 315

Singularity(F) Input: F ∈ K[x_{1}, x_{2}, x_{3}] - defining homogeneous polynomial of an irreducible plane curve C of degree n in regular position Output: standard decomposition of singularities

1. F ← ∅;

2. f ← F (x_{1}, x_{2}, 1); B_{1} ← f;

3. B̄_{1} ← gcd(res_{x_{2}}(f, \frac{∂f}{∂x_{1}} ), res_{x_{2}}(f, \frac{∂f}{∂x_{2}} ));

4. B_{1} ← \frac{B̄_{1}}{gcd(B̄_{1},B̄′_{1})};

5. for i ≥ 2 while deg(B_{i−1}) > 0 do

5.1.  B̄_{i} ← gcd(res_{x_{2}}(f, \frac{∂^{i}f}{∂x_{1}^{i}}), res_{x_{2}}(f, \frac{∂^{i}f}{∂x_{1}^{i−1}∂x_{2}} ), …, res_{x_{2}}(f, \frac{∂^{i}f}{∂x_{1}∂x_{2}^{i−1}} ), res_{x_{2}}(f, \frac{∂^{i}f}{∂x_{2}^{i}}));

5.2. B_{i} ← \frac{B̄_{i}}{gcd(B̄_{i},B̄′_{i})};

5.3.  Ā_{i−1} ← \frac{B_{i−1}}{B_{i}};

5.4. if deg(Ā_{i−1}) > 0 then 5.5. q_{i−1}(x_{2}) ←

p̃_{i−1}(x_{1})x_{2} − p_{i−1}(x_{1}) = subres_{1}(f(x_{1}, x_{2}), \frac{∂f}{∂x_{1}} (x_{1}, x_{2}), x_{2})

mod Ā_{i−1}(x_{1});

5.6. F_{i−1}^{∗} ← \{(α : \frac{p_{i−1}(α)}{p̃_{i−1}(α)} : 1)\}_{Ā_{i−1}(α)=0}; 5.7. determine the expanded neighboring graph F_{i−1} of F_{i−1}^{∗}; 5.8. F ← F ∪ F_{i−1};

end

5.9. i ← i + 1;

end 6. repeat the process, dehomogenizing w.r.t. x_{2} and then w.r.t. x_{1};

7. return F Algorithm 2:

ℚ(α)[x_{2}] (p(α) = 0, p being a factor of Ā_{i}) we have deg_{x_{2}} gcd(f(α, x_{2}), \frac{∂f}{∂x_{1}} (α, x_{2})) = 1. This verifies the correctness of step 5.5. Finally, the set of i + 1-fold singularities is described by

{(αp̃_{i}(α) : p_{i}(α) : p̃_{i}(α))}_{Ā_{i}(α)=0}.

In case Ā_{i} is reducible, more families of singular points may be put together.

Remark 3.2. The output of algorithm SINGULARITY is a family of singular points separated according their multiplicities. Note that {(m(α) : n(α) : p(α))}_{Ā_{i}(α)=0} stands for a set of deg(Ā_{i}) of i + 1-fold points.

Now we are going to analyze the computing time of the algorithm SINGULARITY. Let F (x_{1}, x_{2}, x_{3}) be a homogeneous polynomial defining an algebraic rational plane curve C of degree n, in regular position, and such that all the singularities of C are ordinary. Note, that the algorithm SINGULARITY works for algebraic curves of any genus. It computes the neighborhood graph of C from which it is then trivial to read off the genus. Thus, at the same time, we obtain a decision procedure for determining the rationality of C. The analysis applies to curves of arbitrary genus.

Theorem 3.3. Let L_{F} := length(∥F ∥_{max}). The worst case complexity of the algorithm SINGULARITY is O(n^{12}(n log n + L_{F})^{2}).

Proof. One has basically to analyze the loop in step 5. The loop in step 5 will be executed at most O(n) times. Let T_{SING}(i, j) be the time of execution of step 5.j in the i-th loop. Then if I denotes the set of all the different multiplicities of points of C it holds

T_{SING} = ∑_{i∈I} ∑_{j=1}^{11} T_{SING}(i, j).

Let us consider now the worst case complexity of the execution of i-th loop in step 5. We may assume to have all derivatives of F precomputed and stored in a table. It can be easily verified that this step does not affect the overall complexity. Step 5.1. One has to calculate i + 1 derivatives of the form G_{k} = \frac{∂^{i}f}{∂x_{1}^{k}∂x_{2}^{i−k}}, i + 1 resultants

of the type R_{k} = res_{x_{2}}(f, G_{k}), and gcd(R_{0}, …, R_{i}). Using Proposition 2.6 we have for j = 0, …, i

L_{max}(\frac{∂^{j}f}{∂x_{k}^{j}}) = O(i log n + L_{F})
L_{max}(res_{x_{k}}(f, \frac{∂^{j}f}{∂x_{k}^{j}})) = O(n(i log n + L_{F})).

Then it follows that the time for computing the i + 1 resultants is dominated by i(n^{5}(i log n + L_{F}) + n^{4}(i log n + L_{F})^{2}) which is O(in^{5}(i log n + L_{F})^{2}). Finally, the time to compute the greatest common divisor is O(n^{6}i(n^{4} + n^{4}(i log n + L_{F}) + (n(i log n + L_{F}))^{2})) = O(in^{10}(i log n + L_{F})^{2}). Hence

T_{SING}(i, 1) = O(in^{10}(i log n + L_{F})^{2}).

Moreover, L_{max}(B̄_{i}) = O(n^{2} + n(i log n + L_{F})) and deg(B̄_{i}) ≤ n^{2}. Step 5.2. Since the modular gcd algorithm of Brown computes the gcd and the cofactors, it

holds that the step 5.2. is bounded in time by the time of computing the gcd(B̄_{i}, B̄′_{i}). Now, using Proposition 2.6, and the fact that L_{max}(B̄_{i}) = O(n(i log n + L_{F})), it follows that

T_{SING}(i, 2) = O(n^{8}(i log n + L_{F})^{2}).

We also observe that, since B_{i} is a divisor of res_{x_{2}}(f, \frac{∂^{i}f}{∂x_{1}^{i}}), it holds that length(B_{i}) = O(n(i log n + L_{F})).

Step 5.3. Applying Proposition 2.3, one has that

T_{SING}(i, 3) = O(n^{6}(i log n + L_{F})^{2}).

Step 5.5. Using Proposition 2.6 and that L_{max}(\frac{∂f}{∂x_{1}} ) = O(log n + L_{F}), one has that the subresultant computation requires time O(n^{6}(log n + L_{F})^{2}). Now, we have to bound the time for computing p̃(x_{1}) mod Ā_{i} and p(x_{1}) mod Ā_{i}. We observe that max{L_{max}(p_{i}), L_{max}(p̃_{i})} = O(n log n + nL_{F}) and max{deg(p_{i}), deg(p̃_{i})} = O(n^{2}). Furthermore for Ā_{i}, we use the fact that Ā_{i} divides res_{x_{2}}(f, \frac{∂f}{∂x_{1}} ) (all roots of Ā_{i} are x_{1}- coordinates of some singularities), and therefore deg(Ā_{i}) ≤ n^{2}, L_{max}(Ā_{i}) = O(n(n + L_{F})) (Lemma 2.5). Thus applying Proposition 2.3 one concludes that the time for the two divisions is bounded by O(n^{8}(log n + L_{F})^{2}). Hence

T_{SING}(i, 5) = O(n^{8}(log n + L_{F})^{2})).

By the hypothesis all singularities are ordinary hence no expansion of the neighboring tree is needed and step 5.7. does not contribute to the complexity. Then the worst case complexity for algorithm SINGULARITY can be bounded by

T_{SING} = O(∑_{i∈I} in^{10}(i log n + L_{F})^{2}).

Thus, since ∑_{i∈I} i^{2} = O(n^{2}),

T_{SING} = O(n^{12}(n log n + L_{F})^{2}).

Corollary 3.4. Let C be a irreducible plane algebraic curve with no neighboring singularities given by a homogeneous polynomial F of degree n. Then the genus of C can be computed in O(n^{12}(n log n + L_{F})^{2}) bit operations.

Proof. Using all informations on singularities of C, we have an algorithm for computing the genus. See Algorithm 3.

Genus(F)

1. F ←Singularity(C); g ← 0; for all S ∈ F do

2. m ← multiplicity(S); g ← g + m(m − 1)/2; end return (n − 1)(n − 2)/2 − g;

Algorithm 3:

We have Card(F) = O(n^{2}). Hence the running time is dominated by the computation in step 1.

In the following theorem we summarize some results on singularities which have partially been proved in course of complexity analysis of the algorithm SINGULARITY.

Theorem 3.5. Let F ∈ K[x_{1}, x_{2}, x_{3}] be a homogeneous polynomial of degree n defining an algebraic rational plane curve C with only ordinary singularities and let L_{F} := L_{max}(F). Then, if

⋃_{i∈I}{(m_{i,1}(α) : m_{i,2}(α) : m_{i,3}(α))}_{A_{i}(α)=0}

is the standard decomposition of the set of singularities 𝒮(C) of C it holds that:

(i) deg(A_{i}) ≤ n^{2}, deg(m_{i,j}) ≤ n^{2} for i ∈ I, j = 1, 2, 3; (ii) L_{max}(A_{i}) = O(n(n + L_{F})) for i ∈ I; (iii) L_{max}(m_{i,j}) = O(n^{3}(n + L_{F})) for i ∈ I, j = 1, 2, 3.

Proof. The first two statements have already been proved in Theorem 3.3. We also saw there, that any polynomial component m_{i,j}(t) in the standard decomposition is congruent modulo Ā_{i}(t) to a polynomial dominated in length by O(n(log n + L_{F})) and in degree by O(n^{2}). Therefore, using Proposition 2.3, one has that L_{max}(m_{i,j}) = O(n^{3}(n + L_{F})).

For rational singularities a better upper bound of the length may be given.

Proposition 3.6. Let F ∈ K[x_{1}, x_{2}, x_{3}] be a homogeneous polynomial of degree n defining an algebraic plane curve C. Then, the length of any coordinate of any rational singularity of C is bounded by O(n(log n + L_{max}(F))).

Proof. Let f(x_{1}, x_{2}) = F (x_{1}, x_{2}, 1), R_{1}(x_{1}) = res_{x_{2}}(f, \frac{∂f}{∂x_{1}} ), and R_{2}(x_{1}) = res_{x_{2}}(f, \frac{∂f}{∂x_{2}} ). Then the x_{1}-coordinate of any rational affine singularity is a common rational root of R_{1} and R_{2}. Therefore, the length of any x_{1}-coordinate of any rational singularity is bounded by the maximum of the lengths of R_{1} and R_{2} (cf. [8]),that is O(n(log n + L_{max}(F)). Similarly, considering resultants w.r.t. x_{1} one obtains the same bound for the x_{2}-coordinates.

3.2. Parametrization

In this section we design an algorithm for parametrization of plane rational curves with only ordinary singularities. See Algorithm 4 on the next page. Note, that according to Corollary 3.4 we may apply the subsequent algorithm to any irreducible plane curve regardless whether it is rational or not. In a preprocessing step we may determine the genus and refuse any non-rational curve causing no asymptotic increase of computing time. We assume that POINTS(F,k) is an auxiliary algorithm that computes k simple points on the curve given by F over the smallest algebraic extension of K. Here, we do not want to go into details of construction of such algorithm. For a description we refer to [5, 12].

Remark 3.7. We briefly comment some steps of the algorithm. In step 6, H_{a} is forced to pass through the standard decomposition of the set of singularities with a specified multiplicity. To achieve it, we refer to [11].

The elimination of factors corresponding to fixed common points of the curve and H_{a} can be done by computing the primitive part of S_{1} and S_{2} w.r.t. x_{2} and x_{1}, respectively, or explicitly by dividing by these factors, which are known in advance [11].

In the sequel, the complexity of the algorithm PARAMETRIZE is analyzed. For deriving complexity bounds, two different cases are distinguished. First, we consider only curves whose singularities are ordinary and rational. Second, we deal with the most general case that we consider: curves only with ordinary singularities; probably lying on some algebraic extension of the ground field, Furthermore, as we mentioned in the introduction, we do not take care of simple points on curves. We assume that as many simple points as the algorithm PARAMETRIZE needs are given. For actually finding them, we refer to [5], [12].

M. Mňuk et al.: Complexity of Parametrizing Curves 319

Parametrize(C) Input: F ∈ K[x_{1}, x_{2}, x_{3}] - homogeneous polynomial defining an irreducible rational curve C of degree n Output: rational parametrization of C

1. F ← SINGULARITY(F);

2. choose a ∈ {n − 2, n − 1, n};

3. k ← (a − n + 2)n + (n − 3);

4. {R_{1}, …, R_{k}} ← POINTS(F, k);

5. H_{a}(x_{1}, x_{2}, x_{3}) is a linear system of curves of degree a with undetermined coefficients;

6. pass H_{a}(x_{1}, x_{2}, x_{3}) through F, such that, if P is an r-fold point in F (including the neighboring one), then P has multiplicity r − 1 on H_{a};

7. pass H_{a}(x_{1}, x_{2}, x_{3}) through regular points {R_{1}, …, R_{k}};

8. if a = n then pass H_{a} through an additional point not on C;

9. solve the linear system of equations in the undetermined coefficients of H_{a} created in steps 6, 7 and 8, and substitute the solution in H_{a};

10. S_{1}(x_{2}) ← res_{x_{1}}(F (x_{1}, x_{2}, 1), H_{a}(x_{1}, x_{2}, 1));

11. S_{2}(x_{1}) ← res_{x_{2}}(F (x_{1}, x_{2}, 1), H_{a}(x_{1}, x_{2}, 1));

12. remove the factors in S_{1} and S_{2} coming from fixed intersections of F and H_{a};

13. solve the linear system of equations {S_{1}(x_{2}) = 0, S_{2}(x_{1}) = 0}, where x_{1}, x_{2} are the unknowns. Say that (R_{1}(t), R_{2}(t)) is the solution;

14. return (R_{1}(t), R_{2}(t))

Algorithm 4:

3.2.1. Rational ordinary singularities

In this subsection we deal with curves having only rational ordinary singularities.

Let F (x_{1}, x_{2}, x_{3}) ∈ K[x_{1}, x_{2}, x_{3}] be a homogeneous polynomial defining an algebraic rational curve C of degree n, in regular position, and such that all the singularities are ordinary and rational. We consider given simple points {R_{1}, …, R_{k}} on C with rational coordinates, where k = (a − n + 2) n + (n − 3) for some a ∈ {n − 2, n − 1, n}.

Lemma 3.8. The worst case complexity for the algorithm PARAMETRIZE, working on rational ordinary singularities, is

O(n^{12}(n log n + L_{F})^{2} + n^{12} max{L_{R}, log n + L_{S}}^{2})

where n is the degree of the curve, L_{F} = L_{max}(F), L_{R} is the maximum length of the given rational simple points, and L_{S} is the maximum length of singularities.

Proof. Let T_{PARAM}(i) be the time of execution of step i of the algorithm PARAMETRIZE. Then it holds that

T_{PARAM} = ∑_{i=1}^{14} T_{PARAM}(i).

From the Theorem 3.3 it follows that T_{PARAM}(1) = O(n^{12}(n log n + L_{F})^{2}). Steps 2 and 3 are irrelevant in terms of complexity. Also since a ≤ n one has that

T_{PARAM}(5) = O(n^{2}).

In the step 6, let P_{1}, …, P_{m} be the singularities of C and r_{1}, …, r_{m} the corresponding multiplicities. Let H_{a} be a generic tri-variate homogeneous polynomial with undetermined coefficients, i.e. H_{a} = ∑_{i+j+k=a} c_{ijk}X^{i}Y^{j}Z^{k}. Then, passing H_{a} through F, with the specified multiplicities, implies to compute

\{\{\frac{∂^{r_{j}−2}H_{a}}{∂x_{1}^{i_{1}}∂x_{2}^{i_{2}}∂x_{3}^{i_{3}}} (P_{j})\}_{i_{1}+i_{2}+i_{3}=r_{j}−2}\}_{j=1,...,m} .

This follows from the fact that i-th derivatives of H_{a} may be written as linear combinations of i + 1-st derivatives (this follows from Euler’s Theorem, cf. [3], p. 6).

Since the number of terms of each of the r_{j}(r_{j} − 1)/2 polynomials to be evaluated at P_{j} is (a − r_{j} + 3)(a − r_{j} + 4)/2, then the time for the execution is

T_{PARAM}(6) = O(∑_{j=1}^{m} \frac{r_{j}(r_{j} − 1)}{2} \frac{(a − r_{j} + 3)(a − r_{j} + 4)}{2}t_{j}),

where t_{j} is the time for evaluating any monomial i_{1}(i_{1} −1)·· · ··(i_{1} −α_{1} +1) i_{2}(i_{2} −1)·· · ··(i_{2} − α_{2} +1) i_{3}(i_{3} −1)·· · ··(i_{3} −α_{3} +1) X^{i_{1}−α_{1}}Y^{i_{2}−α_{2}}Z^{i_{3}−α_{3}}, i_{1} +i_{2} +i_{3} = a, α_{1} +α_{2} +α_{3} = r_{j} −2 at P_{j}. Then t_{j} is dominated by the time for evaluating an expression of the form AB^{a}, where A represents the coefficient of the monomial, length(A) = O(r_{j} log a), and B is the coordinate of P_{j} of maximal length. The time to compute B^{a} is dominated by (a length(B))^{2} hence

t_{j} = O(a^{2} length(B)^{2} + a length(B)r_{j} log a) = O(a^{2} length(B) (length(B) + r_{j}))

Hence using a ≤ n and ∑_{i=1}^{m} r_{j}(r_{j} − 1)/2 = (a − 1)(a − 2)/2, we obtain

T_{PARAM}(6) = O(n^{6}L_{S}(L_{S} + n)) = O(n^{6}L_{S}^{2} + n^{7}L_{S}).

In the step 7, let t be the time for passing H_{a} through one simple point R ∈ {R_{1}, …, R_{k}}. Then t ≤ \frac{(n+1)(n+2)}{2}t^{∗}, where t^{∗} is now the time for evaluating any monomial of H_{a} at R. Thus, t^{∗} is dominated by the time for computing B^{a}, where B is the coordinate of R_{i} of maximum length. Consequently,

T_{PARAM}(7) = O(kn^{2}a^{2}L_{R}^{2}) = O(n^{6}L_{R}^{2}).

In the step 8, if a = n then coordinates of an additional point not on C can always be taken bounded by n (not all points (k : 1 : 0), k = 0, …, n, may lie on C). Forcing H_{a} to pass through (k : 1 : 0) will result in the linear equation c_{010} + c_{110}k + ⋯ + c_{a10}k^{a} = 0. The time for computing its coefficients is

T_{PARAM}(8) = O(a^{2} log^{2} a) = O(n^{2} log^{2} n).

In the step 9, a linear system with O(n^{2}) equations has to be solved. On the other hand the length of the entries in the system is dominated by O(n log n + nL_{S}), for rows coming from step 6, and by O(nL_{R}), if the equation comes from steps 7 or 8. Thus, applying the Proposition 2.6, one has that the time for solving the system is dominated by

n^{10} max{n log n + dL_{S}, nL_{R}}^{2} = O(n^{12} max{L_{R}, log n + L_{S}}^{2})

And since the substitution in H_{a} of the solution takes O(n^{2}) it follows that

T_{PARAM}(9) = O(n^{12} max{L_{R}, log n + L_{S}}^{2}).

Now, we are interested in the length of the resulting pencil H_{a}. Then, taking into account that every coordinate of the solutions of a linear system can be expressed as a fraction of determinants, it follows that

L_{max}(H_{a}) = O(n^{3} max{L_{R}, log n + L_{S}})

In steps 10 and 11, we first observe that the maximal length of max-norms of polynomials in ℤ[x_{1}, x_{2}, t] (t being the remaining undetermined coefficient in the solution of the linear system in step 9) involved in the resultants is bounded by O(max{L_{F} , n^{3}D}), where D = max{L_{R}, log n + L_{S}}. Therefore, applying the Proposition 2.6 one has that both steps are dominated in time by n^{7}(log n + max{L_{F} , n^{3}D}) + n^{6} max{L_{F} , n^{3}D}^{2}. But, since n^{3} ≤ max{L_{F} , n^{3}D} it follows that

T_{PARAM}(10) ≈ T_{PARAM}(11) = O(n^{7}(log n + max{L_{F} , n^{3}D})
+ n^{6}(log n + max{L_{F} , n^{3}D}^{2}))
= O(n^{6} max{L_{F} , n^{3}D}^{2}).

On the other hand, from Proposition 2.6 we have that L_{max}(S_{i}) = O(n^{2} max{L_{F} , n^{3}D}).

In the step 12, the quotient of S_{i} and a polynomial p_{i}, obtained as the product of all the factors produced by singular and regular points, has to be calculated. The computation of p_{i} takes O(n^{4}D^{2}), deg(p_{i}) = O(n^{2}) and length(p_{i}) = O(n^{2}D). Thus

T_{PARAM}(12) = O(n^{6} max{L_{F} , n^{3}D}^{2}).

Finally, since the steps 13 and 14 are irrelevant for the complexity analysis, taking in account the result of Theorem 3.3 one concludes that

T_{PARAM} = O(n^{12}(n log n + L_{F})^{2} + n^{12} max{L_{R}, log n + L_{S}}^{2}).

Remark 3.9.

1. In deriving complexity bounds for the algorithm PARAMETRIZE, in the rational ordinary singularity case, we have not utilized any special simplified version for the algorithm SINGULARITY. We have just applied the Theorem 3.3. A suitable version for rational singularities may reduce the upper bound.

2. In the proof of the previous lemma, we have implicitly assumed that the coordinates of the rational singularities are known, although algorithm SINGULARITIES returns families of points. This is not any loss of generality, since an optional step for detecting them can be inserted in the outline of SINGULARITY, without modifying the complexity bound in the Theorem 3.3

In the last part of this subsection we apply the Proposition 3.6 and the previous lemma to derive an upper bound depending only on the rational simple points.

Theorem 3.10. The worst case complexity for algorithm PARAMETRIZE, working on rational ordinary singularities, is

O(n^{12} max{L_{R}, n(log n + L_{F})}^{2})

where n is the degree of the curve, L_{F} = L_{max}(F), and L_{R} bounds the length of the given rational simple points.

Proof. By Lemma 3.8, we know that O(n^{12}(n log n+L_{F})^{2}+n^{12} max{L_{R}, log n+L_{S}}^{2}) bounds the worst case complexity of the algorithm. By Proposition 3.6 L_{S} = O(n(log n + L_{F})). Combining these bounds we immediately obtain the assertion of the theorem.

Corollary 3.11. The worst case complexity of algorithm PARAMETRIZE, working on rational ordinary singularities, is bounded by O(n^{14} log^{2} n max{L_{R}, L_{F} }^{2}).

3.2.2. Standard families of ordinary singularities

This subsection is dedicated to analysis of the complexity in general. We consider curves having only ordinary singularities (i.e. without neighboring ones), possibly lying in some algebraic extensions of the ground field.

Let F ∈ K[x_{1}, x_{2}, x_{3}] be a homogeneous polynomial defining an algebraic rational curve C in regular position of degree n with only ordinary singularities. We consider {R_{1}, …, R_{k}} to be given rational simple points on the curve, where k = (a − n + 2)n + (n − 3) and a ∈ {n − 2, n − 1, n}. Then, the following lemma gives an upper bound for the worst case complexity in terms of the degree and the length of the curve, of the rational simple points and of the standard decomposition.

Theorem 3.12. The worst case complexity for the algorithm PARAMETRIZE is

O(n^{26}(n + L_{F})^{2} + n^{6}L_{R}^{2})

where n is the degree of the curve, L_{F} = length(∥F ∥_{max}), L_{R} is the maximum length of coordinates of simple points returned from the procedure POINTS.

Proof. We will analyze the algorithm PARAMETRIZE allowing the coordinates of singularities to lie in finite extensions of the ground field. Let T_{PARAM} have the same meaning as in the proof of Lemma 3.8. The complexity of first five steps is independent of the type of singularities and has already been determined.

Let F_{S} be the standard singularity decomposition computed in step 1. Then F_{S} may be written as

F_{S} = ⋃_{i∈I} F_{i},

where F_{i} = {(m_{i}(α), n_{i}(α), p_{i}(α))}_{Ā_{i}(α)=0}. In step 6, since F_{i} contains (i + 1)-fold points, passing H_{a} through F_{i} implies to force the polynomials

\{\frac{∂^{i−1}H_{a}}{∂x_{1}^{i_{1}}∂x_{2}^{i_{2}}∂x_{3}^{i_{3}}} \}_{i_{1}+i_{2}+i_{3}=i−1}

to vanish on F_{i}. Therefore, if T_{i} is the time for forcing one of these i(i + 1)/2 polynomials to vanish on F_{i}, it holds that T_{PARAM}(6) = O(∑_{i∈I} i^{2}T_{i}). In deriving bounds for T_{i}, we observe that computing time for obtaining

G(t) = \frac{∂^{i−1}H_{a}}{∂x_{1}^{i_{1}}∂x_{2}^{i_{2}}∂x_{3}^{i_{3}}} (m_{i}(t), n_{i}(t), p_{i}(t))

and g(t) ≡ G(t) mod Ā_{i}(t) have to be analyzed. Since \frac{∂^{i−1}H_{a}}{∂x_{1}^{i_{1}}∂x_{2}^{i_{2}}∂x_{3}^{i_{3}}} is a polynomial of degree

a − i + 1 with O(a − i + 2)(a − i + 3)/2) terms, it follows that, as a ≤ n, T_{i} = O(n^{2}t_{i}), where t_{i} is the time for computing cB(t)^{3n} mod Ā_{i}, with c being an integer of length O(i log n), B ∈ {m_{i}, n_{i}, p_{i}}. Recall (by Theorem 3.5), L_{max}(B) = O(n^{3}(n + L_{F})), deg(B) = O(n^{2}), L_{max}(Ā_{i}) = O(n(n + L_{F})), deg(Ā_{i}) = O(n^{2}). Using Corollary 2.4 we obtain L_{max}(B(t)^{3n} mod Ā_{i} = O(n^{4}(n + L_{F})) and t_{i} = O(n^{11}(n + L_{F})^{2}). Hence

T_{PARAM}(6) = O((n^{15}(n + L_{F})^{2}).

For steps 7 and 8, reasoning as in the proof of Lemma 3.8, it holds that

T_{PARAM}(7) = O(n^{6}L_{R}^{2})
T_{PARAM}(8) = O(n^{3} log n).

In step 9, linear system of O(n^{2}) equations has to be solved. Its entries are univariate polynomials p(t) with L_{max}(p) = O(n^{4}(n + L_{F})) (thus also L_{1}(p) = O(n^{4}(n + L_{F}))) and deg(p) = O(n^{2}). Using Proposition 2.6 we obtain

T_{PARAM}(9) = O(n^{26}(n + L_{F})^{2}).

In steps 10 and 11, length of max-norms of polynomials in ℤ[x_{1}, x_{2}, t] involved in the resultant are bounded by O(n^{4}(n + L_{F})), where applying Proposition 2.6 one has

T_{PARAM}(10) ≈ T_{PARAM}(11) = O(n^{14}(n + L_{F})^{2})).

In step 12 we first compute ∏(x_{1} −ω_{i,1}(t)) and ∏(x_{2} −ω_{i,2}(t)) where ω_{i,1} and ω_{i,2} are first and second coordinates of a singularity of F, respectively. Then an exact division of S_{i} by these polynomials is performed. Since the degree in x_{i} is O(n) and the length of max-norm is bounded by O(n^{3}(n + L_{F})) (3.5) using Proposition 2.3 we obtain

T_{PARAM}(12) = O(n^{11}(n + L_{F})^{2}).

Finally, since steps 13 and 14 are irrelevant in terms of complexity, we conclude

T_{PARAM} = O(n^{26}(n + L_{F})^{2} + n^{5} log nL_{R}^{2}).

4. Curves with neighboring points

Up to now we considered and analyzed algorithms for curves devoid of complicated singularities, i.e. of those having no neighborhood points. Though curves with complex singularities are encountered very often. In this section we study the classical algorithm for computing the neighborhood tree, give basic analysis of its behavior in terms of complexity, and outline the impact on the algorithm SINGULARITY and PARAMETRIZE.

4.1. Computing neighboring singularities

Now we give a sketch of the algorithm for computing the neighborhood graph for a given absolutely irreducible plane curve. See Algorithm 5. As a neighboring singularity is just a usual singularity of a transformed curve we will use the representation as in Section 3.1. Though due to the rather complicated nature of neighboring singularities we will be forced to work in multiple extensions of the underlying field.

NEIGHBORHOOD TREE(P) Input: A singular point P of a curve Output: Neighborhood tree rooted in P

1. determine a change of coordinates T_{1} moving the projective point (0 : 0 : 1) to P;

2. determine a change of coordinates T_{2} such that F′ = F ∘ T_{1} ∘ T_{2} contains (0 : 0 : 1) but none of (1 : 0 : 0), (0 : 1 : 0) and such that no axis is tangent at (0 : 0 : 1) to F′;

3. perform the quadratic transformation on F′ centered at (0 : 0 : 1) yielding a new curve F′′;

4. compute the set S of singularities on F′′ ∩ V (Z);

5. for all R ∈ S do

6. call NEIGHBORHOOD TREE recursively on R;

end Algorithm 5:

Remark 4.1. In the general version of the parametrization algorithm the above procedure will be called in step 5.7. of the algorithm SINGULARITY in Subsection 3.1.

Let us have a closer look at this algorithm. In each recursive call we are computing singular points hence possibly introducing new algebraic extensions. We will examine the two first recursive calls to NEIGHBORHOOD TREE.

(a) Let K be the coefficient domain of the original polynomial F defining the curve. Let P be a singularity of F computed by the algorithm SINGULARITY. Hence

P = (m(α) : n(α) : p(α)), A(α) = 0

where A(U) is a squarefree univariate polynomial (not necessarily irreducible) with a root α. We will mimic the computing in K[α] by performing all computations in K[U]/(A(U)). However, care is needed when doing divisions.

(b) In the step 1. of the previous algorithm we set up a transformation T_{1} which moves the point (0 : 0 : 1) to one singularity. Then T_{1} may contain algebraic numbers as coefficients. Following the transformed polynomial F′′ has coefficients in K[α]. So we have to perform all computations modulo A(U).

(c) Obviously, each recursive call may introduce a new extension of the previously obtained field so that finally we will be computing in K[α_{1}, …, α_{l}]. All computations in this field will be mimicked in the ring K[U_{1}, …, U_{l}] modulo the triangular system of polynomials

A_{1}(U_{1})
A_{2}(U_{1}, U_{2})
⋮
A_{l}(U_{1}, …, U_{l}).

For the sake of complexity consideration it is important to estimate the depth of the neighborhood graph. As we saw in the Section 3 the number of new variables has an immense impact on the theoretical complexity of the parametrization algorithm. In the sequel we will show that this number may be of the same order as the degree of the curve.

We prove some facts about the depth of the neighborhood graph now.

Theorem 4.2. There is an infinite family of rational plane curves {C_{k}} where the depth of the neighborhood graph is Θ(deg(C_{k})) (i.e. of the same order as deg(C_{k})).

We will prove some auxiliary lemmas from which the theorem will immediately follow.

Lemma 4.3. Let F_{k}(X, Y, Z) = X^{2k+1} − Y^{2}Z^{2k−1} and

Φ_{i}^{(k)} = Z^{2k−2i−1}(X + Y)^{2k−2i+1}A_{i}^{(k)}(X, Y, Z) − (XY)^{2k−1}(X − Y)^{2}B_{i}^{(k)}(X, Y, Z) (5)

where

A_{1}^{(k)} = 1  (6)
A_{i}^{(k)} = A_{i−1}^{(k)}(XY, XY + XZ − Y Z, (X + Y)Z)(2XY + XZ − Y Z)^{2k−2i+3}  (7)
B_{1}^{(k)} = 1  (8)
B_{i}^{(k)} = B_{i−1}^{(k)}(XY, XY + XZ − Y Z, (X + Y)Z)(XY + XZ − Y Z)^{2k−1}.  (9)

Then it holds

(i) For all k ≥ 1, C_{k} = V (F_{k}) is a parametrizable plane curve.

(ii) Φ_{i}^{(k)} determines points in the i-th neighborhood of the point (0 : 0 : 1) on C_{k}.

(iii) For all i ≤ k − 1, Φ_{i}^{(k)} has a double non-ordinary point (1 : 1 : 0).

Proof. It is easy to show the rationality of C_{k}. The transformation X = T^{2}, Y = T^{2k+1}, Z = 1 yields the desired birational mapping.

In order to verify the second assertion we perform the following changes of coordinates in ℙ^{2}:

T_{1} : X ← Z  T_{2} : X ← X + Y  T_{3} : X ← Y Z
Y ← Y + Z  Y ← −X + Y  Y ← XZ
Z ← X  Z ← Z  Z ← XY.

The transformation T_{1} moves the point (0 : 0 : 1) to (1 : 1 : 0), T_{2} assures that Φ_{i}^{(k)} does not pass through (1 : 0 : 0) and (0 : 1 : 0), and no axis is a tangent to Φ_{i}^{(k)} at (0 : 0 : 1). The mapping T_{3} is the well known quadratic transformation. Putting them together we obtain

T : X ← XY
Y ← XY + XZ − Y Z
Z ← (X + Y)Z.

First we apply T_{1} and then T_{3} to C_{k} getting Φ_{1}^{(k)}. By induction on i it is not hard to verify Formulae 5 and 6.

For the last assertion of the lemma it is sufficient to consider

\frac{∂Φ_{i}^{(k)}(X, 1, Z)}{∂X} and \frac{∂Φ_{i}^{(k)}(X, 1, Z)}{∂Z}

at X = 1, Z = 0. It is easy to see that (1 : 1 : 0) is exactly a double point on Φ_{i}^{(k)}, for 1 ≤ i ≤ k − 1.

As we agreed on using multiple extensions whenever an enlargement of the ground field is required every such new extension is represented by a polynomial in one additional variable. From the Theorem 4.2 we see that the computation of the neighborhood graph may extend the ground field several times hence introducing a number of variables asymptotically equivalent to the degree of the curve. The complexity estimates from the Section 2 imply an exponential time growth for the algorithm SINGULARITY and hence for the parametrization when run on curves with neighboring points. This is due to the non-constant number of new variables introduced in the process of expanding the neighborhood graph.

Even though we have an explicit bound for the total number of points in the neighborhood graph of the curve O(n^{2}), n being the degree of the curve, in the course of the computation we perform arithmetic operations over polynomials with a growing number of variables. In order to stay below a polynomial time bound we would have to require a constant depth of the neighborhood graph of curves under consideration. The Theorem 4.2 shows that this is impossible.

Resuming, we have shown that there is an infinite family of rational curves on which our algorithm takes exponential time in the degree of the curve. Thus no polynomial time bound is possible using algorithms described above to parametrize curves with neighboring points. Only in a special case where the depth of the neighborhood graph is bounded by a constant we may achieve a polynomial running time.

5. Conclusions

Even though the parametrization algorithm is in use for a long time only little was known about its complexity. Mainly due to the prohibitive running time it is not feasible to determine its average behavior by testing it on a large set of data. In this paper, the worst case complexity for the special case of curves lacking neighboring singularities has been proved. Practical examples reveal that the worst case complexity determined in this paper is too pessimistic for most cases (curves of degree 10 have been parametrized in a reasonable amount of time). This is partially due to the high estimate for the length of coordinates of singularities. If this parameter was taken as an input measure, finer theoretical complexity could be obtained and also some bounds observed in practical computations might be matched closely.

In the course of the analysis of parametrization algorithm we obtained an estimate for the time needed to determine the genus of an irreducible curve and an algorithm to decompose the set of singularities.

Moreover, we have shown that allowing neighboring points may considerably increase the amount of time needed to parametrize curves. It turns out that using strategies described in this paper the time to parametrize a curve may be exponential in the degree of the input curve.

All algorithms described in this paper were implemented in the Maple package CASA ([9]) developed at the Research Institute for Symbolic Computation, Linz, Austria.

References

[1] Buchberger, B.; Collins, G. E.; Loos, R.: Computer Algebra; Symbolic and Algebraic Computation. Springer Verlag Wien–New York, second edition, 1982.

[2] Collins, G. E.; Mignotte, M.; Winkler, F.: Arithmetic in basic algebraic domains. In: Computer Algebra; Symbolic and Algebraic Computation (vgl. [1]), 184–220.

[3] Fulton, W.: Algebraic Curves. Addison–Wesley, 1989.

[4] Gebauer, R.; Kalkbrener, M.; Wall, B.; Winkler, F.: CASA: A Computer Algebra Package for Constructive Algebraic Geometry. In: S. M. Watt, editor, ISSAC 91, 403–410, Bonn, Germany, July 1991.

[5] Hilbert, D.; Hurwitz, A.: Über die Diophantischen Gleichungen vom Geschlecht Null. Acta Math. 1890, 217–224.

[6] Knuth, D. E.: The Art of Computer Programming, vol. 2: Seminumerical Algorithms. Addison–Wesley, second edition, 1981.

[7] Loos, R.: Generalized polynomial remainder sequences. In: Computer Algebra; Symbolic and Algebraic Computation (vgl. [1]), 115–137.

[8] Mignotte, M.: Some useful bounds. In: Computer Algebra; Symbolic and Algebraic Computation (vgl. [1]), 259–263.

[9] Mňuk, M.; Wall, B.; Winkler, F.: CASA reference manual (version 2.2). Technical report, Research Institute for Symbolic Computation, Linz, Austria, 1994. See also: http://www.risc.uni-linz.ac.at:/labs-info/compal/casa/casa.html.

[10] Sakkalis, T.; Farouki, R.: Singular points of algebraic curves. J. Symb. Comput. 9 (1990), 405–421.

[11] Sendra, J. R.; Winkler, F.: Symbolic parametrization of curves. J. Symb. Comput. 12(6) (1991), 607–631.

[12] Sendra, J. R.; Winkler, F.: Determining simple points on rational algebraic curves. Technical Report RISC-93-23, Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria, 1993.

Received July 14, 1995