Quelle  Service.gi   Sprache: unbekannt

# SPDX-License-Identifier: GPL-2.0-or-later
# MatricesForHomalg: Matrices for the homalg project
#
# Implementations
#

####################################
#
# global variables:
#
####################################

HOMALG_MATRICES.colored_info :=
  rec(
      ## Basic Operations:
      
      ## Echelon form
      RowEchelonForm := [ 4, HOMALG_MATRICES.colors.BOE ],
      ColumnEchelonForm := [ 4, HOMALG_MATRICES.colors.BOE ],
      ## reduced Echelon form
      ReducedRowEchelonForm := [ 4, HOMALG_MATRICES.colors.BOE ],
      ReducedColumnEchelonForm := [ 4, HOMALG_MATRICES.colors.BOE ],
      ## Basis
      BasisOfRowModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      BasisOfColumnModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      ## BasisCoeff
      BasisOfRowsCoeff := [ 3, HOMALG_MATRICES.colors.BOB ],
      BasisOfColumnsCoeff := [ 3, HOMALG_MATRICES.colors.BOB ],
      
      ## partially reduced Basis
      PartiallyReducedBasisOfRowModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      PartiallyReducedBasisOfColumnModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      ## reduced Basis
      ReducedBasisOfRowModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      ReducedBasisOfColumnModule := [ 3, HOMALG_MATRICES.colors.BOB ],
      
      ## Decide zero
      DecideZeroRows := [ 2, HOMALG_MATRICES.colors.BOD ],
      DecideZeroColumns := [ 2, HOMALG_MATRICES.colors.BOD ],
      ## Decide zero effectively
      DecideZeroRowsEffectively := [ 2, HOMALG_MATRICES.colors.BOD ],
      DecideZeroColumnsEffectively := [ 2, HOMALG_MATRICES.colors.BOD ],
      
      ## solutions of Homogeneous system
      SyzygiesGeneratorsOfRows := [ 2, HOMALG_MATRICES.colors.BOH ],
      SyzygiesGeneratorsOfColumns := [ 2, HOMALG_MATRICES.colors.BOH ],
      ## relative solutions of Homogeneous system
      RelativeSyzygiesGeneratorsOfRows := [ 2, HOMALG_MATRICES.colors.BOH ],
      RelativeSyzygiesGeneratorsOfColumns := [ 2, HOMALG_MATRICES.colors.BOH ],
      ## reduced solutions of Homogeneous system
      ReducedSyzygiesGeneratorsOfRows := [ 2, HOMALG_MATRICES.colors.BOH ],
      ReducedSyzygiesGeneratorsOfColumns := [ 2, HOMALG_MATRICES.colors.BOH ],
      );

####################################
#
# global functions:
#
####################################

##
InstallGlobalFunction( ColoredInfoForService,
  function( arg )
    local nargs, a, string, l, color, s;
    
    nargs := Length( arg );
    
    a := arg[2];
    
    if IsString( a ) then
        string := a;
        if IsBound( HOMALG_MATRICES.colored_info.(string) ) then
            l := HOMALG_MATRICES.colored_info.(string)[1];
            color := HOMALG_MATRICES.colored_info.(string)[2];
        else
            l := 2;
            color := "\033[1m";
        fi;
    elif IsList( a ) and Length( a ) = 2 and IsString( a[1] ) and IsRecord( a[2] ) then
        string := a[1];
        if IsBound( a[2].(string) ) then
            l := a[2].(string)[1];
            color := a[2].(string)[2];
        else
            l := 2;
            color := "\033[1m";
        fi;
    else
        string := "unknown";
        l := 2;
        color := "\033[1m";
    fi;
    
    if arg[1] = "busy" then
        
        s := Concatenation( HOMALG_MATRICES.colors.busy, "BUSY>\033[0m ", color );
        
        s := Concatenation( s, string, "\033[0m \033[7m", color );
        
        Append( s, Concatenation( List( arg{[ 3 .. nargs ]}, function( a ) if IsStringRep( a ) then return a; else return String( a ); fi; end ) ) );
        
        s := Concatenation( s, "\033[0m " );
        
        if l < 4 then
            Info( InfoHomalgBasicOperations, l , "" );
        fi;
        
        Info( InfoHomalgBasicOperations, l, s );
    
    else
        
        s := Concatenation( HOMALG_MATRICES.colors.done, "<DONE\033[0m ", color );
        
        s := Concatenation( s, string, "\033[0m \033[7m", color );
        
        Append( s, Concatenation( List( arg{[ 3 .. nargs ]}, function( a ) if IsStringRep( a ) then return a; else return String( a ); fi; end ) ) );
        
        s := Concatenation( s, "\033[0m ", "    in ", homalgTotalRuntimes( arg[1], "" ) );
        
        Info( InfoHomalgBasicOperations, l, s );
    
        if l < 4 then
            Info( InfoHomalgBasicOperations, l , "" );
        fi;
        
    fi;
    
end );

####################################
#
# methods for operations:
#
####################################

################################################################
##
## CAUTION: !!!
##
## the following procedures never take ring relations into
## account and hence should never be part of a homalgTable
## of a homalg residue class ring
##
################################################################

if IsBound( _RowEchelonForm ) then
##
InstallOtherMethod( RowEchelonForm,
        "for matrices",
        [ IsMatrix ],
        
  _RowEchelonForm );
fi;

##
InstallMethod( RowEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    ColoredInfoForService( "busy", "RowEchelonForm", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    t := homalgTotalRuntimes( );
    
    if IsBound(RP!.RowEchelonForm) then
        
        B := RP!.RowEchelonForm( M );
        
        B := CertainRows( B, NonZeroRows( B ) );
        
        ColoredInfoForService( t, "RowEchelonForm", NumberRows( B ) );
        
        return B;
        
    elif IsBound(RP!.ColumnEchelonForm) then
        
        B := Involution( RP!.ColumnEchelonForm( Involution( M ) ) );
        
        B := CertainRows( B, NonZeroRows( B ) );
        
        ColoredInfoForService( t, "RowEchelonForm", NumberRows( B ) );
        
        return B;
        
    fi;
    
    TryNextMethod( );
    
end );

##
InstallMethod( RowEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix and IsVoidMatrix ],
        
  function( M, T )
    local R, RP, t, TI, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    ColoredInfoForService( "busy", "RowEchelonForm (M,T)", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    t := homalgTotalRuntimes( );
    
    if IsBound(RP!.RowEchelonForm) then
        
        B := RP!.RowEchelonForm( M, T );
        
        ColoredInfoForService( t, "RowEchelonForm (M,T)", Length( NonZeroRows( B ) ) );
        
        return B;
        
    elif IsBound(RP!.ColumnEchelonForm) then
        
        TI := HomalgVoidMatrix( R );
        
        B := Involution( RP!.ColumnEchelonForm( Involution( M ), TI ) );
        
        ColoredInfoForService( t, "RowEchelonForm (M,T)", Length( NonZeroRows( B ) ) );
        
        SetPreEval( T, Involution( TI ) ); ResetFilterObj( T, IsVoidMatrix );
        
        return B;
        
    fi;
    
    TryNextMethod( );
    
end );

##
InstallMethod( ColumnEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    if IsBound(RP!.ColumnEchelonForm) then
        
        t := homalgTotalRuntimes( );
        
        ColoredInfoForService( "busy", "ColumnEchelonForm", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
        
        B := RP!.ColumnEchelonForm( M );
        
        B := CertainColumns( B, NonZeroColumns( B ) );
        
        ColoredInfoForService( t, "ColumnEchelonForm", NumberColumns( B ) );
        
        return B;
        
    fi;
    
    B := Involution( RowEchelonForm( Involution( M ) ) );
    
    return B;
    
end );

##
InstallMethod( ColumnEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix and IsVoidMatrix ],
        
  function( M, T )
    local R, RP, t, TI, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    if IsBound(RP!.ColumnEchelonForm) then
        
        t := homalgTotalRuntimes( );
        
        ColoredInfoForService( "busy", "ColumnEchelonForm (M,T)", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
        
        B := RP!.ColumnEchelonForm( M, T );
        
        ColoredInfoForService( t, "ColumnEchelonForm (M,T)", Length( NonZeroColumns( B ) ) );
        
        return B;
        
    fi;
    
    TI := HomalgVoidMatrix( R );
    
    B := Involution( RowEchelonForm( Involution( M ), TI ) );
    
    SetPreEval( T, Involution( TI ) ); ResetFilterObj( T, IsVoidMatrix );
    
    return B;
    
end );

##
InstallMethod( ReducedRowEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    ColoredInfoForService( "busy", "ReducedRowEchelonForm", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    t := homalgTotalRuntimes( );
    
    if IsBound(RP!.ReducedRowEchelonForm) then
        
        B := RP!.ReducedRowEchelonForm( M );
        
        ColoredInfoForService( t, "ReducedRowEchelonForm", Length( NonZeroRows( B ) ) );
        
        return B;
        
    elif IsBound(RP!.ReducedColumnEchelonForm) then
        
        B := Involution( RP!.ReducedColumnEchelonForm( Involution( M ) ) );
        
        ColoredInfoForService( t, "ReducedRowEchelonForm", Length( NonZeroRows( B ) ) );
        
        return B;
        
    fi;
    
    TryNextMethod( );
    
end );

##
InstallMethod( ReducedRowEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix and IsVoidMatrix ],
        
  function( M, T )
    local R, RP, t, TI, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    ColoredInfoForService( "busy", "ReducedRowEchelonForm (M,T)", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    t := homalgTotalRuntimes( );
    
    if IsBound(RP!.ReducedRowEchelonForm) then
        
        B := RP!.ReducedRowEchelonForm( M, T );
        
        ColoredInfoForService( t, "ReducedRowEchelonForm (M,T)", Length( NonZeroRows( B ) ) );
        
        return B;
        
    elif IsBound(RP!.ReducedColumnEchelonForm) then
        
        TI := HomalgVoidMatrix( R );
        
        B := Involution( RP!.ReducedColumnEchelonForm( Involution( M ), TI ) );
        
        ColoredInfoForService( t, "ReducedRowEchelonForm (M,T)", Length( NonZeroRows( B ) ) );
        
        SetPreEval( T, Involution( TI ) ); ResetFilterObj( T, IsVoidMatrix );
        
        return B;
        
    fi;
    
    TryNextMethod( );
    
end );

##
InstallMethod( ReducedColumnEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    if IsBound(RP!.ReducedColumnEchelonForm) then
        
        t := homalgTotalRuntimes( );
        
        ColoredInfoForService( "busy", "ReducedColumnEchelonForm", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
        
        B := RP!.ReducedColumnEchelonForm( M );
        
        ColoredInfoForService( t, "ReducedColumnEchelonForm", Length( NonZeroColumns( B ) ) );
        
        return B;
        
    fi;
    
    B := Involution( ReducedRowEchelonForm( Involution( M ) ) );
    
    return B;
    
end );

##
InstallMethod( ReducedColumnEchelonForm,
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix and IsVoidMatrix ],
        
  function( M, T )
    local R, RP, t, TI, B;
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    if IsBound(RP!.ReducedColumnEchelonForm) then
        
        t := homalgTotalRuntimes( );
        
        ColoredInfoForService( "busy", "ReducedColumnEchelonForm (M,T)", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
        
        B := RP!.ReducedColumnEchelonForm( M, T );
        
        ColoredInfoForService( t, "ReducedColumnEchelonForm (M,T)", Length( NonZeroColumns( B ) ) );
        
        return B;
        
    fi;
    
    TI := HomalgVoidMatrix( R );
    
    B := Involution( ReducedRowEchelonForm( Involution( M ), TI ) );
    
    SetPreEval( T, Involution( TI ) ); ResetFilterObj( T, IsVoidMatrix );
    
    return B;
    
end );

#### Basis, DecideZero, Syzygies:

##  <#GAPDoc Label="BasisOfRowModule">
##  <ManSection>
##    <Oper Arg="M" Name="BasisOfRowModule" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )) and
##      <M>S</M> be the row span of <A>M</A>, i.e. the <M>R</M>-submodule of the free left module
##      <M>R^{(1 \times NumberColumns( <A>M</A> ))}</M> spanned by the rows of <A>M</A>. A solution to the
##      <Q>submodule membership problem</Q> is an algorithm which can decide if an element <M>m</M> in
##      <M>R^{(1 \times NumberColumns( <A>M</A> ))}</M> is contained in <M>S</M> or not. And exactly like
##      the Gaussian (resp. Hermite) normal form when <M>R</M> is a field (resp. principal ideal ring), the row span of
##      the resulting matrix <M>B</M> coincides with the row span <M>S</M> of <A>M</A>, and computing <M>B</M> is typically
##      the first step of such an algorithm. (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( BasisOfRowModule, ### defines: BasisOfRowModule (BasisOfModule (low-level))
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, nr_cols, nr_rows, MI, B, nz;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    nr_cols := NumberColumns( M );
    
    ColoredInfoForService( "busy", "BasisOfRowModule", NumberRows( M ), " x ", nr_cols, " : ", RingName( R ) );
    
    if IsBound(RP!.BasisOfRowModule) then
        
        B := RP!.BasisOfRowModule( M );
        
        if HasRowRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr_cols );
        
        nr_rows := NumberRows( B );
        
        if HasIsZero( M ) and not IsZero( M ) then
            
            ## check assertion
            Assert( 6, IsZero( B ) = IsZero( M ) );
            
            SetIsZero( B, false );
            
        elif nr_rows = 1 and IsZero( B ) then
            
            ## most computer algebra systems do not support empty matrices
            ## and return for a trivial BasisOfRowModule a one-row zero matrix
            
            B := HomalgZeroMatrix( 0, nr_cols, R );
            
            SetIsZero( M, true );
            
        else
            
            ## check assertion
            Assert( 6, R!.asserts.BasisOfRowModule( B ) );
            
            SetIsZero( B, nr_rows = 0 );
            SetIsZero( M, nr_rows = 0 );
            
        fi;
        
        SetIsBasisOfRowsMatrix( B, true );
        
        if HasIsReducedBasisOfRowsMatrix( M ) and IsReducedBasisOfRowsMatrix( M ) then
            SetReducedBasisOfRowModule( B, M );
        fi;
        
        ColoredInfoForService( t, "BasisOfRowModule", NumberRows( B ) );
        
        IncreaseRingStatistics( R, "BasisOfRowModule" );
        
        return B;
        
    elif IsBound(RP!.BasisOfColumnModule) then
        
        MI := Involution( M );
        
        B := RP!.BasisOfColumnModule( MI );
        
        if HasColumnRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr_cols );
        
        nr_rows := NumberColumns( B ); ## this is not a mistake
        
        if HasIsZero( M ) and not IsZero( M ) then
            
            ## check assertion
            Assert( 6, IsZero( B ) = IsZero( M ) );
            
            SetIsZero( B, false );
            
        elif nr_rows = 1 and IsZero( B ) then
            
            ## most computer algebra systems do not support empty matrices
            ## and return for a trivial BasisOfColumnModule a one-column zero matrix
            
            B := HomalgZeroMatrix( nr_cols, 0, R );
            
            SetIsZero( M, true );
            
        else
            
            ## check assertion
            Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
            
            SetIsZero( B, nr_rows = 0 );
            SetIsZero( M, nr_rows = 0 );
            
        fi;
        
        SetIsBasisOfColumnsMatrix( B, true );
        
        SetBasisOfColumnModule( MI, B );
        
        B := Involution( B );
        
        SetIsBasisOfRowsMatrix( B, true );
        
        if HasIsReducedBasisOfRowsMatrix( M ) and IsReducedBasisOfRowsMatrix( M ) then
            SetReducedBasisOfRowModule( B, M );
        fi;
        
        ColoredInfoForService( t, "BasisOfRowModule", NumberRows( B ) );
        
        DecreaseRingStatistics( R, "BasisOfRowModule" );
        
        IncreaseRingStatistics( R, "BasisOfColumnModule" );
        
        return B;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    B := ReducedRowEchelonForm( M );
    
    nz := Length( NonZeroRows( B ) );
    
    if nz = 0 then
        B := HomalgZeroMatrix( 0, NumberColumns( B ), R );
    else
        B := CertainRows( B, [ 1 .. nz ] );
    fi;
    
    ## check assertion
    Assert( 6, R!.asserts.BasisOfRowModule( B ) );
    
    nr_rows := NumberRows( B );
    
    SetIsZero( B, nr_rows = 0 );
    SetIsZero( M, nr_rows = 0 );
    
    SetIsBasisOfRowsMatrix( B, true );
    
    if HasIsReducedBasisOfRowsMatrix( M ) and IsReducedBasisOfRowsMatrix( M ) then
        SetReducedBasisOfRowModule( B, M );
    fi;
    
    ColoredInfoForService( t, "BasisOfRowModule", NumberRows( B ) );
    
    IncreaseRingStatistics( R, "BasisOfRowModule" );
    
    return B;
    
end );

##  <#GAPDoc Label="BasisOfColumnModule">
##  <ManSection>
##    <Oper Arg="M" Name="BasisOfColumnModule" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )) and
##      <M>S</M> be the column span of <A>M</A>, i.e. the <M>R</M>-submodule of the free right module
##      <M>R^{(NumberRows( <A>M</A> ) \times 1)}</M> spanned by the columns of <A>M</A>. A solution to the
##      <Q>submodule membership problem</Q> is an algorithm which can decide if an element <M>m</M> in
##      <M>R^{(NumberRows( <A>M</A> ) \times 1)}</M> is contained in <M>S</M> or not. And exactly like
##      the Gaussian (resp. Hermite) normal form when <M>R</M> is a field (resp. principal ideal ring), the column span of
##      the resulting matrix <M>B</M> coincides with the column span <M>S</M> of <A>M</A>, and computing <M>B</M> is typically
##      the first step of such an algorithm. (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( BasisOfColumnModule, ### defines: BasisOfColumnModule (BasisOfModule (low-level))
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, nr_rows, nr_cols, MI, B, nz;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    nr_rows := NumberRows( M );
    
    ColoredInfoForService( "busy", "BasisOfColumnModule", nr_rows, " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    if IsBound(RP!.BasisOfColumnModule) then
        
        B := RP!.BasisOfColumnModule( M );
        
        if HasColumnRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr_rows );
        
        nr_cols := NumberColumns( B );
        
        if HasIsZero( M ) and not IsZero( M ) then
            
            ## check assertion
            Assert( 6, IsZero( B ) = IsZero( M ) );
            
            SetIsZero( B, false );
            
        elif nr_cols = 1 and IsZero( B ) then
            
            ## most computer algebra systems do not support empty matrices
            ## and return for a trivial BasisOfColumnModule a one-column zero matrix
            
            B := HomalgZeroMatrix( nr_rows, 0, R );
            
            SetIsZero( M, true );
            
        else
            
            ## check assertion
            Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
            
            SetIsZero( B, nr_cols = 0 );
            SetIsZero( M, nr_cols = 0 );
            
        fi;
        
        SetIsBasisOfColumnsMatrix( B, true );
        
        if HasIsReducedBasisOfColumnsMatrix( M ) and IsReducedBasisOfColumnsMatrix( M ) then
            SetReducedBasisOfColumnModule( B, M );
        fi;
        
        ColoredInfoForService( t, "BasisOfColumnModule", NumberColumns( B ) );
        
        IncreaseRingStatistics( R, "BasisOfColumnModule" );
        
        return B;
        
    elif IsBound(RP!.BasisOfRowModule) then
        
        MI := Involution( M );
        
        B := RP!.BasisOfRowModule( MI );
        
        if HasRowRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr_rows );
        
        nr_cols := NumberRows( B ); ## this is not a mistake
        
        if HasIsZero( M ) and not IsZero( M ) then
            
            ## check assertion
            Assert( 6, IsZero( B ) = IsZero( M ) );
            
            SetIsZero( B, false );
            
        elif nr_cols = 1 and IsZero( B ) then
            
            ## most computer algebra systems do not support empty matrices
            ## and return for a trivial BasisOfRowModule a one-row zero matrix
            
            B := HomalgZeroMatrix( 0, nr_rows, R );
            
            SetIsZero( M, true );
            
        else
            
            ## check assertion
            Assert( 6, R!.asserts.BasisOfRowModule( B ) );
            
            SetIsZero( B, nr_cols = 0 );
            SetIsZero( M, nr_cols = 0 );
            
        fi;
        
        SetIsBasisOfRowsMatrix( B, true );
        
        SetBasisOfRowModule( MI, B );
        
        B := Involution( B );
        
        SetIsBasisOfColumnsMatrix( B, true );
        
        if HasIsReducedBasisOfColumnsMatrix( M ) and IsReducedBasisOfColumnsMatrix( M ) then
            SetReducedBasisOfColumnModule( B, M );
        fi;
        
        ColoredInfoForService( t, "BasisOfColumnModule", NumberColumns( B ) );
        
        DecreaseRingStatistics( R, "BasisOfColumnModule" );
        
        IncreaseRingStatistics( R, "BasisOfRowModule" );
        
        return B;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    B := ReducedColumnEchelonForm( M );
    
    nz := Length( NonZeroColumns( B ) );
    
    if nz = 0 then
        B := HomalgZeroMatrix( NumberRows( B ), 0, R );
    else
        B := CertainColumns( B, [ 1 .. nz ] );
    fi;
    
    ## check assertion
    Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
    
    nr_cols := NumberColumns( B );
    
    SetIsZero( B, nr_cols = 0 );
    SetIsZero( M, nr_cols = 0 );
    
    SetIsBasisOfColumnsMatrix( B, true );
    
    if HasIsReducedBasisOfColumnsMatrix( M ) and IsReducedBasisOfColumnsMatrix( M ) then
        SetReducedBasisOfColumnModule( B, M );
    fi;
    
    ColoredInfoForService( t, "BasisOfColumnModule", NumberColumns( B ) );
    
    IncreaseRingStatistics( R, "BasisOfColumnModule" );
    
    return B;
    
end );

##  <#GAPDoc Label="DecideZeroRows">
##  <ManSection>
##    <Oper Arg="A, B" Name="DecideZeroRows" Label="for pairs of matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <A>A</A> and <A>B</A> be matrices having the same number of columns and defined over the same ring <M>R</M>
##      (<M>:=</M><C>HomalgRing</C>( <A>A</A> )) and <M>S</M> be the row span of <A>B</A>,
##      i.e. the <M>R</M>-submodule of the free left module <M>R^{(1 \times NumberColumns( <A>B</A> ))}</M>
##      spanned by the rows of <A>B</A>. The result is a matrix <M>C</M> having the same shape as <A>A</A>,
##      for which the <M>i</M>-th row <M><A>C</A>^i</M> is equivalent to the <M>i</M>-th row <M><A>A</A>^i</M> of <A>A</A> modulo <M>S</M>,
##      i.e. <M><A>C</A>^i-<A>A</A>^i</M> is an element of the row span <M>S</M> of <A>B</A>. Moreover, the row <M><A>C</A>^i</M> is zero,
##      if and only if the row <M><A>A</A>^i</M> is an element of <M>S</M>. So <C>DecideZeroRows</C> decides which rows of <A>A</A>
##      are zero modulo the rows of <A>B</A>. (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( DecideZeroRows, ### defines: DecideZeroRows (Reduce)
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix ],
        
  function( A, B )
    local R, RP, t, l, m, n, id, zz, M, C;
    
    ## we can only reduce with respect to a distinguished basis
    B := BasisOfRowModule( B );
    
    if IsBound( A!.DecideZeroRows ) and
       IsIdenticalObj( A!.DecideZeroRows, B ) then
        
        return A;
        
    fi;
    
    if not ( IsMutable( A ) or IsMutable( B ) ) then
        if IsBound( B!.DecideZeroRows ) then
            C := _ElmWPObj_ForHomalg( B!.DecideZeroRows, A, fail );
            if C <> fail then
                return C;
            fi;
        else
            B!.DecideZeroRows :=
              ContainerForWeakPointers(
                      TheTypeContainerForWeakPointersOnComputedValues,
                      [ "operation", "DecideZeroRows" ] );
        fi;
    fi;
    
    ### causes many IsZero external calls without
    ### reducing the effective number of DecideZero calls;
    ### observed with Purity.g in ExamplesForHomalg
    ## if IsZero( A ) or IsZero( B ) then
    ##     ## redispatch to the specialized methods
    ##     return DecideZeroRows( A, B );
    ## fi;
    
    if HasIsZero( B ) and IsZero( B ) then
        ## redispatch to the specialized methods
        return DecideZeroRows( A, B );
    fi;
    
    R := HomalgRing( B );
    
    R!.asserts.DecideZeroRowsWRTNonBasis( B );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    l := NumberRows( A );
    m := NumberColumns( A );
    
    n := NumberRows( B );
    
    ColoredInfoForService( "busy", "DecideZeroRows", "( ", l, " + ", n, " ) x ", m, " : ", RingName( R ) );
    
    if IsBound(RP!.DecideZeroRows) then
        
        C := RP!.DecideZeroRows( A, B );
        
        SetNumberRows( C, l ); SetNumberColumns( C, m );
        
        if not IsZero( C ) then
            Assert( 6, not IsZero( A ) );
            SetIsZero( A, false );
        fi;
        
        C!.DecideZeroRows := B;
        
        if not ( IsMutable( A ) or IsMutable( B ) ) then
            _AddTwoElmWPObj_ForHomalg( B!.DecideZeroRows, A, C );
        fi;
        
        ColoredInfoForService( t, "DecideZeroRows" );
        
        IncreaseRingStatistics( R, "DecideZeroRows" );
        
        return C;
        
    elif IsBound(RP!.DecideZeroColumns) then
        
        C := RP!.DecideZeroColumns( Involution( A ), Involution( B ) );
        
        SetNumberRows( C, m ); SetNumberColumns( C, l );
        
        if not IsZero( C ) then
            Assert( 6, not IsZero( A ) );
            SetIsZero( A, false );
        fi;
        
        C := Involution( C );
        
        C!.DecideZeroRows := B;
        
        if not ( IsMutable( A ) or IsMutable( B ) ) then
            _AddTwoElmWPObj_ForHomalg( B!.DecideZeroRows, A, C );
        fi;
        
        ColoredInfoForService( t, "DecideZeroRows" );
        
        DecreaseRingStatistics( R, "DecideZeroRows" );
        
        IncreaseRingStatistics( R, "DecideZeroColumns" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    if HasIsOne( A ) and IsOne( A ) then ## save as much new definitions as possible
        id := A;
    else
        id := HomalgIdentityMatrix( l, R );
    fi;
    
    zz := HomalgZeroMatrix( n, l, R );
    
    M := UnionOfRows( UnionOfColumns( id, A ), UnionOfColumns( zz, B ) );
    
    M := ReducedRowEchelonForm( M );
    
    C := CertainRows( CertainColumns( M, [ l + 1 .. l + m ] ), [ 1 .. l ] );
    
    if not IsZero( C ) then
        Assert( 6, not IsZero( A ) );
        SetIsZero( A, false );
    fi;
    
    C!.DecideZeroRows := B;
    
    if not ( IsMutable( A ) or IsMutable( B ) ) then
        _AddTwoElmWPObj_ForHomalg( B!.DecideZeroRows, A, C );
    fi;
    
    ColoredInfoForService( t, "DecideZeroRows" );
    
    IncreaseRingStatistics( R, "DecideZeroRows" );
    
    return C;
    
end );

##  <#GAPDoc Label="DecideZeroColumns">
##  <ManSection>
##    <Oper Arg="A, B" Name="DecideZeroColumns" Label="for pairs of matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <A>A</A> and <A>B</A> be matrices having the same number of rows and defined over the same ring <M>R</M>
##      (<M>:=</M><C>HomalgRing</C>( <A>A</A> )) and <M>S</M> be the column span of <A>B</A>,
##      i.e. the <M>R</M>-submodule of the free right module <M>R^{(NumberRows( <A>B</A> ) \times 1)}</M>
##      spanned by the columns of <A>B</A>. The result is a matrix <M>C</M> having the same shape as <A>A</A>,
##      for which the <M>i</M>-th column <M><A>C</A>_i</M> is equivalent to the <M>i</M>-th column <M><A>A</A>_i</M> of <A>A</A>
##      modulo <M>S</M>, i.e. <M><A>C</A>_i-<A>A</A>_i</M> is an element of the column span <M>S</M> of <A>B</A>. Moreover,
##      the column <M><A>C</A>_i</M> is zero, if and only if the column <M><A>A</A>_i</M> is an element of <M>S</M>.
##      So <C>DecideZeroColumns</C> decides which columns of <A>A</A> are zero modulo the columns of <A>B</A>.
##      (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( DecideZeroColumns, ### defines: DecideZeroColumns (Reduce)
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix ],
        
  function( A, B )
    local R, RP, t, l, m, n, id, zz, M, C;
    
    ## we can only reduce with respect to a distinguished basis
    B := BasisOfColumnModule( B );
    
    if IsBound( A!.DecideZeroColumns ) and
       IsIdenticalObj( A!.DecideZeroColumns, B ) then
        
        return A;
        
    fi;
    
    if not ( IsMutable( A ) or IsMutable( B ) ) then
        if IsBound( B!.DecideZeroColumns ) then
            C := _ElmWPObj_ForHomalg( B!.DecideZeroColumns, A, fail );
            if C <> fail then
                return C;
            fi;
        else
            B!.DecideZeroColumns :=
              ContainerForWeakPointers(
                      TheTypeContainerForWeakPointersOnComputedValues,
                      [ "operation", "DecideZeroColumns" ] );
        fi;
    fi;
    
    ### causes many IsZero external calls without
    ### reducing the effective number of DecideZero calls;
    ### observed with Purity.g in ExamplesForHomalg
    ## if IsZero( A ) or IsZero( B ) then
    ##     ## redispatch to the specialized methods
    ##     return DecideZeroColumns( A, B );
    ## fi;
    
    if HasIsZero( B ) and IsZero( B ) then
        ## redispatch to the specialized methods
        return DecideZeroColumns( A, B );
    fi;
    
    R := HomalgRing( B );
    
    R!.asserts.DecideZeroColumnsWRTNonBasis( B );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    l := NumberColumns( A );
    m := NumberRows( A );
    
    n := NumberColumns( B );
    
    ColoredInfoForService( "busy", "DecideZeroColumns", m, " x ( ", l, " + ", n, " ) : ", RingName( R ) );
    
    if IsBound(RP!.DecideZeroColumns) then
        
        C := RP!.DecideZeroColumns( A, B );
        
        SetNumberRows( C, m ); SetNumberColumns( C, l );
        
        if not IsZero( C ) then
            Assert( 6, not IsZero( A ) );
            SetIsZero( A, false );
        fi;
        
        C!.DecideZeroColumns := B;
        
        if not ( IsMutable( A ) or IsMutable( B ) ) then
            _AddTwoElmWPObj_ForHomalg( B!.DecideZeroColumns, A, C );
        fi;
        
        ColoredInfoForService( t, "DecideZeroColumns" );
        
        IncreaseRingStatistics( R, "DecideZeroColumns" );
        
        return C;
        
    elif IsBound(RP!.DecideZeroRows) then
        
        C := RP!.DecideZeroRows( Involution( A ), Involution( B ) );
        
        SetNumberRows( C, l ); SetNumberColumns( C, m );
        
        if not IsZero( C ) then
            Assert( 6, not IsZero( A ) );
            SetIsZero( A, false );
        fi;
        
        C := Involution( C );
        
        C!.DecideZeroColumns := B;
        
        if not ( IsMutable( A ) or IsMutable( B ) ) then
            _AddTwoElmWPObj_ForHomalg( B!.DecideZeroColumns, A, C );
        fi;
        
        ColoredInfoForService( t, "DecideZeroColumns" );
        
        DecreaseRingStatistics( R, "DecideZeroColumns" );
        
        IncreaseRingStatistics( R, "DecideZeroRows" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    if HasIsOne( A ) and IsOne( A ) then ## save as much new definitions as possible
        id := A;
    else
        id := HomalgIdentityMatrix( l, R );
    fi;
    
    zz := HomalgZeroMatrix( l, n, R );
    
    M := UnionOfColumns( UnionOfRows( id, A ), UnionOfRows( zz, B ) );
    
    M := ReducedColumnEchelonForm( M );
    
    C := CertainColumns( CertainRows( M, [ l + 1 .. l + m ] ), [ 1 .. l ] );
    
    if not IsZero( C ) then
        Assert( 6, not IsZero( A ) );
        SetIsZero( A, false );
    fi;
    
    C!.DecideZeroColumns := B;
    
    if not ( IsMutable( A ) or IsMutable( B ) ) then
        _AddTwoElmWPObj_ForHomalg( B!.DecideZeroColumns, A, C );
    fi;
    
    ColoredInfoForService( t, "DecideZeroColumns" );
    
    IncreaseRingStatistics( R, "DecideZeroColumns" );
    
    return C;
    
end );

##  <#GAPDoc Label="SyzygiesGeneratorsOfRows">
##  <ManSection>
##    <Oper Arg="M" Name="SyzygiesGeneratorsOfRows" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )).
##      The matrix of row syzygies <C>SyzygiesGeneratorsOfRows</C>( <A>M</A> ) is a matrix whose rows span
##      the left kernel of <A>M</A>, i.e. the <M>R</M>-submodule of the free left module <M>R^{(1 \times NumberRows( <A>M</A> ))}</M>
##      consisting of all rows <M>X</M> satisfying <M>X<A>M</A>=0</M>.
##      (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( SyzygiesGeneratorsOfRows,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, MI, C, B, nz;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    ColoredInfoForService( "busy", "SyzygiesGeneratorsOfRows", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    if IsBound(R!.ComputeBasisBeforeSyzygies) and R!.ComputeBasisBeforeSyzygies = true then
        BasisOfRowModule( M );
    fi;
    
    if IsBound(RP!.SyzygiesGeneratorsOfRows) then
        
        C := RP!.SyzygiesGeneratorsOfRows( M );
        
        if IsZero( C ) then
            
            SetIsLeftRegular( M, true );
            
            C := HomalgZeroMatrix( 0, NumberRows( M ), R ); ## most of the computer algebra systems cannot handle degenerated matrices
            
        else
            
            SetNumberColumns( C, NumberRows( M ) );
            
        fi;
        
        ColoredInfoForService( t, "SyzygiesGeneratorsOfRows", NumberRows( C ) );
        
        IncreaseRingStatistics( R, "SyzygiesGeneratorsOfRows" );
        
        return C;
        
    elif IsBound(RP!.SyzygiesGeneratorsOfColumns) then
        
        MI := Involution( M );
        
        C := RP!.SyzygiesGeneratorsOfColumns( MI );
        
        SetSyzygiesGeneratorsOfColumns( MI, C );
        
        C := Involution( C );
        
        if IsZero( C ) then
            
            SetIsLeftRegular( M, true );
            
            C := HomalgZeroMatrix( 0, NumberRows( M ), R ); ## most of the computer algebra systems cannot handle degenerated matrices
            
        else
            
            SetNumberColumns( C, NumberRows( M ) );
            
        fi;
        
        ColoredInfoForService( t, "SyzygiesGeneratorsOfRows", NumberRows( C ) );
        
        DecreaseRingStatistics( R, "SyzygiesGeneratorsOfRows" );
        
        IncreaseRingStatistics( R, "SyzygiesGeneratorsOfColumns" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    C := HomalgVoidMatrix( R );
    
    B := ReducedRowEchelonForm( M, C );
    
    nz := Length( NonZeroRows( B ) );
    
    C := CertainRows( C, [ nz + 1 .. NumberRows( C ) ] );
    
    if IsZero( C ) then
        
        SetIsLeftRegular( M, true );
        
        C := HomalgZeroMatrix( 0, NumberRows( M ), R );
        
    fi;
    
    ColoredInfoForService( t, "SyzygiesGeneratorsOfRows", NumberRows( C ) );
    
    IncreaseRingStatistics( R, "SyzygiesGeneratorsOfRows" );
    
    return C;
    
end );

##  <#GAPDoc Label="SyzygiesGeneratorsOfColumns">
##  <ManSection>
##    <Oper Arg="M" Name="SyzygiesGeneratorsOfColumns" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )).
##      The matrix of column syzygies <C>SyzygiesGeneratorsOfColumns</C>( <A>M</A> ) is a matrix whose columns span
##      the right kernel of <A>M</A>, i.e. the <M>R</M>-submodule of the free right module <M>R^{(NumberColumns( <A>M</A> ) \times 1)}</M>
##      consisting of all columns <M>X</M> satisfying <M><A>M</A>X=0</M>.
##      (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( SyzygiesGeneratorsOfColumns,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, MI, C, B, nz;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    ColoredInfoForService( "busy", "SyzygiesGeneratorsOfColumns", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    if IsBound(R!.ComputeBasisBeforeSyzygies) and R!.ComputeBasisBeforeSyzygies = true then
        BasisOfColumnModule( M );
    fi;
    
    if IsBound(RP!.SyzygiesGeneratorsOfColumns) then
        
        C := RP!.SyzygiesGeneratorsOfColumns( M );
        
        if IsZero( C ) then
            
            SetIsRightRegular( M, true );
            
            C := HomalgZeroMatrix( NumberColumns( M ), 0, R );
            
        else
            
            SetNumberRows( C, NumberColumns( M ) );
            
        fi;
        
        ColoredInfoForService( t, "SyzygiesGeneratorsOfColumns", NumberColumns( C ) );
        
        IncreaseRingStatistics( R, "SyzygiesGeneratorsOfColumns" );
        
        return C;
        
    elif IsBound(RP!.SyzygiesGeneratorsOfRows) then
        
        MI := Involution( M );
        
        C := RP!.SyzygiesGeneratorsOfRows( MI );
        
        SetSyzygiesGeneratorsOfRows( MI, C );
        
        C := Involution( C );
        
        if IsZero( C ) then
            
            SetIsRightRegular( M, true );
            
            C := HomalgZeroMatrix( NumberColumns( M ), 0, R );
            
        else
            
            SetNumberRows( C, NumberColumns( M ) );
            
        fi;
        
        ColoredInfoForService( t, "SyzygiesGeneratorsOfColumns", NumberColumns( C ) );
        
        DecreaseRingStatistics( R, "SyzygiesGeneratorsOfColumns" );
        
        IncreaseRingStatistics( R, "SyzygiesGeneratorsOfRows" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    C := HomalgVoidMatrix( R );
    
    B := ReducedColumnEchelonForm( M, C );
    
    nz := Length( NonZeroColumns( B ) );
    
    C := CertainColumns( C, [ nz + 1 .. NumberColumns( C ) ] );
    
    if IsZero( C ) then
        
        SetIsRightRegular( M, true );
        
        C := HomalgZeroMatrix( NumberColumns( M ), 0, R );
        
    fi;
    
    ColoredInfoForService( t, "SyzygiesGeneratorsOfColumns", NumberColumns( C ) );
    
    IncreaseRingStatistics( R, "SyzygiesGeneratorsOfColumns" );
    
    return C;
    
end );

#### Relative:

##  <#GAPDoc Label="RelativeSyzygiesGeneratorsOfRows">
##  <ManSection>
##    <Oper Arg="M, M2" Name="SyzygiesGeneratorsOfRows" Label="for pairs of matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )).
##      The matrix of <E>relative</E> row syzygies <C>SyzygiesGeneratorsOfRows</C>( <A>M</A>, <A>M2</A> ) is a matrix
##      whose rows span the left kernel of <A>M</A> modulo <A>M2</A>, i.e. the <M>R</M>-submodule of the free left module
##      <M>R^{(1 \times NumberRows( <A>M</A> ))}</M> consisting of all rows <M>X</M> satisfying <M>X<A>M</A>+Y<A>M2</A>=0</M>
##      for some row <M>Y \in R^{(1 \times NumberRows( <A>M2</A> ))}</M>. (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( SyzygiesGeneratorsOfRows, ### defines: SyzygiesGeneratorsOfRows (SyzygiesGenerators)
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix ],
        
  function( M1, M2 )
    local R, RP, t, M, C, nz;
    
    ## a LIMAT method takes care of the case when M2 is _known_ to be zero
    ## checking IsZero( M2 ) causes too many obsolete calls
    
    R := HomalgRing( M1 );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    ColoredInfoForService( "busy", "RelativeSyzygiesGeneratorsOfRows", "( ", NumberRows( M1 ), " + ", NumberRows( M2 ), " ) x ", NumberColumns( M1 ), " : ", RingName( R ) );
    
    if IsBound(R!.ComputeBasisBeforeSyzygies) and R!.ComputeBasisBeforeSyzygies = true then
        BasisOfRowModule( M1 );
        BasisOfRowModule( M2 );
    fi;
    
    if IsBound(RP!.RelativeSyzygiesGeneratorsOfRows) then
        
        C := RP!.RelativeSyzygiesGeneratorsOfRows( M1, M2 );
        
        if IsZero( C ) then
            
            C := HomalgZeroMatrix( 0, NumberRows( M1 ), R );
            
        else
            
            SetNumberColumns( C, NumberRows( M1 ) );
            
        fi;
        
        ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfRows", NumberRows( C ) );
        
        IncreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfRows" );
        
        return C;
        
    elif IsBound(RP!.RelativeSyzygiesGeneratorsOfColumns) then
        
        C := Involution( RP!.RelativeSyzygiesGeneratorsOfColumns( Involution( M1 ), Involution( M2 ) ) );
        
        if IsZero( C ) then
            
            C := HomalgZeroMatrix( 0, NumberRows( M1 ), R );
            
        else
            
            SetNumberColumns( C, NumberRows( M1 ) );
            
        fi;
        
        ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfRows", NumberRows( C ) );
        
        DecreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfRows" );
        
        IncreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfColumns" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    M := UnionOfRows( M1, M2 );
    
    C := SyzygiesGeneratorsOfRows( M );
    
    C := CertainColumns( C, [ 1 .. NumberRows( M1 ) ] );
    
    ## since we first compute the syzygies matrix of
    ## the stack of M1 and M2, and then keep only
    ## those columns C corresponding to M1,
    ## zero rows can potentially exist in C
    ## (and we like to remove them)
    
    C := GetRidOfObsoleteRows( C );
    
    if IsZero( C ) then
        
        SetIsLeftRegular( M1, true );
        
    fi;
    
    ## forgetting the original obsolete C may save memory
    if HasEvalCertainColumns( C ) then
        if not IsEmptyMatrix( C ) then
            Eval( C );
        fi;
        ResetFilterObj( C, HasEvalCertainColumns );
        Unbind( C!.EvalCertainColumns );
    fi;
    
    ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfRows", NumberRows( C ) );
    
    DecreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfRows" );
    
    return C;
    
end );

##  <#GAPDoc Label="RelativeSyzygiesGeneratorsOfColumns">
##  <ManSection>
##    <Oper Arg="M, M2" Name="SyzygiesGeneratorsOfColumns" Label="for pairs of matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Let <M>R</M> be the ring over which <A>M</A> is defined (<M>R:=</M><C>HomalgRing</C>( <A>M</A> )).
##      The matrix of <E>relative</E> column syzygies <C>SyzygiesGeneratorsOfColumns</C>( <A>M</A>, <A>M2</A> ) is a matrix
##      whose columns span the right kernel of <A>M</A> modulo <A>M2</A>, i.e. the <M>R</M>-submodule of the free right module
##      <M>R^{(NumberColumns( <A>M</A> ) \times 1)}</M> consisting of all columns <M>X</M> satisfying <M><A>M</A>X+<A>M2</A>Y=0</M>
##      for some column <M>Y \in R^{(NumberColumns( <A>M2</A> ) \times 1)}</M>. (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( SyzygiesGeneratorsOfColumns, ### defines: SyzygiesGeneratorsOfColumns (SyzygiesGenerators)
        "for homalg matrices",
        [ IsHomalgMatrix, IsHomalgMatrix ],
        
  function( M1, M2 )
    local R, RP, t, M, C, nz;
    
    ## a LIMAT method takes care of the case when M2 is _known_ to be zero
    ## checking IsZero( M2 ) causes too many obsolete calls
    
    R := HomalgRing( M1 );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    ColoredInfoForService( "busy", "RelativeSyzygiesGeneratorsOfColumns", NumberRows( M1 ), " x ( ", NumberColumns( M1 ), " + ", NumberColumns( M2 ), " ) : ", RingName( R ) );
    
    if IsBound(R!.ComputeBasisBeforeSyzygies) and R!.ComputeBasisBeforeSyzygies = true then
        BasisOfColumnModule( M1 );
        BasisOfColumnModule( M2 );
    fi;
    
    if IsBound(RP!.RelativeSyzygiesGeneratorsOfColumns) then
        
        C := RP!.RelativeSyzygiesGeneratorsOfColumns( M1, M2 );
        
        if IsZero( C ) then
            
            C := HomalgZeroMatrix( NumberColumns( M1 ), 0, R );
            
        else
            
            SetNumberRows( C, NumberColumns( M1 ) );
            
        fi;
        
        ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfColumns", NumberColumns( C ) );
        
        IncreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfColumns" );
        
        return C;
        
    elif IsBound(RP!.RelativeSyzygiesGeneratorsOfRows) then
        
        C := Involution( RP!.RelativeSyzygiesGeneratorsOfRows( Involution( M1 ), Involution( M2 ) ) );
        
        if IsZero( C ) then
            
            C := HomalgZeroMatrix( NumberColumns( M1 ), 0, R );
            
        else
            
            SetNumberRows( C, NumberColumns( M1 ) );
            
        fi;
        
        ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfColumns", NumberColumns( C ) );
        
        DecreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfColumns" );
        
        IncreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfRows" );
        
        return C;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    M := UnionOfColumns( M1, M2 );
    
    C := SyzygiesGeneratorsOfColumns( M );
    
    C := CertainRows( C, [ 1 .. NumberColumns( M1 ) ] );
    
    ## since we first computes the syzygies matrix of
    ## the augmentation of M1 and M2, and then keep
    ## only those rows C corresponding to M1,
    ## zero columns can potentially exist in C
    ## (and we like to remove them)
    
    C := GetRidOfObsoleteColumns( C );
    
    if IsZero( C ) then
        
        SetIsRightRegular( M1, true );
        
    fi;
    
    ## forgetting the original obsolete C may save memory
    if HasEvalCertainRows( C ) then
        if not IsEmptyMatrix( C ) then
            Eval( C );
        fi;
        ResetFilterObj( C, HasEvalCertainRows );
        Unbind( C!.EvalCertainRows );
    fi;
    
    ColoredInfoForService( t, "RelativeSyzygiesGeneratorsOfColumns", NumberColumns( C ) );
    
    DecreaseRingStatistics( R, "RelativeSyzygiesGeneratorsOfColumns" );
    
    return C;
    
end );

#### Reduced:

##  <#GAPDoc Label="ReducedBasisOfRowModule">
##  <ManSection>
##    <Oper Arg="M" Name="ReducedBasisOfRowModule" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Like <C>BasisOfRowModule</C>( <A>M</A> ) but where the matrix
##      <C>SyzygiesGeneratorsOfRows</C>( <C>ReducedBasisOfRowModule</C>( <A>M</A> ) ) contains no units. This can easily
##      be achieved starting from <M>B:=</M><C>BasisOfRowModule</C>( <A>M</A> )
##      (and using <Ref Oper="GetColumnIndependentUnitPositions" Label="for matrices"/> applied to the matrix of row syzygies of <M>B</M>,
##       etc). (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( ReducedBasisOfRowModule,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, nr, MI, B, S, unit_pos;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    nr := NumberColumns( M );
    
    ColoredInfoForService( "busy", "ReducedBasisOfRowModule", NumberRows( M ), " x ", nr, " : ", RingName( R ) );
    
    if IsBound(RP!.ReducedBasisOfRowModule) then
        
        B := RP!.ReducedBasisOfRowModule( M );
        
        if HasRowRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfRowModule( B ) );
        
        nr := NumberRows( B );
        
        SetIsZero( B, nr = 0 );
        
        if M = B then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfRowModule( M, B ) );
        fi;
        
        SetIsReducedBasisOfRowsMatrix( B, true );
        
        if HasIsBasisOfRowsMatrix( M ) and IsBasisOfRowsMatrix( M ) then
            SetBasisOfRowModule( B, M );
        fi;
        
        ColoredInfoForService( t, "ReducedBasisOfRowModule", NumberRows( B ) );
        
        IncreaseRingStatistics( R, "ReducedBasisOfRowModule" );
        
        return B;
        
    elif IsBound(RP!.ReducedBasisOfColumnModule) then
        
        MI := Involution( M );
        
        B := RP!.ReducedBasisOfColumnModule( MI );
        
        if HasColumnRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr );
        
        SetIsReducedBasisOfColumnsMatrix( B, true );
        
        SetReducedBasisOfColumnModule( MI, B );
        
        B := Involution( B );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfRowModule( B ) );
        
        nr := NumberRows( B );
        
        SetIsZero( B, nr = 0 );
        
        if M = B then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfRowModule( M, B ) );
        fi;
        
        SetIsReducedBasisOfRowsMatrix( B, true );
        
        if HasIsBasisOfRowsMatrix( M ) and IsBasisOfRowsMatrix( M ) then
            SetBasisOfRowModule( B, M );
        fi;
        
        ColoredInfoForService( t, "ReducedBasisOfRowModule", NumberRows( B ) );
        
        DecreaseRingStatistics( R, "ReducedBasisOfRowModule" );
        
        IncreaseRingStatistics( R, "ReducedBasisOfColumnModule" );
        
        return B;
        
    fi;
    
    ## try RP!.PartiallyReducedBasisOf*Module
    if IsBound(RP!.PartiallyReducedBasisOfRowModule) then
        
        B := RP!.PartiallyReducedBasisOfRowModule( M );
        
        if HasRowRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfRowModule( B ) );
        
        nr := NumberRows( B );
        
        SetIsZero( B, nr = 0 );
        
        if NumberRows( M ) <= nr then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfRowModule( M, B ) );
        fi;
        
        IncreaseRingStatistics( R, "PartiallyReducedBasisOfRowModule" );
        
    elif IsBound(RP!.PartiallyReducedBasisOfColumnModule) then
        
        MI := Involution( M );
        
        B := RP!.PartiallyReducedBasisOfColumnModule( MI );
        
        if HasColumnRankOfMatrix( B ) then
            SetRowRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr );
        
        B := Involution( B );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfRowModule( B ) );
        
        nr := NumberRows( B );
        
        SetIsZero( B, nr = 0 );
        
        if NumberRows( M ) <= nr then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfRowModule( M, B ) );
        fi;
        
        DecreaseRingStatistics( R, "PartiallyReducedBasisOfRowModule" );
        
        IncreaseRingStatistics( R, "PartiallyReducedBasisOfColumnModule" );
        
    else
        
        B := M;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    ## iterate the syzygy trick
    while true do
        S := SyzygiesGeneratorsOfRows( B );
        
        unit_pos := GetColumnIndependentUnitPositions( S );
        unit_pos := List( unit_pos, a -> a[2] );
        
        if NumberRows( S ) = 0 or unit_pos = [ ] then
            break;
        fi;
        
        B := CertainRows( B, Filtered( [ 1 .. NumberRows( B ) ], j -> not j in unit_pos ) );
    od;
    
    ## check assertion
    Assert( 6, R!.asserts.BasisOfRowModule( B ) );
    
    nr := NumberRows( B );
    
    SetIsZero( B, nr = 0 );
    SetIsZero( M, nr = 0 );
    
    ## check assertion
    Assert( 6, R!.asserts.ReducedBasisOfRowModule( M, B ) );
    
    SetIsReducedBasisOfRowsMatrix( B, true );
    
    if HasIsBasisOfRowsMatrix( M ) and IsBasisOfRowsMatrix( M ) then
        SetBasisOfRowModule( B, M );
    fi;
    
    ColoredInfoForService( t, "ReducedBasisOfRowModule", NumberRows( B ) );
    
    DecreaseRingStatistics( R, "ReducedBasisOfRowModule" );
    
    return B;
    
end );

##  <#GAPDoc Label="ReducedBasisOfColumnModule">
##  <ManSection>
##    <Oper Arg="M" Name="ReducedBasisOfColumnModule" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Like <C>BasisOfColumnModule</C>( <A>M</A> ) but where the matrix
##      <C>SyzygiesGeneratorsOfColumns</C>( <C>ReducedBasisOfColumnModule</C>( <A>M</A> ) ) contains no units. This can easily
##      be achieved starting from <M>B:=</M><C>BasisOfColumnModule</C>( <A>M</A> )
##      (and using <Ref Oper="GetRowIndependentUnitPositions" Label="for matrices"/> applied to the matrix of column syzygies of <M>B</M>,
##       etc.). (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( ReducedBasisOfColumnModule,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, nr, MI, B, S, unit_pos;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    nr := NumberRows( M );
    
    ColoredInfoForService( "busy", "ReducedBasisOfColumnModule", nr, " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    if IsBound(RP!.ReducedBasisOfColumnModule) then
        
        B := RP!.ReducedBasisOfColumnModule( M );
        
        if HasColumnRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
        
        nr := NumberColumns( B );
        
        SetIsZero( B, nr = 0 );
        
        if M = B then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfColumnModule( M, B ) );
        fi;
        
        SetIsReducedBasisOfColumnsMatrix( B, true );
        
        if HasIsBasisOfColumnsMatrix( M ) and IsBasisOfColumnsMatrix( M ) then
            SetBasisOfColumnModule( B, M );
        fi;
        
        ColoredInfoForService( t, "ReducedBasisOfColumnModule", NumberColumns( B ) );
        
        IncreaseRingStatistics( R, "ReducedBasisOfColumnModule" );
        
        return B;
        
    elif IsBound(RP!.ReducedBasisOfRowModule) then
        
        MI := Involution( M );
        
        B := RP!.ReducedBasisOfRowModule( MI );
        
        if HasRowRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr );
        
        SetIsReducedBasisOfRowsMatrix( B, true );
        
        SetReducedBasisOfRowModule( MI, B );
        
        B := Involution( B );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
        
        nr := NumberColumns( B );
        
        SetIsZero( B, nr = 0 );
        
        if M = B then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfColumnModule( M, B ) );
        fi;
        
        SetIsReducedBasisOfColumnsMatrix( B, true );
        
        if HasIsBasisOfColumnsMatrix( M ) and IsBasisOfColumnsMatrix( M ) then
            SetBasisOfColumnModule( B, M );
        fi;
        
        ColoredInfoForService( t, "ReducedBasisOfColumnModule", NumberColumns( B ) );
        
        DecreaseRingStatistics( R, "ReducedBasisOfColumnModule" );
        
        IncreaseRingStatistics( R, "ReducedBasisOfRowModule" );
        
        return B;
        
    fi;
    
    ## try RP!.PartiallyReducedBasisOf*Module
    if IsBound(RP!.PartiallyReducedBasisOfColumnModule) then
        
        B := RP!.PartiallyReducedBasisOfColumnModule( M );
        
        if HasColumnRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, ColumnRankOfMatrix( B ) );
        fi;
        
        SetNumberRows( B, nr );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
        
        nr := NumberColumns( B );
        
        SetIsZero( B, nr = 0 );
        
        if NumberColumns( M ) <= nr then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfColumnModule( M, B ) );
        fi;
        
        IncreaseRingStatistics( R, "PartiallyReducedBasisOfColumnModule" );
        
    elif IsBound(RP!.PartiallyReducedBasisOfRowModule) then
        
        MI := Involution( M );
        
        B := RP!.PartiallyReducedBasisOfRowModule( MI );
        
        if HasRowRankOfMatrix( B ) then
            SetColumnRankOfMatrix( M, RowRankOfMatrix( B ) );
        fi;
        
        SetNumberColumns( B, nr );
        
        B := Involution( B );
        
        ## check assertion
        Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
        
        nr := NumberColumns( B );
        
        SetIsZero( B, nr = 0 );
        
        if NumberColumns( M ) <= nr then
            B := M; ## we might know more about M
        else
            SetIsZero( M, nr = 0 );
            
            ## check assertion
            Assert( 6, R!.asserts.ReducedBasisOfColumnModule( M, B ) );
        fi;
        
        DecreaseRingStatistics( R, "PartiallyReducedBasisOfColumnModule" );
        
        IncreaseRingStatistics( R, "PartiallyReducedBasisOfRowModule" );
        
    else
        
        B := M;
        
    fi;
    
    #=====# begin of the core procedure #=====#
    
    ## iterate the syzygy trick
    while true do
        S := SyzygiesGeneratorsOfColumns( B );
        
        unit_pos := GetRowIndependentUnitPositions( S );
        unit_pos := List( unit_pos, a -> a[2] );
        
        if NumberColumns( S ) = 0 or unit_pos = [ ] then
            break;
        fi;
        
        B := CertainColumns( B, Filtered( [ 1 .. NumberColumns( B ) ], j -> not j in unit_pos ) );
    od;
    
    ## check assertion
    Assert( 6, R!.asserts.BasisOfColumnModule( B ) );
    
    nr := NumberColumns( B );
    
    SetIsZero( B, nr = 0 );
    SetIsZero( M, nr = 0 );
    
    ## check assertion
    Assert( 6, R!.asserts.ReducedBasisOfColumnModule( M, B ) );
    
    SetIsReducedBasisOfColumnsMatrix( B, true );
    
    if HasIsBasisOfColumnsMatrix( M ) and IsBasisOfColumnsMatrix( M ) then
        SetBasisOfColumnModule( B, M );
    fi;
    
    ColoredInfoForService( t, "ReducedBasisOfColumnModule", NumberColumns( B ) );
    
    DecreaseRingStatistics( R, "ReducedBasisOfColumnModule" );
    
    return B;
    
end );

##  <#GAPDoc Label="ReducedSyzygiesGeneratorsOfRows">
##  <ManSection>
##    <Oper Arg="M" Name="ReducedSyzygiesGeneratorsOfRows" Label="for matrices"/>
##    <Returns>a &homalg; matrix</Returns>
##    <Description>
##      Like <C>SyzygiesGeneratorsOfRows</C>( <A>M</A> ) but where the matrix
##      <C>SyzygiesGeneratorsOfRows</C>( <C>ReducedSyzygiesGeneratorsOfRows</C>( <A>M</A> ) ) contains no units.
##      This can easily be achieved starting from <M>C:=</M><C>SyzygiesGeneratorsOfRows</C>( <A>M</A> )
##      (and using <Ref Oper="GetColumnIndependentUnitPositions" Label="for matrices"/> applied to the matrix of row syzygies of <M>C</M>,
##       etc.). (&see; Appendix <Ref Chap="Basic_Operations"/>)
##    </Description>
##  </ManSection>
##  <#/GAPDoc>
##
InstallMethod( ReducedSyzygiesGeneratorsOfRows,
        "for homalg matrices",
        [ IsHomalgMatrix ],
        
  function( M )
    local R, RP, t, MI, C, B, nz;
    
    if IsZero( M ) then
        ## redispatch to the specialized methods
        return ReducedSyzygiesGeneratorsOfRows( M );
    fi;
    
    ## this is an attribute
    
    R := HomalgRing( M );
    
    RP := homalgTable( R );
    
    t := homalgTotalRuntimes( );
    
    ColoredInfoForService( "busy", "ReducedSyzygiesGeneratorsOfRows", NumberRows( M ), " x ", NumberColumns( M ), " : ", RingName( R ) );
    
    if IsBound(R!.ComputeBasisBeforeSyzygies) and R!.ComputeBasisBeforeSyzygies = true then
        BasisOfRowModule( M );
    fi;
    
    if IsBound(RP!.ReducedSyzygiesGeneratorsOfRows) then
        
        C := RP!.ReducedSyzygiesGeneratorsOfRows( M );
        
        if IsZero( C ) then
            
            SetIsLeftRegular( M, true );
            
            C := HomalgZeroMatrix( 0, NumberRows( M ), R );
            
        else
            
            SetNumberColumns( C, NumberRows( M ) );
            
        fi;
        
        ## check assertion
        Assert( 6, R!.asserts.ReducedSyzygiesGeneratorsOfRows( M, C ) );
        
        ColoredInfoForService( t, "ReducedSyzygiesGeneratorsOfRows", NumberRows( C ) );
        
        IncreaseRingStatistics( R, "ReducedSyzygiesGeneratorsOfRows" );
        
        return C;
        
    elif IsBound(RP!.ReducedSyzygiesGeneratorsOfColumns) then
        
        MI := Involution( M );
        
        C := RP!.ReducedSyzygiesGeneratorsOfColumns( MI );
        
        SetReducedSyzygiesGeneratorsOfColumns( MI, C );
--> --------------------

--> maximum size reached

--> --------------------

[ zur Elbe Produktseite wechseln0.66Quellennavigators  Analyse erneut starten  ]