Project

General

Profile

Feature #1197

IsZeroDet: new fn

Added by John Abbott almost 6 years ago. Updated 20 days ago.

Status:
In Progress
Priority:
Normal
Assignee:
Category:
New Function
Target version:
Start date:
26 Jun 2018
Due date:
% Done:

40%

Estimated time:
Spent time:

Description

Implement IsZeroDet which should allow a fast modular impl.


Related issues

Related to CoCoALib - Slug #1057: Slug: Polynomial ring contructor slow with (big) matrix orderingIn Progress2017-05-04

Related to CoCoALib - Bug #1641: gcd does not recognize univariate input Closed2021-12-20

History

#1 Updated by John Abbott almost 5 years ago

The idea is simple: compute the det modulo various primes, and if any is non-zero then we know the non-modular det is non-zero.

Probably this fn should accept a VerificationLevel parameter. It might even be nice if the "verification level" is interpreted as the log (base 2?) of the product of the moduluses tried -- this would make it more-or-less independent of the size of the primes we choose as the moduli.

The idea extends trivially to matrices over QQ (without having to clear denoms).

#2 Updated by John Abbott almost 5 years ago

  • Related to Slug #1057: Slug: Polynomial ring contructor slow with (big) matrix ordering added

#3 Updated by John Abbott almost 5 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-0.99700

#4 Updated by John Abbott about 4 years ago

  • Target version changed from CoCoALib-0.99700 to CoCoALib-0.99800

#5 Updated by John Abbott about 4 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

I have just made a very simplistic first impl: it simply computes the det, and checks whether it is zero. (also checked-in)

This first impl does not accept a VerificationLevel optional arg.

The fn is accessible from CoCoA-5; it may be useful for the school in Vietnam...

STILL TO DO: make a proper implementation & consider adding in a VerificationLevel parameter.

Special cases:
  • over finite field -- no short-cut comes to mind
  • over QQ or ZZ we can use "early termination" in a CRT approach; the existing code should be modified slightly
  • not sure what to do about small dimension mats over QQ or ZZ (currently the det is computed by special purpose code)
  • over a poly ring, we could make some random subst for the indets; if result has nz det then orig mat has nz det

#6 Updated by John Abbott over 3 years ago

  • Target version changed from CoCoALib-0.99800 to CoCoALib-0.99850

#7 Updated by John Abbott about 2 years ago

  • Related to Bug #1641: gcd does not recognize univariate input added

#8 Updated by John Abbott about 2 months ago

  • Assignee set to John Abbott
  • % Done changed from 10 to 40

There is some non-trivial code in MatrixOps-IsZeroDet.C developed from a project in Passau

With contributions from Mohanad Baraghith (Uni Passau)

#9 Updated by John Abbott 20 days ago

  • Target version changed from CoCoALib-0.99850 to CoCoALib-0.99880

Also available in: Atom PDF