Upgrade polynomial + rational function representation, gcd namespace #341
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
14 tasks
669ff95 to
06c85d2
Compare
Codecov Report
@@ Coverage Diff @@
## master sicmutils/sicmutils#341 +/- ##
==========================================
- Coverage 84.05% 81.62% -2.43%
==========================================
Files 83 93 +10
Lines 9367 11279 +1912
Branches 496 557 +61
==========================================
+ Hits 7873 9206 +1333
- Misses 998 1516 +518
- Partials 496 557 +61
Continue to review full report at Codecov.
|
This was referenced Apr 27, 2021
1c236f6 to
55054e2
Compare
Codecov Report
@@ Coverage Diff @@
## master sicmutils/sicmutils#341 +/- ##
==========================================
+ Coverage 83.95% 83.97% +0.01%
==========================================
Files 95 97 +2
Lines 12113 12872 +759
Branches 619 673 +54
==========================================
+ Hits 10170 10809 +639
- Misses 1324 1390 +66
- Partials 619 673 +54
Continue to review full report at Codecov.
|
f3b6683 to
df7b942
Compare
a13f185 to
3e53e15
Compare
654c2c3 to
d2998de
Compare
4 tasks
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
From the CHANGELOG:
Upgrade polynomial + rational function representation, gcd namespace #341 takes on a large rewrite of the rational function and polynomial
simplfiers. One goal of this project was to improve the performance of the
Bianchi Identities in
sicmutils.fdg.bianchi-test, and I'm happy to say thatthey are now a good bit faster than the original scmutils implementation.
sicmutils.polynomialandsicmutils.rational-functionare now solid datastructures of their own, with many operations installed into the generic
system. These are now valuable and useful outside of their role in the
simplifier.
This was a large project, and many small improvements and bugfixes snuck in.
Here is the full list:
v/kindnow works forsorted-mapinstances.GCD in Clojurescript is now fast and efficient between all combinations of
js/BigIntandjs/Number, and in Clojure between all combinations ofclojure.lang.BigInt,BigInteger,LongandInteger.on the JVM, GCD now works properly with rational numbers. Previously
anything non-integral would return
1; now(gcd 1/2 1/3)properly returns1/6.g/exact-dividenow succeeds for all non-exact::v/scalartypes (symbols,floats, etc) either if the denominator is zero, or if the two arguments are
equal. Else, it throws, just like before.
A multi-arity call to
sicmutils.generic/*now stops if it encounters a0, rather than attempting to multiply all remaining items by 0.
The default function for
sicmutils.generic/lcmprotects against overflowby dividing only a single one of its arguments
aandbby(gcd a b).(g/lcm 0 0)now properly returns 0.New
sicmutils.util.aggregate/{monoid,group}functions let you buildmulti-arity aggregations out of binary combination functions, with an option
to bail early at "annihilator" values, like 0 for multiplication.
New multi-arity
lcmandgcdimplementations for symbolic expressionsappropriately handle
0and1on either side, as well as the case whereboth arguments are equal.
In the
sicmutils.numsymbnamespace, thanks tomonoidandgroup, the'*,'/,'-,'+,'or,'and,'gcd,'lcmand'=operationsnow have efficient multi-arity implementations that stop computing when they
receive an annihilator, like
0for multiplication ortrueforor.Access these via
(sicmutils.numsymb/symbolic-operator <symbol>).sicmutils.series/PowerSeriesgainsarg-scaleandarg-shiftfunctions;these are identical to
sicmutils.function/arg-{scale,shift}, but preservethe
PowerSeriestype. (#367 proposes making these functions generic.)New
sicmutils.ratio/IRationalprotocol, withnumeratoranddenominatorfunctions implemented for ratios and for the
RationalFunctiondata type.These two are now exposed in
sicmutils.env.sicmutils.simplify.rules/*divide-numbers-through-simplify?*is nowtrueby default; numbers in the denominator will now automatically pull up into
the numerator. All tests now reflect this setting.
Any analyzer generated from
sicmutils.expression.analyzecan now act onboth bare, unwrapped expressions (raw lists etc) and on
sicmutils.expression.Literalinstances. This means that you can now callsicmutils.simplify/{*rf-simplify*,*poly-simplify*}as functions andcanonicalize some form with either simplifier without triggering a full
simplification. A small win, but ice.
sicmutils.polynomial.factorgot a major rewrite, and now exposes a fewfunctions like
poly->factored-expression,factor-expressionandfactor.factoris tremendously useful! Callfactor(it's aliased intosicmutils.env) on any expression to factor out all possible terms.This makes it much easier to see where there is some cancellation
lurking, in, say, some expression you know should equal zero (a
residual).
bugfix:
sicmutils.expression.Literalinstances now compare their containedexpression via
sicmutils.value/=.sicmutils.rules/constant-eliminationcan now eliminate constants fromexpressions with any arity, not just binary forms.
Now, the three big namespaces...
sicmutils.polynomial,sicmutils.rational-functionandsicmutils.polynomial.gcdall got a bigoverhaul.
sicmutils.polynomialnotes:Polynomialuses a new sparse representation for its "power product"term; this, plus an arithmetic rewrite, makes the whole system much faster
for larger numbers of variables (for all #s, really).
Polynomialinstances implement many more Clojure(script) protocols. Theycan hold metadata; they can be evaluated as functions of their
indeterminates, and
seqnow returns a sequence of terms.Polynomialextendssicmutils.function/IArityanddifferential/IPerturbed, so you can usesicmutils.function/arity, andtake derivatives of functions that return polynomials.
In their arithmetic,
Polynomialinstances will drop down to barecoefficients whenever some multiplication or addition removes all
indeterminates. All binary arithmetic exposed in the namespace can handle
non-
Polynomialinstances on either or both sides, so this is fine.Coefficients are treated as constant polynomials.
The namespace holds many new functions. Some choice ones are:
constructors:
make,constant,linear,c*xn,identity, andnew-variablesaccessor functions:
arity,degree,coefficients,leading-term,leading-coefficient,leading-exponents,leading-base-coefficient,trailing-coefficient,lowest-degreepredicates:
monomial?,monic?,univariate?,multivariate?,negative?functions to generate new polynomials:
map-coefficients,map-exponents,scale,scale-l,normalize,reciprocal,drop-leading-term,contractandextendalongsidecontractible?,lower-arity,raise-arity,with-lower-arity,arg-scale,arg-shiftarithmetic:
negate,abs,add,sub,mul,square,cube,expt,dividealong withdivisible?,evenly-divide,pseudo-remainder, and lots of functions installed into the genericarithmetic system.
different ways to evaluate polynomials:
evaluate,horner-with-errorcalculus!
partial-derivativeandpartial-derivativesare alive andwell, and work with the
Doperator.Functions to get in and out of polynomials from other types:
univariate->dense,->power-series,expression->,->expressionsicmutils.polynomial.gcdalso got a rewrite; it's fairly clear to readnow, and prepared for the eventual addition of the sparse multivariate GCD
routine that scmutils uses. There are some efficiency gains here too that
let us turn a number of tests back on, or demote them from
:longmarkers.sicmutils.rational-functionnotes:RationalFunctioninstances implement many more Clojure(script)protocols. They can hold metadata; they can be evaluated as functions of
their indeterminates, and
seqnow returns a pair ofnumerator,denominator.RationalFunctionextendssicmutils.function/IArityandsicmutils.ratio/IRational, so our genericarity,numeratoranddenominatorwork on these instances.Here are some new functions from the
RationalFunctionnamespace:constructor:
make, drops to polynomial or coefficient where neededjust like
Polynomialfunctionsfunctions to generate new rational functions:
arg-scale,arg-shiftpredicates:
negative?arithmetic:
negate,abs,add,sub,mul,square,cube,expt,invert,div,gcd, and many functions installed into thegeneric arithmetic system.
evaluation via
evaluatecalculus!
partial-derivativeandpartial-derivativesare alive andwell, and work with the
Doperator.Functions to get in and out of rational functions from symbolic
expressions:
expression->,->expression.