search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.38k stars 469 forks source link

add is_trivial_zero() method to symbolic expressions #11513

Closed burcin closed 12 years ago

burcin commented 13 years ago

A fast way to check if an expression is zero is important in many places, see for example #11143 comment:15. We should put the numerical check mentioned there in a method (_is_numerically_zero()) of symbolic expressions (sage.symbolic.expression.Expression).

Apply attachment: trac_11513-is_trival_zero.patch.

CC: @kcrisman

Component: symbolics

Keywords: sd35.5

Author: Burcin Erocal

Reviewer: Benjamin Jones, Paul Zimmermann

Merged: sage-5.0.beta0

Issue created by migration from https://trac.sagemath.org/ticket/11513

burcin commented 13 years ago

Attachment: trac_11513-is_numerically_zero.patch.gz

temporary patch

burcin commented 13 years ago
comment:2

I attached a patch providing a function which doesn't do much. It should eventually check (reasonably quickly I hope) if expressions like (pi-1)*pi - (pi-2)*pi - pi) or e<sup>I</sup>pi +1 are zero. This function can be used to provide a template for implementing #11143 while someone tries to improve it.

kcrisman commented 13 years ago
comment:3

I thought this was a computationally unsolvable problem in general? Maybe I'm missing something here.

burcin commented 13 years ago
comment:4

That's why the function name says numerically. It might have said trivially as well. This is just supposed to be a quick check. Maybe the examples in comment:2 were too ambitious.

kcrisman commented 13 years ago
comment:5

So what does this exactly check? Just if something is a numeric Ginac object that Ginac knows is zero? So we won't get any false positives? That is my main concern, for instance with #1173 or #11143 - we wouldn't want mathematical incorrectness to get a speedup.

kcrisman commented 13 years ago
comment:6

Also, what happened to the use of CIF mentioned at #11143? I assume it's commented out because it's slower, or less reliable, or something?

zimmermann6 commented 12 years ago
comment:7

I'm puzzled about this ticket. Why doesn't the is_zero method suffice? As said by Karl-Dieter, for general expressions the problem is undecidable, thus if you want to check expressions that reduce to zero, the name of the method should reflect the fact that there could be false negatives.

Paul

zimmermann6 commented 12 years ago

Changed keywords from none to sd35.5

burcin commented 12 years ago
comment:8

Replying to @zimmermann6:

I'm puzzled about this ticket. Why doesn't the is_zero method suffice? As said by Karl-Dieter, for general expressions the problem is undecidable, thus if you want to check expressions that reduce to zero, the name of the method should reflect the fact that there could be false negatives.

Hi Paul, I wanted to ask you about this in Warwick. I got caught up in the linear algebra stuff and this slipped my mind.

is_zero() usually ends up calling maxima, which is very slow especially in the context of automatic evaluation of symbolic functions.

At the moment, many symbolic functions (see sage/functions/generalized.py for example) use code similar to the following to test if an argument is zero within a reasonable time: (BTW, this code should not initialize CIF on every call.)

        try:
            approx_x = ComplexIntervalField()(x)
            if bool(approx_x.imag() == 0):      # x is real
                if bool(approx_x.real() == 0):  # x is zero
                    return None
                else:
                    return 0
        except:                     # x is symbolic
            pass

The reason for this ticket was to move this to a separate function to avoid code duplication. If this function can detect pi + (pi - 1)*pi - pi^2 == 0 or (pi - 1)*x - pi*x + x == 0 it would be even better. In this context, false negatives are not a problem. We should just avoid false positives. It's also OK if this test is not purely numeric. Any suggestions for a better name for this function is also welcome of course.

zimmermann6 commented 12 years ago
comment:9

Dear Burcin,

The reason for this ticket was to move this to a separate function to avoid code duplication.

ok I understand. But I don't like the proposed solution, since:

(1) it might say a number is zero whereas it is not (if the number is tiny, but due to rounding errors it gets numerically evaluated to zero, because the precision used is fixed)

(2) it might say a zero number is not (again due to rounding errors)

It should be the responsibility of the user only to make such approximations.

What happens if your function _is_numerically_zero() only checks for exact integer or real or complex zero? Do many doctests fail?

Paul

benjaminfjones commented 12 years ago
comment:10

The _is_numerically_zero() has only been used in a few new symbolic functions, we haven't tested replacing the heavily duplicated test code that Burcin is talking about with this new method to see if many doctests fail. My impression is that it is useful to have such a method for automatic simplifications like e.g. erf(0) should return 0 not erf(0), for instance to address #8983.

burcin commented 12 years ago

Attachment: trac_11513-is_trivally_zero.patch.gz

burcin commented 12 years ago
comment:11

After playing around with ComplexIntervalField, different precisions and symbolic expressions, I finally realized that they cannot perform magic and detect zero. :)

attachment: trac_11513-is_trivally_zero.patch implements a method is_trivially_zero() instead. This is just a wrapper around pynac's is_zero() method, which amounts to the exact integer or real/complex zero check Paul suggested.

Can we review this quickly and turn to another ticket that requires magic: #9953?

burcin commented 12 years ago

Author: Burcin Erocal

burcin commented 12 years ago

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 A fast way to check if an expression is zero is important in many places, see for example [#11143 comment:15](https://github.com/sagemath/sage/issues/11143#comment:15). We should put the numerical check mentioned there in a method (`_is_numerically_zero()`) of symbolic expressions (`sage.symbolic.expression.Expression`).
+
+Apply [attachment: trac_11513-is_trivally_zero.patch.](https://github.com/sagemath/sage/files/ticket11513/trac_11513-is_trivally_zero.patch..gz)
benjaminfjones commented 12 years ago

Reviewer: Benjamin Jones

benjaminfjones commented 12 years ago
comment:12

I think this is certainly sufficient for our needs with fast evaluation and automatic simplification of symbolic functions.

Positive Review.

The patch looks good, applies cleanly to Sage-4.8.alpha6, and all doctests in the file pass. I'm going to work now on updating various tickets that depended on the name _is_numerically_zero.

benjaminfjones commented 12 years ago
comment:13

Sorry, I didn't mean to change the status so quick. I'll defer to others that are interested, but it gets a positive review from me anyhow.

kcrisman commented 12 years ago
comment:16

Should this be an underscore method like the previous one?

kcrisman commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 A fast way to check if an expression is zero is important in many places, see for example [#11143 comment:15](https://github.com/sagemath/sage/issues/11143#comment:15). We should put the numerical check mentioned there in a method (`_is_numerically_zero()`) of symbolic expressions (`sage.symbolic.expression.Expression`).

-Apply [attachment: trac_11513-is_trivally_zero.patch.](https://github.com/sagemath/sage/files/ticket11513/trac_11513-is_trivally_zero.patch..gz)
+Apply [attachment: trac_11513-is_trivally_zero.patch](https://github.com/sagemath/sage-prod/files/10653168/trac_11513-is_trivally_zero.patch.gz).
kcrisman commented 12 years ago
comment:17

Can we review this quickly and turn to another ticket that requires magic: #9953?

So is that a dup of #9627 or not? I'm not sure, myself.

burcin commented 12 years ago
comment:18

Replying to @kcrisman:

Should this be an underscore method like the previous one?

I don't see any reason to hide this from the user. We also removed the leading underscore from is_symbol(), is_numeric(), etc. recently.

zimmermann6 commented 12 years ago
comment:19

the patch looks good to me. Since this a new function, and it is not used anywhere yet, the doctests should still run, but I will try to be sure. Just a minor point: I'd prefer as name is_trivial_zero which is simpler.

Paul

zimmermann6 commented 12 years ago
comment:20

I change the summary to better reflect the new function name.

Paul

burcin commented 12 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
 A fast way to check if an expression is zero is important in many places, see for example [#11143 comment:15](https://github.com/sagemath/sage/issues/11143#comment:15). We should put the numerical check mentioned there in a method (`_is_numerically_zero()`) of symbolic expressions (`sage.symbolic.expression.Expression`).

-Apply [attachment: trac_11513-is_trivally_zero.patch](https://github.com/sagemath/sage-prod/files/10653168/trac_11513-is_trivally_zero.patch.gz).
+Apply [attachment: trac_11513-is_trival_zero.patch](https://github.com/sagemath/sage-prod/files/10653169/trac_11513-is_trival_zero.patch.gz).
burcin commented 12 years ago
comment:21

Attachment: trac_11513-is_trival_zero.patch.gz

Replying to @zimmermann6:

Just a minor point: I'd prefer as name is_trivial_zero which is simpler.

Done, see attachment: trac_11513-is_trival_zero.patch.

zimmermann6 commented 12 years ago

Changed reviewer from Benjamin Jones to Benjamin Jones, Paul Zimmermann

zimmermann6 commented 12 years ago
comment:22

all doctests pass (with the previous patch). However, since the change is trivial, I give a positive review.

Paul

jdemeyer commented 12 years ago

Merged: sage-5.0.beta0