Special Semester on Gröbner Bases and Related Methods 2006

Linz

Algorithms for basic ideal/module operations [in the CoCoALib]

Massimo Caboara Dipartimento di Matematica Università di Pisa caboara@dm.unipi.it

February 28th, 2006 What are we speaking about: Syzygy, ∩, Colon, ϕ^{−1}, Linear System Solving, … Not so basic: Saturation, (Multi)Homogenization, Resolution, … Algorithms are well known but … We have: Buchberger algorithm for ideals

• we want: Buchberger algorithm for modules • we want: operations for ideals

• we want: operations for modules

• we want: HDriven optimizations Buchberger for modules: idealization

• k[x_{1}, …, x_{n}]^{r} ⟶^{ϕ} k[x_{1}, …, x_{n}, e_{1}, …, e_{s}] module embedding

• Slight modifications of the standard Buchberger algorithms for ideals produce an efficient and easy to implement algorithm for modules in the polynomial ring k[x_{1}, …, x_{n}, e_{1}, …, e_{s}]

• ϕ can be made graded and ordered Modus operandi:

M ⊂ k[x]^{r} ⟶^{ϕ} M′ ⊂ k[x, e] ⟶^{Buch ′} GB(M′) ⊂ k[x, e] ⟶^{ϕ^{−1}} GB(M) ⊂ k[x]^{r}

We have a Buchberger’s algorithm for modules - now what?

First problem: syzygy computations Standard algorithm:

1. Gröbner Basis with bookkeeping

2. Syzygy from the GB

3. (opt) Syzygy of the Original generators [via Linear Algebra] Syzygy: details

Input (f_{1}, …, f_{k}).

• Extended Buchberger Algorithm ⟶ GB G + bookkeeping matrix A

Modifications: New matrix A. Special representation via division algorithm S_{ij} = q_{1}g_{1} + ⋯ + q_{s′}g_{s′} + p... If p ≠ 0 append column vector \frac{t_{j}}{c_{i}cgd(t_{i},t_{j})} a_{i} − \frac{t_{i}}{c_{j}cgd(t_{i},t_{j})} a_{j} − q_{1}a_{1} ⋯ − q_{s′}g_{s′} to A

• Compute B s.t. G = HA, H = GB via division algorithm.

• Special algorithm for M, Gröbner Basis of the syzygy of G

• Columns of (AM | I_{t} − AB) give syzygy of H

That is complex!

An old problem: A^{−1} A ∈ Mat_{r×r}(K)

A^{−1} = \frac{1}{det (A)} [\begin{matrix}(−1)^{1+1} A_{1,1} & … & (−1)^{1+r} A_{1,r} \\ ⋮ & ⋮ & ⋮ \\ (−1)^{r+1} A_{r,1} & … & (−1)^{r+r} A_{r,r} \end{matrix} ]

det A = ∑_{σ∈S_{n}}(sgn(σ)a_{1σ(1)} a_{2σ(2)} ⋯ a_{rσ(r)}) A_{i,j} = det M_{i,j} M_{i,j} = A − i^{th}row , j^{th}col An old solution Old algorithm New indeterminates keep track of operations

A · x = b [A | b | I_{r}] ⟶^{GJ} \{ \begin{matrix}[I | x̄ | A^{−1}] \\ or \\ A is not invertible \end{matrix} Syzygy: example

Syz(x + y, x − y) = [\begin{matrix}y − x \\ x + y \end{matrix}]

[\begin{matrix}x + y & x − y \\ 1 & 0 \\ 0 & 1 \end{matrix}] RedGBasis ⟶ [ \begin{matrix}y  x & 0 \\ \begin{matrix}1/2 & 1/2 \\ −1/2 & 1/2 \end{matrix} & [\begin{matrix}y − x \\ x + y \end{matrix}] \end{matrix} ]

Proposition Let S = {v_{1}, …, v_{k}} ⊆ (k[x])^{r}

[\begin{matrix}S \\ I_{k} \end{matrix}] ⟶^{GB_{τ}} [ \begin{matrix}GB_{τ′}(S) & 0 \\ • & GB_{τ′′}(Syz (S)) \end{matrix} ]

τ suitable module term-ordering eliminating the first components τ′ = τ_{|k[x]^{r}} τ′′ = τ_{|k[x]^{k}} Module component elimination: not as bad as indeterminate elimination M ⊆ k[x]^{r}, τ′ module term-ordering

M ⟶^{GB_{τ′}} ( \begin{matrix}GB_{τ}(I_{1}) & 0 & ⋯ & 0 \\ • & GB_{τ}(I_{2}) & & ⋮ \\ ⋮ & • & & ⋮ \\ ⋮ & ⋮ & & 0 \\ • & • & ⋯ & GB_{τ}(I_{r}) \end{matrix} )

\overbrace{G_{s}}

G_{s} is a τ′ − GBasis M ∩ (0^{r−s} ⊕ k[x]^{s}) = (G_{s}) Module term ordering τ′ :

me_{i} >_{τ′} ne_{j} ⇔ \begin{cases}i > j \\ i = j and m >_{τ} n \end{cases}

Linear Operations via module component elimination

M ⟶ [\begin{matrix}M \\ I \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 \\ • & Syz(M) \end{matrix} ]

M, N ⟶ [\begin{matrix}M & N \\ 0 & N \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 \\ • & M ∩ N \end{matrix}]

M, f ⟶ [\begin{matrix}M & f · I \\ 0 & I \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 \\ • & M : (f) \end{matrix} ]

M, v ⟶ [\begin{matrix}M & v \\ 0 & 1 \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 \\ • & M : (v) \end{matrix} ]

M_{ϕ}, M ⟶ [\begin{matrix}M & M_{ϕ} \\ 0 & I \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 \\ • & ϕ^{−1}(M) \end{matrix} ]

AX = B mod N ⟶ [\begin{matrix}−B & A & N \\ I & 0 & 0 \\ 0 & I & 0 \end{matrix}] ⟶^{GB_{τ′}} [\begin{matrix}• & 0 & 0 \\ • & C & 0 \\ • & D & E \end{matrix}]

AX = B mod N has solutions ⇔ C = I A(D + E) = B mod N, E ∈ E Comparisons

GB(tM + (t − 1)N) ≠ GB ([\begin{matrix}M & N \\ 0 & N \end{matrix}]) I = (x, y), J = (x, z) ⊂ ℚ[x, y, z]

(I ∩ J) = (tI + (1 − t)J) ∩ ℚ[x, y, z] = (x, yz)
= ([ \begin{matrix}[x & y] & [x & z] \\ 0 & 0 & [x & z] \end{matrix} ]) ∩ (0 ⊕ ℚ[x, y, z]) = (x, yz)

GB(tI + (1 − t)J) = {zt − z, yt, x, yz }

1 2 3 4

GB ([ \begin{matrix}x & y & x & z \\ 0 & 0 & x & z \end{matrix} ]) = [ \begin{matrix}z & y & x & 0 & 0 \\ z & 0 & 0 & [x & yz] \end{matrix} ]

1 2 3 4 5

• In practice: comparable to usual algorithms (some stat later)

Comparisons: truncations Easy truncation ⟶ generators of the result, not GB

e. g. Generators only for I ∩ J: Working on [\begin{matrix}I & J \\ 0 & J \end{matrix}] don’t generate pairs in the second component

Truncation is not so natural in other algorithms • HDriven is easy

Syz(v_{1}, …, v_{k}), M = [\begin{matrix}v_{1} & ⋯ & v_{k} \\ 1 & ⋯ & 0 \\ 0 & ⋯ & ⋮ \\ ⋮ & ⋯ & 0 \\ 0 & ⋯ & 1 \end{matrix}] ( 0 ) ; (∂v_{1}) ; ⋮ ; ⋮ ; (∂v_{k}) HF(R^{k}/M) = ∑_{i=1}^{k} \frac{(1 − z^{∂v_{i}})}{(1 − z)^{n}}

M ∩ N K = [\begin{matrix}M & N \\ 0 & N \end{matrix}] \begin{matrix}( 0 ) \\ (∂N) \end{matrix} HF(R^{n}/K) = HF(R^{n}/M) + HF(R^{n}/N)

M : (f) K = [\begin{matrix}M & f \\ 0 & 1 \end{matrix}] \begin{matrix}( 0 ) \\ (∂N) \end{matrix} HF(R^{n}/K) = HF(R^{n}/M) + \frac{1−z^{∂f}}{(1−z)^{n}}

HDriven optimizations for the other operations are similar • Modularity ((A ∩ B) : (v)) ∩ J

[\begin{matrix}A & B & 0 & 0 \\ 0 & B & v & 0 \\ 0 & 0 & 1 & J \\ 0 & 0 & 0 & J \end{matrix}]
GB_{τ′}↓
[\begin{matrix}A + B & 0 & 0 & 0 \\ • & A ∩ B & 0 & 0 \\ • & • & (A ∩ B) : (v) & 0 \\ • & • & • & ((A ∩ B) : (v)) ∩ J \end{matrix} ]

Repeated operations require no additional embedding An example: AX = B f ∗ (x − y) + g ∗ (x + y) = 2x^{2} + 2xy on ℚ[x, y]

( \begin{matrix}−2x^{2} − 2xy & x − y & x + y \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )
GB_{τ′}↓
( y  x ; 0  0 ; \begin{matrix}−1/2 & 1/2 \\ 1/2 & 1/2 \end{matrix}  \begin{aligned}& 0 \\ ( & 1 & ) \end{aligned} ; ( \begin{matrix}0 \\ 2x \end{matrix} )  {0 \atop 0} ; ( \begin{matrix}x + y \\ y − x \end{matrix} ) )

( \begin{matrix}f \\ g \end{matrix} ) = ( \begin{matrix}0 \\ 2x \end{matrix} ) + λ ( \begin{matrix}x + y \\ y − x \end{matrix} )

Linear System solving - Example

\{ \begin{matrix}x f + x^{2}g = x^{3}y^{2} + x^{2} + xy \\ y^{2}f + y g = xy^{3} + xy^{2} + y^{3} \end{matrix}

[\begin{matrix}−x^{3}y^{2} − x^{2} − xy & x & x^{2} \\ −xy^{3} − xy^{2} − y^{3} & y^{2} & y \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] ⟶^{GB_{τ}} [\begin{matrix}• ⋯ • & 0 \\ • ⋯ • & 0 \\ • ⋯ • & 1 \\ • ⋯ • & x + y \\ • ⋯ • & xy^{2} \end{matrix} ]

No general solution, special solution [\begin{matrix}f \\ g \end{matrix}] = [\begin{matrix}x + y \\ xy^{2} \end{matrix} ],

Same system modulo [\begin{matrix}x + y \\ 0 \end{matrix} ]  [\begin{matrix}−B & A & N \\ I & 0 & 0 \\ 0 & I & 0 \end{matrix}] ⟶ [\begin{matrix}• & 0 & 0 \\ • & C & 0 \\ • & D & E \end{matrix}]
[\begin{matrix}−x^{3}y^{2} − x^{2} − xy & x & x^{2} & x + y \\ −xy^{3} − xy^{2} − y^{3} & y^{2} & y & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{matrix} ] ⟶^{GB_{τ}} [\begin{matrix}• ⋯ • & 0 & 0 \\ • ⋯ • & 0 & 0 \\ • ⋯ • & 1 & 0 \\ • ⋯ • & 0 & x + y \\ • ⋯ • & xy^{2} + xy + y^{2} & −xy − y^{2} \end{matrix} ]

Special solution

[\begin{matrix}f \\ g \end{matrix}] = [\begin{matrix}0 \\ xy^{2} + xy + y^{2} \end{matrix} ] + [\begin{matrix}x + y \\ −xy − y^{2} \end{matrix}] = [\begin{matrix}x + y \\ xy^{2} \end{matrix} ] mod [\begin{matrix}x + y \\ 0 \end{matrix} ]

General solution

[\begin{matrix}x + y \\ −xy − y^{2} \end{matrix}] = [\begin{matrix}0 \\ −xy − y^{2} \end{matrix}] mod [\begin{matrix}x + y \\ 0 \end{matrix} ]

An example: Gröbner basis and Gauss-Jordan

\begin{cases}x + y = 3 \\ x − y = 1 \end{cases} ⇒ \begin{cases}x = 2 \\ y = 1 \end{cases}

[\begin{matrix}1 & 1 \\ 1 & −1 \end{matrix}]^{−1} = [\begin{matrix}1/2 & 1/2 \\ 1/2 & −1/2 \end{matrix} ]

[\begin{matrix}1 & 1 & 3 & 1 & 0 \\ 1 & −1 & 1 & 0 & 1 \end{matrix}] ⟶^{GJ} [ 1 0 0 1 [\begin{matrix}2 \\ 1 \end{matrix}] [\begin{matrix}1/2 & 1/2 \\ 1/2 & −1/2 \end{matrix} ] ]

Sol. [ ]^{−1}

[\begin{matrix}−3 & 1 & 1 \\ −1 & 1 & −1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}] ⟶^{GB_{τ′}} [ \begin{matrix}1  0 0  1 0  0 & \begin{aligned}& 0 \\ & 0 \\ [ & 1 & ] \end{aligned} \\ [\begin{matrix}1/2 & 1/2 \\ 1/2 & −1/2 \end{matrix} ] & [\begin{matrix}2 \\ 1 \end{matrix}] \end{matrix} ]

[ ]^{−1} Sol.

CoCoAL code: Intersection

Define IntMod(I,J)
LI:=[[P,0]|P In Gens(I)];
LJ:=[[P,P]|P In Gens(J)];
M:=Module(Concat(LI,LJ));
M.PSeries:=PoincSum(I,J); -- If HDriven
E:=ReducedGBasis(M);
Return FCMod(E); -- Extract result
End;

All other operations are implemented in the same way

Use R::=Q[x,y,z],PosTo;
I:=Ideal(x,y);    J:=Ideal(y,z);     -- We want I intersect J
M:=Module([x,0],[y,0],[y,y],[z,z]);  -- Module building
Transposed(Mat(M));
Mat([[x, y, y, z],
     [0, 0, y, z]])
ReducedGBasis(M);
[Vector(0, y), Vector(x, 0), Vector(0, xz), Vector(z, z), Vector(y, 0)]
Transposed(Mat(Module(It)));
Mat([[0, x,  0, z, y],    -->     Mat([[x, z, y, 0,  0],
     [y, 0, xz, z, 0]])                [0, z, 0, y, xz]])
                             -- Result is: Ideal(y, xz)

(Slightly) more complex operations M_{1} ∩ M_{2} ∩ … ∩ M_{k}, M : N, M : I, M : N^{∞}, M : I^{∞}

• Repeated use of simple operations e. g. M : (v_{1}, …, v_{k}) = ⋂ M : (v_{i})

• Generalized Kronecker’s trick (generic elements)

e. g. M : N = (M : (v)) ∩ k[x]

where y new variable and v := u_{1} + yu_{2} + ⋯ + y^{l−1}u_{l} ∈ k[x, y]^{r}

Smart tricks: exploit special cases:

e. g. i−1 ; ⋂ ; j=1 (M : (u_{j})) ⊂ M : (u_{i}) ⟺ u_{i} · i−1 ; ⋂ ; j=1 (M : (u_{j})) ⊂ M

Statistics for C_{4} ∩ C_{5}

cocoa 4
Time IntMod   11.09
Time IntHMod   3.35
Time IntRing  14.10
Time IntHRing  4.01
Time IntSyz   12.66
Time IntHSyz   4.05
cocoa 5
-- IntMod  CoCoAServer: computing Cpu time = 2.680
-- IntRing CoCoAServer: computing Cpu time = 2.812
-- IntSyz  CoCoAServer: computing Cpu time = 0.276 + 2.960
Singular
-- IntMod  //used time: 1.20 sec
-- IntRing //used time: 2.72 sec
-- IntSyz  //used time: 0.13 sec +  1.25 sec

Statistics for (C_{4} ∩ C_{5}) : C_{4}

Colon by Intersection
Time TrMod+IntHMod    2.34
Time TrHMod+IntHMod   1.30
Time TrBayer+IntHMod  2.40
Time TrHBayer+IntHMod 1.88
Generic Colon
Time TrMod    8.03
Generic Module Colon
Time TrMod    9.20
Generic Colon HDriven
Time TrMod    4.37
Time TrHMod   2.91
Time TrBayer  6.74
Time TrHBayer 4.34
Generic Module Colon HDriven
Time TrMod    4.94
Time TrHMod   4.92
Time TrBayer  4.87
Time TrHBayer 4.91

Conclusions

Module component elimination algorithms: • Are easy to proof and implement

• Look at least as efficient as the others • Allow easy partial computations

• Have efficient HDriven versions • A. Seidenberg,Construction in Algebra, Trans. Amer. Math. Soc., 197, pp. 273–313, 1974.

• M. Caboara and C. Traverso, Efficient algorithms for ideal operations (extended abstract). ACM Press, New York, ISSAC 98: Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, August 13–15, University of Rostock, Germany, pp. 147-152, 1998.

• A.M. Perdon, M. Caboara and G.G. Peroli, Algorithms for geometric control of systems over rings. Proceedings (CD) of the 2nd IFAC Conference, CONTROL SYSTEMS DESIGN, (CSD 03) September 7 - 10, Bratislava, 2003.

• M. Caboara and C. Traverso, Efficient algorithms for basic module operations. Preprint.