#7580: bugs in infinite polynomial ring
------------------------------------------------------------------------------------------+
Reporter: was
| Owner: SimonKing
Type: defect
| Status: needs_review
Priority: major
| Milestone: sage-4.3.1
Component: algebra
| Keywords: infinite polynomial ring coercion
Work_issues: Doctests for 32 bit; work around bug in multipolynomial
conversion (#7654) | Author: Simon King
Upstream: N/A
| Reviewer:
Merged:
|
------------------------------------------------------------------------------------------+
Changes (by SimonKing):
* status: needs_work => needs_review
Comment:
I provided a new patch under the old namee
7580_fixes_and_extensions.patch. It is relative to sage-4.3.rc0, and it is
self-contained (i.e., the "follow-up" patch is not needed).
'''__Remarks__'''
1.
New compared to the previous patch (see description above): I am now using
a {{{WeakKeyDictionary}}} to cache whether there is a coercion map from
another ring. Reason: Otherwise, many finite polynomial ring might be
stored in a dictionary with ''strong'' references, and would thus be
prevented from garbage collection (compare #5970).
2.
Note that I slightly modified the code for the tab completion (compare
#6854): if p is an infinite polynomial, {{{p.__methods__}}} now returns
the methods (and only methods) of the underlying finite polynomial.
3.
I changed the 32 bit hash in the doc test as provided by William, but I
had problems to connect with Ubuntu32. So, I'd appreciate if a reviewer
could test it.
4.
I tried to make the code as robust against bugs in
{{{MPolynomialRing_libsingular}}} and {{{..._polydict}}} as possible. For
example, before calling for conversion into a libsingular-ring, I first
test if the number of variables coincides; if it does, there is no
guarantee that the conversion is name preserving. Then I test whether
there is a coercion; if there isn't then conversion is very likely to
''not'' work even when it should. In both situations, I construct a name-
preserving map explicitely, and use it for conversion. And should this
fail as well (it didn't happen, yet), then I fall back to string
evaluation.
In particular, the one doc test that was supposed to demonstrate wrong
usage (but had different results on 64 and 32 bit) could now be removed --
the formerly wrong usage is now OK.
Doc tests of all changed files pass for me. I guess that mip.pyx is now
fine (I didn't test), as it doesn't rely on infinite polynomial rings
anymore.
As a result of my random tests, I think it is now working consistently.
The random test was as follows:
* Create a dense and a sparse infinite polynomial ring with two
generators, over GF(3).
* Choose a random element with two up to four summands, degree at most
three, variable indices at most four, and consider the ideal generated by
it.
* Compute the symmetric Gröbner basis of that ideal, both in the sparse
and the dense approach; interrupt if this takes more than 10 minutes
(recall: even for principal ideals, symmetric Gröbner bases aren't easy).
* Apart from timeouts, there should be no error. And if both the dense
and the sparse approach had no timeout, the results should coincide.
With the new patch, the tests (about 50 runs) did not reveal a wrong
computation.
However, one problem exists:
'''__Known issue__'''
{{{
sage: X.<x,y> = InfinitePolynomialRing(GF(3), order='degrevlex')
sage: Y.<x,y> = InfinitePolynomialRing(GF(3), order='degrevlex',
implementation='sparse')
sage: while(1):
....: I = ['x_1*y_3^2 + y_2*y_1*y_0']*X
....: G = I.groebner_basis()
....: print get_memory_usage()
....:
827.81640625
832.32421875
836.91015625
841.03515625
845.70703125
849.81640625
854.5546875
858.4375
# hitting Ctrl-C at that point
sage: while(1):
....: I = ['x_1*y_3^2 + y_2*y_1*y_0']*Y
....: G = I.groebner_basis()
....: print get_memory_usage()
....:
878.2109375
882.1171875
886.08203125
889.93359375
893.91796875
897.76953125
901.84765625
905.58203125
}}}
So, there is a memory leak.
'''__Suggestion__'''
I think that my patch does provide a considerable progress. For example,
the old version raised an error on the above Gröbner basis computation
(so, I can't even tell whether the memory leak is new). And of course it
is nice to have general base rings.
So, would it be acceptable (unless a reviewer finds further issues) to
accept the patch as is, and to fix the memory leak later on a different
ticket?
Cheers,
Simon
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7580#comment:20>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
