move conditions to predicates in all rules, to mitigate the oooomm problem

[Bumblebee00]

the oooomm problem is one of the problems stopping from integrating some expressions with the rule based method, read the linked issue to know the problem. It's particularly evident in the rules for symbolic integration, that usually have a lot of conditions on the variables, joined in a and. for example:

("1_1_1_2_32",
:(∫(((~!a) + (~!b)*(~x))^(~m)*((~!c) + (~!d)*(~x))^(~n),(~x)) ) => :(
    !contains_var((~a), (~b), (~c), (~d), (~x)) &&
    !eq((~b)*(~c) - (~a)*(~d), 0) &&
    lt(-1, (~m), 0) &&
    le(-1, (~n), 0) &&
    le(ext_den((~n)), ext_den((~m))) &&
    int_linear((~a), (~b), (~c), (~d), (~m), (~n), (~x)) ?
ext_den((~m))⨸(~b)* int_and_subst((~x)^(ext_den((~m))*((~m) + 1) - 1)*((~c) - (~a)*(~d)⨸(~b) + (~d)*(~x)^ext_den((~m))⨸(~b))^(~n),  (~x), (~x), ((~a) + (~b)*(~x))^(1⨸ext_den((~m))), "1_1_1_2_32") : nothing))

these conditions are all in the rhs, and after a match for the rule is found, the rhs is evaluated and the conditions too.
as said in the issue one way to mitigate the oooomm problem is to bring all conditions that depend on only one variable, to a predicate in the rule. predicates in rules are special conditions that get evaluated as soon as the match is made, during the matching process. This would also increase the speed of the matching process because a bad match is discarded immediatly.

So for example the above rule, can be rewritten like:

("1_1_1_2_32",

:(∫(((~!a) + (~!b)*(~x))^(~m::(m->lt(-1,m,0)))*((~!c) + (~!d)*(~x))^(~n::(n->le(-1, n, 0))),(~x)) ) => :(
    !contains_var((~a), (~b), (~c), (~d), (~x)) &&
    !eq((~b)*(~c) - (~a)*(~d), 0) &&
    le(ext_den((~n)), ext_den((~m))) &&
    int_linear((~a), (~b), (~c), (~d), (~m), (~n), (~x)) ?
ext_den((~m))⨸(~b)* int_and_subst((~x)^(ext_den((~m))*((~m) + 1) - 1)*((~c) - (~a)*(~d)⨸(~b) + (~d)*(~x)^ext_den((~m))⨸(~b))^(~n),  (~x), (~x), ((~a) + (~b)*(~x))^(1⨸ext_den((~m))), "1_1_1_2_32") : nothing))

where the conditions on ~m and ~n have been moved as predicates. add5a99

ideally we should do this for every rule. this can first be done manually, but then its possible and also not too difficult to implement it atuomatically in the translator script

[SamUpid]

Hi @Bumblebee00,

Thanks for pointing me to this issue! I'm interested in working on it.

I've read through the issue and understand the oooomm problem. Before I start, I wanted to confirm a few things:

1. Should I start by manually converting rules in a specific file, or would you prefer I work on all rules systematically?
2. Are there any rules I should prioritize or avoid?
3. For the automatic translation script - should I work on that after doing some manual conversions first, or is it okay to attempt both in parallel?

My plan:

• Week 1: Manually convert 10-15 rules to understand the pattern
• Week 1: Start on the automatic translator script (if you think it's a good idea)
• Week 2: Apply the remaining rules and test

Does this sound reasonable? Happy to adjust based on your guidance!

Thanks!
Neeraj

[Bumblebee00]

Hi Neeraj, thanks for replying! For starting it's important to understand the problem and how to work with the repo. So i advise you to fork it, clone it, and look into the files:

• src/methods.jl that simply takes the initial input expression to integrate (of tyep Symbolics Num), unwraps it to the SymbolicUtils type, and calls the function in src/methods/rule_based/frontend.jl
• src/methods/rule_based/frontend.jl that contains the code that applies all the rules
• src/methods/rule_based/rule2.jl that contains the code to apply one rule. you can look test/test_rule2.jl for examples on how to use the rules

then reading here you can see some examples of the oooomm problem in action, so try modifying rule 1_1_1_2_23 as discussed above, bringing the conditions to predicates, and see if after the expression 1/(sqrt(1+200x)*sqrt(2-x)) gets integrated.

once you do that we can think of updating more expressions manually and after that we can think of the script. I am saying this bc at the beginning should be better to work on rules that you can actually test if your change improves the system, rather than blindly change all the rules in a file

[SamUpid]

Hi! I've successfully modified rule 1_1_1_2_23 and tested it. The expression 1/(sqrt(1+200x)*sqrt(2-x)) now integrates successfully!
The test output shows:

• Rule 1_1_1_2_23 was applied correctly with the predicate
• The integration completed successfully
• Result: 0.1414213562373095*asin(sqrt(1 + 200x) / 20.024984394500787)

""Here is my terminal:

Testing the expression: 1/(sqrt(1+200x)*sqrt(2-x))
┌-------Applied rule 1_1_1_2_23 (change of variables):
| ∫(1 / (sqrt(a + (!(b::(b->begin
| gt(b, 0)
| end))) * x) * √(c + d * x)), x) => if !(contains_var(a, b, c, d, x)) && gt(b * c - a * d, 0)
| (2 / √b) * substitute(∫{1 / √((b * c - a * d) + d * x ^}d),, x, => x, √(a + b)
| else
| nothing
| end
└-------with result: ∫1 / sqrt(401 - (u^2)) du where u = sqrt(1 + 200x)
┌-------Applied rule 1_1_2_1_17 on ∫(1 / sqrt(401 - (x^2)), x)
| ∫(1 / √(a + b * x ^ 2), x) => if
| !(contains_var(a, b, x)) &&
| (
| gt(a, 0) &&
| neg(b)
| )
| asin((√(-b) * x) / √a) / √(-b)
└-------with result: asin(x / 20.024984394500787)

Result:
0.1414213562373095asin(sqrt(1 + 200x) / 20.024984394500787)

julia>
""
I noticed rule 1_1_1_2_32 already has predicates (probably from your earlier work).

Should I:

1. Look for more rules in this file with single-variable conditions to optimize?
2. Move to a different rule file?
3. Create a pull request with just this change first?

Looking forward to your guidance!

[Bumblebee00]

Great job. Fyi you can also write simply

b::(b->gt(b, 0))

Instead of adding begin and end.
Now if you do like this for all the rules in the file and open a PR I will merge it. I am also curious to see how many rules are improvable in this way in a single file.

[Bumblebee00]

Before changing something for a lot of rules is important to think about the speed. so below is the speed of three different ways of handling with one variable conditions:

• r1 putting the conditions at the end like they are right now in the rules. with the oooomm problem
• r2 is with putting a inline predicate, so like m::(x->something(x,...)), like we tried to do in this issue before now
• r3 is with defining the condition in a function outside the rule, and then putting just the function name in the predicate, so foo1(x)=something(x,...) and then m::foo1

As you can see from the speed we should defenetly choose option 3. this will add a bit of time to the precompilation time of the package, the one that you have to wait after typing using SymbolicIntegration, but i dont think is a problem after version 3.3.0

julia> @benchmark SymbolicIntegration.rule2(r1, ∫(1 / (((1 - x)^(1//2))*x),x))
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
 Range (min … max):  294.792 μs …  10.338 ms  ┊ GC (min … max): 0.00% … 95.32%
 Time  (median):     298.291 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   305.420 μs ± 130.735 μs  ┊ GC (mean ± σ):  0.57% ±  1.34%

  █▇▃                                                         ▁ ▁
  █████▆▆▇▇▇▇▇▅▃▁▄▁▁▁▁▁▁▃▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▅█ █
  295 μs        Histogram: log(frequency) by time        558 μs <

 Memory estimate: 29.12 KiB, allocs estimate: 837.

julia> @benchmark SymbolicIntegration.rule2(r2, ∫(1 / (((1 - x)^(1//2))*x),x))
BenchmarkTools.Trial: 956 samples with 1 evaluation per sample.
 Range (min … max):  5.013 ms … 29.425 ms  ┊ GC (min … max): 0.00% … 79.40%
 Time  (median):     5.103 ms              ┊ GC (median):    0.00%
 Time  (mean ± σ):   5.228 ms ±  1.105 ms  ┊ GC (mean ± σ):  0.87% ±  3.57%

  ▃▅██▇▆▆▆▄▄▃▁                                                
  █████████████▆▇▄▆▅▄▅▁▁▄▁▁▅▅▅▁▁▁▅▁▁▄▄█▆▇▇▄▆▅▆██▆▇▆▄▁▁▁▄▁▁▁▄ █
  5.01 ms      Histogram: log(frequency) by time     6.11 ms <

 Memory estimate: 796.98 KiB, allocs estimate: 16981.

julia> @benchmark SymbolicIntegration.rule2(r3, ∫(1 / (((1 - x)^(1//2))*x),x))
BenchmarkTools.Trial: 10000 samples with 1 evaluation per sample.
 Range (min … max):  262.334 μs … 973.750 μs  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     265.708 μs               ┊ GC (median):    0.00%
 Time  (mean ± σ):   273.701 μs ±  58.158 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

  █▄                                                            ▁
  ███▇▇▅▃▁▁▄▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▅▄▆▇ █
  262 μs        Histogram: log(frequency) by time        742 μs <

 Memory estimate: 26.59 KiB, allocs estimate: 767.

details of r1, r2, r3:

r1 = :(∫(((~!a) + (~!b)*(~x))^(~m)*((~!c) + (~!d)*(~x))^(~n),(~x)) ) => :(
    !contains_var((~a), (~b), (~c), (~d), (~x)) &&
    !eq((~b)*(~c) - (~a)*(~d), 0) &&
    le(ext_den((~n)), ext_den((~m))) &&
    lt(-1,~m,0) &&
    le(-1,~n,0) &&
    int_linear((~a), (~b), (~c), (~d), (~m), (~n), (~x)) ?
~x : nothing)

r2 = :(∫(((~!a) + (~!b)*(~x))^(~m::(m->lt(-1,m,0)))*((~!c) + (~!d)*(~x))^(~n::(n->le(-1, n, 0))),(~x)) ) => :(
    !contains_var((~a), (~b), (~c), (~d), (~x)) &&
    !eq((~b)*(~c) - (~a)*(~d), 0) &&
    le(ext_den((~n)), ext_den((~m))) &&
    int_linear((~a), (~b), (~c), (~d), (~m), (~n), (~x)) ?
~x : nothing)

foo1(x) = lt(-1, x, 0)
foo2(x) = le(-1, x, 0)

r3 = :(∫(((~!a) + (~!b)*(~x))^(~m::foo1)*((~!c) + (~!d)*(~x))^(~n::foo2),(~x)) ) => :(
    !contains_var((~a), (~b), (~c), (~d), (~x)) &&
    !eq((~b)*(~c) - (~a)*(~d), 0) &&
    le(ext_den((~n)), ext_den((~m))) &&
    int_linear((~a), (~b), (~c), (~d), (~m), (~n), (~x)) ?    ~x : nothing)

[SamUpid]

Hi @Bumblebee00,
I've successfully modified 10 rules (1_1_1_2_5, 7, 10, 11, 13, 16, 19, 20, 21, 23) by moving single-variable conditions to predicates using inline lambdas like ~m::(m->igt(m + 1/2, 0)).
However, I just saw your benchmark showing that named function predicates (Option 3) are 17x faster than inline lambdas (Option 2). Before proceeding further, I plan to:

• Convert all 10 modified rules to use named predicates (like ~m::pred_igt_m_plus_half)
• Define the predicate functions at the top of the file
• Test to confirm they work correctly
• Then systematically go through all remaining rules in the file

Does this approach sound good? Should I open a PR with just these 10 rules first, or continue modifying more rules before submitting?
Thanks!

[Bumblebee00]

yeah start opening a pr with the work you have done so far, also just the code using lambdas on rules 1_1_1_2_5, 7, 10, 11, 13, 16, 19, 20, 21, 23. If you open a pr the CI can be run that test automatically if everything is ok. later you will update it to use named predicates. I was thinking that for the names of these condition functions, you could call them something like condition_<rule number> or c_<rule number> to be short, instead of pred_igt_m_plus_half

[Bumblebee00]

if you dont know how to open the pr you need to: create a new branch from main, call it something with "oooomm". then push the work done so far with some commits on that branch. then push that branch to your fork on github wit git push origin <branch name> and on github.com on your fork you will see something like compare and pull request

[SamUpid]

Hi @Bumblebee00

I've created this PR as requested.

Summary:

• Converted rules to use lambda functions
• This is the intermediate step before named predicates
• Branch: oooomm
• PR is ready for review

Status:

• PR created successfully
• 3 workflows awaiting approval (CI tests)
• No merge conflicts

Could you please approve the workflows so CI tests can run? Also, let me know if you'd like me to convert this to a draft PR since this is work in progress.

Next steps (as per your guidance): After this, I'll update to use named predicates like condition_<rule> or c_<rule>.

Thanks!

[SamUpid]

Dear @Bumblebee00,

About next steps:

1. Should I address the low test coverage (28.57%) or is it acceptable for this refactoring?
2. Can I start converting these lambdas to named predicates (condition_<rule>/c_<rule>) tomorrow morning?

I'll keep you updated on my progress.

[Bumblebee00]

no we dont care about low coverage. convert to named predicates in that rule file you are working on, and if good I will merge it