fglm.cc File Reference

#include "kernel/mod2.h"
#include "misc/options.h"
#include "polys/monomials/ring.h"
#include "polys/monomials/maps.h"
#include "kernel/polys.h"
#include "kernel/ideals.h"
#include "kernel/GBEngine/kstd1.h"
#include "kernel/fglm/fglm.h"
#include "Singular/fglm.h"
#include "Singular/ipid.h"
#include "Singular/ipshell.h"
#include "Singular/tok.h"

Go to the source code of this file.

Enumerations
enum	FglmState {   FglmOk , FglmHasOne , FglmNoIdeal , FglmNotReduced ,   FglmNotZeroDim , FglmIncompatibleRings , FglmPolyIsOne , FglmPolyIsZero }

Functions
ideal	fglmUpdatesource (const ideal sourceIdeal)
void	fglmUpdateresult (ideal &result)
FglmState	fglmConsistency (ring sring, ring dring, int *vperm)
FglmState	fglmIdealcheck (const ideal theIdeal)
BOOLEAN	fglmProc (leftv result, leftv first, leftv second)
ideal	fglmQuot (ideal first, poly second)
BOOLEAN	fglmQuotProc (leftv result, leftv first, leftv second)
ideal	findUni (ideal first)
BOOLEAN	findUniProc (leftv result, leftv first)

Enumeration Type Documentation

FglmState

enum FglmState

Enumerator
FglmOk
FglmHasOne
FglmNoIdeal
FglmNotReduced
FglmNotZeroDim
FglmIncompatibleRings
FglmPolyIsOne
FglmPolyIsZero

Definition at line 39 of file fglm.cc.

              {
    FglmOk,
    FglmHasOne,
    FglmNoIdeal,
    FglmNotReduced,
    FglmNotZeroDim,
    FglmIncompatibleRings,
    // for fglmquot:
    FglmPolyIsOne,
    FglmPolyIsZero
};

Function Documentation

fglmConsistency()

FglmState fglmConsistency	(	ring	sring,
		ring	dring,
		int *	vperm
	)

Definition at line 121 of file fglm.cc.

{
    int k;
    FglmState state= FglmOk;
 
    if ( sring->cf != dring->cf )
    {
        WerrorS( "rings must have same characteristic" );
        state= FglmIncompatibleRings;
    }
    if ( (sring->OrdSgn != 1) || (dring->OrdSgn != 1) )
    {
        WerrorS( "only works for global orderings" );
        state= FglmIncompatibleRings;
    }
    if ( sring->N != dring->N )
    {
        WerrorS( "rings must have same number of variables" );
        state= FglmIncompatibleRings;
    }
    if ( rPar(sring) != rPar(dring) )
    {
        WerrorS( "rings must have same number of parameters" );
        state= FglmIncompatibleRings;
    }
    if ( state != FglmOk ) return state;
    // now the rings have the same number of variables resp. parameters.
    // check if the names of the variables resp. parameters do agree:
    int nvar = sring->N;
    int npar = rPar(sring);
    int * pperm;
    if ( npar > 0 )
        pperm= (int *)omAlloc0( (npar+1)*sizeof( int ) );
    else
        pperm= NULL;
    maFindPerm( sring->names, nvar, rParameter(sring), npar,
                dring->names, nvar, rParameter(dring), npar, vperm, pperm,
                dring->cf->type);
    for ( k= nvar; (k > 0) && (state == FglmOk); k-- )
        if ( vperm[k] <= 0 )
        {
            WerrorS( "variable names do not agree" );
            state= FglmIncompatibleRings;
        }
    for ( k= npar-1; (k >= 0) && (state == FglmOk); k-- )
        if ( pperm[k] >= 0 )
        {
            WerrorS( "parameter names do not agree" );
            state= FglmIncompatibleRings;
        }
    if (pperm != NULL) // OB: ????
      omFreeSize( (ADDRESS)pperm, (npar+1)*sizeof( int ) );
    if ( state != FglmOk ) return state;
    // check if both rings are qrings or not
    if ( sring->qideal != NULL )
    {
        if ( dring->qideal == NULL )
        {
            WerrorS( "source ring is a qring, destination ring not" );
            return FglmIncompatibleRings;
        }
        // both rings are qrings, now check if both quotients define the same ideal.
        // check if sring->qideal is contained in dring->qideal:
        rChangeCurrRing( dring );
        nMapFunc nMap=n_SetMap(dring->cf, sring->cf );
        ideal sqind = idInit( IDELEMS( sring->qideal ), 1 );
        for ( k= IDELEMS( sring->qideal )-1; k >= 0; k-- )
          (sqind->m)[k]= p_PermPoly( (sring->qideal->m)[k], vperm, sring,
                          dring, nMap);
        ideal sqindred = kNF( dring->qideal, NULL, sqind );
        if ( ! idIs0( sqindred ) )
        {
            WerrorS( "the quotients do not agree" );
            state= FglmIncompatibleRings;
        }
        idDelete( & sqind );
        idDelete( & sqindred );
        rChangeCurrRing( sring );
        if ( state != FglmOk ) return state;
        // check if dring->qideal is contained in sring->qideal:
        int * dsvperm = (int *)omAlloc0( (nvar+1)*sizeof( int ) );
        maFindPerm( dring->names, nvar, NULL, 0, sring->names, nvar, NULL, 0,
                    dsvperm, NULL, sring->cf->type);
        nMap=n_SetMap(currRing->cf, dring->cf);
        ideal dqins = idInit( IDELEMS( dring->qideal ), 1 );
        for ( k= IDELEMS( dring->qideal )-1; k >= 0; k-- )
          (dqins->m)[k]=p_PermPoly( (dring->qideal->m)[k], dsvperm, sring,
                         currRing, nMap);
        ideal dqinsred = kNF( sring->qideal, NULL, dqins );
        if ( ! idIs0( dqinsred ) )
        {
            WerrorS( "the quotients do not agree" );
            state= FglmIncompatibleRings;
        }
        idDelete( & dqins );
        idDelete( & dqinsred );
        omFreeSize( (ADDRESS)dsvperm, (nvar+1)*sizeof( int ) );
        if ( state != FglmOk ) return state;
    }
    else
    {
        if ( dring->qideal != NULL )
        {
            WerrorS( "source ring is a qring, destination ring not" );
            return FglmIncompatibleRings;
        }
    }
    return FglmOk;
}

fglmIdealcheck()

FglmState fglmIdealcheck

(

const ideal

theIdeal

)

Definition at line 240 of file fglm.cc.

{
    FglmState state = FglmOk;
    int power;
    int k;
    BOOLEAN * purePowers = (BOOLEAN *)omAlloc0( currRing->N*sizeof( BOOLEAN ) );
 
    for ( k= IDELEMS( theIdeal ) - 1; (state == FglmOk) && (k >= 0); k-- )
    {
        poly p = (theIdeal->m)[k];
        if (p!=NULL)
        {
          if( pIsConstant( p ) ) state= FglmHasOne;
          else if ( (power= pIsPurePower( p )) > 0 )
          {
            fglmASSERT( 0 < power && power <= currRing->N, "illegal power" );
            if ( purePowers[power-1] == TRUE  ) state= FglmNotReduced;
            else purePowers[power-1]= TRUE;
          }
          for ( int l = IDELEMS( theIdeal ) - 1; state == FglmOk && l >= 0; l-- )
            if ( (k != l) && pDivisibleBy( p, (theIdeal->m)[l] ) )
                state= FglmNotReduced;
        }
    }
    if ( state == FglmOk )
    {
        for ( k= currRing->N-1 ; (state == FglmOk) && (k >= 0); k-- )
            if ( purePowers[k] == FALSE ) state= FglmNotZeroDim;
    }
    omFreeSize( (ADDRESS)purePowers, currRing->N*sizeof( BOOLEAN ) );
    return state;
}

fglmProc()

BOOLEAN fglmProc	(	leftv	result,
		leftv	first,
		leftv	second
	)

Definition at line 277 of file fglm.cc.

{
    FglmState state = FglmOk;
 
    ring destRing = currRing;
    // ring destRing = currRing;
    ideal destIdeal = NULL;
    ring sourceRing = (ring)first->Data();
    rChangeCurrRing( sourceRing );
    // ring sourceRing = currRing;
 
    int * vperm = (int *)omAlloc0( (sourceRing->N+1)*sizeof( int ) );
    state= fglmConsistency( sourceRing, destRing, vperm );
    omFreeSize( (ADDRESS)vperm, (sourceRing->N+1)*sizeof(int) );
 
    if ( state == FglmOk )
    {
        idhdl ih = sourceRing->idroot->get( second->Name(), myynest );
        if ( (ih != NULL) && (IDTYP(ih)==IDEAL_CMD) )
        {
            ideal sourceIdeal;
            if ( sourceRing->qideal != NULL )
                sourceIdeal= fglmUpdatesource( IDIDEAL( ih ) );
            else
                sourceIdeal = IDIDEAL( ih );
            state= fglmIdealcheck( sourceIdeal );
            if ( state == FglmOk )
            {
                // Now the settings are compatible with FGLM
                assumeStdFlag( (leftv)ih );
                if ( fglmzero( sourceRing, sourceIdeal, destRing, destIdeal, FALSE, (currRing->qideal != NULL) ) == FALSE )
                    state= FglmNotReduced;
            }
        } else state= FglmNoIdeal;
    }
    if ( currRing != destRing )
        rChangeCurrRing( destRing );
    switch (state)
    {
        case FglmOk:
            if ( currRing->qideal != NULL ) fglmUpdateresult( destIdeal );
            break;
        case FglmHasOne:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        case FglmIncompatibleRings:
            WerrorS( "source ring and current ring are incompatible" );
            destIdeal= NULL;
            break;
        case FglmNoIdeal:
            Werror( "Can't find ideal %s in source ring", second->Name() );
            destIdeal= NULL;
            break;
        case FglmNotZeroDim:
            Werror( "The ideal %s has to be 0-dimensional", second->Name() );
            destIdeal= NULL;
            break;
        case FglmNotReduced:
            Werror( "The ideal %s has to be given by a reduced SB", second->Name() );
            destIdeal= NULL;
            break;
        default:
            destIdeal= idInit(1,1);
    }
 
    result->rtyp = IDEAL_CMD;
    result->data= (void *)destIdeal;
    setFlag( result, FLAG_STD );
    return (state != FglmOk);
}

fglmQuot()

ideal fglmQuot	(	ideal	first,
		poly	second
	)

Definition at line 350 of file fglm.cc.

{
    FglmState state = FglmOk;
 
    ideal sourceIdeal = first;
    poly quot = second;
    ideal destIdeal = NULL;
 
    state = fglmIdealcheck( sourceIdeal );
    if ( state == FglmOk )
    {
      if ( quot == NULL ) state= FglmPolyIsZero;
      else if ( pIsConstant( quot ) ) state= FglmPolyIsOne;
    }
 
    if ( state == FglmOk )
    {
      if ( fglmquot( sourceIdeal, quot, destIdeal ) == FALSE )
        state= FglmNotReduced;
    }
 
    switch (state)
    {
        case FglmOk:
            break;
        case FglmHasOne:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        case FglmNotZeroDim:
            WerrorS( "The ideal has to be 0-dimensional" );
            destIdeal= idInit(1,1);
            break;
        case FglmNotReduced:
            WerrorS( "The poly has to be reduced" );
            destIdeal= idInit(1,1);
            break;
        case FglmPolyIsOne:
            int k;
            destIdeal= idInit( IDELEMS(sourceIdeal), 1 );
            for ( k= IDELEMS( sourceIdeal )-1; k >=0; k-- )
              (destIdeal->m)[k]= pCopy( (sourceIdeal->m)[k] );
            state= FglmOk;
            break;
        case FglmPolyIsZero:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        default:
            destIdeal= idInit(1,1);
    }
 
    return destIdeal;
}

fglmQuotProc()

BOOLEAN fglmQuotProc	(	leftv	result,
		leftv	first,
		leftv	second
	)

Definition at line 411 of file fglm.cc.

{
    FglmState state = FglmOk;
 
    //    STICKYPROT("quotstart\n");
    ideal sourceIdeal = (ideal)first->Data();
    poly quot = (poly)second->Data();
    ideal destIdeal = NULL;
 
    state = fglmIdealcheck( sourceIdeal );
    if ( state == FglmOk )
    {
      if ( quot == NULL ) state= FglmPolyIsZero;
      else if ( pIsConstant( quot ) ) state= FglmPolyIsOne;
    }
 
    if ( state == FglmOk )
    {
      assumeStdFlag( first );
      if ( fglmquot( sourceIdeal, quot, destIdeal ) == FALSE )
        state= FglmNotReduced;
    }
 
    switch (state)
    {
        case FglmOk:
            break;
        case FglmHasOne:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        case FglmNotZeroDim:
            Werror( "The ideal %s has to be 0-dimensional", first->Name() );
            destIdeal= NULL;
            break;
        case FglmNotReduced:
            Werror( "The poly %s has to be reduced", second->Name() );
            destIdeal= NULL;
            break;
        case FglmPolyIsOne:
            int k;
            destIdeal= idInit( IDELEMS(sourceIdeal), 1 );
            for ( k= IDELEMS( sourceIdeal )-1; k >=0; k-- )
              (destIdeal->m)[k]= pCopy( (sourceIdeal->m)[k] );
            state= FglmOk;
            break;
        case FglmPolyIsZero:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        default:
            destIdeal= idInit(1,1);
    }
 
    result->rtyp = IDEAL_CMD;
    result->data= (void *)destIdeal;
    setFlag( result, FLAG_STD );
    // STICKYPROT("quotend\n");
    return (state != FglmOk);
} // fglmQuotProt

fglmUpdateresult()

void fglmUpdateresult

(

ideal &

result

)

Definition at line 89 of file fglm.cc.

{
    int k, l;
    BOOLEAN found;
    for ( k= IDELEMS( result )-1; k >=0; k-- )
    {
        if ( (result->m)[k] != NULL )
        {
            found= FALSE;
            for ( l= IDELEMS( currRing->qideal )-1; (l >= 0) && ( found == FALSE ); l-- )
                if ( pDivisibleBy( (currRing->qideal->m)[l], (result->m)[k] ) )
                    found= TRUE;
            if ( found ) pDelete( & ((result->m)[k]) );
        }
    }
    idSkipZeroes( result );
}

fglmUpdatesource()

ideal fglmUpdatesource

(

const ideal

sourceIdeal

)

Definition at line 57 of file fglm.cc.

{
    int k, l, offset;
    BOOLEAN found;
    ideal newSource= idInit( IDELEMS( sourceIdeal ) + IDELEMS( currRing->qideal ), 1 );
    for ( k= IDELEMS( sourceIdeal )-1; k >=0; k-- )
        (newSource->m)[k]= pCopy( (sourceIdeal->m)[k] );
    offset= IDELEMS( sourceIdeal );
    for ( l= IDELEMS( currRing->qideal )-1; l >= 0; l-- )
    {
        if ( (currRing->qideal->m)[l] != NULL )
        {
            found= FALSE;
            for ( k= IDELEMS( sourceIdeal )-1; (k >= 0) && (found == FALSE); k-- )
                if ( pDivisibleBy( (sourceIdeal->m)[k], (currRing->qideal->m)[l] ) )
                    found= TRUE;
            if ( ! found )
            {
                (newSource->m)[offset]= pCopy( (currRing->qideal->m)[l] );
                offset++;
            }
        }
    }
    idSkipZeroes( newSource );
    return newSource;
}

findUni()

ideal findUni

(

ideal

first

)

Definition at line 474 of file fglm.cc.

{
    ideal sourceIdeal;
    ideal destIdeal = NULL;
    FglmState state;
 
    sourceIdeal = first;
 
    state= fglmIdealcheck( sourceIdeal );
    if ( state == FglmOk )
    {
      // check for special cases: if the input contains
      // univariate polys, try to reduce the problem
      int i,k;
      int count=0;
      BOOLEAN * purePowers = (BOOLEAN *)omAlloc0( currRing->N*sizeof( BOOLEAN ) );
      for ( k= IDELEMS( sourceIdeal ) - 1; k >= 0; k-- )
      {
        if((i=pIsUnivariate(sourceIdeal->m[k]))>0)
        {
          if (purePowers[i-1]==0)
          {
            purePowers[i-1]=k;
            count++;
            if (count==currRing->N) break;
          }
        }
      }
      if (count==currRing->N)
      {
        destIdeal=idInit(currRing->N,1);
        for(k=currRing->N-1; k>=0; k--) destIdeal->m[k]=pCopy(sourceIdeal->m[purePowers[k]]);
      }
      omFreeSize((ADDRESS)purePowers, currRing->N*sizeof( BOOLEAN ) );
      if (destIdeal!=NULL)
            state = FglmOk;
      else if ( FindUnivariateWrapper( sourceIdeal, destIdeal ) == FALSE )
            state = FglmNotReduced;
    }
    switch (state)
    {
        case FglmOk:
            break;
        case FglmHasOne:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        case FglmNotZeroDim:
            WerrorS( "The ideal has to be 0-dimensional" );
            destIdeal= idInit(1,1);
            break;
        case FglmNotReduced:
            Werror( "The ideal has to be reduced" );
            destIdeal= idInit(1,1);
            break;
        default:
            destIdeal= idInit(1,1);
    }
 
    return destIdeal;
}

findUniProc()

BOOLEAN findUniProc	(	leftv	result,
		leftv	first
	)

Definition at line 541 of file fglm.cc.

{
    ideal sourceIdeal;
    ideal destIdeal = NULL;
    FglmState state;
 
    sourceIdeal = (ideal)first->Data();
 
    assumeStdFlag( first );
    state= fglmIdealcheck( sourceIdeal );
    if ( state == FglmOk )
    {
      // check for special cases: if the input contains
      // univariate polys, try to reduce the problem
      int i,k;
      int count=0;
      BOOLEAN * purePowers = (BOOLEAN *)omAlloc0( currRing->N*sizeof( BOOLEAN ) );
      for ( k= IDELEMS( sourceIdeal ) - 1; k >= 0; k-- )
      {
        if((i=pIsUnivariate(sourceIdeal->m[k]))>0)
        {
          if (purePowers[i-1]==0)
          {
            purePowers[i-1]=k;
            count++;
            if (count==currRing->N) break;
          }
        }
      }
      if (count==currRing->N)
      {
        destIdeal=idInit(currRing->N,1);
        for(k=currRing->N-1; k>=0; k--) destIdeal->m[k]=pCopy(sourceIdeal->m[purePowers[k]]);
      }
      omFreeSize((ADDRESS)purePowers, currRing->N*sizeof( BOOLEAN ) );
      if (destIdeal!=NULL)
            state = FglmOk;
      else if ( FindUnivariateWrapper( sourceIdeal, destIdeal ) == FALSE )
            state = FglmNotReduced;
    }
    switch (state)
    {
        case FglmOk:
            break;
        case FglmHasOne:
            destIdeal= idInit(1,1);
            (destIdeal->m)[0]= pOne();
            state= FglmOk;
            break;
        case FglmNotZeroDim:
            Werror( "The ideal %s has to be 0-dimensional", first->Name() );
            destIdeal= NULL;
            break;
        case FglmNotReduced:
            Werror( "The ideal %s has to be reduced", first->Name() );
            destIdeal= NULL;
            break;
        default:
            destIdeal= idInit(1,1);
    }
 
    result->rtyp = IDEAL_CMD;
    result->data= (void *)destIdeal;
 
    return FALSE;
}