Re: [sage-devel] modulo is broken in some (fairly simple) rings

[Charles Bouillaguet]

Dear all,

I would like to make a case for the quo_rem() method to actually implement 
euclidean division when it makes sense, or to raise an exception when the 
result is not defined. After all, this is what it is **supposed** to do, at 
least according to the docstring in sage/ring/polynomial/polynomial_element.pyx 
: 

"""
@coerce_binop
def quo_rem(self, other):
"""
Returns the quotient and remainder of the Euclidean division of
``self`` and ``other``.

Raises ZerodivisionError if ``other`` is zero. Raises ArithmeticError 
if ``other`` has
a nonunit leading coefficient.
"""

I personally think that this specification is correct and decent. 

Presently, depending on the domain, quo_rem does not always behave the same, 
and not according to the same specification. Examples : 

In ZZ[X] or ZZ[X,Y] : 
---

sage: R. = ZZ[]
sage: (X^100).quo_rem(2*X+1)
(0, X^100)

---> Result is not defined, but quo_rem() does not complain. It tries to reduce 
"as much as possible".

in QQ[x][y] :


sage: P. = QQ[]
sage: R. = P[]
sage: f = R.random_element(10)
sage: g = y^5+R.random_element(5)
sage: q,r = f.quo_rem(g)
sage: f == q*g + r
True
sage: g = x*y^5
sage: f.quo_rem(g)
Traceback (most recent call last):
...
ArithmeticError: Nonunit leading coefficient

---> quo_rem() complains when result is not defined.

So, I suggest that : 
a) we stick to the spec (what happens in QQ[x][y]).
b) we fix the cases like ZZ[X] that do not stick to the spec
c) we make sure, eventually by adding a "reduce" method or something like that, 
that the previous behavior is still available somehow.

I am willing to implement these changes. Do we agree on this?

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] modulo is broken in some (fairly simple) rings

[Charles Bouillaguet]

Anyway, this is now :

http://trac.sagemath.org/ticket/16276

waiting for a ---very simple--- review. (All test pass for me)
---
Charles

On 30 Apr 2014, at 11:36, John Cremona  wrote:

> On 30 April 2014 10:13, Jean-Pierre Flori  wrote:
>> 
>> 
>> On Wednesday, April 30, 2014 11:04:06 AM UTC+2, John Cremona wrote:
>>> 
>>> On 30 April 2014 09:35, Jean-Pierre Flori  wrote:
>>>> 
>>>> 
>>>> On Wednesday, April 30, 2014 8:28:24 AM UTC+2, Charles Bouillaguet
>>>> wrote:
>>>>> 
>>>>> Hi all,
>>>>> 
>>>>> I just noticed that we carefully check that Sage computes something
>>>>> completely wrong. From sage/structure/element.pyx, line 2052 :
>>>>> 
>>>>> --
>>>>>  When little is implemented about a given ring, then mod may
>>>>>return simply return `f`.  For example, reduction is not
>>>>>implemented for `\ZZ[x]` yet. (TODO!)
>>>>> 
>>>>>sage: R. = PolynomialRing(ZZ)
>>>>>sage: f = x^3 + x + 1
>>>>>sage: f.mod(x + 1)
>>>>>x^3 + x + 1
>>>>> --
>>>>> 
>>>>> The problem is that mod() does the following :
>>>>> 
>>>>> from sage.rings.ideal import is_Ideal
>>>>>if not is_Ideal(I) or not I.ring() is self._parent:
>>>>>I = self._parent.ideal(I)
>>>>>#raise TypeError, "I = %s must be an ideal in %s"%(I,
>>>>> self.parent())
>>>>>return I.reduce(self)
>>>>> 
>>>>> So, mod relies on Ideal.reduce, which by default does nothing and
>>>>> returns
>>>>> its argument. As such, mod is badly broken.
>>>>> 
>>>>> What seems reasonable is to make Ideal.reduce() raise a
>>>>> NotImplementedError by default instead of doing nothing, by this breaks
>>>>> a
>>>>> lot of other stuff (because Ideal.reduce() is called a lot).
>>>>> 
>>>>> What do you think is right ?
>>>>> 
>>>>> *) Go with NotImplementedError and fix 30+ doctests?
>>>>> *) create a StopGap that warn the user that mod may be complete
>>>>> rubbish?
>>>>> 
>>>>> Cheers,
>>>>> ---
>>>>> Charles Bouillaguet
>>>>> http://www.lifl.fr/~bouillaguet/
>>>>> 
>>>> Wouldn't modify the mod method for polynomial rings over ZZ be enough?
>>>> 
>>>> In a similar way, the pow (python?) function accepts an optional
>>>> "modulus"
>>>> third args, but Sage just ignores it over a bunch of rings.
>>>> For example, over QQ, pow(x,100,x+1) yields x^100.
>>>> For non euclidean rings that might be a sensible default choice but for
>>>> euclidean rings or even just univariate polynomial rings over fields we
>>>> might want to modify that (maybe something for the category framework as
>>>> Luca De Feo suggested).
>>> 
>>> Of course ZZ[X] is not Euclidean and it is not clear (to me) what a
>>> good definition of reduction modulo (say) 2*X+1 should be.  But
>>> reduction modulo a monic polynomial is easy, and that special case
>>> would be worth having even if one did nothing in the general case.
>>> 
>>> Quiz question:  what do YOU think that the reduction of X^100 modulo
>>> 2X+1 should be?
>>> 
>> Good question...
>> We had a look around last week to gather info about what other libs do and
>> IIRC, at least for flint, what happens is that start at top degree monomial
>> you substract the largest multiple of the modulus so that the leading
>> coefficient is positive (did not look at negative leading coeffs...).
>> In fact, that's also what Sage does when you do (x^100) % (x^2+1) (which
>> does not call the same function as pow(x,100,x^2+1)).
>> 
>> Anyway in my case, where I wanted fast modular exponentiation, so reducing
>> at each step was necessary to keep degrees low, such a case does not make
>> sense as with such a definition the resulting polynomial has high degree
>> anyway (and I don't really care about such a case...).
> 
> Sure.  I think the underlying mathematical issue is that Z[X]/(2*X+1)
> is not finitely-generated as an abelian group, (equivalently, -1/2

[sage-devel] Re: modulo is broken in some (fairly simple) rings [update]

[Charles Bouillaguet]

On 30 Apr 2014, at 08:28, Charles Bouillaguet  
wrote:

> Hi all,
> 
> I just noticed that we carefully check that Sage computes something 
> completely wrong. From sage/structure/element.pyx, line 2052 : 
> 
> --
>  When little is implemented about a given ring, then mod may
>return simply return `f`.  For example, reduction is not
>implemented for `\ZZ[x]` yet. (TODO!)
> 
>sage: R. = PolynomialRing(ZZ)
>sage: f = x^3 + x + 1
>sage: f.mod(x + 1)
>x^3 + x + 1
> --

Well, the good thing is that 

sage: f % (x+1)
-1

DOES work... (but still, f advertises a broken "mod" method).
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

[sage-devel] modulo is broken in some (fairly simple) rings

[Charles Bouillaguet]

Hi all,

I just noticed that we carefully check that Sage computes something completely 
wrong. From sage/structure/element.pyx, line 2052 : 

--
  When little is implemented about a given ring, then mod may
return simply return `f`.  For example, reduction is not
implemented for `\ZZ[x]` yet. (TODO!)

sage: R. = PolynomialRing(ZZ)
sage: f = x^3 + x + 1
sage: f.mod(x + 1)
x^3 + x + 1
--

The problem is that mod() does the following : 

 from sage.rings.ideal import is_Ideal
if not is_Ideal(I) or not I.ring() is self._parent:
I = self._parent.ideal(I)
#raise TypeError, "I = %s must be an ideal in %s"%(I, self.parent())
return I.reduce(self)

So, mod relies on Ideal.reduce, which by default does nothing and returns its 
argument. As such, mod is badly broken.

What seems reasonable is to make Ideal.reduce() raise a NotImplementedError by 
default instead of doing nothing, by this breaks a lot of other stuff (because 
Ideal.reduce() is called a lot).

What do you think is right ?

*) Go with NotImplementedError and fix 30+ doctests?
*) create a StopGap that warn the user that mod may be complete rubbish?

Cheers,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Polynomials over non-commutative rings

[Charles Bouillaguet]

On 23 Dec 2013, at 10:27, Marc Mezzarobba  wrote:

> Vincent Delecroix wrote:
>> Does polynomial over non-commutative ring make sense ? Because in that
>> context axbx is not abx^2. Depending on what you call polynomial, they
>> may or may not form a ring.

The polynomials over matrices with scalar coefficients are probably an instance 
of what Marc means...

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-devel] Re: reviewing git patch

[charles Bouillaguet]

Le mercredi 2 octobre 2013, Volker Braun  a écrit :
> On Wednesday, October 2, 2013 4:57:53 PM UTC+1, Volker Braun wrote:
>>
>> 2) make sure that the ticket version actually works. Since it is an spkg
you'll have to copy the tarball manually into the upstream/ directory for
testing.
>
> Just realized that its an old-style spkg, so you just need to "sage -f
" it as usual

What should I do to make it "new-style"? And is it desirable?

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] LELA for matrices?

[Charles Bouillaguet]

On Jun 2, 2013, at 9:20 AM, Dima Pasechnik wrote:

> On 2013-06-01, Volker Braun  wrote:
> [...]
>> 
>> On a related note, sparse matrices in Sage suck (dictionary of keys). 
>> Sparse matrices in LELA only suck slightly less (list of lists). For fast 
>> computation one should implement compressed sparse row/column, I think.
> 
> IMHO one needs to create a framework where one can choose a backend for
> sparse matrices, rather than aim for a complete from scratch
> implementation. 

I don't know what kind of interface do these package exhibit to 
access/modify/compute with a sparse matrix (eg. Linbox VS numerical-stuff)

There is a presumably standard sparse-blas  API : 

http://math.nist.gov/spblas/


> E.g.  there is a kind of standard, in numerics world, implementation of sparse
> matrices, which comes with a lot of extra goodies (including such
> important things like sparse Cholesky factorization, etc):
> http://www.cise.ufl.edu/research/sparse/SuiteSparse/
> A part of it, complete with a Python interface, is already in Sage, 
> in CVXOPT.

And part of this is accessible already through SciPy (for floating-point 
matrices) :

http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html#module-scipy.sparse.linalg
http://docs.scipy.org/doc/scipy/reference/sparse.linalg.html

---
Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] LELA for matrices?

[Charles Bouillaguet]

My understanding is that only a very small subset of linbox is wired into Sage. 
In particular, all the iterative methods for the [rank/minpoly/charpoly/det] of 
sparse matrices are not accessible yet, but they are Linbox's strong point. 
Currently, sparse matrices are converted to dense ones, and very generic cython 
code is then used.

Recent versions of linbox have some support for (read-only) compressed row 
matrices.

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



On Jun 1, 2013, at 6:48 PM, Martin Albrecht wrote:

> Hi,
> 
> as far as I know LELA does not support the same operations as LinBox, it's 
> not 
> a straight-forward fork but a re-implementation of a subset (that's my 
> understanding, anyway). it has some advantages, i.e., that some bits nicely 
> generic, i.e., it should be fairly easy to add new matrix types by adding 
> stuff like matrix-matrix multiplication and e.g. PLE decomposition is handled 
> generically.
> 
> Also, the main developer of LELA Bradford has left academia. He usually 
> responds fairly quickly to e-mail and is up for helping out, but as far as I 
> know nobody is actively developing LELA at the moment (I might be terribly 
> wrong here!)
> 
> On Saturday 01 Jun 2013, Volker Braun wrote:
>> I would like to have some discussion about the roadmap for matrices in
>> Sage. It seems that linbox has essentially been forked by LELA
>> (http://www.singular.uni-kl.de/lela). Since it optionally contains M4RI,
>> one would think that it is a good fit for Sage, too. Has anybody given any
>> thoughts to switching Sage from linbox to LELA? In particular, Burcin and
>> Martin should have an opinion and it would be nice to hear from them ;-)
>> 
>> On a related note, sparse matrices in Sage suck (dictionary of keys).
>> Sparse matrices in LELA only suck slightly less (list of lists). For fast
>> computation one should implement compressed sparse row/column, I think.
> 
> Cheers,
> Martin
> 
> --
> name: Martin Albrecht
> _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x6532AFB4
> _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
> _www: http://martinralbrecht.wordpress.com/
> _jab: martinralbre...@jabber.ccc.de

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] GIT + release management

[Charles Bouillaguet]

On Mar 31, 2013, at 11:49 AM, Martin Albrecht wrote:

> Indeed +1

Completely +1

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] test failures for 5.9.beta0

[Charles Bouillaguet]

Hi,

I tried to start a patchbot for 5.9beta0, and I got the following failure :

plugins.docbuild -- 11 seconds
== end plugins.docbuild ==
$SAGE_ROOT/sage -tp 3 -sagenb $SAGE_ROOT/devel/sage-0/doc/common 
$SAGE_ROOT/devel/sage-0/doc/en $SAGE_ROOT/devel/sage-0/doc/fr 
$SAGE_ROOT/devel/sage-0/sage

Usage: sage -t [options] filenames

sage-runtests: error: no such option: -s
Traceback (most recent call last):
  File "/scratch/sage-5.9.beta0/local/bin/patchbot/patchbot.py", line 
443, in test_a_ticket

do_or_die("$SAGE_ROOT/sage %s %s" % (test_cmd, ' '.join(test_dirs)))
  File "/scratch/sage-5.9.beta0/local/bin/patchbot/util.py", line 66, 
in do_or_die

raise Exception, "%s %s" % (res, cmd)
Exception: 512 $SAGE_ROOT/sage -tp 3 -sagenb 
$SAGE_ROOT/devel/sage-0/doc/common $SAGE_ROOT/devel/sage-0/doc/en 
$SAGE_ROOT/devel/sage-0/doc/fr $SAGE_ROOT/devel/sage-0/sage

2013-03-21 12:20:12 +0100
86 seconds
Traceback (most recent call last):
  File "/scratch/sage-5.9.beta0/local/bin/patchbot/patchbot.py", line 
443, in test_a_ticket

do_or_die("$SAGE_ROOT/sage %s %s" % (test_cmd, ' '.join(test_dirs)))
  File "/scratch/sage-5.9.beta0/local/bin/patchbot/util.py", line 66, 
in do_or_die

raise Exception, "%s %s" % (res, cmd)
Exception: 512 $SAGE_ROOT/sage -tp 3 -sagenb 
$SAGE_ROOT/devel/sage-0/doc/common $SAGE_ROOT/devel/sage-0/doc/en 
$SAGE_ROOT/devel/sage-0/doc/fr $SAGE_ROOT/devel/sage-0/sage

Reporting 0 TestsFailed
0 TestsFailed

Is this an error on my side ?

Charles


On 03/21/2013 08:03 AM, Jeroen Demeyer wrote:

On 2013-03-21 04:09, Stephen Montgomery-Smith wrote:

1.  I notice that many tests (like "sage -t
devel/sage/sage/rings/arith.py") are run three times.

Any suspicious environment variables? What is
$ env | grep SAGE


File "devel/sage/sage/misc/interpreter.py", line 566, in
sage.misc.interpreter.interface_shell_embed
Failed example:
 shell.run_cell('List( [1..10], IsPrime )')
Expected:
 [ false, true, true, false, true, false, true, false, false, false ]
Got:
 [ false, true, true, false, true, false, true, false, false, false ]

I don't see any difference between Expected and Got.

This is related to IPython, did you change any configuration of IPython,
different from the default?


 tgammal domain error

This also looks like a bug in the math library...



--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] Strange bug (or "feature") in relative number fields

[Charles Bouillaguet]

Hi,

regarding the problem of number fields defined by polynomial with 
rational coefficients (http://trac.sagemath.org/sage_trac/ticket/252), I 
implemented a simple patch that justs prints a warning at  :


http://trac.sagemath.org/sage_trac/ticket/14146

However, I don't understand why this patch causes failures on some 
machines, and not on others (see the patchbot results).


Cheers,
-
Charles Bouillaguet

On 02/19/2013 08:54 PM, David Roe wrote:

I'm fairly sure the problem is that the defining polynomial for the
relative extension is not monic.  One solution would be to use an
equivalent monic polynomial and keep track of a simple transformation
allowing one to translate between the internal representation of
elements on the one hand and print representations and conversions from
polynomials on the other.
David


On Tue, Feb 19, 2013 at 10:48 AM, Charles Bouillaguet
mailto:charles.bouillag...@gmail.com>>
wrote:

Hi all,

Adrien Poteaux reported this bug
(http://trac.sagemath.org/sage_trac/ticket/14146) to me. When you
create a number field (possibly on top of another number field),
what are the restrictions on the defining polynomial ? Currently,
strange PARI error occur, that are quite cryptic. Apparently,

At the very least, these restrictions (if they actually exist)
should be (better) documented...

Thanks,
    ---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



--
You received this message because you are subscribed to the Google
Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it,
send an email to sage-devel+unsubscr...@googlegroups.com
<mailto:sage-devel%2bunsubscr...@googlegroups.com>.
To post to this group, send email to sage-devel@googlegroups.com
<mailto:sage-devel@googlegroups.com>.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.



--
You received this message because you are subscribed to the Google
Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.




--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-devel] patchbot timeout

[Charles Bouillaguet]

Hi all,

I am running a patchbot on my (mostly idle) machine, and I witnessed this :


Traceback (most recent call last):
  File "/scratch/sage-5.8.beta2/local/bin/patchbot/patchbot.py", line 
687, in 

main(args)
  File "/scratch/sage-5.8.beta2/local/bin/patchbot/patchbot.py", line 
671, in main

patchbot.test_a_ticket(ticket)
  File "/scratch/sage-5.8.beta2/local/bin/patchbot/patchbot.py", line 
463, in test_a_ticket
self.report_ticket(ticket, status=status[state], log=log, 
plugins=plugins_results)
  File "/scratch/sage-5.8.beta2/local/bin/patchbot/patchbot.py", line 
588, in report_ticket
print post_multipart("%s/report/%s" % (self.server, ticket['id']), 
fields, files)
  File "/scratch/sage-5.8.beta2/local/bin/patchbot/http_post_file.py", 
line 16, in post_multipart

return urllib2.urlopen(r).read()
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 126, 
in urlopen

return _opener.open(url, data, timeout)
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 400, 
in open

response = self._open(req, data)
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 418, 
in _open

'_open', req)
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 378, 
in _call_chain

result = func(*args)
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 
1207, in http_open

return self.do_open(httplib.HTTPConnection, req)
  File "/scratch/sage-5.8.beta2/local/lib/python/urllib2.py", line 
1177, in do_open

raise URLError(err)
urllib2.URLError: 

Maybe the timeout should be made longer ?

Cheers,
--
Charles Bouillaguet

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-devel] Linear algebra reviewer wanted

[Charles Bouillaguet]

Hi,

http://trac.sagemath.org/sage_trac/ticket/13853 has been in need of a reviewer 
for a while. It fixes a bug in a basic functionality of free modules (at least, 
it fixes an inconsistency between the code and the specification). It also 
makes some code cleaner.

Thanks,

Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

---
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-devel] Strange bug (or "feature") in relative number fields

[Charles Bouillaguet]

Hi all,

Adrien Poteaux reported this bug 
(http://trac.sagemath.org/sage_trac/ticket/14146) to me. When you create a 
number field (possibly on top of another number field), what are the 
restrictions on the defining polynomial ? Currently, strange PARI error occur, 
that are quite cryptic. Apparently, 

At the very least, these restrictions (if they actually exist) should be 
(better) documented...

Thanks,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] What can we change on a parent?

[Charles Bouillaguet]

On Feb 10, 2013, at 8:27 PM, Nils Bruin wrote:

> Can we safely muck about with the category, though? Presently we
> already have (due to an external cache lookup):
> 
> sage: R=ZZ.quo(7)
> sage: R in IntegralDomains() ##1
> False
> sage: R in Fields()
> True
> sage: R in IntegralDomains() ##2
> True

I find this disturbing… (without even considering the question at hand, namely 
the immutability of parents). Why doesn't the first call to R in 
IntegralDomains() decide wether this is true or not ?

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

[sage-devel] Sage builds and (almost) passes dockets on ARM chromebook

[Charles Bouillaguet]

Hi sage-lovers,

You'll be happy to know that Sage builds out-of-the-box on a (samsung) ARM 
Chromebook running ubuntu. All but 3 doctests pass. The remaining 3 are 
numerical accuracy errors.

I've opened http://trac.sagemath.org/sage_trac/ticket/14077 for those who are 
interested.

Cheers,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.

Re: [sage-devel] Univariate quotient ring returning wrong results

[Charles Bouillaguet]

On Jan 26, 2013, at 11:31 PM, Florent Hivert wrote:

>  Dear all,
> 
> In some circumstance polynomial ring quotients returns wrong results: the
> following quotient by a single polynomial works correctly:
> 
>sage: R. = PolynomialRing(ZZ)
>sage: 
>sage: S. = R.quotient(x^2+x+1)
>sage: xbar^2
>-xbar - 1
>sage: xbar^2 + x + 1 == 0
>True
> 
> whereas quotient by several polynomial is wrong:
> 
>sage: S. = R.quotient((x^2+x+1, x^2))
>sage: xbar^2
>xbar^2
>sage: xbar^2 + x + 1 == 0
>False
> 
> The reason is that the default implementation of reduce in ideal.py is
> 
>def reduce(self, f):
>return f   # default
> 
> and is *not* overloaded for those kinds of polynomials. I'd rather replace
> that with
> 
>raise NotImplementedError
> 
> leading   
> 
>sage: R. = PolynomialRing(ZZ)
>sage: S. = R.quotient((x^2+x+1, x^2))
> 
> to raise a NotImplementedError. Do you all agree with this behavior ? Is there
> a simple way to fix that, knowing that "multivariate" polynomials in one
> variable correctly implement the feature:
> 
>sage: R. = PolynomialRing(ZZ, 1)
>sage: S. = R.quotient((x^2+x+1, x^2))
>sage: xbar^2 + x + 1 == 0
>True

If I am not mistaken, any ideal I =  of R[x] is spanned by  a 
**single** polynomial (which is the gcd of the f_i). So, in your examples, the 
ideal spanned by x^2 and x^2+x+1 is in fact R[x], because their gcd is one.

Then reduction should just be the remainder of the division by the single 
generator of the ideal...

(this is of course only true with polynomial in one variables)

Charles


> Thanks for any advice.
> 
> Cheers,
> 
> Florent
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to 
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] optional […] package […] installed ?

[Charles Bouillaguet]

Hi,

The développer manual claims that if a doctoring contains the three word 
"optional", "package" and "installed", then all the doctests there are 
considered optional.

I couldn't make this work, and looking a bit closer at 
$SAGE_ROOT/local/bin/sage-doctest, I couldn't find a trace of this.

Does it actually work ?

Thanks,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] CDF[X] pretty-printing

[Charles Bouillaguet]

> That's good to know! So doing computations in sage with numerical
> polynomials does not give you an upper bound on the degree of the
> resulting polynomial, contrary to what one would get from a naive
> implementation:
> 
> sage: R.=CDF[]
> sage: f=10^30*x
> sage: g=3*x
> sage: (g+f)-f
> 0

Well, I would prefer this thing to print "0.0", just as a gentle reminder that 
the result may not be accurate…

> sage: ((g+f)-f).list()
> []
> sage: ((g+f)-f).degree()
> -1

And we don't get an upper-bound, but a lower bound.

My proposal is that CDF[x](0) prints as "0.0", without changing anything else. 
After all, R[x](alpha) typically uses R's code to pretty-print alpha when alpha 
is a constant, so why not do the same when alpha is the constant zero?

I guess that I have trouble with this because I have been educated with the 
idea that zero, being a constant polynomial, has degree zero (the notion of 
"degree -1" did not exist…).
-
Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] CDF[X] pretty-printing

[Charles Bouillaguet]

Hi all,

I just stumbled upon this:

sage: CDF(0)
0.0

sage: CDF['x'](0)
0

I would have liked these two to pretty-print identically. OK, I agree that this 
is an ultra-minor nitpick, but it made doctest fail in the "french sage book"  
(http://trac.sagemath.org/sage_trac/ticket/11672).

Should we somehow try to make CDF(y) and CDF['x'](y) print identically ?

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] unpicking once works ; twice crash

[Charles Bouillaguet]

Hi,

sage: sage.structure.sage_object.unpickle_all()

works nicely, but running it TWICE makes sage crash and exit.

This problem was in fact mentioned there :  
http://trac.sagemath.org/sage_trac/ticket/5838

Looking a bit further into it, the actual pickles that trigger the problem are 
those in sage.combinat.sf.macdonald. Namely, if these ones are removed from the 
pickle jar, then the problem disappears...

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Re: What to do with magically-resolved tickets ?

[Charles Bouillaguet]

Hi Simon,

On Jan 4, 2013, at 2:59 PM, Simon King wrote:

> On 2013-01-04, Charles Bouillaguet  wrote:
>> There's also a (fixed) memory-leak : I am not sure if this can be doctested 
>> properly…
> 
> Which memory leak do you mean? sage-5.6.beta2 contains a couple of fixes for 
> memory
> leaks (#715). The fixes originally made some trouble (segfaults), but now 
> seem to be
> fine, thanks to a bug fix in Cython (#13896).
> 
> It could of course be the case that incidentally fixed other known leaks. Can
> you provide us with ticket numbers?

http://trac.sagemath.org/sage_trac/ticket/9298

I don't know if it is related to #715...

> And, by the way, memory leaks can be tested using get_memory_usage.

I was afraid of writing a dockets such a : 

sage: x = get_memory_usage()
…
do crazy stuff
…
assert x == get_memory_usage()

Isn't this likely to raise false positives sometimes?

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] What to do with magically-resolved tickets ?

[Charles Bouillaguet]

> solved). How do we handle these tickets ? Mark them as invalid/won't 
> fix/duplicates ? Give them a positive review ? 
> Maybe also add doctests (with a reference to the tickets) showing that the 
> problems are actually solved? 
> 
> Absolutely.  We want to prevent regression.  Another reason to do this is 
> that it's conceivable that the error was actually partly OS-dependent and 
> that was not recognized at the time, so that others testing the patch will 
> see that it still doesn't work.
> 
> You're right though that some of them are unreasonable or hard to doctest.  
> How do we usually test timing ones?  It's pretty machine-dependent, so it 
> might be hard to do properly.

There's also a (fixed) memory-leak : I am not sure if this can be doctested 
properly…

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] What to do with magically-resolved tickets ?

[Charles Bouillaguet]

Hi,

I have found a few tickets that have been magically resolved ; the problem at 
the origin of the ticket (apparently) no longer exists in the current version 
of Sage, yet the tickets are still open (maybe because nobody noticed the 
problems have been solved). How do we handle these tickets ? Mark them as 
invalid/won't fix/duplicates ? Give them a positive review ?

Examples :

http://trac.sagemath.org/sage_trac/ticket/5917
http://trac.sagemath.org/sage_trac/ticket/12792
http://trac.sagemath.org/sage_trac/ticket/9298
http://trac.sagemath.org/sage_trac/ticket/7795
http://trac.sagemath.org/sage_trac/ticket/5402


---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Apparent inconsistency between doctoring and behavior of module-related functions

[Charles Bouillaguet]

On Dec 24, 2012, at 3:59 PM, Charles Bouillaguet wrote:

> Hi,
> 
> By the way, I realized that membership in RDF and CDF is completely broken:
> 
> sage: vector( [1, 2, sqrt(-1)] ) in RDF^3
> True   # o_O
> 
> sage: R. = QQ[]
> sage: vector( [1,x] ) in CDF^2
> True   # O_o

This happens because

 :

class RealDoubleVectorSpace_class(FreeModule_ambient_field):
….
def coordinates(self,v):
   return v

Membership testing relies on the coordinates() method complaining when the 
argument is not in the free module. Any reason why there is this special 
"coordinates" method in RealDoubleVectorSpace_class instead of the "normal" one 
that checks its argument? Performance reasons maybe? Anyone cares if this 
method checks its argument? (btw this coordinates method does not accept the 
"check" flag it is supposed to accept by inheriting from the parent classes…)

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Apparent inconsistency between doctoring and behavior of module-related functions

[Charles Bouillaguet]

Hi,

By the way, I realized that membership in RDF and CDF is completely broken:

sage: vector( [1, 2, sqrt(-1)] ) in RDF^3
True   # o_O

sage: R. = QQ[]
sage: vector( [1,x] ) in CDF^2
True   # O_o


and of course :

sage: vector( RDF,  [1, 2, sqrt(-1)] )
---
Traceback (most recent call last)
…
TypeError: Unable to convert 1.0*I to float; use abs() or real_part() as desired


sage: vector( CDF, [1,x] )
---
Traceback (most recent call last)
...
TypeError: cannot coerce nonconstant polynomial to float

I will try to fix this also in http://trac.sagemath.org/sage_trac/ticket/13853

Merry Xmas to you all,

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Correct procedure for an experimental package

[Charles Bouillaguet]

> I am not suggesting to patch the Sage library when installing your
> package. You can put the interface in a separate Cython module which is
> built by the usual Python/Cython setup.py magic and installed in the
> system python module directory. Then people will be able to import your
> module from the Sage command line as usual.

The python interface **uses** the sage library (matrices, modules, polynomials, 
term orders, etc. etc. etc.). It does not make sense outside of sage. It is a 
binding between sage and my piece of C-code.

I actrually followed the same pattern I found there : 
http://trac.sagemath.org/sage_trac/ticket/418

> I don't think there is a well established procedure for this. There is
> code in the Sage library that depends on optional packages. This works
> just like you described. modules_list.py already includes some examples.
> In this case, all doctests will need to be marked optional.

Strictly speaking, they don't, because the code is not even considered if the 
spkg is not there.

> I can see the benefits of having the wrappers "included in Sage" from a
> reputation/review point of view.

You are right, but again I followed what I thought was the right way to go 
(http://trac.sagemath.org/sage_trac/ticket/418). I certainly agree that it is a 
bit weird to have a lot of "inactive" code on everyone's installation.

Again, what should I do :) ?

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Correct procedure for an experimental package

[Charles Bouillaguet]

On 12/20/2012 01:02 PM, Burcin Erocal wrote:

What should I do ? Unconditionally include the cython interface to
the sage library, and mark all doctests as optional ?


Can you compile the Cython interface without the header files installed
by your package?


No


I assume the Cython interface needs to be changed whenever you update
your library.


Yes, but changing spkg versions requires a ticket, on which the sage 
library can also be changed.



Which Sage version is used with an experimental package
cannot be controlled, since Sage just grabs the latest version available
at install time. Hence, if you keep the interface separate from
the spkg, you will run into many incompatibility issues.


OK. But then how do the other spkgs do ?


Wouldn't it be easier to include the Cython interface in the package?
AFAIK, Cython's build system improved significantly and there is no
reason to use Sage's build system for a Cython module.


Is it possible to patch the sage library when installing an spkg ? What 
if the patch fails because the sage library was updated since the last 
spkg updatye ??? This seems like asking for trouble, and incompatibilities.


I still don't understand how it is currently done.

Charles

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] Correct procedure for an experimental package

[Charles Bouillaguet]

Hi all,

I (amongst with others) have written a library that solves boolean 
equations in some way. I wanted to include it as an experimental spkg. I 
thus wrote a cython interface to Sage. To be usable from inside Sage, 
both the library itself and the cython interface are necessary. What is 
the proper way to do this ?


I first thought that the Right Way (r) was to conditionally include the 
cython part to the library when the spkg is installed, by writing 
something like this in module_list.py :


if is_package_installed('stuff'):
ext_modules.extend([ blablabla ])


This works fine, except that it forces potential users to not only 
install an spkg but also run sage -b, and it apparently makes it 
impossible to update the reference manual: if I add a line


   sage/libs/stuff

to libs.rst, then building the reference manual fails when the spkg is 
not installed.


What should I do ? Unconditionally include the cython interface to the 
sage library, and mark all doctests as optional ?


Cheers,
--
Charles Bouillaguet

--
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Apparent inconsistency between doctoring and behavior of module-related functions

[Charles Bouillaguet]

On Dec 19, 2012, at 12:44 PM, John Cremona wrote:


---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



> I suggest adding to the documentation of A.coordinates() that it works
> also if the given element is in the ambient space, with an example of
> that.  In concrete terms you need the element to be an F-linear
> combination of the generators where F is the fraction field of the
> base ring R, and not just an R-linear combination.
> 
> This functionality is useful (I have used it in some number field
> functions) and I would not want it removed.

Well, you could always access it through: 

R.ambient_vector_space().coordinates( x )

One problem I can see is "what to do when the ambient vector space is not 
defined?" (this happens when the ring is not a PID, because then its fraction 
field is not defined). Examples include:

sage: R. = QQ[]
sage: I = (x*y) * R
sage: Q = R.quotient( I )
sage: M = Q^3
sage: M.ambient_vector_space() # BOOM

This is now : http://trac.sagemath.org/sage_trac/ticket/13853
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/


> John
> 
> 
>> ---
>> Charles Bouillaguet
>> http://www.lifl.fr/~bouillaguet/
>> 
>> --
>> You received this message because you are subscribed to the Google Groups 
>> "sage-devel" group.
>> To post to this group, send email to sage-devel@googlegroups.com.
>> To unsubscribe from this group, send email to 
>> sage-devel+unsubscr...@googlegroups.com.
>> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>> 
>> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to 
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Apparent inconsistency between doctoring and behavior of module-related functions

[Charles Bouillaguet]

On Dec 19, 2012, at 4:16 AM, P Purkayastha wrote:

> On 12/19/2012 12:28 AM, Charles Bouillaguet wrote:
>> Hi all,
>> 
>> There seems to be an inconsistency between the docstrings and the actual 
>> behavior of some module-related methods. For instance, I am surprised by the 
>> behavior of the coordinates() method :
>> 
> 
> It is consistent with whatever A.ambient_vector_space() is doing. There is 
> even a doctest:
> 
>  sage: M = ZZ^3;
>  sage: V = M.ambient_vector_space(); V
>  Vector space of dimension 3 over Rational Field
> 
> Since the "ambient vector space" is the Rational field, A.coordinates returns 
> the rational numbers. I don't know what is meant by the term "ambient vector 
> space" in this context.

Fair enough, but the docstring of A.coordinates() says nothing about ambient 
space. So I think that a) either the docstring must be fixed or b) the function 
must be fixed.

Which one has your preference ?
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] Apparent inconsistency between doctoring and behavior of module-related functions

[Charles Bouillaguet]

Hi all,

There seems to be an inconsistency between the docstrings and the actual 
behavior of some module-related methods. For instance, I am surprised by the 
behavior of the coordinates() method : 

sage: A = ZZ^3
sage: A.coordinates?
…
Definition: A.coordinates(self, v, check=True)
Docstring:
 Write v in terms of the basis for self.
 ….
 "check" - bool (default: True); if True, also verify that v is really in 
self.
 ….
 If v is not in self, raises an "ArithmeticError" exception.

sage: v = vector( [1/2, 1/3, 1/4] )
sage: v in A
False
sage: A.coordinates( v )
[1/2, 1/3, 1/4]   # BIZARRE

Shouldn't this raise the ArithmeticError exception, as advertised ?

Looking at the code of this method reveals that it does: 

return self.coordinate_vector(v, check=check).list()

A.coordinate_vector is presumably doing:

 Write v in terms of the standard basis for self and return the
 resulting coefficients in a vector over the fraction field of the
 base ring.
... 
 If v is not in self, raises an ArithmeticError exception.

And, presumably, it does not really implement this specification.

Unless I am missing something, of course.

Cheers,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Reviewer wanted for the DifferentialAlgebra package

[Charles Bouillaguet]

Hi,

I just stumbled upon 
https://groups.google.com/d/topic/sage-support/SlmhkCvo3Ak/discussion

So, there is at least **one** other person somewhere that would enjoy #13268 
getting a review :)

Thanks,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



On Nov 26, 2012, at 10:13 PM, Simon King wrote:

> Dear Charles,
> 
> On 2012-11-26, Charles Bouillaguet  wrote:
>> We (at Lille, France) propose to integrate the DifferentialAlgebra into SAGE.
>> This package, which is already present in MAPLE, is the product of years of
>> work from François Boulier et al. on differential elimination. It relies on
>> François's C libraries. Its core is an implementation of the 
>> Rosenfeld-Groebner
>> algorithm, which rewrites systems of differential (or partial derivative)
>> equations into potentially simpler ones. In algebraic terms, it decomposes
>> the radical of a differential ideal into the intersection of prime 
>> differential
>> ideals.
> 
> That's a very valuable contribution, I think!
> 
>> Next, it is not completely clear to us *where* to put this in sage. We 
>> (somewhat
>> arbitrarily) chose to put it in sage.calculus.DifferentialAlgebra, to keep it
>> close with the other functions dealing with differential equations, but we 
>> agree
>> that this is bizarre, because differential elimination is 100% algebraic.
> 
> Differential algebra is a nice example where methods from one
> mathematical field are applied to another mathematical field.
> 
> So, why shouldn't one split the code accordingly and put it into
> *two* parts of Sage?
> 
> I'd suggest you implement the algebraic part in classes, say,
> sage.algebras.differential_algebras.differential_algebra.DifferentialAlgebra 
> and
> sage.algebras.differential_algebras.ideal.DifferentialAlgebraIdeal etc.
> 
> And then, the application to the solution of differential equations may be
> put into sage.calculus.desolvers.rosenfeld_groebner (or whatever
> better name there is): After all, you can easily do "from
> sage.algebras.differential_algebras import ..." in your DE-solver,
> no matter where it is implemented.
> 
> Actually, I think it might even be easier to review if the different
> mathematical topics are cleanly separate in the code base.
> 
> By the way, note that since more or less recently, the
> g-algebras provided by Singular became wrapped in libsingular.
> This is sage.rings.polynomial.plural.NCPolynomialRing_plural.
> Would it make sense to define conversions back and forth between your
> differential algebras and those in libsingular?
> 
> 
>> Lastly, what is the right way to go ? experimental package ?
>> optional package ? We confirmed that it compiles and works on
>> Linux and Mac OS X.
> 
> I think new stuff should first be experimental for a while, and then
> promoted to an optional or even standard spkg. But there may be
> exceptions.
> 
> Best regards,
> Simon
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to 
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] VectorSpaces vs tuples

[Charles Bouillaguet]

On Dec 11, 2012, at 10:54 PM, Jason Grout wrote:

> On 12/11/12 3:50 PM, Volker Braun wrote:
>> A tuple isn't a vector. For example:
>> 
>> (1,2) + (2,3) == (1,2,2,3)
>> 
>> I think you'd end up in a weird place if you try to make tuples behave
>> like vectors. Also, vectors over what? Since they are native Python
>> types they don't have parents. So you can't coerce them into a vector
>> space (over what?)
> 
> I think the OP's point was that it should complain about the types, not that 
> we should make tuples act like vectors:
> "I think that the first one should complain about types instead of just 
> saying "no". Who has an opinion :)? "

That's correct. 

> That makes sense to me, especially seeing how easy it would be for someone to 
> cut and paste the printed representation of a vector and get a tuple.

On the other hand, Volker made me realize that SAGE's answer is mathematically 
correct. Things that are not vectors do not belong to a vector space (seen as a 
set).

The point I was raising is that "(1,0,0,0) in ZZ^4 --> False" is mathematically 
correct, but may be surprising and/or confusing to some. "(1,0,0,0) in ZZ^4 --> 
WARNING : you are doing something stupid" restricts the meaning of "in" for no 
mathematical reason, but may be more user-friendly. Also, testing if "x in V" 
when V is a vector space and x is not (coercible to) a vector probably 
indicates a bug somewhere in the code.

I no longer have any definitive opinion now, though (thanks to Volker).

Charles

> Jason
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to 
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
> 
> 

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] VectorSpaces vs tuples

[Charles Bouillaguet]

Hi all,

I am disturbed by this : 

sage: (1,0,0,0) in QQ^4
False

Of course,  we have : 

sage: vector( (1,0,0,0) ) in QQ^4
True

I think that the first one should complain about types instead of just saying 
"no". Who has an opinion :)? 

Cheers

---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] High level architectural design document of Sage

[charles Bouillaguet]

2012/12/3 John H Palmieri :
> See
> http://sage.math.washington.edu/home/palmieri/misc/6495-jsmath/html/en/reference/index.html
> for what the reference manual might look like if
> http://trac.sagemath.org/sage_trac/ticket/6495 is every merged into Sage. Do
> you like that any better?

I do ! I think it would help to make SAGE easier to get acquainted
with (especially for people like me accustomed to another CAS).

My next remarks may be more a matter of personal taste. I used to
teach Maple to undergrads, and I use a specific subset of SAGE
functionnality on a daily basus, so that I may be a bit biased.

I still think that MAGMA's "handbook" is easier to browse than SAGE's
reference manual (both are supposed to exhaustively describe all the
functions in the system). One reason for that is probably that in
SAGE, we auto-generate the manual...

But still, there might be a few things we could do to help, e.g.
#6495. My generic opinion is that the most frequently used
mathematical objects should be the easiest to find in  the reference
manual (think of it as Huffman coding...).

For instance, it is close to impossible to find "vector spaces" in the
reference manual. This has puzzled and annoyed me for a while! I now
realize that this is because we don't have a "VectorSpace" class, and
that we instead have "FreeModules", which are more generic. The thing
is that most, if not all, undergrads looking to play with vector
spaces will not know that they should in fact look for FreeModule's.
Wouldn't it be possible to work around that, and make the reference
manual a bit more "non-advanced-mathematicians-friendly" ?

Comparing with the MAGMA handbook again, I think that their design
decision to expose "basic rings and linear algebra" as one of the
first titles of their manual is a very good one. It has certainly
helped me learning MAGMA quickly...

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] High level architectural design document of Sage

[charles Bouillaguet]

Hi,

Actually, I think I agree with the request of WM Chung. I found myself
longing for a high-level overview of SAGE development. I think it
could be pretty simple, but that it could explain how some things are
organized. For instance :

*) what is the category framework? what purpose does it serve? How
should it (in theory) interact with the rest of the code?

*) What is the rationale behind the class hierarchy? (mathematical sub-concept?)

*) A pointer to the document somewhere that explains the
coercion/conversion framework.


And now, for something completely different.

I think that the reference manual is very useful, but its linear
structure (a loong list of items where it is not obvious where to
find what you are looking for) is a bit baffling for beginners. I come
from the MAGMA community, and I tend to think that the hierarchical
structure of the MAGMA reference manual is a bit easier to navigate
(http://magma.maths.usyd.edu.au/magma/handbook/). I could try to
propose a patch implementing such a structure if someone thinks its
worth it...

Also, the presence of the category framework in the reference manual
is also a bit confusing. For instance, when I was new to SAGE, I
wanted to write something that manipulated vector spaces. I thus
browsed the reference manual, and naturally found the "Vector Space"
category... where, of course, I could not find the functions I was
looking for. Why not remove the categories from the reference manual?
What purpose do they serve?

Cheers,

2012/12/1 Wai Man Chung :
> Hi,
>
> I am new to Sage and I am interested to participate in the development work
> of Sage. I would like to understand the codes of Sage.
>
> I would like to know if there is any high level architectural design
> document on Sage. I can find fragments of information related to this, e.g.
> -  Sage use some other software components like GAP,
> -  Sage use languages like C/C++, Python, etc,
> -  Sage has object-oriented approach in coding ;
> -  Sage has many functional module like Calculus, algebra, etc.
>
> Is there any high level architectural diagram showing the inter-relationship
> among these ? e.g. Inheritance tree of the object hierarchy, dependency
> among the software components, e.g. a certain functional module may have
> used some software components, etc. I think such document is helpful to
> beginner.
>
> As a beginner, can anyone share some experience on the way to trace the
> codes ? e.g. when I see from tutorial or reference manual on some functions,
> any ways to look for the corresponding source codes ? (by searching the text
> pattern, etc.)  Or in the other way round, when I look at the source code,
> any way to know how to use and run it at sage ?
>
> Thanks in advance.
> WM Chung
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] Reviewer wanted for the DifferentialAlgebra package

[Charles Bouillaguet]

Hi all,

We (at Lille, France) propose to integrate the DifferentialAlgebra into SAGE. 
This package, which is already present in MAPLE, is the product of years of 
work from François Boulier et al. on differential elimination. It relies on 
François's C libraries. Its core is an implementation of the Rosenfeld-Groebner 
algorithm, which rewrites systems of differential (or partial derivative) 
equations into potentially simpler ones. In algebraic terms, it decomposes the 
radical of a differential ideal into the intersection of prime differential 
ideals.

We are willing to make some effort for the last push until it's done :)

First of all, #13268 is waiting for a reviewer.

Next, it is not completely clear to us *where* to put this in sage. We 
(somewhat arbitrarily) chose to put it in sage.calculus.DifferentialAlgebra, to 
keep it close with the other functions dealing with differential equations, but 
we agree that this is bizarre, because differential elimination is 100% 
algebraic.

Lastly, what is the right way to go ? experimental package ? optional package ? 
We confirmed that it compiles and works on Linux and Mac OS X.  

Thanks,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] upgrading sage while working on patches

[Charles Bouillaguet]

Hi all,

I just tried to upgrade from 5.4 to 5.4.1, and it worked.

However, the upgrade process interacts bizarrely with mercurial's patch queue. 
I had a non-empty patch queue, and applied the upgrade. But now, all the 
upgraded files appear as "uncommitted local changes", and I can't really use 
the queue anymore. I can potentially break a lot of stuff by doing "hg revert 
--all".

It would probably be safer to check if there are local change to the sage 
library repos before applying the upgrade, and the upgrade process should 
complain if it is the case…

Opinions ?
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] Conventions for writing documentation

[Charles Bouillaguet]

Hi,

Skimming over the reference manual, it seems that there is no clear standard 
regarding how to write some things. For instance, sometimes self is 
double-quoted (``self``), sometimes it isn't. Sometimes True and False are 
double-quoted, sometimes not. Sometimes the name of arguments (say, x) is 
single-quoted (when they are mathematical variables), sometimes they are 
double-quoted, and sometimes they are not quoted at all, etc. etc. etc.

What is the preferred way to go?

Also, to describe what a function does, is it better to write maths in latex 
(i.e., if `x = 0`) or in "sage code" (i.e., if ``x == 0``) ?

Thanks,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] PolynomialRing import problem

[Charles Bouillaguet]

On Nov 9, 2012, at 7:57 PM, Volker Braun wrote:

> If you use the
> 
> class MyParent(Parent)
> Element = MyElement
> 
> syntax then you have to import MyElement. So you shouldn't import MyParent in 
> your element code or you will create a cyclic import (=bad). 
> 
> Are you sure that you need to create new parents from the element? Your 
> element should only work with the parent that it is an element of. New 
> Parents are generally constructed by coercion, but the coercion code lives in 
> MyParent.

It's a bit more complicated than that… The setting is that if R is a 
(multivariate) polynomial ring, and I is an ideal of R, then checking that 
elements of the quotient R/I are regular requires working with a new polynomial 
ring R', which is essentially a copy of R with one more variable.

So, sage.rings.QuotientRingElement needs to create instances of multivariate 
polynomial rings. 

> If all fails you can still do a method-level import. But its likely that you 
> should not.

Sorry for not being very familiar with python, but could you elaborate a little?

Thanks,
Charles

> 
> 
> 
> 
> On Friday, November 9, 2012 1:13:20 PM UTC-5, Charles Bouillaguet wrote:
> Hi, 
> 
> Why does adding : 
> 
> from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing 
> 
> at the beginning of quotient_ring_element.py create the weird error: 
> 
> Traceback (most recent call last): 
> … 
> AttributeError: 'module' object has no attribute 'quotient_ring' 
> 
> Is there a circular dependency problem? If so, how can I possibly create 
> polynomial rings inside quotient_ring_element ??? 
> 
> Cheers, 
>  
> Charles Bouillaguet 
> http://www.lifl.fr/~bouillaguet/
> 
> -- 
> You received this message because you are subscribed to the Google Groups 
> "sage-devel" group.
> To post to this group, send email to sage-devel@googlegroups.com.
> To unsubscribe from this group, send email to 
> sage-devel+unsubscr...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel?hl=en.
>  
>  



---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] PolynomialRing import problem

[Charles Bouillaguet]

Hi,

Why does adding : 

from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing

at the beginning of quotient_ring_element.py create the weird error:

Traceback (most recent call last):
…
AttributeError: 'module' object has no attribute 'quotient_ring'

Is there a circular dependency problem? If so, how can I possibly create 
polynomial rings inside quotient_ring_element ???

Cheers,

Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] dividing zero by something weird in multivariate quotient rings

[Charles Bouillaguet]

Hi,

while working on the apparently trivial #13670, Marco Streng made me notice the 
following inconsistency in the present code base:

sage: R. = QQ[]
sage: S = R.quotient_ring(R.ideal(x^2, y))
sage: 0/S(x)
0

sage: P. = QQ[]
sage: S = P.quotient_ring(x^2)
sage: 0/S(x)
ZeroDivisionError: element xbar of quotient polynomial ring not invertible

I am inclined to believe that the second behavior is correct, if only because 
it could potentially catch bugs.

In the same vein, we presently have : 

sage: S(2*x)/S(x)
2

However, the quotient is not uniquely defined, because 
sage: S(x)*S(2+x) == S(2*x)
True
sage: S(x)*S(2) == S(2*x)
True

So why return S(2) instead of S(2+x) ? Should we refuse to perform the 
(not-well defined) division in this case?

Cheers,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Bits and pieces about Quotient Rings

[Charles Bouillaguet]

> Sure.  So we have 4 (?) possible outcomes:
> 
> 1. Inverse exists and we can compute it: return the inverse
> 2. We can compute that the inverse does not exist:  ZeroDivisionError
> 3. We can compute that the inverse exists but cannot find the inverse: 
> NotImplementedError
> 4. We cannot determine invertibility: NotImplementedError
> 
> For your rings, and (for example) in Z/nZ, we would be in cases 1 or 2.  For 
> a completely general abstract ring: case 4.  I added Case 3 later, but have 
> not yet come up with an example.

In fact, it seems weird to handle the polynomial case inside 
rings/quotient_ring_element.py

This file actually implements the computation of the inverse of a polynomial 
modulo a polynomial ideal, and it seems (to me at least) that this is not the 
right place for this.

This should be implemented in rings/polynomial/multi_polynomial.pyx, as the 
inverse_mod() method. The existence of this method is advertised by the 
TAB-completion, but it is in fact NotImplemented. Thus, #13675 which adds this 
method awaits review :)

Then, as a second step, I suggest to remove this bizarre code from 
rings/quotient_ring_element.py

Charles

PS : John, how could I construct an example for case 4?

> John
>  
> I have written a patch, and I'm presently testing it.
> 
> Charles
> 
> > John
> >
> >>
> >> Let R be a polynomial ring, I be an ideal of R, and f be a non-zero 
> >> element of R/I.
> >>
> >> To check whether f is invertible in R/I, we check whether 1 belongs to the 
> >> ideal (I + ). If it is the case, then an inverse exist. Indeed, in this 
> >> case, there exist g in R such that 1 = [something in I] + g*f. It follows 
> >> that the class of g in R/I is the inverse of f.
> >>
> >> But this test in fact **decides** whether an inverse exist. If there exist 
> >> a g such that f*g = 1 mod I, then by definition there exist two 
> >> polynomials of R, say f' and g', such that f is the class of f' and g is 
> >> the class of g' modulo I. Then in R we have f*g = 1 + [something in I]. 
> >> This automatically implies that 1 belongs to the ideal (I + ).
> >>
> >> Thus, the current implementation should not return "ErrorNotImplemented", 
> >> it should return "NonInvertible", because we KNOW that it is the case...
> >>
> >> This is now #13670.
> >>
> >> However, presently this test uses p.lift(…), and as you pointed out the 
> >> answer becomes bogus as soon as one tries to invert something 
> >> non-invertible….
> >>
> >> This one is now #13671 .
> >>
> >> Cheers,
> >> ---
> >> Charles Bouillaguet
> >> http://www.lifl.fr/~bouillaguet/
> >>
> >>>> *) Non-deterministic output of some (presumably deterministic) functions
> >>>>
> >>>> Here is an example :
> >>>>
> >>>> sage: R. = QQ[]
> >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
> >>>> sage: test = I.gen(0) + x2*I.gen(1)
> >>>> sage: (test).lift( I )
> >>>> [1, x2] # this is correct
> >>>>
> >>>> sage: R. = QQ[]
> >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
> >>>> sage: test = I.gen(0) + x2*I.gen(1)
> >>>> sage: (test + 1).lift( I )
> >>>> [0, 0]   # this is correct
> >>>
> >>> No it isn't, the correct output would be ValueError, as (test+1) is
> >>> not in I. So this is a bug in the "lift" method.
> >>>
> >>>>
> >>>> sage: R. = QQ[]
> >>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
> >>>> sage: test = I.gen(0) + x2*I.gen(1)
> >>>> sage: (test).lift( I )
> >>>> [0, 0]   # this is WRONG !!! should be [1, x2]
> >>>>
> >>>> It looks like this could be a caching issue, so I am not sure whether I 
> >>>> need to open a new ticket for this, or if it is already "catch" by an 
> >>>> already-opened ticket.
> >>>
> >>> It is some kind of corruption triggered by the abovementioned bug, so
> >>> it may vanish when that bug is fixed.
> >>>
> >>> Here is a shortened version of your input:
> >>>
> >>> sage: R. = QQ[]
> >>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
> >>> sage: test = I.gen(0) + x2*I.gen(1)
> >>> sage: test.lift(I) # corr

Re: [sage-devel] Bits and pieces about Quotient Rings

[Charles Bouillaguet]

> I think all that Marco meant was that for a general ring, there may be
> no algorithm to decide invertibility.  In this ring, of course there
> is.

Yes, but the NotImplemented exception was raised **in the case where a Groebner 
basis could be computed**, and I maintain that it is not the most adapted 
answer.

I have written a patch, and I'm presently testing it.

Charles

> John
> 
>> 
>> Let R be a polynomial ring, I be an ideal of R, and f be a non-zero element 
>> of R/I.
>> 
>> To check whether f is invertible in R/I, we check whether 1 belongs to the 
>> ideal (I + ). If it is the case, then an inverse exist. Indeed, in this 
>> case, there exist g in R such that 1 = [something in I] + g*f. It follows 
>> that the class of g in R/I is the inverse of f.
>> 
>> But this test in fact **decides** whether an inverse exist. If there exist a 
>> g such that f*g = 1 mod I, then by definition there exist two polynomials of 
>> R, say f' and g', such that f is the class of f' and g is the class of g' 
>> modulo I. Then in R we have f*g = 1 + [something in I]. This automatically 
>> implies that 1 belongs to the ideal (I + ).
>> 
>> Thus, the current implementation should not return "ErrorNotImplemented", it 
>> should return "NonInvertible", because we KNOW that it is the case...
>> 
>> This is now #13670.
>> 
>> However, presently this test uses p.lift(…), and as you pointed out the 
>> answer becomes bogus as soon as one tries to invert something 
>> non-invertible….
>> 
>> This one is now #13671 .
>> 
>> Cheers,
>> ---
>> Charles Bouillaguet
>> http://www.lifl.fr/~bouillaguet/
>> 
>>>> *) Non-deterministic output of some (presumably deterministic) functions
>>>> 
>>>> Here is an example :
>>>> 
>>>> sage: R. = QQ[]
>>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>>>> sage: test = I.gen(0) + x2*I.gen(1)
>>>> sage: (test).lift( I )
>>>> [1, x2] # this is correct
>>>> 
>>>> sage: R. = QQ[]
>>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>>>> sage: test = I.gen(0) + x2*I.gen(1)
>>>> sage: (test + 1).lift( I )
>>>> [0, 0]   # this is correct
>>> 
>>> No it isn't, the correct output would be ValueError, as (test+1) is
>>> not in I. So this is a bug in the "lift" method.
>>> 
>>>> 
>>>> sage: R. = QQ[]
>>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>>>> sage: test = I.gen(0) + x2*I.gen(1)
>>>> sage: (test).lift( I )
>>>> [0, 0]   # this is WRONG !!! should be [1, x2]
>>>> 
>>>> It looks like this could be a caching issue, so I am not sure whether I 
>>>> need to open a new ticket for this, or if it is already "catch" by an 
>>>> already-opened ticket.
>>> 
>>> It is some kind of corruption triggered by the abovementioned bug, so
>>> it may vanish when that bug is fixed.
>>> 
>>> Here is a shortened version of your input:
>>> 
>>> sage: R. = QQ[]
>>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>>> sage: test = I.gen(0) + x2*I.gen(1)
>>> sage: test.lift(I) # correct
>>> [1, x2]
>>> sage: (test+1).lift(I) # invalid input, should give error
>>> [0, 0]
>>> sage: test.lift(I) # incorrect
>>> [0, 0]
>>> 
>>> 
>>> 
>>>> 
>>>> *) Segfault
>>>> 
>>>> The same kind of problem allows a small piece of code to cause segfaults 
>>>> in SAGE (apparently in singular-related stuff) :
>>>> 
>>>> sage: R. = QQ[]
>>>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
>>>> sage: 1 / S(x1 + x2)# should raise NotImplementedError
>>>> sage:
>>>> sage: R. = QQ[]
>>>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
>>>> sage: S.is_integral_domain()
>>>> 
>>>> ---> BOOM
>>>> 
>>>> *) bizarre output of p.lift(….)
>>>> 
>>>> When R is a Polynomial Ring, I is an ideal of R, and p is a polynomial of 
>>>> I, then p.lift( I ) returns a polynomial combination of a (groebner) basis 
>>>> of I which is equal to p. However, when p is not in I, then p.lift( I ) 
>>>> returns [0,0,…,0]. I find this a bit strange. Sho

Re: [sage-devel] Bits and pieces about Quotient Rings

[Charles Bouillaguet]

On Oct 29, 2012, at 4:39 PM, Marco Streng wrote:


> 2012/10/28 Charles Bouillaguet :
>> Hi all,
>> 
>> While playing with the quotient of a polynomial ring with an ideal, I 
>> encountered several glitches.
>> 
>> *) Trying to compute the inverse of something which is not invertible.
>> 
>> I know it is kind of weird to try this. However, it raises a 
>> NotImplementedError exception, instead of something more informative such as 
>> NonInvertible or whatever. I am willing to patch this, but could someone 
>> tell me what is the correct exception to raise?
> 
> Based on http://docs.python.org/2/library/exceptions.html, it should
> be ValueError (unless Sage has a more precise error for this
> situation, but I don't think so).
> 
> But in order to be able to raise a ValueError, you need to first
> decide whether your element is invertible or not. If such a decision
> mechanism is not implemented, then NotImplementedError is the only
> possibility. And I guess that is the current situation here.

Actually, I beg to differ. What is currently implemented is the following.

Let R be a polynomial ring, I be an ideal of R, and f be a non-zero element of 
R/I.

To check whether f is invertible in R/I, we check whether 1 belongs to the 
ideal (I + ). If it is the case, then an inverse exist. Indeed, in this 
case, there exist g in R such that 1 = [something in I] + g*f. It follows that 
the class of g in R/I is the inverse of f.

But this test in fact **decides** whether an inverse exist. If there exist a g 
such that f*g = 1 mod I, then by definition there exist two polynomials of R, 
say f' and g', such that f is the class of f' and g is the class of g' modulo 
I. Then in R we have f*g = 1 + [something in I]. This automatically implies 
that 1 belongs to the ideal (I + ).

Thus, the current implementation should not return "ErrorNotImplemented", it 
should return "NonInvertible", because we KNOW that it is the case...

This is now #13670.

However, presently this test uses p.lift(…), and as you pointed out the answer 
becomes bogus as soon as one tries to invert something non-invertible….

This one is now #13671 .

Cheers,
---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/

>> *) Non-deterministic output of some (presumably deterministic) functions
>> 
>> Here is an example :
>> 
>> sage: R. = QQ[]
>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>> sage: test = I.gen(0) + x2*I.gen(1)
>> sage: (test).lift( I )
>> [1, x2] # this is correct
>> 
>> sage: R. = QQ[]
>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>> sage: test = I.gen(0) + x2*I.gen(1)
>> sage: (test + 1).lift( I )
>> [0, 0]   # this is correct
> 
> No it isn't, the correct output would be ValueError, as (test+1) is
> not in I. So this is a bug in the "lift" method.
> 
>> 
>> sage: R. = QQ[]
>> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
>> sage: test = I.gen(0) + x2*I.gen(1)
>> sage: (test).lift( I )
>> [0, 0]   # this is WRONG !!! should be [1, x2]
>> 
>> It looks like this could be a caching issue, so I am not sure whether I need 
>> to open a new ticket for this, or if it is already "catch" by an 
>> already-opened ticket.
> 
> It is some kind of corruption triggered by the abovementioned bug, so
> it may vanish when that bug is fixed.
> 
> Here is a shortened version of your input:
> 
> sage: R. = QQ[]
> sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
> sage: test = I.gen(0) + x2*I.gen(1)
> sage: test.lift(I) # correct
> [1, x2]
> sage: (test+1).lift(I) # invalid input, should give error
> [0, 0]
> sage: test.lift(I) # incorrect
> [0, 0]
> 
> 
> 
>> 
>> *) Segfault
>> 
>> The same kind of problem allows a small piece of code to cause segfaults in 
>> SAGE (apparently in singular-related stuff) :
>> 
>> sage: R. = QQ[]
>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
>> sage: 1 / S(x1 + x2)# should raise NotImplementedError
>> sage:
>> sage: R. = QQ[]
>> sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
>> sage: S.is_integral_domain()
>> 
>> ---> BOOM
>> 
>> *) bizarre output of p.lift(….)
>> 
>> When R is a Polynomial Ring, I is an ideal of R, and p is a polynomial of I, 
>> then p.lift( I ) returns a polynomial combination of a (groebner) basis of I 
>> which is equal to p. However, when p is not in I, then p.lift( I ) returns 
>> [0,0,…,0]. I find this a bit strange. Should p.lift(…) raise an exception 
>> instea

[sage-devel] Bits and pieces about Quotient Rings

[Charles Bouillaguet]

Hi all,

While playing with the quotient of a polynomial ring with an ideal, I 
encountered several glitches.

*) Trying to compute the inverse of something which is not invertible. 

I know it is kind of weird to try this. However, it raises a 
NotImplementedError exception, instead of something more informative such as 
NonInvertible or whatever. I am willing to patch this, but could someone tell 
me what is the correct exception to raise? 

*) Non-deterministic output of some (presumably deterministic) functions

Here is an example :

sage: R. = QQ[]
sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
sage: test = I.gen(0) + x2*I.gen(1)
sage: (test).lift( I )
[1, x2] # this is correct

sage: R. = QQ[]
sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
sage: test = I.gen(0) + x2*I.gen(1)
sage: (test + 1).lift( I )
[0, 0]   # this is correct

sage: R. = QQ[]
sage: I = R.ideal(x2**2 + x1 - 2, x1**2 - 1)
sage: test = I.gen(0) + x2*I.gen(1)
sage: (test).lift( I )
[0, 0]   # this is WRONG !!! should be [1, x2]

It looks like this could be a caching issue, so I am not sure whether I need to 
open a new ticket for this, or if it is already "catch" by an already-opened 
ticket.

*) Segfault

The same kind of problem allows a small piece of code to cause segfaults in 
SAGE (apparently in singular-related stuff) : 

sage: R. = QQ[]
sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
sage: 1 / S(x1 + x2)# should raise NotImplementedError
sage:
sage: R. = QQ[]
sage: S = R.quotient_ring( R.ideal(x2**2 + x1 - 2, x1**2 - 1) )
sage: S.is_integral_domain()

---> BOOM

*) bizarre output of p.lift(….)

When R is a Polynomial Ring, I is an ideal of R, and p is a polynomial of I, 
then p.lift( I ) returns a polynomial combination of a (groebner) basis of I 
which is equal to p. However, when p is not in I, then p.lift( I ) returns 
[0,0,…,0]. I find this a bit strange. Should p.lift(…) raise an exception 
instead? This would be a change of specification, so I guess it should be 
discussed first…




---
Charles Bouillaguet
http://www.lifl.fr/~bouillaguet/



-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] Cython chokes on Matrix class cimport (M4RI problem ?)

[Charles Bouillaguet]

Hi all,

I triggered a problem by writing a very simple python file, which only contains 
one line : 


from sage.matrix.matrix_mod2_dense cimport Matrix_mod2_dense


then, inside sage, running 

sage: load "mini_problem.spyx"

raises an error : 

sage: load "mini_problem.spyx"
Compiling ./mini_problem.spyx...
Error compiling cython file:
Error compiling ./mini_problem.spyx:
running build
running build_ext
building '_Users_cbouilla_Desktop_svn_eurocrypt_mini_problem_spyx_9' extension
gcc -fno-strict-aliasing -fwrapv -DNDEBUG -g -fwrapv -O3 -Wall 
-Wstrict-prototypes -I/Users/cbouilla/Desktop/sage-5.3/local/include/csage/ 
-I/Users/cbouilla/Desktop/sage-5.3/local/include/ 
-I/Users/cbouilla/Desktop/sage-5.3/local/include/python2.7/ 
-I/Users/cbouilla/Desktop/sage-5.3/local/lib/python2.7/site-packages/numpy/core/include
 -I/Users/cbouilla/Desktop/sage-5.3/devel/sage/sage/ext/ 
-I/Users/cbouilla/Desktop/sage-5.3/devel/sage/ 
-I/Users/cbouilla/Desktop/sage-5.3/devel/sage/sage/gsl/ -I. 
-I/Users/cbouilla/Desktop/sage-5.3/local/include/python2.7 -c 
_Users_cbouilla_Desktop_svn_eurocrypt_mini_problem_spyx_9.c -o 
build/temp.macosx-10.7-x86_64-2.7/_Users_cbouilla_Desktop_svn_eurocrypt_mini_problem_spyx_9.o
 -w -O2

In file included from 
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h:46:0,
from 
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzp.h:31,
from 
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/m4ri.h:56,
from 
_Users_cbouilla_Desktop_svn_eurocrypt_mini_problem_spyx_9.c:283:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/debug_dump.h: In function 
‘calculate_hash’:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/debug_dump.h:34:3: error: 
‘for’ loop initial declarations are only allowed in C99 mode
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/debug_dump.h:34:3: note: 
use option -std=c99 or -std=gnu99 to compile your code
In file included from 
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzp.h:31:0,
from 
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/m4ri.h:56,
from 
_Users_cbouilla_Desktop_svn_eurocrypt_mini_problem_spyx_9.c:283:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h: In function 
‘_mzd_row_swap’:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h:410:5: error: ‘for’ 
loop initial declarations are only allowed in C99 mode
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h: In function 
‘mzd_row_swap’:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h:447:5: error: ‘for’ 
loop initial declarations are only allowed in C99 mode
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h: In function 
‘mzd_hash’:
/Users/cbouilla/Desktop/sage-5.3/local/include/m4ri/mzd.h:1396:3: error: ‘for’ 
loop initial declarations are only allowed in C99 mode
error: command 'gcc' failed with exit status 1

Is this a local problem ?

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] running .spyx files

[Charles Bouillaguet]

Dear all,

I have a sage file (let us call it foo.sage), that sage runs finely : 

./sage foo.sage

--> OK

then, if I ever wanted to "cythonize" it (for greater speed), things start to 
go wrong

mv foo.sage foo.spyx
./sage foo.spyx

-->

Traceback (most recent call last):
  File "/Users/cbouilla/Desktop/sage-5.3/local/bin/sage-sagex", line 5, in 

from sage.misc.interpreter import load_sagex
ImportError: cannot import name load_sagex

Is this normal ? Am I doing something wrong ? This happens on sage 5.3 freshly 
compiled from source without apparent problem on Mac Os 10.7.5

Thanks,
--
Charles Bouillaguet

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] the new SHA-3 candidate Keccak uses Sage during its design

[Charles Bouillaguet]

On Oct 3, 2012, at 9:26 AM, Jeroen Demeyer wrote:

> On 2012-10-03 09:07, Minh Nguyen wrote:
>> Hi folks,
>> 
>> Two pieces of good news today:
>> 
>> * The new SHA-3 candidate has been announced following a five-year
>> period of intense scrutiny.
>> 
>> * The winner is Keccak, whose authors used Sage in the design of the 
>> algorithm.
> ...and again, just like AES, the competition was won by a team of
> (mostly?) Belgians!

Including one of the designers of the AES, (probably) the most widely used 
secret-key encryption scheme.

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

Re: [sage-devel] Re: Normalization of a vector

[Charles Bouillaguet]

On Sep 22, 2012, at 11:12 AM, Volker Braun wrote:

> On Saturday, September 22, 2012 2:11:08 AM UTC+1, Travis Scrimshaw wrote:
> normal_form() is good, and to be standard with the other code packages I've 
> seen, dividing by the L2-norm should be normalize().
> 
> As Robert pointed out, normalize() is bad because the name implies that the 
> vector is mutated (which is not what the method does). It should have been 
> normalization() from the start.
> 
> So the updated proposal is:
> 1) deprecate normalize() and point to normalization() and normal_form()
> 2) normalization() is division by L2-norm
> 3) normal_form() is the old normalize()
> 4) alias norm() -> normalization() to save typing

Isn't v.norm() supposed to denote the… norm of v ? (the docstring says that by 
default it is the L2 norm). I would find it quite confusing that v.norm() 
returns a vector instead of the norm itself (a scalar)

Charles

-- 
You received this message because you are subscribed to the Google Groups 
"sage-devel" group.
To post to this group, send email to sage-devel@googlegroups.com.
To unsubscribe from this group, send email to 
sage-devel+unsubscr...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel?hl=en.

[sage-devel] 5.3.beta-1 does not start

[Charles Bouillaguet]

ages/IPython/ipstruct.py", 
line 17, in 

from IPython.genutils import list2dict2
  File 
"/home/charles/Downloads/sage-5.3.beta1-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/IPython/genutils.py", 
line 53, in 

from IPython.external.path import path
  File 
"/home/charles/Downloads/sage-5.3.beta1-sage.math.washington.edu-x86_64-Linux/local/lib/python2.7/site-packages/IPython/external/path.py", 
line 35, in 

import md5
  File 
"/home/charles/Downloads/sage-5.3.beta1-sage.math.washington.edu-x86_64-Linux/local/lib/python/md5.py", 
line 10, in 

from hashlib import md5
ImportError: cannot import name md5


--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] CTRL-C crashes the notebook in 5.2

[Charles Bouillaguet]

Hi William and all,

> I don't see this on OS X with a fresh 5.2 build.  You might want to

give more system details -- in particular, did you build from source
or install a binary?


I am running ubuntu 12.04 (64bits), and I installed the right binary...

--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] CTRL-C crashes the notebook in 5.2

[charles Bouillaguet]

Hi,

while the notebook runs, hitting CTRL-C in the sage shell makes it go
into a SEGFAULT


charles@samsung:~$ sage
--
| Sage Version 5.2, Release Date: 2012-07-25 |
| Type "notebook()" for the browser-based notebook interface.|
| Type "help()" for help.|
--
sage: notebook()
The notebook files are stored in: sage_notebook.sagenb
**
**
* Open your web browser to http://localhost:8080 *
**
**
2012-07-31 16:26:38+0200 [-] Log opened.
2012-07-31 16:26:38+0200 [-] twistd 12.1.0
(/usr/local/sage/local/bin/python 2.7.3) starting up.
2012-07-31 16:26:38+0200 [-] reactor class:
twisted.internet.epollreactor.EPollReactor.
2012-07-31 16:26:38+0200 [-] QuietSite starting on 8080
2012-07-31 16:26:38+0200 [-] Starting factory <__builtin__.QuietSite
instance at 0x62a9b90>
^C
2012-07-31 16:26:56+0200 [-] Quitting all running worksheets...
2012-07-31 16:26:56+0200 [-] Saving notebook...
2012-07-31 16:26:56+0200 [-] Notebook cleanly saved.
2012-07-31 16:26:56+0200 [-] (TCP Port 8080 Closed)
2012-07-31 16:26:56+0200 [-] Stopping factory <__builtin__.QuietSite
instance at 0x62a9b90>
2012-07-31 16:26:56+0200 [-] Main loop terminated.
2012-07-31 16:26:56+0200 [-] Server Shut Down.
/usr/local/sage/local/lib/libcsage.so(print_backtrace+0x31)[0x7f5f245c916a]
/usr/local/sage/local/lib/libcsage.so(sigdie+0x14)[0x7f5f245c919c]
/usr/local/sage/local/lib/libcsage.so(sage_signal_handler+0x216)[0x7f5f245c8d56]
/lib/x86_64-linux-gnu/libpthread.so.0(+0xfcb0)[0x7f5f2a9f5cb0]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x1c)[0x7f5f2a6ac02c]
/usr/local/sage/local/lib/libcsage.so(+0xa2a9)[0x7f5f245c92a9]
/usr/local/sage/local/lib/libcsage.so(sage_mpir_free+0x1c)[0x7f5f245c9355]
/usr/local/sage/local/lib/libgivaro.so.0(_ZN7IntegerD2Ev+0x18)[0x7f5f11664b1c]
/usr/local/sage/local/lib/libgivaro.so.0(_ZN8RationalD2Ev+0x1d)[0x7f5f1166f0bd]
/lib/x86_64-linux-gnu/libc.so.6(+0x3b921)[0x7f5f2a664921]
/lib/x86_64-linux-gnu/libc.so.6(+0x3b9a5)[0x7f5f2a6649a5]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf4)[0x7f5f2a64a774]
python[0x400661]


Unhandled SIGSEGV: A segmentation fault occurred in Sage.
This probably occurred because a *compiled* component of Sage has a bug
in it and is not properly wrapped with sig_on(), sig_off(). You might
want to run Sage under gdb with 'sage -gdb' to debug this.
Sage will now terminate.

Segmentation fault (core dumped)
True
sage:


Is this bug specific to me ?

Charles

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] Re: gmp build failure in sage...

[Charles Bouillaguet]

Hi,

On 07/28/2012 03:33 PM, leif wrote:

Frankly speaking I'm somewhat surprised that you *expect* that
optional GMP spkg to work (with newer versions of Sage) -- it's
completely outdated, and AFAIK many spkgs meanwhile won't work with
that very old version anyway.


In fact, I just assumed that SAGE was relying on GMP (because of the 
-lgmp flags all over during compilation). I just realized my mistake and 
the whole MPIR vs GMP mess.


Best wishes,
--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] Re: Problems building farey_symbol.pyx on Cygwin

[Charles Bouillaguet]

I'm not using Windows, but I share your excitement :)

Charles

On 07/27/2012 03:39 PM, Jean-Pierre Flori wrote:




Tada!

On Friday, July 27, 2012 3:23:41 PM UTC+2, Jean-Pierre Flori wrote:



On Friday, July 27, 2012 3:19:38 PM UTC+2, Jean-Pierre Flori wrote:

As in #12104, libntl.dll could not be found.
Is it because it was moved rather than copied to libntl.dll.a
in #9050?

And I can now start Sage!
I don't seem to suffer from #11551.

--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at 
http://groups.google.com/group/sage-devel

URL: http://www.sagemath.org





--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Re: gmp build failure in sage...

[charles Bouillaguet]

This seems awfully similar to #490, i.e. a very old bug. Why is this
happening again, with recent gcc and gmp?

Charles

2012/7/26 charles Bouillaguet :
> Hi all,
>
> I am experiencing an annoying compilation failure under ubuntu 12.04, 64-bits.
>
> sage -f gmp produces this :
>
>
> Making all in cxx
> make[2]: entrant dans le répertoire «
> /home/charles/sage-5.2.rc1/spkg/build/gmp-4.2.1.p10/src/cxx »
> /bin/bash ../libtool --mode=compile g++ -DHAVE_CONFIG_H -I. -I. -I..
> -D__GMP_WITHIN_GMPXX -I.. -c -o isfuns.lo isfuns.cc
> mkdir .libs
>  g++ -DHAVE_CONFIG_H -I. -I. -I.. -D__GMP_WITHIN_GMPXX -I.. -c
> isfuns.cc  -fPIC -DPIC -o .libs/isfuns.o
> In file included from isfuns.cc:25:0:
> ../gmp.h:515:12: error: 'std::FILE' has not been declared
> make[2]: *** [isfuns.lo] Erreur 1
>
>
> The error seems very weird...
>
> g++ is gcc 4.6.3
>
> Any hints ?
> 
> Charles

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] gmp build failure in sage...

[charles Bouillaguet]

Hi all,

I am experiencing an annoying compilation failure under ubuntu 12.04, 64-bits.

sage -f gmp produces this :


Making all in cxx
make[2]: entrant dans le répertoire «
/home/charles/sage-5.2.rc1/spkg/build/gmp-4.2.1.p10/src/cxx »
/bin/bash ../libtool --mode=compile g++ -DHAVE_CONFIG_H -I. -I. -I..
-D__GMP_WITHIN_GMPXX -I.. -c -o isfuns.lo isfuns.cc
mkdir .libs
 g++ -DHAVE_CONFIG_H -I. -I. -I.. -D__GMP_WITHIN_GMPXX -I.. -c
isfuns.cc  -fPIC -DPIC -o .libs/isfuns.o
In file included from isfuns.cc:25:0:
../gmp.h:515:12: error: 'std::FILE' has not been declared
make[2]: *** [isfuns.lo] Erreur 1


The error seems very weird...

g++ is gcc 4.6.3

Any hints ?

Charles

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] libssl-dev required to build 5.2rc1

[charles Bouillaguet]

Hi all,

I am currently trying to compile 5.2rc1, and the process failed (while
doing the notebook), complaining that I lacked ssl.h (I am running a
quite fresh ubuntu 12.04). After a quick search I installed
libssl-dev, and this was enough to solve the problem. Ergo, either
this extra dependency ought to be advertized, or there is something
wrong with me...

Cheers,
--
Charles Bouillaguet

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] How to... get 5.2rc0 ?

[charles Bouillaguet]

>> The command
>>
>> $ sage -upgrade
>
> More specifically:
>
> sage --upgrade http://boxen.math.washington.edu/home/release/sage-5.2.rc0/

This is getting closer!

Downloading packages from
'http://boxen.math.washington.edu/home/release/sage-5.2.rc0//spkg'.
Reading package lists
404 Error: Package server
'http://boxen.math.washington.edu/home/release/sage-5.2.rc0//spkg' not
found.
Abort.

the // is not the cause of the problem

:(

Charles

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] How to... get 5.2rc0 ?

[charles Bouillaguet]

Hi all,

I know this must sound like a pretty stupid question, but how do I get
sage 5.2rc0, if only just to rebase a patch I wrote for an earlier
version against it? There must be something obvious I'm missing...

Thanks,
---
Charles Bouillaguet

-- 
-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] vote required for (small) backward incompatible change

[Charles Bouillaguet]

BEFORE:

namely, the 0 polynomial has one monomial, which is not a monomial, but
the zero of the ground ring.

AFTER:

the result will be given by the empty list, which is the only sensible
result.


I am 100% with the proposed change. Zero shouldn't be a monomial.

---
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/


--
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: Re: [sage-devel] Re: GL( N,GF(p) ).random_element() is slow

[charles Bouillaguet]

Opening a ticket with a patch, then...

Charles

2012/7/3 Dima Pasechnik :
>
>
> On Tuesday, 3 July 2012 21:20:16 UTC+8, Martin Albrecht wrote:
>>
>>
>> On Tuesday 03 Jul 2012, Dima Pasechnik wrote:
>> > On Tuesday, 3 July 2012 19:55:54 UTC+8, Javier López Peña wrote:
>> > > On Tuesday, July 3, 2012 10:53:23 AM UTC+1, Dima Pasechnik wrote:
>> > >> well, it's not that small, especially for finite fields. E.g. for F_2
>> > >> and n=3, one only gets 168 invertible matrices out of 512=2^9 in
>> > >> total... (I can't resist saying that the order of GL(n,q) is
>> > >> (q^n-1)(q^{n-1}-1)...(q^2-1)(q-1))
>> > >> So it's not gonna be very fast, also note that computing the
>> > >> determinant
>> > >> comes at a nonzero cost when matrices are big...
>> > >
>> > > I stand corrected. Even in the worst case scenario (with F_2) it still
>> > > seems that about one in three matrices is invertible,
>> >
>> > no. As n grows, the ratio gets much, much worse: e.g. for n=2, q=2:
>> >
>> > sage:
>> >
>> > float((2^10-1)*(2^9-1)*(2^8-1)*(2^7-1)*(2^6-1)*(2^5-1)*(2^4-1)*7*3/2^100)
>> > 8.215872026646278e-15
>> >
>> > It's asymptotically 0, as is not hard to see, just look at the behaviour
>> > of
>> > the dominating sequence
>> > q^n q^{n-1}... q^2 q/q^{n^2}
>>
>> This analysis doesn't seem right:
>>
>> sage: j = 0
>> sage: for i in range(100):
>> A = random_matrix(GF(2),1,1)
>> if A.rank() == 1:
>> j+=1
>> :
>> sage: j
>> 25
>
>
> oops, wrong formula. Jetlag got me :–(
> It should have been
> |GL(n,q)}=(q^n-1)(q^n-q)(q^n-q^2)...(q^n-q^{n-2})(q^n-q^{n-1})
>
> Indeed, you're right, it's a finite limit, and taking
> a random matrix and checking its rank will do just fine.
>
> Dima
>>
>>
>> Indeed, the *probability* that a *random* binary matrix has full rank is
>> prod(1-2^i for i in range(1,infinity)) ~= 0.288.
>>
>> > > so the situation is not too bad.  Also, there is no need to compute
>> > > the
>> > > determinants, knowing if the rank is full or not is enough.
>> >
>> > sure, but for F_2 rank and determinant are essentially equal problems
>> > :–)
>> >
>> > > So my point is: even if not *very* fast, still seems faster than what
>> > > we
>> > > have now, and it is very easy to implement while we think of a better
>> > > solution.
>> >
>> > well, pseudorandom field element generation is not very cheap, and
>> > generating "good" pseudorandom elements got be be expensive, otherwise
>> > some (generally believed to be true) conjectures of complexity theory
>> > would
>> > fail.
>> >
>> > No, it's not the way to go, unless n is very small: see above.
>> >
>> > Dima
>> >
>> > > Javier
>>
>> Cheers,
>> Martin
>>
>> --
>> name: Martin Albrecht
>> _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
>> _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF
>> _www: http://martinralbrecht.wordpress.com/
>> _jab: martinralbre...@jabber.ccc.de
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] Re: GL( N,GF(p) ).random_element() is slow

[charles Bouillaguet]

> Mhh, why not? If A = LUP we just write AP^-1  = LU, hence for each LU we
> construct there are as many As as there are permutation matrices, or am I
> missing something (again :))?

I am not sure that the LUP decomposition is unique (I understand that
the LU is). If A has more distinct LUP factorizations than B, then A
is more likely to be produced by this process than B

Charles

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] GL( N,GF(p) ).random_element() is slow

[charles Bouillaguet]

Hi,

I was wondering why some of my code was Dawn Slow (tm), and I ended up
being surprised to notice that it was spending all its time trying to
generate a random invertible matrix In particular, over finite
fields, GL(N, GF(q)).random_element() is MUCH MUCH MUCH slower than
the naive method that just generates a random matrix, checks if it is
invertible, and tries again if it is not the case


sage: %time GL(64, GF(2)).random_element()
CPU times: user 20.47 s, sys: 2.64 s, total: 23.11 s
Wall time: 28.93 s

--> 30s is not a reasonable performance to generate a small random
invertible matrix

By the way, this fails with large primes.

%time GL(64, GF(2^127-1)).random_element()

TypeError: Unable to convert Gap element 'ZmodpZObj(
152551219330529388046437174479921365258,
170141183460469231731687303715884105727 )'
error coercing to finite field

I would suggest overloading GL(N, K).random_element() with the naive
procedure when K is a finite field.

def faster_random_invertible_matrix(n,K):
S = matrix(K,n)
while not S.is_invertible():
S = MatrixSpace(K,n,n).random_element()
return S


sage: %timeit faster_random_invertible_matrix(64, GF(2))
125 loops, best of 3: 1.8 ms per loop

---> this is about 15000 times faster

How do you feel about this ? It's not a bug stricto sensu, but
math-oriented people might stumble across GL(N,K).random_element() and
try to use it even is a much faster solution is available.
--
Charles Bouillaguet

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] New optional spkg

[Charles Bouillaguet]

On 06/25/2012 07:00 PM, Martin Albrecht wrote:

It is interesting to have such an algorithm in sage, because despite
being simple, it is asymptotically faster than the computation of a
Groebner basis


Can you elaborate on the asymptotically faster bit? IIRC the leading constant
for GB computations is less than 1 for quadratic systems, but it seems to be 1
for exhaustive search?


I had in Mind Magali Bardet's PhD thesis (unfortunately it's in 
french...), where she computes the number of elementary operations 
needed to compute a GB of n generic quadratic equations with the 
matrix-F5 algorithm. She finds something of order 2^{4.3n}, regardless 
of the field [thm 3.4.3, page 75].


If you take field equations into account, then you will have something a 
bit lower, but not very much lower. In any case, she proves (p82) that 
you have to go up to degree :


Dreg \approx 0.09n + n^{1/3} - 1.58 + o(1),

So for instance with n=64, that makes D=10, and your matrix has size 
2^37 (approximately). You can hardly deal with this is less than 2^64 
operations...


--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] Re: New optional spkg

[Charles Bouillaguet]

On 06/25/2012 05:09 PM, Harald Schilly wrote:



On Monday, June 25, 2012 2:24:48 PM UTC+2, bouillaguet wrote:

I propose the spkg to
become optional.


Hi, I would put it into "experimental", not "optional".



Does it run on all systems (since it is optimized C)? and also, since
you describe it as experimental with limitations.


Well, the ./configure script detect whether it is dealing with an intel 
CPU with SSE instructions, and if so it enables the compilation of a 
special version of the code, but there is a fallback in plain C that 
should work everywhere (altough I did not really had a chance to test on 
exotic/non-x86 machines). At least I would like it to!


I have no objection to putting the spkg into "experimental" though. I am 
however pretty clueless regarding the next steps to take.


--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] New optional spkg

[charles Bouillaguet]

Dear all,

I just packed a new spkg for SAGE called "fes". It contains an very
efficient C implementation of a procedure that solves systems of
Boolean Equations by exhaustive search ("fes" = Fast Exhaustive
Search). The algorithm itself, whose complexity is about d*2^n for
degree-d equations in n boolean variables, is described in the article
"Fast Exhaustive Search for Polynomial Systems in GF(2)" (CHES'10).
Note that this is an improvement over naive exhaustive procedures
whose complexity is n^d * 2^n.

It is interesting to have such an algorithm in sage, because despite
being simple, it is asymptotically faster than the computation of a
Groebner basis, even with efficient datastructures such as PolyBoRi,
except in special cases (e.g. HFE public keys). This particular
implementation in fes is particularly efficient, as it is capable (in
the good cases) of testing each candidate solution in a bit less than
one CPU cycle (shameless advertisement : an additional 3x speedup is
announced).

The "fes" library is still in a early stage and suffers several
limitations : so far only quadratic equations are supported, the
number of equations is limited to 32, and only one core can be used.
These restrictions will be removed in future releases (in principle
this summer).

You can get the spkg here :
http://www.di.ens.fr/~bouillaguet/fes-0.1.spkg and a patch that adds
an interface to sage here :
http://www.di.ens.fr/~bouillaguet/fes.patch

After installing the spkg and applying the patch, a fes module becomes
available, with an exhastive_search() function. After you apply the
patches of #13155 and #13155, the .variety() function should work on
ideals of BooleanPolynomial's, and you can check that exhaustive
search is indeed the way to go :

sage: K = GF(2)
sage: n = 16
sage: R = BooleanPolynomialRing(n, 'x')
sage: Ps = [   sum([ R.gen(i)*R.gen(j) * K.random_element() for i in
range(n) for j in range(n) ]) \
 + sum([ R.gen(i) * K.random_element() for i in range(n)
]) + K.random_element() for k in range(n) ]
sage: time V = exhaustive_search( Ps )
...
Time: CPU 0.02 s, Wall: 0.02 s

# and now with a GB computation

sage: I = R.ideal( Ps )
sage: time V = I.variety()
...
Time: CPU 4.28 s, Wall: 4.29 s


Ideally, the functionality offered by the fes library should be
accessible with an argument to the .variety() function of
BooleanPolynomialIdeal's. In the meanwhile, I propose the spkg to
become optional.

Thanks !
--
Charles Bouillaguet
http://www.di.ens.fr/~bouillaguet/

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[sage-devel] Detecting inheritance problems ?

[charles Bouillaguet]

Hi all,

I am currently working with the polybori interface in sage, and I
already filled several tickets that all have the same origin.

The class BooleanPolynomial (resp. BooleanPolynomialIdeal) inherits
MPolynomial (resp. MPolynomialIdeal) and redefines some of the
methods. The problem is that some other methods (dimension(),
variety(); etc.) are not implemented and thus rely on the "generic"
code in MPolynomial. However, these methods break badly when invoked
on BooleanPolynomial objects :

MPolynomialIdeal.variety() --> works
BooleanPolynomialIdeal.variety() --> same code, but fails

MPolynomialIdeal.dimension() --> works
BooleanPolynomialIdeal.dimension() --> same code, but fails

To actually fix these problems, we need to write specialized versions
of the generic functions (e.g.BooleanPolynomialIdeal.dimension()
should always return 0). One anyoing problem is that it seems that we
have no way to test for this kind of bugs, because we cannot have a
docstring for a method that is *NOT* implemented

Did this situation occur already ? (How) was it handled ?

Cheers,
--
Charles Bouillaguet

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

Re: [sage-devel] sage 5.0.1 build failure on fedora-17

[charles Bouillaguet]

Hi,

I also had a build failure for sage 5.0.1, also when building gcc, but
the bug looks different (see error message below). I am running ubuntu
12.04. I was surprised sage wanted to compile gcc, as I have an
up-to-date version, but it turns out sage wants a fortran compiler. I
read the f###ing manual too fast and did not install gfortran myself
using the package manager, so sage decided to build its own.

gcc -c   -O0 -DIN_GCC   -W -Wall -Wwrite-strings -Wcast-qual
-Wstrict-prototypes -Wmissing-prototypes -Wmissing-format-attribute
-pedantic -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings
-Wold-style-definition -Wc++-compat -fno-common  -DHAVE_CONFIG_H -I.
-I. -I../../src/gcc -I../../src/gcc/. -I../../src/gcc/../include
-I../../src/gcc/../libcpp/include
-I/home/cbouilla/sage-5.0.1/local/include
-I/home/cbouilla/sage-5.0.1/local/include
-I/home/cbouilla/sage-5.0.1/local/include
-I../../src/gcc/../libdecnumber -I../../src/gcc/../libdecnumber/bid
-I../libdecnumber../../src/gcc/except.c -o except.o
 from ../../../src/libgcc/../gcc/tsystem.h:87,
 from ../../../src/libgcc/../gcc/libgcc2.c:29:
/usr/include/features.h:324:26: fatal error: bits/predefs.h: No such
file or directory
compilation terminated.
make[5]: *** [_muldi3.o] Error 1

Installing gfortran apparently solves the problem... but there is
still something a bit woing

Cheers,
---
Charles
http://www.di.ens.fr/~bouillaguet/

2012/6/20 john_perry_usm :
> Hello
>
> I encountered a build failure for 5.0.1 when building gcc (of all things).
> Error message (somewhat truncated) below. Apparently, it wants me to install
> libopcodes.
>
> This is an Intel Core 2 Quad w/4GB of memory, running Fedora 17.
>
> regards
> john perry
>
> /usr/bin/as: error while loading shared libraries:
> libopcodes-2.21.53.0.1-6.fc16.so: cannot open shared object file: No such
> file or directory
> ...
> 
> Error installing package gcc-4.6.3
> 
> Please email sage-devel (http://groups.google.com/group/sage-devel)
> explaining the problem and including the relevant part of the log file
>   /home/sage-5.0.1/spkg/logs/gcc-4.6.3.log
> Describe your computer, operating system, etc.
>
> --
> To post to this group, send an email to sage-devel@googlegroups.com
> To unsubscribe from this group, send an email to
> sage-devel+unsubscr...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org

-- 
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to 
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org