0.19.0: Oh-So-Fast Simplification, Quicker Derivatives

@ptaoussanis

(If you have any questions about how to use any of the following, please ask us at our Github Discussions page!)

This release focused on improving the expressiveness and performance of the three simplification engines in SICMUtils:

sicmutils.polynomial and sicmutils.rational-function are now quite well fleshed out, with full polynomial and rational function APIs and many generics.
The polynomial and rational function simplifiers work by round-tripping expressions through these types, depending on each namespace to emit symbolic expressions in "canonical form". This process is now much faster! On one important Bianchi Identity benchmark in sicmutils.fdg.bianchi-test, one test that formerly took close to 30 minutes now runs in 30 seconds, and all see a 60-fold improvement.
By default, these simplifiers emit expressions with all terms multiplied out; the new factor function in sicmutils.env lets you factor expressions, overriding this default.
The rule-based simplifier is now based on a powerful pattern matching engine, implemented in pattern.match and pattern.rule. sicmutils.simplify.rules now contains every rule and possible customization from the original scmutils codebase.

There is a lot in this release, all motivated by performance. Please read on for the detailed notes, and enjoy version 0.19.0!

Rule-Based Simplifier Overhaul

#353 introduces a powerful new simplifier, ported from the new-simplify procedure in simplify/rules.scm of the scmutils library. There are now a BUNCH of new rulesets and rule simplifiers in sicmutils.simplify.rules!

The next step with these is to massage them into separate bundles of rules that users can mix and match into custom simplifiers for objects like abstract matrices, abstract bra and ket structures, up and down, booleans (for representing equations and inequalities) and so on.
#349 introduces a new pattern matching system, built out of matcher combinators. All of the rules in sicmutils.simplify.rules now use the new syntax offered by the library. Some notes:
- pattern.match defines a number of "matcher combinators"; these are functions that take a map of bindings, a data input and a success continuation and either succeed by calling their continuation, or fail. Out of the box, the library provides fail, pass, with-frame, update-frame, predicate, frame-predicate, eq, bind, match-when, match-if, or, and, not, segment and sequence.
- Additionally, any combinator that takes another combinator can ALSO take a pattern form like '?x. See pattern.syntax for the full, rich range of syntax allowed. These are all functions, so you'll have to quote your symbols at this stage.
- Passing a matcher combinator to pattern.match/matcher to generate a matcher object. This is a function from some data input to a map of bindings on success, or an explicit pattern.match/failure object on failure. Test for failure with pattern.match/failed?.
- A combination of a matcher and a "consequence function" is called a "rule". A consequence is a function that takes a binding map and either returns a new result or fails by returning nil or false. (Don't worry, you can succeed with these values too by wrapping them in sicmutils.rule/succeed.)
  
  Rules are the heart of the whole simplification mechanism in sicmutils! To learn about how to build these, see the documentation for pattern*, pattern, consequence, template, rule*and rule.
- pattern.rule gives you some starter rules, and many combinators you can use to build more and more powerful and complex sets of rules. These are pass, fail, predicate, return, branch, choice*, choice, pipe*, pipe, n-times, attempt, guard, iterated, while, until, fixed-point and trace.
- Rules are nice for rewriting entire expressions recursively, from the bottom up or top down. This is called "term rewriting". A big motivation for this rewrite was to make it easy to build custom term rewriters for types like abstract matrices or abstract up and down structures. You can use your rules to rewrite structures recursively with bottom-up, top-down, iterated-bottom-up and iterated-top-down. ruleset*, ruleset, rule-simplifier and term-rewriting capture some common patterns the library uses to go from rules => term rewriters.
- If you want ideas about how to use the pattern matching library to rewrite expressions, see sicmutils.simplify.rules for many examples.
#354 adds SCI support for all macros and functions in the new pattern matching namespaces, and adds these to the namespaces exposed via sicmutils.env.sci.

Rational Function, Polynomial Simplifiers

#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).
- 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
    - 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 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.

New Functions, Performance Improvements

#358:
- Adds a more efficient literal-derivative implementation to sicmutils.abstract.function, making the Bianchi identity benchmarks run 40% faster.
- In Clojurescript, Range instances now implement sicmutils.value.Value and sicmutils.differential.IPerturbed, allowing them to be returned from derivative-taking functions
- Major, unexpected performance improvement - it turns out sicmutils.value/number? was quite slow in Clojure (less so in Clojurescript). Changing this function from an isa? check to a series of explicit instance? checks cut the build time in half. This makes the numeric tower less extensible... but it wasn't terribly extensible to start with, and needs some attention to make it so. A big win!
- The Bianchi identity benchmarks have all been updated to reflect the big performance improvements achieved here, thanks to the wonderful Tufte profiling library from @ptaoussanis. The remaining very slow piece in the simplifier is the implementation of g/add for polynomial instances. #341 will improve this situation.
#360 introduces a number of performance improvements to the sicmutils.differential.Differential implementation, primarily in terms:+ and terms:*. thanks again to @ptaoussanis and the Tufte profiling library for helping me track these down.
#357:
- Adds the ability to do incremental simplification, every time an operation is performed involving a symbolic expression. Bind sicmutils.numsymb/*incremental-simplifier* to a function from raw expression -> raw expression, like sicmutils.simplify/simplify-expression or any of the rules in sicmutils.simplify.rules to enable this behavior.
- Expands the sicmutils.expression.analyze API with the functions default-simplifier, expression-simplifier, initializer, expression-analyzer and auxiliary-variable-fetcher. See the API documentation for detailed notes on how to do interactive expression analysis and simplification with these new tools.
- by default, each simplification pass uses both rational function 4A35 and polynomial canonicalization. This brings the simplifier into line with the scmutils simplifier.
#353:
- Adds a new sicmutils.util.logic namespace with an assume! function that allows rules to log assumptions when some simplification like (sqrt (square x)) might have to choose one of multiple possible simplifications ((non-negative? x), in this example).
  
  This function simply logs the assumption for now, instead of performing any checks. now. Turn off assumption logging with the dynamic variable *log-assumptions?* in that namespace.
- new sicmutils.value/almost-integral? returns true if its argument is VERY close to an integral value, false otherwise.
Efficient symmetric-difference implementation in sicmutils.util.vector-set (#346)

Bug fixes, file moves, misc

#369:
- Removes JVM dependencies on Guava and nrepl.
- Removes sicmutils.env/sicmutils-repl-init; this is only used by lein repl, and we now accomplish the same task with the :repl-options entry in project.clj.
- Makes sicmutils.polynomial.{factor,gcd} available to SCI via the sicmutils.env.sci namespace
- moves a few namespaces to more valid locations, now that the rational function and polynomial namespaces are tidied:
  - sicmutils.numerical.interpolate.polynomial -> sicmutils.polynomial.interpolate
  - sicmutils.numerical.interpolate.richardson -> sicmutils.polynomial.richardson
  - sicmutils.numerical.interpolate.rational -> sicmutils.rational-function.interpolate
#358:
- Converts the Clojurescript test build and REPL command from lein-cljsbuild to shadow-cljs. This enables more formerly-slow tests for Clojurescript; these are now fast enough to run, thanks to the performance improvements described below.
- Upgrades our Timbre logging dependency to version 5.1.2, and SCI to 0.2.5
#353:
- expression->stream, expression->string, print-expression, pe move from sicmutils.simplify to sicmutils.expression, and are now aliased in sicmutils.env.
- pattern.rule/guard now fails if its rule argument fails; previously it wrapped the result in attempt, and would return its original input on failure.
- fixed a heisenbug in sicmutils.expression.analyze/make-analyzer where, in Clojurescript, using expressions containing a js/BigInt as a hashmap key caused certain simplifications to fail. (This is vague, but the bug was really subtle.) The fix was to make sure we freeze keys in the symbol cache. This is now noted in the function body.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

0.19.0: Oh-So-Fast Simplification, Quicker Derivatives

Rule-Based Simplifier Overhaul

Rational Function, Polynomial Simplifiers

New Functions, Performance Improvements

Bug fixes, file moves, misc