> This is a big problem for algebraic functions because they can be > represented in multiple different ways, and that representation can > affect the result of integration (a big piece of the "real" Risch > algorithm for algebraic functions is normalizing things so that this > isn't a problem). For example, the derivative of s = sqrt(x) can be > represented as 1/(2*s) or s/(2*x).
The strength of the numerical method is that the distinction between 1/(2*s) and s/(2*x) is lost. We can have both expressions in the ansatz list, and one will be dropped because they are linearly dependent. > I like the idea of using some faster linear algebra as a preprocessor > to reduce the size of the problem to be solved. You could then take > the reduced problem and solve it with exact symbolic arithmetic. The > worst that can happen is you might drop an ansatz that shouldn't have > been dropped, but you would still always give a symbolically correct > answer when you do. This is the plan. We can use hyint to prune the set of ansatzes to those actually in the integral and then solve symbolically for the coefficients. > I'm also wondering if you've thought about symbolic constants and if > there's any tricks you could do to support them. I think there might > be, especially when still thinking about things in terms of just using > faster linear algebra as a pre-processor to a symbolic solve. The basic idea is to generate ansatzes with intact symbolic constants, but then substitute them with random numbers (same as we do for x), solve the integral with sparse regression, and then, starting with the pruned set of symbolic ansatzes, solve for the coefficients as above. Regarding improving the speed of calculations, I cannot comment on sympy linear solvers and polys module but should mention that symbolic-numeric methods can also improve the speed. Currently, hyint separates the symbolic part (ansatz generation) from the numerical part. But it is possible to mix numerical methods in ansatz generation. We can calculate only the diff of factors of the integrands and not the whole expressions. Afterward, ansatz generation can proceed mainly numerically (while keeping track of the path for each ansatz; polys may be helpful here). Finally, we can reconstruct the relevant ansatz symbolically. This way, we can skip most of the symbolic diffs and cancellations. Thanks, Shahriar Iravanian On Friday, September 1, 2023 at 3:58:27 PM UTC-4 [email protected] wrote: > On Fri, Sep 1, 2023 at 4:12 AM Oscar Benjamin > <[email protected]> wrote: > > > > On Fri, 1 Sept 2023 at 06:45, Aaron Meurer <[email protected]> wrote: > > > > > > I like the idea of using some faster linear algebra as a preprocessor > > > to reduce the size of the problem to be solved. You could then take > > > the reduced problem and solve it with exact symbolic arithmetic. The > > > worst that can happen is you might drop an ansatz that shouldn't have > > > been dropped, but you would still always give a symbolically correct > > > answer when you do. > > > > > > If heurisch could support much larger, possibly linearly dependent > > > ansatz, then that would open up a lot of possibilities, like for > > > instance, trying to use ansatz coming from both sqrt(x) and x/sqrt(x) > > > simultaneously. But right now it's way too slow even with just the > > > linear system it generates. > > > > I'm not sure if I've interpreted this point correctly but when > > heurisch is slow it is not usually because of the linear algebra part. > > Probably that is the easiest part to speed up as well. > > Maybe things have changed since the introduction of things like > DomainMatrix, but when I benchmarked it years ago this was the case. > That and the fact that it was using the dense poly representation with > hundreds of variables. > > > > > The slow parts of heurisch are converting back and forth between Expr > > and the domains, differentiation, and cancel. > > > > If heurisch was being rewritten then I think it could be written > > without the back and forth conversions. The differentiation could be > > handled in the domain representation. The cancellation could be > > handled there as well. > > We could probably merge a lot of the code in risch and heurisch, but > loosening the restrictive rigorous code from risch. Actually Risch > itself can solve some algebraic integrals if the restrictions are > removed (just the nonelementary integral errors would be incorrect). > > > > > I suspect that heurisch was implemented at a time when SymPy did not > > have as many of the pieces that it now has that you would want to use > > to implement the algorithm within the algebra subsystem rather than > > the symbolic subsystem. > > Yes, heurisch predates the polys module. I integrated it with the > polys back in 2012 or 2013, but I didn't really refactor it in any > major way. > > Aaron Meurer > > > > > Possibly the limiting factor for SymPy implementing heurisch in the > > ideal way right now is support for symbolic algebraic extensions like > > Q(x)[sqrt(x)] within the domain system although polys.agca has > > FiniteMonogenicExtension that could represent that. > > > > -- > > Oscar > > > > -- > > You received this message because you are subscribed to the Google > Groups "sympy" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to [email protected]. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/sympy/CAHVvXxSN%2BVBubjX6i3mq%3DwE7nXZSorg7drnSP_X3-2daxbzE0Q%40mail.gmail.com > . > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/b7933de4-1154-47d4-94f8-2a8444b4b8b5n%40googlegroups.com.
