[sage-devel] Re: QQbar benchmarks

[Samuel Lelievre]

Hi Fredrik,

These papers might provide benchmark problems
for QQbar/AA arithmetic which originate in actual
math problems, though not in Sage.

Pierre-Vincent Koseleff, Fabrice Rouillier, Cuong Tran
On the Sign of a Trigonometric Expression
ISSAC’15, July 6–9, 2015, Bath, United Kingdom.
http://dx.doi.org/10.1145/2755996.2756664.

Koseleff, P.-V., Pecker, D., and Rouillier, F.
Computing Chebyshev knot diagrams.
http://arxiv.org/abs/1001.5192

Koseleff, P.-V., Pecker, D., and Rouillier, F.
The first rational Chebyshev knots.
Journal of Symbolic Computation 45 (2010), 1341–1358. 

See Pierre-Vincent Koseleff's publications page:
https://webusers.imj-prg.fr/~pierre-vincent.koseleff/publications.html

There are some interesting algebraic numbers in Theorem 3 of

Shigeki Akiyama
Minimum polyhedron with n vertices
https://arxiv.org/abs/1704.03149

which maybe can also provide benchmark problems.

Happy benchmarking!   --Samuel

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/00e6a3a0-b5de-4a4c-b127-ae582d3b06b2n%40googlegroups.com.

Re: [sage-devel] QQbar benchmarks

[Fredrik Johansson]

On Sunday, April 25, 2021 at 4:26:18 PM UTC+2 vdelecroix wrote:

> Dear Fredrik, 
>
> One technical question: I thought that your ca_t implementation 
> used multivariate polynomials. This is what Magma does but not 
> what sage does. The latter uses expression trees and take union 
> fields anytime there is an exactification to be done. Is it a 
> misconception of mine? 
>
>
> For "real world" problems 
>
> 1) algebraic solutions of zero dimensional varieties 
> defined over QQ 
>
> sage: R. = QQ[] 
> sage: A = x^4 + y^4 + z^3 - 1 
> sage: B = x^2*z + 2*y^2*x - x*y*z + 5 
> sage: C = y*z^2 - 2*(x+y+z) + 2 
> sage: %time solutions = R.ideal([A,B,C]).variety(QQbar) 
> CPU times: user 24.3 s, sys: 23.3 ms, total: 24.3 s 
> Wall time: 24.4 s 
>
> Though here is the bottleneck is Groebner basis computation 
> of multivariate polynomials and not really QQbar (21s over the 24s). 
>

I managed to isolate the final QQbar part of this computation in a way that 
I could benchmark outside of Sage. Results:

sage qqbar: 500 ms
calcium ca: 80 ms
calcium qqbar: ~forever (hours)

What takes forever here is evaluating polynomials with coefficients in Q at 
QQbar arguments, using a generic algorithm (Horner's rule or adding 
powers). This is slow in the minpoly representation, because you get huge 
temporary results which each need to be factored.  You could throw in some 
specialized polynomial evaluation code that generates a number field 
element and then computes the absolute minimal polynomial, but it'd 
essentially be reinventing the number field arithmetic which Sage's QQbar 
and Calcium's ca do automatically.

I'd be interested in some way to improve arithmetic in the minpoly 
representation when the operands lie in the same field (e.g. by quickly 
recognizing such operands using LLL). My earlier attempts to implement such 
hacks were unsuccessful (only slowed things down on examples I tried), but 
perhaps it can make difference here if I get it right.

Fredrik

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/07321bf7-0343-416f-b3c4-383c18838537n%40googlegroups.com.

Re: [sage-devel] Error building deformation and libsemigroups 0.6.7

[Dima Pasechnik]

On Mon, Apr 26, 2021 at 11:11 AM Dima Pasechnik  wrote:
>
> On Mon, Apr 26, 2021 at 10:09 AM Jean-Pierre Flori  wrote:
> >
> > Fix for deformation has been tagged in my fork.
> > And mentioned here:
> > https://trac.sagemath.org/ticket/30325
> > Feel free to package and review.

https://trac.sagemath.org/ticket/30325 is now ready for reviewing.

>
> I've quickly checked, and it appears to just work with modern GMP. See
> https://github.com/jpflori/deformation/pull/3
>
> >
> > Not sure that it supports GMP instead of MPIR (which is also abandonware).
> >
> > Le jeudi 22 avril 2021 à 17:44:39 UTC+2, dim...@gmail.com a écrit :
> >>
> >> errors building libsemigroups should be reported on its github page:
> >>
> >> https://github.com/libsemigroups/libsemigroups
> >>
> >> deformation package, on the other hand is more or less abandonware.
> >>
> >>
> >>
> >> On Thu, 22 Apr 2021, 15:17 Tirthankar Mazumder,  
> >> wrote:
> >>>
> >>> While running make ptestalllong, I was able to build all the packages 
> >>> that it needs except for Deformation. I tried building it many times, but 
> >>> it failed every time. It said
> >>> /usr/bin/ld: -r and -pie may not be used together
> >>> collect2: error: ld returned 1 exit status
> >>>
> >>> I got all the other packages to install, even though in some of them I 
> >>> had to manually go to their download directory (which was in 
> >>> SAGE_ROOT/local/var/tmp/sage/build/) and edit the Makefile. The reason 
> >>> for this was, some of the packages (specifically, libsemigroups-0.6.7) 
> >>> output a Makefile with the -march and -mtune flags set for the compiler, 
> >>> but I have an 11th gen Intel processor, so GCC doesn't accept tigerlake 
> >>> or native as a valid flag yet. The Makefile generator for that library 
> >>> (which I believe is GNU AutoTools) should incorporate a check to see if 
> >>> the -march=native flag is available on the target system, like the 
> >>> cryptominisat-5.6.8 package does.
> >>>
> >>> I'm attaching 4 log files: The entire log for for deformation-d05941b.p0, 
> >>> which contains the build output for every single time I tried to build 
> >>> the package, a shortened version of that log file which contains what (I 
> >>> feel) is the relevant portion of that log file, the entire log file of 
> >>> libsemigroups-0.6.7, and a shorter version of the libsemigroups-0.6.7 log 
> >>> file which contains what (I feel) is the relevant portion of that lengthy 
> >>> log file.
> >>>
> >>> P.S. --- I have some experience in building Sage on WSL2, having done it 
> >>> twice (on two different machines), so I want to edit the Sage on Windows 
> >>> page's WSL section, but it appears that you can't use your GitHub-linked 
> >>> Trac account on the Wiki. How would I go about getting an account I can 
> >>> use on the Wiki? I'd prefer having one account to use across 
> >>> trac.sagemath.org and the Wiki, if that's possible.
> >>>
> >>> Thanks in advance,
> >>> Tirthankar
> >>>
> >>> --
> >>> 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+...@googlegroups.com.
> >>> To view this discussion on the web visit 
> >>> https://groups.google.com/d/msgid/sage-devel/f1184a5e-d6d4-4247-ad07-703de70a6fefn%40googlegroups.com.
> >
> > --
> > 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 view this discussion on the web visit 
> > https://groups.google.com/d/msgid/sage-devel/136b5fce-5f05-4d78-8bdf-97defa9bfd4bn%40googlegroups.com.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAAWYfq3DDGsBXWJcTGoLZqfGe%2BEQw50ZtxYRYLxueM--gGg9-w%40mail.gmail.com.

Re: [sage-devel] Error building deformation and libsemigroups 0.6.7

[Dima Pasechnik]

On Mon, Apr 26, 2021 at 10:09 AM Jean-Pierre Flori  wrote:
>
> Fix for deformation has been tagged in my fork.
> And mentioned here:
> https://trac.sagemath.org/ticket/30325
> Feel free to package and review.

I've quickly checked, and it appears to just work with modern GMP. See
https://github.com/jpflori/deformation/pull/3

>
> Not sure that it supports GMP instead of MPIR (which is also abandonware).
>
> Le jeudi 22 avril 2021 à 17:44:39 UTC+2, dim...@gmail.com a écrit :
>>
>> errors building libsemigroups should be reported on its github page:
>>
>> https://github.com/libsemigroups/libsemigroups
>>
>> deformation package, on the other hand is more or less abandonware.
>>
>>
>>
>> On Thu, 22 Apr 2021, 15:17 Tirthankar Mazumder,  wrote:
>>>
>>> While running make ptestalllong, I was able to build all the packages that 
>>> it needs except for Deformation. I tried building it many times, but it 
>>> failed every time. It said
>>> /usr/bin/ld: -r and -pie may not be used together
>>> collect2: error: ld returned 1 exit status
>>>
>>> I got all the other packages to install, even though in some of them I had 
>>> to manually go to their download directory (which was in 
>>> SAGE_ROOT/local/var/tmp/sage/build/) and edit the Makefile. The reason for 
>>> this was, some of the packages (specifically, libsemigroups-0.6.7) output a 
>>> Makefile with the -march and -mtune flags set for the compiler, but I have 
>>> an 11th gen Intel processor, so GCC doesn't accept tigerlake or native as a 
>>> valid flag yet. The Makefile generator for that library (which I believe is 
>>> GNU AutoTools) should incorporate a check to see if the -march=native flag 
>>> is available on the target system, like the cryptominisat-5.6.8 package 
>>> does.
>>>
>>> I'm attaching 4 log files: The entire log for for deformation-d05941b.p0, 
>>> which contains the build output for every single time I tried to build the 
>>> package, a shortened version of that log file which contains what (I feel) 
>>> is the relevant portion of that log file, the entire log file of 
>>> libsemigroups-0.6.7, and a shorter version of the libsemigroups-0.6.7 log 
>>> file which contains what (I feel) is the relevant portion of that lengthy 
>>> log file.
>>>
>>> P.S. --- I have some experience in building Sage on WSL2, having done it 
>>> twice (on two different machines), so I want to edit the Sage on Windows 
>>> page's WSL section, but it appears that you can't use your GitHub-linked 
>>> Trac account on the Wiki. How would I go about getting an account I can use 
>>> on the Wiki? I'd prefer having one account to use across trac.sagemath.org 
>>> and the Wiki, if that's possible.
>>>
>>> Thanks in advance,
>>> Tirthankar
>>>
>>> --
>>> 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+...@googlegroups.com.
>>> To view this discussion on the web visit 
>>> https://groups.google.com/d/msgid/sage-devel/f1184a5e-d6d4-4247-ad07-703de70a6fefn%40googlegroups.com.
>
> --
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/sage-devel/136b5fce-5f05-4d78-8bdf-97defa9bfd4bn%40googlegroups.com.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAAWYfq1GFc0GnLCsgVYMFAh5WbcofcX%2BHq8rf1XRmfP2511trQ%40mail.gmail.com.

Re: [sage-devel] Error building deformation and libsemigroups 0.6.7

[Jean-Pierre Flori]

Fix for deformation has been tagged in my fork.
And mentioned here:
https://trac.sagemath.org/ticket/30325
Feel free to package and review.

Not sure that it supports GMP instead of MPIR (which is also abandonware).

Le jeudi 22 avril 2021 à 17:44:39 UTC+2, dim...@gmail.com a écrit :

> errors building libsemigroups should be reported on its github page:
>
> https://github.com/libsemigroups/libsemigroups
>
> deformation package, on the other hand is more or less abandonware.
>
>
>
> On Thu, 22 Apr 2021, 15:17 Tirthankar Mazumder,  
> wrote:
>
>> While running make ptestalllong, I was able to build all the packages 
>> that it needs except for Deformation. I tried building it many times, but 
>> it failed every time. It said
>> /usr/bin/ld: -r and -pie may not be used together
>> collect2: error: ld returned 1 exit status
>>
>> I got all the other packages to install, even though in some of them I 
>> had to manually go to their download directory (which was in 
>> SAGE_ROOT/local/var/tmp/sage/build/) and edit the Makefile. The reason 
>> for this was, some of the packages (specifically, libsemigroups-0.6.7) 
>> output a Makefile with the -march and -mtune flags set for the compiler, 
>> but I have an 11th gen Intel processor, so GCC doesn't accept tigerlake or 
>> native as a valid flag yet. The Makefile generator for that library 
>> (which I believe is GNU AutoTools) should incorporate a check to see if the 
>> -march=native flag is available on the target system, like the 
>> cryptominisat-5.6.8 package does.
>>
>> I'm attaching 4 log files: The entire log for for deformation-d05941b.p0, 
>> which contains the build output for every single time I tried to build the 
>> package, a shortened version of that log file which contains what (I feel) 
>> is the relevant portion of that log file, the entire log file of 
>> libsemigroups-0.6.7, and a shorter version of the libsemigroups-0.6.7 
>> log file which contains what (I feel) is the relevant portion of that 
>> lengthy log file.
>>
>> P.S. --- I have some experience in building Sage on WSL2, having done it 
>> twice (on two different machines), so I want to edit the Sage on Windows 
>>  page's WSL section, but it 
>> appears that you can't use your GitHub-linked Trac account on the Wiki. How 
>> would I go about getting an account I can use on the Wiki? I'd prefer 
>> having one account to use across trac.sagemath.org and the Wiki, if 
>> that's possible.
>>
>> Thanks in advance,
>> Tirthankar
>>
>> -- 
>> 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+...@googlegroups.com.
>> To view this discussion on the web visit 
>> https://groups.google.com/d/msgid/sage-devel/f1184a5e-d6d4-4247-ad07-703de70a6fefn%40googlegroups.com
>>  
>> 
>> .
>>
>

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/136b5fce-5f05-4d78-8bdf-97defa9bfd4bn%40googlegroups.com.

Re: [sage-devel] QQbar benchmarks

[John Cremona]

+1 for Vincent's zero-dimensional variety point finding.   I used to
use Magma's AlgebraicallyClosedField a lot for this (for some project
which I did before Sage existed).  The idea is to find the points over
Qbar, then construct the absolute field they generate, then find them
again over that field before continuing.  I can imagine a nice Sage
function to do that automatically  including a field_of_definition_of
points method on such a variety.

John

On Sun, 25 Apr 2021 at 23:35, Michael Orlitzky  wrote:
>
> On Sun, 2021-04-25 at 15:07 +0200, Fredrik Johansson wrote:
> > Hi all,
> >
> > I'm looking for benchmark problems for QQbar/AA arithmetic. Ideally such a
> > problem will:
> >
> > * Be reducible to a short program that, apart from using QQbar/AA
> > operations, is reasonably self-contained.
> > * Reflect real-world use, i.e. originate from using Sage to solve an actual
> > mathematical problem, with QQbar/AA arithmetic being a significant
> > ingredient.
>
> I'm interested in Gram-Schmidt and the coordinate_vector() methods that
> solve linear systems over AA.
>
> For a benchmark, you could conjure a set of long vectors with entries
> in AA/QQbar, and orthonormalize them using the kindergarten algorithm
> that everyone knows. That will leave a linearly-independent set, and if
> you keep the input/output indices matched up, will let you know which
> of the input vectors correspond to that linearly independent set. Call
> the set of those input vectors "X". Then to benchmark the
> coordinate_vector() methods, you can generate random elements in
> W=span(X), and solve the system to find their W-coordinates in terms of
> the basis X. (Using the de-orthonormalized vectors as the basis makes
> the system harder to solve, and more representative of the general
> case.)
>
>
> Unimportant background information:
>
> A Euclidean Jordan algebra (EJA) is a real vector space where every
> element "x" has a self-adjoint "left multiplication by x" operation
> that I'll write L_x.
>
> It turns out that every EJA is a mishmash of various Hermitian matrix
> algebras, which is nice, because it lets you think of their elements as
> being some concrete object rather than just an abstract vector space
> element. For example, the space of real symmetric matrices with
>
>   L_x(y) := (xy + yx)/2
>
> induces an EJA. But when people think of a symmetric matrix, they're
> thinking of it in terms of the standard basis, which leads to a
> problem; namely that the basis
>
>   [1 0]  [0 1]  [0 0]
>   [0 0], [1 0], [0 1]
>
> for S^2 is not normalized. This raises a problem: while L_x is always
> self-adjoint, its matrix representation won't be symmetric unless your
> basis is orthonormal. And you need its matrix to be symmetric if you
> want to do anything cool with it in sage, because sage assumes that
> when you have a matrix full of numbers, they're with respect to the
> standard basis.
>
> In short, this means that a sqrt(2) must become involved, and the "2"
> isn't special. Here's where Gram-Schmidt comes in. Afterwards, matrices
> aren't vectors in sage, so converting back and forth between
> matrix/vector representations involves a lot of to_vector() and
> coordinate_vector() over AA.
>
> Things get worse: when constructing a subalgebra, its basis needs to be
> orthonormalized as well, and we need to be able to convert back and
> forth between the orthonormalized superalgebra coordinates and the
> orthonormalized subalgebra coordinates. Thus we wind up
> orthonormalizing vectors that already have ugly entries, and solving
> systems with uglier and uglier entries in AA. This is a bottleneck when
> the algebras get "big," which they do even in simple examples (the
> Albert algebra has dimension 27).
>
>
> --
> 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 view this discussion on the web visit 
> https://groups.google.com/d/msgid/sage-devel/1620f0b7f268a16e477d74f7295d9b1340285604.camel%40orlitzky.com.

-- 
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 view this discussion on the web visit 
https://groups.google.com/d/msgid/sage-devel/CAD0p0K4sFsRNjEQ8aL%2BATfQ5hngik4aonLPX14sRkPdmoFnq0g%40mail.gmail.com.