Relaxed lifting of triangular sets

 Notations Throughout

this chapter, we use the notions and notations of Chapter 1, Section 1.1. In particular, we use the ring of p-adics Rp with its assumption on the length function λ and its complexity model. We recall that I(n) and R(n) denotes the cost of multiplying two p-adics of length n by respectively an off-line and an on-line algorithm. In this chapter, we choose to denote elements by small letters, e.g. a∈Rp, vectors by bold fonts, e.g. a ∈ (Rp) n , and matrices by capital letters, e.g. A ∈Mn(Rp). We denote by v1 ·v2 the inner product between two vectors and c ×v the coefficientwise product of a scalar c by a vector v. Let M(d1, , dn) denote the cost of multiplication of dense multivariate polynomials P ∈ R[X1, , Xn] satisfying degXi (P) 6 di for all 1 6 i 6 n. By Kronecker substitution, we get that M(d1, , dn) = O(M(2n d1 dn)). We point to Chapter 1, Section 1.2 for details on the cost function M of polynomial multiplication. We denote by hP1, , Pki the ideal spanned by P1, , Pk ∈ R[X1, , Xn].Let us introduce the notion of univariate representation of a zero-dimensional ideal I ⊆R[X1, , Xn] for any ring R. An element P of A7 R[X1, , Xn]/I will be called primitive if the R-algebra R[P] spanned by P is equal to A itself. If Λ is a primitive linear form in A, a univariate representation of A consists of polynomials P = (Q, S1, , Sn) in R[T] with deg (Si) < deg (Q) such that we have a R-algebra isomorphism A = R[X1, , Xn]/I → R[T]/(Q) X1, , Xn  S1, , Sn Λ  T . The oldest trace of this representation is to be found in [Kro82] and a few years later in [Kön03]. A good summary of their work can be found in [Mac16]. The shape lemma [GM89] states the existence of such a representation for a generic linear form Λ of a zero-dimensional ideal. Different algorithms compute this representation, from a geometric resolution [GHMP97, GHH+97, GLS01, HMW01] or using a Gröbner basis [Rou99]. When using univariate representations, the elements of A ≃ R[T]/(Q) are then represented as univariate polynomials of degree less than d 7 deg (Q). Then, multiplication in A costs O(M(d)). A triangular set is a set of n polynomials t= (t1, , tn)⊆ R[X1, , Xn] such that ti is in R[X1, , Xi ], monic and reduced with respect to (t1, , ti−1). The notion of triangular set comes from [Rit66] in the context of differential algebra. Many similar notions were introduced afterwards [Wu84, Laz91, Kal93, ALMM99]. Although all these notions do not coincide in general, they are the same for zero-dimensional ideals. As it turns out, univariate representations can be seen as a special case of triangular sets. Indeed, with the notations above, the family (Q(T), X1 − S1(T), , Xn − Sn(T)) is a triangular set in the algebra R[T , X1, , Xn]. For any triangular set t in R[X1, , Xn], we define the number e of essential variables by e 7 #{i|di > 1} where di 7 degXi (ti). If r is a reduced normal form modulo t, then r is written on e variables, that is r ∈ R[Xj]j∈{i|di>1}. Only those variables play a true role in the quotient algebra A 7 R[X1, , Xn]/hti. We define Rem(d1, , de) to be the cost of reducing polynomials P ∈ R[X1, , Xn] satisfying degXi (P) 6 2 (di − 1) modulo t. As it turns out, the cost of arithmetic operations in the quotient algebra A is O(Rem(d1, , de)) (see Section 6.2). The number e of essential variables plays an important role because Rem(d1, , de) is exponential in e. As in Chapter 3, we denote by ω the exponent of linear algebra on fields, so that we can multiply and invert matrices in Mn×n(R) in O(n ω ) arithmetic operations. We will also need to invert matrices over rings that are not fields, e.g. in quotients of polynomial ring R[T]/(Q). We denote by O(n Ω) the arithmetic complexity of the elementary operations on n × n matrices over any commutative ring: addition, multiplication, determinant and adjoint matrix. In fact, Ω can be taken less than 2.70 [Ber84, Kal92, KV04]. For the special case of matrices over Rp[T]/(Q), we combine linear algebra over (R/(p))[T]/(Q) and Newton iteration to invert matrices in time O((n ω I(N) + n Ω) M(d)), where d 7 degT (Q).In this chapter, we denote by f = (f1, , fn)∈R[X1, , Xn] a polynomial system given by an s.l.p. with L operations in {+,−, ∗}. If Lfi is the evaluation complexity of only the output fi , then we denote by L ⊥ 7 Lf1 + + Lfn the complexity that corresponds to computing f1, , fn independently, that is without sharing any operations between the computation of different outputs fi . Since Lfi6L, we always have L 6 L ⊥ 6 n L. When f is given as an s.l.p., its Jacobian matrix can be computed by an algorithm from Baur and Strassen [BS83]. This method uses O(Lfi ) arithmetic operations to compute the gradient of fi . Therefore, the Jacobian matrix of f can be evaluated in time O(L ⊥). 

Motivations

Lifting triangular sets (or univariate representations) is a crucial operation. Most implementations of algorithms that compute triangular set on rationals compute this object modulo a prime number, and then lift the representation. For example, the Kronecker software [L+02] for univariate representations and the RegularChains package [LMX05] of Maple for triangular sets use a lifting. Even better, the geometric resolution algorithm [GLS01, HMW01] which is implemented in Kronecker requires yet another lifting: a lifting on power series is employed to compute univariate representations of curves, which is a basic step of the algorithm. As it turns out, most of the time required to compute triangular sets (or univariate representations) is spend in the lifting. Therefore, any improvement on the lifting complexity will have repercussions on the whole algorithm. It was shown in Chapter 5 that relaxed algorithms could reduce the cost due to linear algebra when lifting a regular root of a polynomial system compared to offline, or zealous, algorithms. In the same way that the Newton iteration was adapted to lift univariate representations in [GLS01, HMW01] and then triangular sets in [Sch02], we adapt our relaxed approach to lift such objects with the hope of getting rid of the contribution of linear algebra in the complexity. 

Quotient and remainder modulo a triangular set

This section deals with Euclidean division modulo a triangular set. From now on, we denote by t= (t1, , tn) a triangular set of R[X1, , Xn]. Computing remainders is a basic operation necessary to be able to compute with the quotient algebra A 7 R[X1, , Xn]/hti. We are also interested in the quotients of the division since we will need them later.

Overview of off-line lifting algorithms

We present three existing lifting algorithms, which are off-line, in increasing order of generality (and complexity). First algorithm lifts only a regular root, so it applies only to triangular sets with d1 = = dn = 1. Second algorithm lifts a univariate representation, that is a triangular set with d1 = = dn−1 = 1 and any degree dn. And finally we present an algorithm that lift any triangular set.

Hensel-Newton local lifting of a root

We start by recalling the local Newton iterator, that lift a regular root of an algebraic system into the completion ring Rp. It was first introduced by [New36] for finding power series solutions of univariate polynomials with coefficients in k[[X]]. This method allows a local study of an algebraic variety. A relaxed version of this algorithm is presented in Chapter 5.We detail the Newton iteration that doubles the precision of a regular solution of the algebraic system f.