Upgrade polynomial + rational function representation, gcd namespace by sritchie · Pull Request #341 · sicmutils/sicmutils · GitHub
More Web Proxy on the site http://driver.im/
You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
This repository was archived by the owner on Jun 18, 2025. It is now read-only.
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
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 that
they are now a good bit faster than the original scmutils implementation.
sicmutils.polynomial and sicmutils.rational-function are now solid data
structures 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/kind now works for sorted-map instances.
GCD in Clojurescript is now fast and efficient between all combinations of js/BigInt and js/Number, and in Clojure between all combinations of clojure.lang.BigInt, BigInteger, Long and Integer.
on the JVM, GCD now works properly with rational numbers. Previously
anything non-integral would return 1; now (gcd 1/2 1/3) properly returns 1/6.
g/exact-divide now succeeds for all non-exact ::v/scalar types (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 a
0, rather than attempting to multiply all remaining items by 0.
The default function for sicmutils.generic/lcm protects against overflow
by dividing only a single one of its arguments a and b by (gcd a b).
(g/lcm 0 0) now properly returns 0.
New sicmutils.util.aggregate/{monoid,group} functions let you build
multi-arity aggregations out of binary combination functions, with an option
to bail early at "annihilator" values, like 0 for multiplication.
New multi-arity lcm and gcd implementations for symbolic expressions
appropriately handle 0 and 1 on either side, as well as the case where
both arguments are equal.
In the sicmutils.numsymb namespace, thanks to monoid and group, the '*, '/, '-, '+, 'or, 'and, 'gcd, 'lcm and '= operations
now have efficient multi-arity implementations that stop computing when they
receive an annihilator, like 0 for multiplication or true for or.
Access these via (sicmutils.numsymb/symbolic-operator <symbol>).
sicmutils.series/PowerSeries gains arg-scale and arg-shift functions;
these are identical to sicmutils.function/arg-{scale,shift}, but preserve
the PowerSeries type. (#367 proposes making these functions generic.)
New sicmutils.ratio/IRational protocol, with numerator and denominator
functions implemented for ratios and for the RationalFunction data type.
These two are now exposed in sicmutils.env.
sicmutils.simplify.rules/*divide-numbers-through-simplify?* is now true
by 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.analyze can now act on
both bare, unwrapped expressions (raw lists etc) and on sicmutils.expression.Literal instances. This means that you can now call sicmutils.simplify/{*rf-simplify*,*poly-simplify*} as functions and
canonicalize some form with either simplifier without triggering a full
simplification. A small win, but ice.
sicmutils.polynomial.factor got a major rewrite, and now exposes a few
functions like poly->factored-expression, factor-expression and factor.
factor is tremendously useful! Call factor (it's aliased into sicmutils.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).
8000
bugfix: sicmutils.expression.Literal instances now compare their contained
expression via sicmutils.value/=.
sicmutils.rules/constant-elimination can now eliminate constants from
expressions with any arity, not just binary forms.
Now, the three big namespaces... sicmutils.polynomial, sicmutils.rational-function and sicmutils.polynomial.gcd all got a big
overhaul.
sicmutils.polynomial notes:
Polynomial uses 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).
Polynomial instances implement many more Clojure(script) protocols. They
can hold metadata; they can be evaluated as functions of their
indeterminates, and seq now returns a sequence of terms.
Polynomial extends sicmutils.function/IArity and differential/IPerturbed, so you can use sicmutils.function/arity, and
take derivatives of functions that return polynomials.
In their arithmetic, Polynomial instances will drop down to bare
coefficients whenever some multiplication or addition removes all
indeterminates. All binary arithmetic exposed in the namespace can handle
non-Polynomial instances 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, and new-variables
functions to generate new polynomials: map-coefficients, map-exponents, scale, scale-l, normalize, reciprocal, drop-leading-term, contract and extend alongside contractible?, lower-arity, raise-arity, with-lower-arity, arg-scale, arg-shift
arithmetic: negate, abs, add, sub, mul, square, cube, expt, divide along with divisible?, evenly-divide, pseudo-remainder, and lots of functions installed into the generic
arithmetic system.
different ways to evaluate polynomials: evaluate, horner-with-error
calculus! partial-derivative and partial-derivatives are alive and
well, and work with the D operator.
Functions to get in and out of polynomials from other types: univariate->dense, ->power-series, expression->, ->expression
sicmutils.polynomial.gcd also got a rewrite; it's fairly clear to read
now, 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 :long markers.
sicmutils.rational-function notes:
RationalFunction instances implement many more Clojure(script)
protocols. They can hold metadata; they can be evaluated as functions of
their indeterminates, and seq now returns a pair of numerator, denominator.
RationalFunction extends sicmutils.function/IArity and sicmutils.ratio/IRational, so our generic arity, numerator and denominator work on these instances.
Here are some new functions from the RationalFunction namespace:
constructor: make, drops to polynomial or coefficient where needed
just like Polynomial functions
functions to generate new rational functions: arg-scale, arg-shift
predicates: negative?
arithmetic: negate, abs, add, sub, mul, square, cube, expt, invert, div, gcd, and many functions installed into the
generic arithmetic system.
evaluation via evaluate
calculus! partial-derivative and partial-derivatives are alive and
well, and work with the D operator.
Functions to get in and out of rational functions from symbolic
expressions: expression->, ->expression.
Merging #341 (2c314e6) into master (da43ad1) will decrease coverage by 2.42%.
The diff coverage is 75.33%.
❗ Current head 2c314e6 differs from pull request most recent head 9e14091. Consider uploading reports for the commit 9e14091 to get more accurate results
sritchie
changed the title
Upgrade polynomial gcd [in progress]
Upgrade polynomial + rational function representation, prep for sparse gcd [in progress]
May 3, 2021
sritchie
changed the title
Upgrade polynomial + rational function representation, prep for sparse gcd [in progress]
Upgrade polynomial + rational function representation, prep for sparse gcd
May 26, 2021
sritchie
changed the title
Upgrade polynomial + rational function representation, prep for sparse gcd
Upgrade polynomial + rational function representation, gcd namespace
May 27, 2021
Sign up for freeto subscribe to this conversation on GitHub.
Already have an account?
Sign in.
Labels
None yet
4 participants
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.polynomial
andsicmutils.rational-function
are 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/kind
now works forsorted-map
instances.GCD in Clojurescript is now fast and efficient between all combinations of
js/BigInt
andjs/Number
, and in Clojure between all combinations ofclojure.lang.BigInt
,BigInteger
,Long
andInteger
.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-divide
now succeeds for all non-exact::v/scalar
types (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/lcm
protects against overflowby dividing only a single one of its arguments
a
andb
by(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
lcm
andgcd
implementations for symbolic expressionsappropriately handle
0
and1
on either side, as well as the case whereboth arguments are equal.
In the
sicmutils.numsymb
namespace, thanks tomonoid
andgroup
, the'*
,'/
,'-
,'+
,'or
,'and
,'gcd
,'lcm
and'=
operationsnow have efficient multi-arity implementations that stop computing when they
receive an annihilator, like
0
for multiplication ortrue
foror
.Access these via
(sicmutils.numsymb/symbolic-operator <symbol>)
.sicmutils.series/PowerSeries
gainsarg-scale
andarg-shift
functions;these are identical to
sicmutils.function/arg-{scale,shift}
, but preservethe
PowerSeries
type. (#367 proposes making these functions generic.)New
sicmutils.ratio/IRational
protocol, withnumerator
anddenominator
functions implemented for ratios and for the
RationalFunction
data type.These two are now exposed in
sicmutils.env
.sicmutils.simplify.rules/*divide-numbers-through-simplify?*
is nowtrue
by 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.analyze
can now act onboth bare, unwrapped expressions (raw lists etc) and on
sicmutils.expression.Literal
instances. 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.factor
got a major rewrite, and now exposes a fewfunctions like
poly->factored-expression
,factor-expression
andfactor
.factor
is 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.Literal
instances now compare their containedexpression via
sicmutils.value/=
.sicmutils.rules/constant-elimination
can now eliminate constants fromexpressions with any arity, not just binary forms.
Now, the three big namespaces...
sicmutils.polynomial
,sicmutils.rational-function
andsicmutils.polynomial.gcd
all got a bigoverhaul.
sicmutils.polynomial
notes:Polynomial
uses 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).
Polynomial
instances implement many more Clojure(script) protocols. Theycan hold metadata; they can be evaluated as functions of their
indeterminates, and
seq
now returns a sequence of terms.Polynomial
extendssicmutils.function/IArity
anddifferential/IPerturbed
, so you can usesicmutils.function/arity
, andtake derivatives of functions that return polynomials.
In their arithmetic,
Polynomial
instances will drop down to barecoefficients whenever some multiplication or addition removes all
indeterminates. All binary arithmetic exposed in the namespace can handle
non-
Polynomial
instances 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-variables
accessor functions:
arity
,degree
,coefficients
,leading-term
,leading-coefficient
,leading-exponents
,leading-base-coefficient
,trailing-coefficient
,lowest-degree
predicates:
monomial?
,monic?
,univariate?
,multivariate?
,negative?
functions to generate new polynomials:
map-coefficients
,map-exponents
,scale
,scale-l
,normalize
,reciprocal
,drop-leading-term
,contract
andextend
alongsidecontractible?
,lower-arity
,raise-arity
,with-lower-arity
,arg-scale
,arg-shift
arithmetic:
negate
,abs
,add
,sub
,mul
,square
,cube
,expt
,divide
along withdivisible?
,evenly-divide
,pseudo-remainder
, and lots of functions installed into the genericarithmetic system.
different ways to evaluate polynomials:
evaluate
,horner-with-error
calculus!
partial-derivative
andpartial-derivatives
are alive andwell, and work with the
D
operator.Functions to get in and out of polynomials from other types:
univariate->dense
,->power-series
,expression->
,->expression
sicmutils.polynomial.gcd
also 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
:long
markers.sicmutils.rational-function
notes:RationalFunction
instances implement many more Clojure(script)protocols. They can hold metadata; they can be evaluated as functions of
their indeterminates, and
seq
now returns a pair ofnumerator
,denominator
.RationalFunction
extendssicmutils.function/IArity
andsicmutils.ratio/IRational
, so our genericarity
,numerator
anddenominator
work on these instances.Here are some new functions from the
RationalFunction
namespace:constructor:
make
, drops to polynomial or coefficient where neededjust like
Polynomial
functionsfunctions to generate new rational functions:
arg-scale
,arg-shift
predicates:
negative?
arithmetic:
negate
,abs
,add
,sub
,mul
,square
,cube
,expt
,invert
,div
,gcd
, and many functions installed into thegeneric arithmetic system.
evaluation via
evaluate
calculus!
partial-derivative
andpartial-derivatives
are alive andwell, and work with the
D
operator.Functions to get in and out of rational functions from symbolic
expressions:
expression->
,->expression
.