Bug #15
Adjoint of a non-invertible matrix
Description
Problem with
Fp5 := NewZZmod(5); adj(mat(Fp5, [[1,2],[3,1]]));
Related issues
History
#1
Updated by Anna Maria Bigatti over 12 years ago
Updated by - Category set to New Function
#2
Updated by Anna Maria Bigatti about 10 years ago
- Target version set to CoCoALib-0.99533 Easter14
#3
Updated by John Abbott about 10 years ago
Updated by - Target version changed from CoCoALib-0.99533 Easter14 to CoCoALib-1.0
#4
Updated by John Abbott about 9 years ago
- Status changed from New to In Progress
- Priority changed from Normal to High
I do not recall when, but adj has aleady been added to CoCoALib.
It has a VERY BAD SLUG: even after several minutes it has not yet computed adj of a 5x5 matrix whose entries are distinct indeterminates. The result should be a 5x5 matrix each of whose entries contain a polynomial of 24 terms (just the det of the "co-matrix").
Boosting priority because I need adj for some work I'm doing now.
#5
Updated by John Abbott about 9 years ago
adj is a very simple function: it chooses between AdjByDetOfMinors and AdjByInverse.
AdjByInverse should do?
- accept a matrix over a field, otherwise error
- accept a matrix over an integral domain (otherwise error), create field of fractions if necessary...
- accept any (square) matrix, do those it can, otherwise pass the matrix to
AdjByDetOfMinors?
Currently, the implementation is a combination of (2) and (3).
I have doubts about (3): if I say to compute via the inverse then it shouldn't switch to some other method if my explicit choice of method does not work in that case.
I even have some doubts about (2); perhaps it would better to have another fn called AdjByInverseOverFrF?
Comments? Opinions?
#6
Updated by John Abbott about 9 years ago
Even AdjByDetOfMinors takes too long for a 6x6 matrix of distinct indets. Why?
2015-03-26 NOTE I think the problem is probably very slow GCD (via G-bases) during arithmetic in a fraction field of a multivariate polynomial ring.
#7
Updated by John Abbott about 9 years ago
- % Done changed from 0 to 10
I am planning to implement a direct algorithm: each entry in the adj is just a determinant, and each determinant is just a sum of products of (n-1) matrix entries.
In the case of a matrix of indeterminates the direct approach should be fine (essentially it just "writes down" the answer) even though the complexity is not good
(probably N*factorial(N), but that is the size of the answer!).
#8
Updated by John Abbott almost 9 years ago
- % Done changed from 10 to 20
I have implemented a first version of AdjByDetOfMinors; it may already be obsolete because I have also implemented an improved version of det which calls DetDirect in the cases that interest me.
NEXT reimplement AdjByDetOfMinors to call explicitly det and let the latter choose the best way to compute the det of each submatrix.
#9
Updated by John Abbott almost 5 years ago
- Related to Bug #1280: Determinant & Inverse of matrix over non integral domain added
#10
Updated by John Abbott over 4 years ago
- Related to Bug #1331: adj: for matrices 7x7 and bigger added
#11
Updated by John Abbott over 3 years ago
- Description updated (diff)
- Assignee set to John Abbott
- Target version changed from CoCoALib-1.0 to CoCoALib-0.99800
- % Done changed from 20 to 100
- Estimated time set to 3.55 h
This now works (since when?).
Surely the impl for adj can be improved; there are several later issues about adj too (e.g. #1280 and #1331)
Closing this one (mostly because it is old... and also rather too vague).
PS I modified the original description because of some later syntax changes; the revised description is equivalent to the original one.
#12
Updated by John Abbott over 2 years ago
- Status changed from In Progress to Closed