Symbolic-Numeric Integration of Univariate Expressions via Sparse Regression | Hacker News Reader

Symbolic-Numeric Integration of Univariate Expressions via Sparse Regression

arxiv.org

This paper is loads of fun so I thought it would be worth sharing here.

Summary: Implementing symbolic integration for a computer algebra system using numerical methods for symbolic regression.

Abstract: Most computer algebra systems (CAS) support symbolic integration as core functionality. The majority of the integration packages use a combination of heuristic algebraic and rule-based (integration table) methods. In this paper, we present a hybrid (symbolic-numeric) methodology to calculate the indefinite integrals of univariate expressions. The primary motivation for this work is to add symbolic integration functionality to a modern CAS (the symbolic manipulation packages of SciML, the Scientific Machine Learning ecosystem of the Julia programming language), which is mainly designed toward numerical and machine learning applications and has a different set of features than traditional CAS. The symbolic part of our method is based on the combination of candidate terms generation (borrowed from the Homotopy operators theory) with rule-based expression transformations provided by the underlying CAS. The numeric part is based on sparse-regression, a component of Sparse Identification of Nonlinear Dynamics (SINDy) technique. We show that this system can solve a large variety of common integration problems using only a few dozen basic integration rules.

Interesting approach. The use of a numerical solver for the indeterminate coefficients is clever, but also not without dangers. One major drawback is that it tends to destroy the symbolic form of the coefficients. E.g., integrate(x^pi) will give 0.24145300700522387(x^4.141592653589793) rather than (x^(pi+1))/(pi+1). Another, more damaging, problem is that incorrect integrals can be found within the given tolerance. Trying a couple of examples from the Readme, I quickly ran into this: integrate(x^2/(16 + x^2)) with the default tolerance gives

    0.0032(x^3) + 0.08374(x^2)*atan((-1//4)*x) + 0.61083x*log(16 + x^2) - 1.68734x - 0.09989x*((16 + x^2)^-1)

Only after manually setting a tighter tolerance is the correct result reported: x - 4 atan(x/4). The difference is not just cosmetic. Near zero both results are within tolerance, but the first result is very badly wrong for large x (try x=20).

Yes, the coefficient part is not great, though main thing though is getting candidates of the function form, from that using differentiation could be useful in re-deriving the coefficients. The fact that a tolerance is introduced into a symbolic method is a major downside to this approach. Using some alternative symbolic regression methods (i.e. https://datadriven.sciml.ai/dev/solvers/symbolic_regression/) could decrease this issue, though sparse regression finding the sparsest possible result is in general a hard problem.

But note that our plan is not to use this in isolation. I think the final solution will make use of a polyalgorithm. Sparse regression is in the low-medium cost of cheapness, so a polyalgorithm that does simple rules, then if that fails this sparse regression, then if that fails a larger rule set (maybe through e-graphs), then if that fails use the Risch algorithm. That could be a robust algorithm that attempts to take some fast outs before progressively falling back to the slowest form. Tests just require differentiation and checking equality.

  > Tests just require differentiation and checking equality.

Is that not implemented yet? I was wondering how a result with such an obviously incommensurate functional form could be produced.

Differentiation and equality checking through e-graphs/simplification is already supported. But it's not done automatically with the symbolic-numeric integration: you'd have to call it after the integration to check which terms are necessary. We could probably improve the algorithm by doing this automatically and then doing more trimming of some sort.

If you want a wide range of symbolic integration it would make more sense to use Rich's pattern matching method. Visit https://rulebasedintegration.org/

There is also a theory of integration, the Risch integral algorithm. See https://en.wikipedia.org/wiki/Risch_algorithm

Axiom, a computer algebra system, implements the Risch algorithm. To see how these two approaches compare, look at the Axiom Computer Algebra Test Suite Visit http://axiom-developer.org/axiom-website/CATS/index.html

Reply on news.ycombinator.com