Performance
frontend
iratrecon - rational reconstruction
sprem - sparse pseudo division
gcdex - extended Euclidean algorithm
Expand, Quo, and, Rem mod p
normal
indets, coeffs, degree, and miscellaneous
solve command and Groebner Bases
The frontend command is used extensively by Maple to map expressions to the domain of rational functions. It was rewritten for Maple 2017 to reduce time and memory usage. The typical gain is a factor of two but for complicated expressions it runs an order of magnitude faster. The example below runs over 30 times faster in Maple 2017.
expr≔randpolysinx,cosx,I:for i to 3 do expr ≔ addrandpolyexpri,i=−3..3; end:timefrontendlength,expr
0.265
The iratrecon command for rational reconstruction has been re-engineered in the kernel to improve performance. The first two examples below run about 9x and 5x faster, respectively. We have also added a new fraction-free syntax that returns true or false and assigns the numerator and denominator to the fifth and sixth arguments. By not constructing fractions, the new syntax gains an additional factor of five speedup.
m ≔ prevprime260⋅nextprime260:f ≔ mulrandpolyi,'dense',i=x,y,z,t,u,v,w:f ≔ Expandfrandmodm:timeiratreconf,m;timeiratreconf,m,scaled
5.116
0.530
b ≔ isqrtiquom,2:timeiratreconf,m,b,b,'n','d' # new syntax
0.124
The sprem command performs sparse fraction-free pseudo division on polynomials. In previous versions of Maple, sprem(f,g,x) would multiply by lcoeff(g,x) in each division step. In Maple 2017, sprem has been changed to compute gcds and use the smallest possible multiplier, allowing it to handle problems of much higher degree with less blowup. When degree(g)=degree(g,x) the command calls a dedicated division routine written in C. The example below runs about 360 times faster, and finds a multiplier that is 19x shorter.
f ≔ randpolyx,degree=10000,terms=102:g ≔ randpolyx,degree=5000,terms=102:timespremf,g,x,'m';lengthm
0.156
225
For univariate polynomials, gcdex now uses a sparse primitive polynomial remainder sequence together with the new code for sprem. For sparse structured problems the new routine is orders of magnitude faster. The example below was previously intractable.
f ≔ 128x203−625591465x196−1379565483492966x189−69051360012922713930x182+503269676439575515122310x175−358607771626419731119489079x168−147952840877635699778667316508x161−1147922766589841137530437873498x154−3283047528072876955188179107557x147−5494471139223382529181506689788x140−6295323446544817875033709377526x133−5439730226339556502298385195313x126−4047134740954486045236505654710x119−2699447938384037396439601445910x112−1005987107212742027676051174393x105+1005987107212742027676051174393x98+2699447938384037396439601445910x91+4047134740954486045236505654710x84+5439730226339556502298385195313x77+6295323446544817875033709377526x70+5494471139223382529181506689788x63+3283047528072876955188179107557x56+1147922766589841137530437873498x49+147952840877635699778667316508x42+358607771626419731119489079x35−503269676439575515122310x28+69051360012922713930x21+1379565483492966x14+625591465x7−128:timegcdex∂∂xf,f,x,'inv'
0.031
Expansion of fk mod p has been optimized in the case where p is a prime and k≥p, using the Frobenius map a+bp =ap+bp. The expansion below previously took a few seconds but is now instantaneous. Quo and Rem have also been improved for multivariate polynomials and the division below runs about 90x faster.
f ≔ Expandx3+yz+z+yy+xz4mod7:g ≔ CodeTools:-UsageExpandf50mod7:
memory used=75.71KiB, alloc change=0 bytes, cpu time=78.00ms, real time=140.00ms, gc time=0ns
r ≔ CodeTools:-UsageRemg,f,x,'q'mod7:
memory used=13.05KiB, alloc change=0 bytes, cpu time=16.00ms, real time=4.00ms, gc time=0ns
Maple 2017 includes a powerful new algorithm for simplifying large multivariate rational expressions using normal. Previous versions of Maple could not do this problem automatically.
unassign'g':
s1 ≔ l2ga223−l1ga12a21a222−l2n22a21a222+l2n11a21a222+2l2ga12a222−l1ga12a222+l2g2a222−l2n11n22a222+l2n11a222+l1n22a12a212a22−l1n11a12a212a22−l2ga212a22−l1ga122a21a22−l2g2a12a21a22−l1g2a12a21a22+l2n11n22a12a21a22+l1n11n22a12a21a22−2l2n22a12a21a22+l1n22a12a21a22+l2n11a12a21a22−2l1n11a12a21a22−l2ga21a22+l2ga122a22−l1ga122a22+l2g2a12a22−l1g2a12a22−l2n11n22a12a22+l1n11n22a12a22+l2n11a12a22−l1n11a12a22+l1ga12a213+l1g2a122a212−l1n11n22a122a212+l1n22a122a212−l2ga12a212+2l1ga12a212−l2g2a122a21+l1g2a122a21+l2n11n22a122a21−l1n11n22a122a21−l2n22a122a21+l1n22a122a21−l2ga12a21+l1ga12a21l2ga12a21a222−l1ga12a21a222−l2n22a21a222+l1n22a21a222+l1l2ga12a222−l1ga12a222−l1l2n22a222+l1n22a222+l2n11a12a212a22−l1n11a12a212a22−l2ga212a22+l1ga212a22−l1l2ga122a21a22+2l2ga122a21a22−l1ga122a21a22+l1l2n22a12a21a22−2l2n22a12a21a22+l1n22a12a21a22+l1l2n11a12a21a22+l2n11a12a21a22−2l1n11a12a21a22−l1l2ga21a22−l2ga21a22+2l1ga21a22+l1l2ga122a22−l1ga122a22−l1l2n22a12a22+l1n22a12a22+l1l2n11a12a22−l1n11a12a22−l1l2ga22+l1ga22−l1l2n11a122a212+l2n11a122a212+l1l2ga12a212−l2ga12a212−l1l2ga123a21+l2ga123a21+l1l2n22a122a21−l2n22a122a21−l1l2n11a122a21+l2n11a122a21+l1l2ga12a21−l2ga12a21:s2 ≔ l2ga12a222−l2n22a222+l2a222−l1ga122a21a22+l1n22a12a21a22+l2n11a12a21a22−l2a12a21a22−l1a12a21a22−l2ga21a22+l2ga122a22−l1ga122a22−l2n22a12a22+l1n22a12a22+l2a12a22−l1a12a22−l1n11a122a212+l1a122a212+l1ga12a212+l2n11a122a21−l1n11a122a21−l2a122a21+l1a122a21−l2ga12a21+l1ga12a21l2ga12a222−ga12a222−l2n22a222+n22a222−l1ga122a21a22+ga122a21a22+l1n22a12a21a22−n22a12a21a22+l2n11a12a21a22−n11a12a21a22−l2ga21a22+ga21a22+l2ga122a22−ga122a22−l2n22a12a22+n22a12a22+l2n11a12a22−n11a12a22−l2ga22+ga22−l1n11a122a212+n11a122a212+l1ga12a212−ga12a212−l1ga123a21+ga123a21+l1n22a122a21−n22a122a21−l1n11a122a21+n11a122a21+l1ga12a21−ga12a21:s3 ≔ l2p21a223−l1p21a12a21a222−l2p22a21a222+l2p11a21a222+2l2p21a12a222−l1p21a12a222−l2p11p22a222+l2p12p21a222+l2p11a222+l1p22a12a212a22−l1p11a12a212a22−l2p12a212a22−l1p21a122a21a22+l2p11p22a12a21a22+l1p11p22a12a21a22−2l2p22a12a21a22+l1p22a12a21a22−l2p12p21a12a21a22−l1p12p21a12a21a22+l2p11a12a21a22−2l1p11a12a21a22−l2p12a21a22+l2p21a122a22−l1p21a122a22−l2p11p22a12a22+l1p11p22a12a22+l2p12p21a12a22−l1p12p21a12a22+l2p11a12a22−l1p11a12a22+l1p12a12a213−l1p11p22a122a212+l1p22a122a212+l1p12p21a122a212−l2p12a12a212+2l1p12a12a212+l2p11p22a122a21−l1p11p22a122a21−l2p22a122a21+l1p22a122a21−l2p12p21a122a21+l1p12p21a122a21−l2p12a12a21+l1p12a12a21l2p21a12a21a222−l1p21a12a21a222−l2p22a21a222+l1p22a21a222+l1l2p21a12a222−l1p21a12a222−l1l2p22a222+l1p22a222+l2p11a12a212
