1#############################################################################
2##
3##  LocalizeRingBasic.gi     LocalizeRingBasic package       Mohamed Barakat
4##                                                    Markus Lange-Hegermann
5##
6##  Copyright 2009, Mohamed Barakat, Universität des Saarlandes
7##           Markus Lange-Hegermann, RWTH-Aachen University
8##
9##  Implementation stuff for LocalizeRingForHomalg.
10##
11#############################################################################
12
13####################################
14#
15# global variables:
16#
17####################################
18
19InstallValue( CommonHomalgTableForLocalizedRingsBasic,
20
21        rec(
22               ## Must only then be provided by the RingPackage in case the default
23               ## "service" function does not match the Ring
24
25##  <#GAPDoc Label="BasisOfRowModule">
26##  <ManSection>
27##    <Func Arg="M" Name="BasisOfRowModule" Label="for local rings"/>
28##    <Returns>a "basis" of the module generated by M</Returns>
29##    <Description>
30##    This procedure computes a basis by using the Funcod of the underlying computation ring. If the computation ring is given by Mora's Algorithm, we will indeed compute a local basis. If we just use the global ring for computations, this will be a global basis and is just computed for some simplifications and not for the use of reducing by it. Of course we can just forget about the denominator of <A>M</A>.
31##      <Listing Type="Code"><![CDATA[
32BasisOfRowModule :=
33  function( M )
34
35    Info(
36      InfoLocalizeRingForHomalg,
37      2,
38      "Start BasisOfRowModule with ",
39      NrRows( M ), "x", NrColumns( M )
40    );
41
42    return HomalgLocalMatrix( BasisOfRowModule( Numerator( M ) ), HomalgRing( M ) );
43
44end,
45##  ]]></Listing>
46##    </Description>
47##  </ManSection>
48##  <#/GAPDoc>
49
50BasisOfColumnModule :=
51  function( M )
52
53    Info( InfoLocalizeRingForHomalg, 2, "Start BasisOfColumnModule with ", NrRows( M ), "x", NrColumns( M ) );
54
55    return HomalgLocalMatrix( BasisOfColumnModule( Numerator( M ) ), HomalgRing( M ) );
56
57  end,
58
59BasisOfRowsCoeff :=
60  function( M, T )
61    local R, ComputationRing, TT, result;
62
63    Info( InfoLocalizeRingForHomalg, 2, "Start BasisOfRowsCoeff with ", NrRows( M ), "x", NrColumns( M ) );
64
65    R := HomalgRing( M );
66    ComputationRing := AssociatedComputationRing( R );
67
68    TT := HomalgVoidMatrix( ComputationRing );
69    result := BasisOfRowsCoeff( Numerator( M ) , TT );
70    if IsBound(TT!.Denominator) then
71      SetEval( T, [ TT, TT!.Denominator ] );
72      Unbind(TT!.Denominator);
73    else
74      SetEval( T, [ TT, One ( ComputationRing ) ] );
75    fi;
76    result := HomalgLocalRingElement( One( ComputationRing), Denominator( M ), R ) * HomalgLocalMatrix( result, R );
77
78    Assert( 6, result = T * M );
79
80    Info( InfoLocalizeRingForHomalgShowUnits, 1, "BasisOfRowsCoeff: produces denominator: ", Name( Denominator( result ) ), " and for the transformation matrix: ", Name(Denominator(T)) );
81
82    return result;
83
84  end,
85
86BasisOfColumnsCoeff :=
87  function( M, T )
88    local R, ComputationRing, TT, result;
89
90    Info( InfoLocalizeRingForHomalg, 2, "Start BasisOfColumnsCoeff with ", NrRows( M ), "x", NrColumns( M ) );
91
92    R := HomalgRing( M );
93    ComputationRing := AssociatedComputationRing( R );
94
95    TT := HomalgVoidMatrix( ComputationRing );
96    result := BasisOfColumnsCoeff( Numerator( M ), TT );
97    if IsBound(TT!.Denominator) then
98      SetEval( T, [ TT, TT!.Denominator ] );
99      Unbind(TT!.Denominator);
100    else
101      SetEval( T, [ TT, One ( ComputationRing ) ] );
102    fi;
103    result := HomalgLocalRingElement( One( ComputationRing), Denominator( M ), R ) * HomalgLocalMatrix( result, R );
104
105    Assert( 6, result = M * T );
106
107    Info( InfoLocalizeRingForHomalgShowUnits, 1, "BasisOfColumnsCoeff: produces denominator: ", Name( Denominator( result ) ), " and for the transformation matrix: ", Name(Denominator(T)) );
108
109    return result;
110
111  end,
112
113##  <#GAPDoc Label="DecideZeroRows:generic">
114##  <ManSection>
115##    <Func Arg="A, B" Name="DecideZeroRows" Label="for local rings with Mora's algorithm"/>
116##    <Returns>a "reduced" form of <A>A</A> with respect to <A>B</A></Returns>
117##    <Description>
118##    This procedure just calls the DecideZeroRows of the computation ring for the numerator of <A>A</A>. <P/>If we use Mora's algorithm this procedure will just call it. The result is divided by the denominator of <A>A</A> afterwards. Again we do not need to care about the denominator of B. <P/>If we use the reduction implemented in this package, this Funcod is overwritten and will not be called.
119##      <Listing Type="Code"><![CDATA[
120DecideZeroRows :=
121  function( A, B )
122    local R, ComputationRing, hook, result;
123
124    Info(
125      InfoLocalizeRingForHomalg,
126      2,
127      "Start DecideZeroRows with ",
128      NrRows( A ), "x", NrColumns( A ),
129      " and ",
130      NrRows( B ), "x", NrColumns( B )
131    );
132
133    R := HomalgRing( A );
134    ComputationRing := AssociatedComputationRing( R );
135
136    result := DecideZeroRows( Numerator( A ) , Numerator( B ) );
137    result := HomalgLocalMatrix( result, Denominator( A ) , R );
138    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRows: produces denominator: ", Name( Denominator( result ) ) );
139    return result;
140
141  end,
142##  ]]></Listing>
143##    </Description>
144##  </ManSection>
145##  <#/GAPDoc>
146
147DecideZeroColumns :=
148  function( A, B )
149    local R, ComputationRing, hook, result;
150
151    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroColumns with ", NrRows( A ), "x", NrColumns( A ), " and ", NrRows( B ), "x", NrColumns( B ) );
152
153    R := HomalgRing( A );
154    ComputationRing := AssociatedComputationRing( R );
155
156    result := DecideZeroColumns( Numerator( A ) , Numerator( B ) );
157    result := HomalgLocalMatrix( result, Denominator( A ) , R );
158    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroColumns: produces denominator: ", Name( Denominator( result ) ) );
159    return result;
160
161  end,
162
163DecideZeroRowsEffectively :=
164  function( A, B, T )
165    local R, T1, result, ComputationRing;
166
167    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroRowsEffectively with ", NrRows( A ), "x", NrColumns( A ), " and ", NrRows( B ), "x", NrColumns( B ) );
168
169    R := HomalgRing( A );
170    ComputationRing := AssociatedComputationRing( R );
171
172    T1 := HomalgVoidMatrix( ComputationRing );
173    #little remark: the return value of DecideZeroRowsEffectively also has a denominator as an attribute, which is used in HomalgLocalMatrix
174    result := HomalgLocalMatrix( DecideZeroRowsEffectively( Numerator( A ), Numerator ( B ), T1 ), Denominator( A ), R );
175
176    if IsBound(T1!.Denominator) then
177      SetEval( T, [ T1, T1!.Denominator * Denominator( A ) ] );
178      Unbind(T1!.Denominator);
179    else
180      SetEval( T, [ T1, Denominator( A ) ] );
181    fi;
182
183    Assert( 6, result = A + T * B );
184
185    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRowsEffectively: produces denominator: ", Name( Denominator( result ) ), " and for the transformation matrix: ", Name( Denominator( T ) ) );
186
187    return result;
188
189  end,
190
191DecideZeroColumnsEffectively :=
192  function( A, B, T )
193    local R, T1, result, ComputationRing;
194
195    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroColumnsEffectively with ", NrRows( A ), "x", NrColumns( A ), " and ", NrRows( B ), "x", NrColumns( B ) );
196
197    R := HomalgRing( A );
198    ComputationRing := AssociatedComputationRing( R );
199
200    T1 := HomalgVoidMatrix( ComputationRing );
201    #little remark: the return value of DecideZeroColumnsEffectively also has a denominator as an attribute, which is used in HomalgLocalMatrix
202    result := HomalgLocalMatrix( DecideZeroColumnsEffectively( Numerator( A ), Numerator ( B ), T1 ), Denominator( A ), R );
203
204    if IsBound(T1!.Denominator) then
205      SetEval( T, [ T1, T1!.Denominator * Denominator( A ) ] );
206      Unbind(T1!.Denominator);
207    else
208      SetEval( T, [ T1, Denominator( A ) ] );
209    fi;
210
211    Assert( 6, result = A + B * T );
212
213    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroColumnsEffectively: produces denominator: ", Name( Denominator( result ) ), " and for the transformation matrix: ", Name( Denominator( T ) ) );
214
215    return result;
216
217  end,
218
219##  <#GAPDoc Label="SyzygiesGeneratorsOfRows">
220##  <ManSection>
221##    <Func Arg="M" Name="SyzygiesGeneratorsOfRows" Label="for local rings"/>
222##    <Returns>a "basis" of the syzygies of the arguments (for details consult the homalg help)</Returns>
223##    <Description>
224##    It is easy to see, that a global syzygy is also a local syzygy and vice versa when clearing the local Syzygy of its denominators. So this procedure just calls the syzygy Funcod of the underlying computation ring.
225##      <Listing Type="Code"><![CDATA[
226SyzygiesGeneratorsOfRows :=
227  function( M )
228
229    Info(
230      InfoLocalizeRingForHomalg,
231      2,
232      "Start SyzygiesGeneratorsOfRows with ",
233      NrRows( M ), "x", NrColumns( M )
234    );
235
236    return HomalgLocalMatrix(\
237             SyzygiesGeneratorsOfRows( Numerator( M ) ), HomalgRing( M )\
238           );
239
240  end,
241##  ]]></Listing>
242##    </Description>
243##  </ManSection>
244##  <#/GAPDoc>
245
246RelativeSyzygiesGeneratorsOfRows :=
247  function( M, N )
248    local CommonDenomMatrix, M2, N2;
249
250    Info( InfoLocalizeRingForHomalg, 2, "Start RelativeSyzygiesGeneratorsOfRows with ", NrRows( M ), "x", NrColumns( M ), " and ", NrRows( N ), "x", NrColumns( N ) );
251
252    CommonDenomMatrix := UnionOfRowsOp( M, N );
253    M2 := CertainRows( CommonDenomMatrix, [ 1 .. NrRows( M ) ] );
254    N2 := CertainRows( CommonDenomMatrix, [ NrRows( M ) + 1 .. NrRows( CommonDenomMatrix ) ] );
255
256    return HomalgLocalMatrix( SyzygiesGeneratorsOfRows( Numerator( M2 ), Numerator( N2 ) ), HomalgRing( M ) );
257
258  end,
259
260SyzygiesGeneratorsOfColumns :=
261  function( M )
262
263    Info( InfoLocalizeRingForHomalg, 2, "Start SyzygiesGeneratorsOfColumns with ", NrRows( M ), "x", NrColumns( M ) );
264    return HomalgLocalMatrix( SyzygiesGeneratorsOfColumns( Numerator( M ) ), HomalgRing( M ) );
265
266  end,
267
268RelativeSyzygiesGeneratorsOfColumns :=
269  function( M, N )
270    local CommonDenomMatrix, M2, N2;
271
272    Info( InfoLocalizeRingForHomalg, 2, "Start RelativeSyzygiesGeneratorsOfColumns with ", NrRows( M ), "x", NrColumns( M ), " and ", NrRows( N ), "x", NrColumns( N ) );
273
274    CommonDenomMatrix := UnionOfColumnsOp( M, N );
275    M2 := CertainColumns( CommonDenomMatrix, [ 1 .. NrColumns( M ) ] );
276    N2 := CertainColumns( CommonDenomMatrix, [ NrColumns( M ) + 1 .. NrColumns( CommonDenomMatrix ) ] );
277
278    return HomalgLocalMatrix( SyzygiesGeneratorsOfColumns( Numerator( M2 ), Numerator( N2 ) ), HomalgRing( M ) );
279
280  end,
281
282            )
283);
284
285InstallValue( HomalgTableReductionMethodsForLocalizedRingsBasic,
286
287        rec(
288
289##  <#GAPDoc Label="DecideZeroRows">
290##  <ManSection>
291##    <Func Arg="B, A" Name="DecideZeroRows" Label="for local rings"/>
292##    <Returns>a "reduced" form of <A>B</A> with respect to <A>A</A></Returns>
293##    <Description>
294##    This procedure is the mathematical core procedure of this package. We use a trick to decide locally, whether <A>B</A> can be reduced to zero by <A>A</A> with a global computation. First a heuristic is used by just checking, whether the element lies inside the global module, generated by the generators of the local module. This of course implies this for the local module having the advantage of a short computation time and leaving a normal form free of denominators. If this check fails, we use our trick to check for each row of <A>B</A> independently, whether it lies in the module generated by <A>B</A>.
295##      <Listing Type="Code"><![CDATA[
296DecideZeroRows :=
297  function( B, A )
298    local R, T, m, gens, n, GlobalR, one, N, b, numB, denB, i, B1, A1, B2, A2, B3;
299
300    Info(
301       InfoLocalizeRingForHomalg,
302       2,
303       "Start DecideZeroRows with ",
304       NrRows( B ), "x", NrColumns( B ),
305       " and ",
306       NrRows( A ), "x", NrColumns( A )
307    );
308
309    R := HomalgRing( B );
310    GlobalR := AssociatedComputationRing( R );
311    T := HomalgVoidMatrix( R );
312    gens := GeneratorsOfMaximalLeftIdeal( R );
313    n := NrRows( gens );
314    one := One( GlobalR );
315
316    m := NrRows( A );
317    A1 := Numerator( A );
318
319    N := HomalgZeroMatrix( 0, NrColumns( B ), R );
320    b := Eval( B );
321    numB := b[1];
322    denB := b[2];
323
324    for i in [ 1 .. NrRows( B ) ] do
325
326        #use global reduction as heuristic
327        B1 := CertainRows( numB, [ i ] );
328        B2 := HomalgLocalMatrix( DecideZeroRows( B1, A1 ), R );
329
330        #if it is nonzero, check whether local reduction makes it zero
331        if not IsZero( B2 ) then
332          A2 := UnionOfRowsOp( A1, gens * B1 );
333          A2 := BasisOfRows( A2 );
334          B3 := HomalgLocalMatrix( DecideZeroRows( B1, A2 ), R );
335          if IsZero( B3 ) then
336            B2 := B3;
337          fi;
338        fi;
339
340        N := UnionOfRowsOp( N, B2 );
341
342    od;
343
344    N := HomalgRingElement( one, denB, R ) * N;
345
346    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRows: produces denominator: ", Name( Denominator( N ) ) );
347
348    return N;
349
350  end,
351##  ]]></Listing>
352##    </Description>
353##  </ManSection>
354##  <#/GAPDoc>
355
356DecideZeroColumns :=
357  function( B, A )
358    local R, T, m, gens, n, GlobalR, one, N, b, numB, denB, i, B1, A1, B2, A2, B3;
359
360    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroColumns with ", NrRows( B ), "x", NrColumns( B ), " and ", NrRows( A ), "x", NrColumns( A ) );
361
362    R := HomalgRing( B );
363    GlobalR := AssociatedComputationRing( R );
364    T := HomalgVoidMatrix( R );
365    gens := GeneratorsOfMaximalRightIdeal( R );
366    n := NrColumns( gens );
367    one := One( GlobalR );
368
369    m := NrColumns( A );
370    A1 := Numerator( A );
371
372    N := HomalgZeroMatrix( NrRows( B ), 0, R );
373    b := Eval( B );
374    numB := b[1];
375    denB := b[2];
376
377    for i in [ 1 .. NrColumns( B ) ] do
378
379        B1 := CertainColumns( numB, [ i ] );
380        B2 := HomalgLocalMatrix( DecideZeroColumns( B1, A1 ), R );
381
382        if not IsZero( B2 ) then
383          A2 := UnionOfColumnsOp( A1, B1 * gens );
384          A2 := BasisOfColumns( A2 );
385          B3 := HomalgLocalMatrix( DecideZeroColumns( B1, A2 ), R );
386          if IsZero( B3 ) then
387            B2 := B3;
388          fi;
389        fi;
390
391        N := UnionOfColumnsOp( N, B2 );
392
393    od;
394
395    N := HomalgRingElement( one, denB, R ) * N;
396
397    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroColumns: produces denominator: ", Name(Denominator(N)) );
398
399    return N;
400
401  end,
402
403DecideZeroRowsEffectively :=
404  function( B, A, T )
405    local R, m, gens, n, GlobalR, one, N, TT, b, numB, denB, a, numA, denA, i, B1, A1, B2, A2, S, S1, u, SS, B3;
406
407    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroRowsEffectively with ", NrRows( B ), "x", NrColumns( B ), " and ", NrRows( A ), "x", NrColumns( A ) );
408
409    R := HomalgRing( B );
410    GlobalR := AssociatedComputationRing( R );
411    gens := GeneratorsOfMaximalLeftIdeal( R );
412    one := One( GlobalR );
413
414    m := NrRows( A );
415    n := NrRows( gens );
416    N := HomalgZeroMatrix( 0, NrColumns( B ), R );
417    TT := HomalgZeroMatrix( 0, m, R );
418
419    b := Eval( B );
420    numB := b[1];
421    denB := b[2];
422    a := Eval( A );
423    numA := a[1];
424    denA := a[2];
425
426    for i in [ 1 .. NrRows( B ) ] do
427
428        B1 := CertainRows( numB, [ i ] );
429        A1 := numA;
430        S1 := HomalgVoidMatrix( GlobalR );
431        #heuristic to prevent cases which would decide zero even globally producing denominators:
432        B2 := HomalgLocalMatrix( DecideZeroRowsEffectively( B1, A1, S1 ), R );
433
434        if not IsZero( B2 ) then
435          A2 := UnionOfRowsOp( A1, gens * B1 );
436          SS := HomalgVoidMatrix( GlobalR );
437          A2 := BasisOfRowsCoeff( A2, SS );
438          S := HomalgVoidMatrix( GlobalR );
439          B3 := HomalgLocalMatrix( DecideZeroRowsEffectively( B1, A2, S ), R );
440          if IsZero( B3 ) then
441            S := S * SS;
442            u := CertainColumns( S, [ m + 1 .. n + m ] ) * gens;
443            u := MatElm( u, 1, 1, GlobalR );
444            IsZero( u );
445            u := one + u;
446            S := HomalgLocalMatrix( CertainColumns( S, [ 1 .. m ] ), u, R );
447            B2 := HomalgRingElement( one , u , R ) * B3;
448          else
449            S := HomalgVoidMatrix( GlobalR );
450            B2 := HomalgLocalMatrix( DecideZeroRowsEffectively( B1 , A1 , S ) , one , R );
451            S := HomalgLocalMatrix( S , one , R );
452          fi;
453        else
454          S := HomalgLocalMatrix( S1 , one , R );
455        fi;
456
457        TT := UnionOfRowsOp( TT, S );
458        N := UnionOfRowsOp( N, B2 );
459
460        Assert( 7, S * HomalgLocalMatrix( A1, R ) + HomalgLocalMatrix( B1, R ) = B2 );
461
462    od;
463
464    TT := HomalgRingElement( denA, denB, R ) * TT;
465
466    if HasEvalUnionOfRows( TT ) then
467        SetEvalUnionOfRows( T, EvalUnionOfRows( TT ) );
468    elif HasEvalMulMat( TT ) then
469        SetEvalMulMat( T, EvalMulMat( TT ) );
470    else
471        SetEval( T, Eval( TT ) );
472    fi;
473
474    N := HomalgRingElement( one , denB , R ) * N;
475
476    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRowsEffectively: produces denominator: ", Name( Denominator( N ) ), " and for the transformation matrix: ", Name( Denominator( T ) ) );
477
478    return N;
479
480  end,
481
482DecideZeroColumnsEffectively :=
483  function( B, A, T )
484    local R, m, gens, n, GlobalR, one, N, TT, b, numB, denB, a, numA, denA, i, B1, A1, B2, A2, S, S1, u, SS, B3;
485
486    Info( InfoLocalizeRingForHomalg, 2, "Start DecideZeroColumnsEffectively with ", NrRows( B ), "x", NrColumns( B ), " and ", NrRows( A ), "x", NrColumns( A ) );
487
488    R := HomalgRing( B );
489    GlobalR := AssociatedComputationRing( R );
490    gens := GeneratorsOfMaximalRightIdeal( R );
491    one := One( GlobalR );
492
493    m := NrColumns( A );
494    n := NrColumns( gens );
495    N := HomalgZeroMatrix( NrRows( B ), 0, R );
496    TT := HomalgZeroMatrix( m, 0, R );
497
498    b := Eval( B );
499    numB := b[1];
500    denB := b[2];
501    a := Eval( A );
502    numA := a[1];
503    denA := a[2];
504
505    for i in [ 1 .. NrColumns( B ) ] do
506
507        B1 := CertainColumns( numB, [ i ] );
508        A1 := numA;
509        S1 := HomalgVoidMatrix( GlobalR );
510        B2 := HomalgLocalMatrix( DecideZeroColumnsEffectively( B1, A1, S1 ), R );
511
512        if not IsZero( B2 ) then
513          A2 := UnionOfColumnsOp( A1, B1 * gens );
514          SS := HomalgVoidMatrix( GlobalR );
515          A2 := BasisOfColumnsCoeff( A2, SS );
516          S := HomalgVoidMatrix( GlobalR );
517          B3 := HomalgLocalMatrix( DecideZeroColumnsEffectively( B1, A2, S ), R );
518          if IsZero( B3 ) then
519            S := SS * S;
520            u := gens * CertainRows( S, [ m + 1 .. n + m ] );
521            u := MatElm( u, 1, 1, GlobalR );
522            IsZero( u );
523            u := one + u;
524            S := HomalgLocalMatrix( CertainRows( S, [ 1 .. m ] ), u, R );
525            B2 := HomalgRingElement( one, u, R ) * B3;
526          else
527            S := HomalgVoidMatrix( GlobalR );
528            B2 := HomalgLocalMatrix( DecideZeroColumnsEffectively( B1 , A1 , S ) , one , R );
529            S := HomalgLocalMatrix( S , one , R );
530          fi;
531
532        else
533
534          S := HomalgLocalMatrix( S1 , one , R );
535
536        fi;
537
538        TT := UnionOfColumnsOp( TT, S );
539        N := UnionOfColumnsOp( N, B2 );
540
541        Assert( 7, HomalgLocalMatrix( A1, R ) * S + HomalgLocalMatrix( B1, R ) = B2 );
542
543    od;
544
545    TT := HomalgRingElement( denA, denB, R ) * TT;
546
547    if HasEvalUnionOfColumns( TT ) then
548        SetEvalUnionOfColumns( T, EvalUnionOfColumns( TT ) );
549    elif HasEvalMulMat( TT ) then
550        SetEvalMulMat( T, EvalMulMat( TT ) );
551    else
552        SetEval( T, Eval( TT ) );
553    fi;
554
555    N := HomalgRingElement( one , denB , R ) * N;
556
557    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroColumnsEffectively: produces denominator: ", Name( Denominator( N ) ), " and for the transformation matrix: ", Name( Denominator( T ) ) );
558
559    return N;
560
561  end,
562
563        )
564 );
565