Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Dima Pasechnik]

On Monday, March 20, 2017 at 11:50:53 PM UTC, Nils Bruin wrote:
>
> On Monday, March 20, 2017 at 3:03:05 PM UTC-7, Dima Pasechnik wrote:
>>
>>
>> surely you can do this, but it seems to be harder to certify if a number 
>> is zero or not.
>>
>
> Exactly. That's the idea of Allan's approach: rather than tracking these 
> questions in characteristic 0, you do it in a finite field of some (large) 
> characteristic. The bet that unequal numbers will have unequal reduction 
> modulo your large modulus will almost certainly hold in practice, and if 
> you track it carefully you know when it fails. THEN you take the hit, lift 
> everything you had to characteristic 0, and use a different modulus. It 
> means you basically never have to work with number field representations, 
> and certainly not run expensive operations such as reducing lattices of 
> algebraic integers.
>  
> Tracking real embeddings only involves tracking some mild inequalities 
> (which can be refined using newton iteration whenever necessary).
>

the idea that you don't need irreducible polynomials and/or polynomial 
factorisation is behind the line of research described in
"Algorithms in Real Algebraic Geometry 
" 
by Basu, Pollack, and Roy. I have not heard anything about using finite 
fields to speed up
what they do (probably because there are no anywhere complete 
implementations of algorithms they describe available).

Dima

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Nils Bruin]

On Monday, March 20, 2017 at 3:03:05 PM UTC-7, Dima Pasechnik wrote:
>
>
> surely you can do this, but it seems to be harder to certify if a number 
> is zero or not.
>

Exactly. That's the idea of Allan's approach: rather than tracking these 
questions in characteristic 0, you do it in a finite field of some (large) 
characteristic. The bet that unequal numbers will have unequal reduction 
modulo your large modulus will almost certainly hold in practice, and if 
you track it carefully you know when it fails. THEN you take the hit, lift 
everything you had to characteristic 0, and use a different modulus. It 
means you basically never have to work with number field representations, 
and certainly not run expensive operations such as reducing lattices of 
algebraic integers.
 
Tracking real embeddings only involves tracking some mild inequalities 
(which can be refined using newton iteration whenever necessary).

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Dima Pasechnik]

On Monday, March 20, 2017 at 9:06:26 PM UTC, William wrote:
>
> On Mon, Mar 20, 2017 at 1:52 PM, Dima Pasechnik  > wrote: 
> >> The original poster is asking only about basic arithmetic and equality 
> >> testing in AA.  Since AA embeds as a subfield of QQbar, a solution to 
> >> these problems in QQbar automatically implies one in AA. 
> >> 
> > Does taking square roots qualify as basic arithmetic? 
>
> Taking roots is the most basic operation of any algorithm for 
> "Computing with algebraically closed fields" since "roots of 
> polynomials" is the only meaningful way in general to define elements 
> of an algebraic closure. 
>

Sure, but you do not "take" square roots, i.e. you do not specify an 
embedding,
if you compute in an algebraically closed field.
Trouble starts when you have to pick up a root, as happens here
(unlike in the algebraically closed case).
 

>
> Noting Nils' remark: 
>
>  >> If an embedding in CC or RR is required, it could be tracked with just 
> >> numerical information. 
>
> one sees that one can track all numbers involved to some floating 
> point precision.   With that, you can tell with a real number is 
> positive or negative, after which taking square roots is possible. 
>

surely you can do this, but it seems to be harder to certify if a number is 
zero or not.
It's a classical story that it's harder in general to figure out whether a 
system
of polynomial equations has a real root, as opposed to it having a root. 
Effectively
here you are checking that the following system has real solutions: 

a^4=5, s^2=13, c=a+r,
r^2=(s-a)^2+3, 2ac=c^2-r^2+a^2.

It is easy in this case by eliminating variables in a good order, but hard 
if one does something dumb,
and has to do real root isolation and substitution, etc etc.

(perhaps number theorists know better, though...)

>
>
>  -- William 
>

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[William Stein]

On Mon, Mar 20, 2017 at 1:52 PM, Dima Pasechnik  wrote:
>> The original poster is asking only about basic arithmetic and equality
>> testing in AA.  Since AA embeds as a subfield of QQbar, a solution to
>> these problems in QQbar automatically implies one in AA.
>>
> Does taking square roots qualify as basic arithmetic?

Taking roots is the most basic operation of any algorithm for
"Computing with algebraically closed fields" since "roots of
polynomials" is the only meaningful way in general to define elements
of an algebraic closure.

Noting Nils' remark:

 >> If an embedding in CC or RR is required, it could be tracked with just
>> numerical information.

one sees that one can track all numbers involved to some floating
point precision.   With that, you can tell with a real number is
positive or negative, after which taking square roots is possible.


 -- William

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Dima Pasechnik]

On Monday, March 20, 2017 at 8:04:04 PM UTC, William wrote:
>
> On Mon, Mar 20, 2017 at 12:48 PM, Dima Pasechnik  > wrote: 
> > 
> > 
> > On Monday, March 20, 2017 at 3:06:28 PM UTC, Nils Bruin wrote: 
> >> 
> >> On Monday, March 20, 2017 at 5:49:24 AM UTC-7, Jeroen Demeyer wrote: 
> >>> 
> >>> I believe that this is simply https://trac.sagemath.org/ticket/15600 
> >>> 
> >>> The variable d lies in a number field of degree 32, which is rather 
> big 
> >>> to call polredbest() on. 
> >> 
> >> If the sage implementation ends up doing this then that's a good 
> >> indication that the approach described in: 
> >> 
> >> Allan K. Steel, Computing with algebraically closed fields, Journal of 
> >> Symbolic Computation, Volume 45, Issue 3, March 2010, Pages 342-372, 
> ISSN 
> >> 0747-7171, http://dx.doi.org/10.1016/j.jsc.2009.09.005. 
> >> 
> >> would really be much better. It would avoid any number field 
> computations. 
> >> If an embedding in CC or RR is required, it could be tracked with just 
> >> numerical information. 
> >> One would use finite fields to track identity. 
> >> If there's such a use for QQbar, it might be interesting to run a 
> project 
> >> in that direction. 
> >> 
> > this is about algebraically closed fields; IMHO real fields are harder. 
>
> The original poster is asking only about basic arithmetic and equality 
> testing in AA.  Since AA embeds as a subfield of QQbar, a solution to 
> these problems in QQbar automatically implies one in AA. 
>
> Does taking square roots qualify as basic arithmetic?

 

> William 
>
>
> -- 
> William (http://wstein.org) 
>

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[William Stein]

On Mon, Mar 20, 2017 at 12:48 PM, Dima Pasechnik  wrote:
>
>
> On Monday, March 20, 2017 at 3:06:28 PM UTC, Nils Bruin wrote:
>>
>> On Monday, March 20, 2017 at 5:49:24 AM UTC-7, Jeroen Demeyer wrote:
>>>
>>> I believe that this is simply https://trac.sagemath.org/ticket/15600
>>>
>>> The variable d lies in a number field of degree 32, which is rather big
>>> to call polredbest() on.
>>
>> If the sage implementation ends up doing this then that's a good
>> indication that the approach described in:
>>
>> Allan K. Steel, Computing with algebraically closed fields, Journal of
>> Symbolic Computation, Volume 45, Issue 3, March 2010, Pages 342-372, ISSN
>> 0747-7171, http://dx.doi.org/10.1016/j.jsc.2009.09.005.
>>
>> would really be much better. It would avoid any number field computations.
>> If an embedding in CC or RR is required, it could be tracked with just
>> numerical information.
>> One would use finite fields to track identity.
>> If there's such a use for QQbar, it might be interesting to run a project
>> in that direction.
>>
> this is about algebraically closed fields; IMHO real fields are harder.

The original poster is asking only about basic arithmetic and equality
testing in AA.  Since AA embeds as a subfield of QQbar, a solution to
these problems in QQbar automatically implies one in AA.

William


-- 
William (http://wstein.org)

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Dima Pasechnik]

On Monday, March 20, 2017 at 3:06:28 PM UTC, Nils Bruin wrote:
>
> On Monday, March 20, 2017 at 5:49:24 AM UTC-7, Jeroen Demeyer wrote:
>>
>> I believe that this is simply https://trac.sagemath.org/ticket/15600 
>>
>> The variable d lies in a number field of degree 32, which is rather big 
>> to call polredbest() on. 
>>
> If the sage implementation ends up doing this then that's a good 
> indication that the approach described in:
>
> Allan K. Steel, Computing with algebraically closed fields, Journal of 
> Symbolic Computation, Volume 45, Issue 3, March 2010, Pages 342-372, ISSN 
> 0747-7171, http://dx.doi.org/10.1016/j.jsc.2009.09.005.
>
> would really be much better. It would avoid any number field computations.
> If an embedding in CC or RR is required, it could be tracked with just 
> numerical information.
> One would use finite fields to track identity.
> If there's such a use for QQbar, it might be interesting to run a project in 
> that direction.
>
> this is about algebraically closed fields; IMHO real fields are harder.
 

>  
>

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Nils Bruin]

On Monday, March 20, 2017 at 5:49:24 AM UTC-7, Jeroen Demeyer wrote:
>
> I believe that this is simply https://trac.sagemath.org/ticket/15600 
>
> The variable d lies in a number field of degree 32, which is rather big 
> to call polredbest() on. 
>
If the sage implementation ends up doing this then that's a good indication 
that the approach described in:

Allan K. Steel, Computing with algebraically closed fields, Journal of Symbolic 
Computation, Volume 45, Issue 3, March 2010, Pages 342-372, ISSN 0747-7171, 
http://dx.doi.org/10.1016/j.jsc.2009.09.005.

would really be much better. It would avoid any number field computations.
If an embedding in CC or RR is required, it could be tracked with just 
numerical information.
One would use finite fields to track identity.
If there's such a use for QQbar, it might be interesting to run a project in 
that direction.

 

-- 
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.

Re: [sage-devel] Re: An "easy looking" computation in AA that sage can't do

[Jeroen Demeyer]

I believe that this is simply https://trac.sagemath.org/ticket/15600

The variable d lies in a number field of degree 32, which is rather big 
to call polredbest() on.


--
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 https://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.