Project

General

Profile

Feature #520

Compute inverse in quotient ring (i.e. division in algebraic extn)

Added by John Abbott about 10 years ago. Updated about 9 years ago.

Status:
Closed
Priority:
High
Assignee:
Anna Maria Bigatti
Category:
New Function
Target version:
CoCoALib-0.99536 June 2015
Start date:
04 Apr 2014
Due date:
% Done:

100%

Estimated time:
10.00 h
Spent time:
9.35 h

Description

Implement "division" in a quotient ring.

Related issues

Related to CoCoALib - Feature #627: Gaussian integer and rationals ZZi, QQiNew2014-09-22

Related to CoCoALib - Design #871: Redesign idealsNew2016-04-26

Related to CoCoALib - Feature #107: Recognizing finite fieldsClosed2012-03-19

History

#1 Updated by John Abbott about 10 years ago

A robust general solution is to use GenRepr:
inside R/I
invert element alpha
Check that 1 isin ideal(alpha)+I
if not, there's no inverse
if so, compute GenRepr(1, ideal(alpha, g1, ..., gn))
result is coeff corr to alpha (it's residue class in R/I, of course).

This approach will work even if R/I is not "zero-dimensional".
If R/I is an algebraic field extn, maybe linear algebra would be faster?

#2 Updated by John Abbott about 10 years ago

  • Category set to New Function
  • Estimated time set to 5.00 h

#3 Updated by John Abbott about 10 years ago

Anna suggests that elim may be quicker/simpler/better?

#4 Updated by John Abbott about 10 years ago

  • Target version changed from CoCoALib-0.99533 Easter14 to CoCoALib-0.99534 Seoul14

#5 Updated by John Abbott almost 10 years ago

  • Target version changed from CoCoALib-0.99534 Seoul14 to CoCoALib-1.0

#6 Updated by Anna Maria Bigatti about 9 years ago

  • Status changed from New to In Progress
  • Assignee set to Anna Maria Bigatti
  • Priority changed from Normal to High
  • % Done changed from 0 to 70

Implemented SparsePolyRingBase::IdealImpl::myDivMod for the 0-dimensional case.

/**/ Use R ::= QQ[i];
/**/ QQi := NewQuotientRing(R, ideal(i^2+1));
/**/ use QQi[x];
/**/ 1/i;
(-i)

in principle it works.
In practice it needs optimizing and polishing because ideal(this) does not compile (so I used a horrible ideal(myGensValue)) and MultiplicationMatrix might be made more efficient.

#7 Updated by Anna Maria Bigatti about 9 years ago

  • % Done changed from 70 to 90
  • Estimated time changed from 5.00 h to 10.00 h

Polishing up all the code is always long and tedious....
Anyway!
The code is there and it works.
I still have problems with the case

/**/ R ::= QQ[i,r];
/**/ K := NewQuotientRing(R, ideal(ReadExpr(R, "i^2+1"),ReadExpr(R, "r^2-1")));
/**/ Use K[x];
/**/ x/i;

Slugs:
- when calling num/den there is a call to IsZeroDivisor(den). That's a correct thing to do, but maybe it could be done more efficiently? (for example: try to compute the answer first...)
- when IsZeroDivisor is called and should return false then its ring is not integral! In the case of a QuotientRing one could call myDefiningIdeal->SetPrimeFlag(false)... but how?

#8 Updated by Anna Maria Bigatti about 9 years ago

Also x/i is working now.
(will cvs it this afternoon)

#9 Updated by Anna Maria Bigatti about 9 years ago

Anna Maria Bigatti wrote:

- when IsZeroDivisor is called and should return false then its ring is not integral! In the case of a QuotientRing one could call myDefiningIdeal->SetPrimeFlag(false)... but how?

done: this forced to have the member function myIsZeroDivisor which, for a QuotienRing R/I, may set I's primality flag to false.

#10 Updated by John Abbott about 9 years ago

  • Target version changed from CoCoALib-1.0 to CoCoALib-0.99536 June 2015

#11 Updated by John Abbott about 9 years ago

  • Status changed from In Progress to Closed
  • % Done changed from 90 to 100

No problems arisen in the last month (perhaps not much real testing either?)
Anyway, closing.

#12 Updated by John Abbott about 8 years ago

#13 Updated by Anna Maria Bigatti about 8 years ago

Also available in: Atom PDF