GAP (LocalizeRingForHomalg) - Appendix A: Overview of the LocalizeRingForHomalg Package Source Code

This appendix is included in the documentation to shine some light on the mathematical backgrounds of this Package. Neither is it needed to work with this package nor should the methods presented here be called directly. The functions documented here are entries of the so called ring table and not to be called directly. There are higher level methods in declared and installed in MatricesForHomalg, which call this functions (--> ?MatricesForHomalg:The Basic Matrix Operations).

We only present the simpler procedures, where no transformation matrices are computed, since the computation of transformation matrices carries no further mathematical ideas.

A.1 The generic Methods

There are some methods in localized rings, where homalg is able to fall back on procedures of the corresponding global ring. Furthermore these methods work quite good together with Mora's algorithm as implemented in Singular, since we can treat it like a global ring. We will present some methods as an example, to show the idea:

A.1-1 BasisOfRowModule

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 M.

BasisOfRowModule :=
  function( M )

    Info(
      InfoLocalizeRingForHomalg,
      2,
      "Start BasisOfRowModule with ",
      NumberRows( M ), "x", NumberColumns( M )
    );

    return HomalgLocalMatrix( BasisOfRowModule( Numerator( M ) ), HomalgRing( M ) );
    
end,

A.1-2 DecideZeroRows

This procedure just calls the DecideZeroRows of the computation ring for the numerator of A.

If we use Mora's algorithm this procedure will just call it. The result is divided by the denominator of A afterwards. Again we do not need to care about the denominator of B.

If we use the reduction implemented in this package, this Funcod is overwritten and will not be called.

DecideZeroRows :=
  function( A, B )
    local R, ComputationRing, hook, result;
    
    Info(
      InfoLocalizeRingForHomalg,
      2,
      "Start DecideZeroRows with ",
      NumberRows( A ), "x", NumberColumns( A ),
      " and ",
      NumberRows( B ), "x", NumberColumns( B )
    );
    
    R := HomalgRing( A );
    ComputationRing := AssociatedComputationRing( R );
    
    result := DecideZeroRows( Numerator( A ) , Numerator( B ) );
    result := HomalgLocalMatrix( result, Denominator( A ) , R );
    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRows: produces denominator: ", Name( Denominator( result ) ) );
    return result;

  end,

A.1-3 SyzygiesGeneratorsOfRows

Returns: a "basis" of the syzygies of the arguments (for details consult the homalg help)

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.

SyzygiesGeneratorsOfRows :=
  function( M )
    
    Info(
      InfoLocalizeRingForHomalg,
      2,
      "Start SyzygiesGeneratorsOfRows with ",
      NumberRows( M ), "x", NumberColumns( M )
    );

    return HomalgLocalMatrix(\
             SyzygiesGeneratorsOfRows( Numerator( M ) ), HomalgRing( M )\
           );
    
  end,

A.2 The Local Decide Zero trick

A.2-1 DecideZeroRows

This procedure is the mathematical core procedure of this package. We use a trick to decide locally, whether B can be reduced to zero by 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 B independently, whether it lies in the module generated by B.

DecideZeroRows :=
  function( B, A )
    local R, T, m, gens, n, GlobalR, one, N, b, numB, denB, i, B1, A1, B2, A2, B3;
    
    Info( 
       InfoLocalizeRingForHomalg,
       2,
       "Start DecideZeroRows with ",
       NumberRows( B ), "x", NumberColumns( B ),
       " and ",
       NumberRows( A ), "x", NumberColumns( A ) 
    );
    
    R := HomalgRing( B );
    GlobalR := AssociatedComputationRing( R );
    T := HomalgVoidMatrix( R );
    gens := GeneratorsOfMaximalLeftIdeal( R );
    n := NumberRows( gens );
    one := One( GlobalR );
    
    m := NumberRows( A );
    A1 := Numerator( A );
    
    N := HomalgZeroMatrix( 0, NumberColumns( B ), R );
    b := Eval( B );
    numB := b[1];
    denB := b[2];
    
    for i in [ 1 .. NumberRows( B ) ] do
    
        #use global reduction as heuristic
        B1 := CertainRows( numB, [ i ] );
        B2 := HomalgLocalMatrix( DecideZeroRows( B1, A1 ), R );
        
        #if it is nonzero, check whether local reduction makes it zero
        if not IsZero( B2 ) then
          A2 := UnionOfRows( A1, gens * B1 );
          A2 := BasisOfRows( A2 );
          B3 := HomalgLocalMatrix( DecideZeroRows( B1, A2 ), R );
          if IsZero( B3 ) then
            B2 := B3;
          fi;
        fi;
        
        N := UnionOfRows( N, B2 );
        
    od;
    
    N := HomalgRingElement( one, denB, R ) * N;
    
    Info( InfoLocalizeRingForHomalgShowUnits, 1, "DecideZeroRows: produces denominator: ", Name( Denominator( N ) ) );
    
    return N;
    
  end,

A.3 Tools

The package LocalizeRingForHomalg also implements tool functions. These are referred to from MatricesForHomalg automatically. We list the implemented methods here are and refer to the MatricesForHomalg documentation (--> ?MatricesForHomalg: The Matrix Tool Operations and ?MatricesForHomalg:RingElement) for details. All tools functions from MatricesForHomalg not listed here are also supported by fallback tools.