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.<x,y,z> = 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.
