Unstable plotting

[kliem]

#29935 discovered unstable plotting with doctests. This causes the following failures:

sage -t --long --random-seed=319106504607147180164974137764334084020 src/doc/en/prep/Symbolics-and-Basic-Plotting.rst  # 2 doctests failed
sage -t --long --random-seed=319106504607147180164974137764334084020 src/doc/en/prep/Calculus.rst  # 1 doctest failed
sage -t --long --random-seed=319106504607147180164974137764334084020 src/doc/en/thematic_tutorials/tutorial-notebook-and-help-long.rst  # 1 doctest failed
sage -t --long --random-seed=319106504607147180164974137764334084020 src/doc/en/prep/Programming.rst  # 1 doctest failed

sage -t --long --warn-long 85.2 --random-seed=123134235245245234 src/sage/combinat/sine_gordon.py  # 1 doctest failed

In all of those instances, primitives where split into two (with a hole).

To reproduce

sage: f(x)=x^3+1
sage: set_random_seed(319106504607147180164974137764334084020)
sage: plot(1,(x,-1,1),color="red", linestyle="--")
Launched png viewer for Graphics object consisting of 1 graphics primitive
sage: plot(1,(x,-1,1),color="red", linestyle="--")
Launched png viewer for Graphics object consisting of 1 graphics primitive
sage: plot(1,(x,-1,1),color="red", linestyle="--")
Launched png viewer for Graphics object consisting of 2 graphics primitives

sage: set_random_seed(319106504607147180164974137764334084020)
sage: plot(cos(x),(x,0,pi/2),fill=True,ticks=[[0,pi/4,pi/2],None],tick_formatter=pi)
Launched png viewer for Graphics object consisting of 2 graphics primitives
sage: plot(cos(x),(x,0,pi/2),fill=True,ticks=[[0,pi/4,pi/2],None],tick_formatter=pi)
Launched png viewer for Graphics object consisting of 2 graphics primitives
sage: plot(cos(x),(x,0,pi/2),fill=True,ticks=[[0,pi/4,pi/2],None],tick_formatter=pi)
Launched png viewer for Graphics object consisting of 3 graphics primitives

sage: set_random_seed(319106504607147180164974137764334084020)
sage: plot(sin(x), (x,0,2*pi))
Launched png viewer for Graphics object consisting of 1 graphics primitive
sage: plot(sin(x), (x,0,2*pi))
Launched png viewer for Graphics object consisting of 1 graphics primitive
sage: plot(sin(x), (x,0,2*pi))
Launched png viewer for Graphics object consisting of 2 graphics primitives

sage: set_random_seed(319106504607147180164974137764334084020)
sage: plot([x^n for n in [2..6]],(x,0,1))
Launched png viewer for Graphics object consisting of 6 graphics primitives
sage: plot([x^n for n in [2..6]],(x,0,1))
Launched png viewer for Graphics object consisting of 5 graphics primitives

sage: set_random_seed(123134235245245234)
sage: Y = SineGordonYsystem('A',(6,4,3))
sage: Y.plot()
Launched png viewer for Graphics object consisting of 220 graphics primitives
sage: Y.plot()
Launched png viewer for Graphics object consisting of 221 graphics primitives
sage: Y.plot()
Launched png viewer for Graphics object consisting of 221 graphics primitives
sage: Y.plot()
Launched png viewer for Graphics object consisting of 219 graphics primitives

This is caused by #13246, which adds exclusion points in the plot, whenever two x-values are far apart. However, it seems more natural to actually keep track of those points where the computation failed.

Component: graphics

Keywords: plotting

Author: Jonathan Kliem

Branch/Commit: d6e51f3

Reviewer: Dave Morris

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

[mkoeppe]

Replying to @kliem:

In all of those instances, primitives where split into two (with a hole).

I think I have seen such sporadic plotting errors in the wild.

[kliem]

comment:3

It's not like I tried many random seeds.

For the first one, your chance is about 99 percent to get it right. The more complicated your object, the lower the chance obviously. For the last object, it appears to be about 64 percent. Of course, it is much harder to see the mistake there.

[kliem]

comment:4

One more

sage -t --long --random-seed=1231241241243 src/sage/plot/plot.py
**********************************************************************
File "src/sage/plot/plot.py", line 321, in sage.plot.plot
Failed example:
    print(p1 + p2)
Expected:
    Graphics object consisting of 2 graphics primitives
Got:
    Graphics object consisting of 3 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 323, in sage.plot.plot
Failed example:
    p1 + p2    # display it
Expected:
    Graphics object consisting of 2 graphics primitives
Got:
    Graphics object consisting of 3 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 1620, in sage.plot.plot.plot
Failed example:
    plot([b(n) for n in [1..5]], 0, 20, fill='axis')
Expected:
    Graphics object consisting of 10 graphics primitives
Got:
    Graphics object consisting of 11 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 2756, in sage.plot.plot.polar_plot
Failed example:
    polar_plot([(1.2+k*0.2)*log(x) for k in range(6)], 1, 3 * pi, fill={0: [1], 2: [3], 4: [5]})
Expected:
    Graphics object consisting of 9 graphics primitives
Got:
    Graphics object consisting of 10 graphics primitives

[kliem]

comment:5

And more

sage -t --long --random-seed=319106504607147180164974137764334084020 src/sage/plot/colors.py
**********************************************************************
File "src/sage/plot/colors.py", line 1166, in sage.plot.colors.hue
Failed example:
    p
Expected:
    Graphics object consisting of 20 graphics primitives
Got:
    Graphics object consisting of 21 graphics primitives
**********************************************************************

sage -t --long --random-seed=319106504607147180164974137764334084020 src/sage/plot/plot.py
**********************************************************************
File "src/sage/plot/plot.py", line 1086, in sage.plot.plot.plot
Failed example:
    plot(sin, 0, 10, color='purple')
Expected:
    Graphics object consisting of 1 graphics primitive
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 2053, in sage.plot.plot.?
Failed example:
    p1+p2
Expected:
    Graphics object consisting of 2 graphics primitives
Got:
    Graphics object consisting of 3 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 2512, in sage.plot.plot.parametric_plot
Failed example:
    parametric_plot((1, t), (t, 0, 4))
Expected:
    Graphics object consisting of 1 graphics primitive
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************
File "src/sage/plot/plot.py", line 3155, in sage.plot.plot.plot_semilogx
Failed example:
    plot_semilogx(20*log(abs(f), 10), (s, 1, 1e6))
Expected:
    Graphics object consisting of 1 graphics primitive
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************

[kliem]

comment:6

sage -t --long --random-seed=123134235245245234 src/sage/plot/plot.py
**********************************************************************
File "src/sage/plot/plot.py", line 1931, in sage.plot.plot.plot
Failed example:
    plot(x, x, 0, 1, legend_label=label)
Expected:
    Graphics object consisting of 1 graphics primitive
Got:
    Graphics object consisting of 2 graphics primitives
**********************************************************************

[kliem]

It's not like you wouldn't see it.

[kliem]

comment:7

Attachment: tmp_768r4405.png

I'm moving this up to critical, because there is a total of 1354 doctests while they are pretty unstable.

[DaveWitteMorris]

Branch: public/29954

[DaveWitteMorris]

comment:10

I think this will be easy to fix. In fact, this PR may solve the problem, but I think we should do something more intelligent.

The problem is a bug in the adaptive graphing code. It assumes that if two consecutive plot points a and b are more than twice as far apart as the average distance between consecutive plot points, then there is a problem and we should not plot anything between a and b. However, the distance between consecutive plot points will be very large in any region where the graph is close to being linear, so the algorithm can erroneously add gaps to the graph in those regions.

This PR just changes "twice as far apart" to "five times as far apart". It seems to fix all of the examples listed above. But it should be easy to write a more intelligent patch that only puts gaps in regions where there is a problem evaluating the function.

---

New commits:

7c9ab8f

trac 29954 graph gap times 5

[DaveWitteMorris]

Commit: 7c9ab8f

[DaveWitteMorris]

comment:11

The ticket that introduced this part of the code is #13246 (merged in 6.3). The discussion on that ticket mentions the need for speed, so, although I think we do want to be more intelligent, perhaps we will decide to also offer a simple patch like this one (just changing "twice" to some other number) as an option (or maybe even as the default).

[kliem]

comment:12

Thanks for figuring out the problem.

The whole fix in #13246 seems strange to me and needs serious reworking:

plot(1/(x+1), -3, 1, plot_points=500)

plot(tan(x), -3, 3)

This is awful and -infinity and +infinity should never be connected. Here the y-value is too far apart to connect it and this isn't checked at all.

I don't like the approach done in #13246 for the following reasons:

adaptive_refinement distinguishes between not returning anything, because the y-values are close enough together and not returning anything because either recursion depth was exceeded or there was a computation error. Also generate_plot_points collects the exception indices.

However, none of this already collected information is returned by generate_plot_points and we completely start over trying to guess, where to add exclusion points. I mean generate_plot_points and adaptive_refinement have already figured out, where the those things should be.

As you mentioned above, in our case adaptive_refinement just doesn't refine, because this thing is close to linear and thus adaptive_refinement thinks things are fine. We should use this information and not discard it.

It think this will also fix the errornous connection made above.

[kliem]

Changed commit from 7c9ab8f to none

[kliem]

Changed branch from public/29954 to -remove-failures-of-adaptive-recursionpublic/29954-

[kliem]

comment:13

Actually, adaptive_refinement fails quite a lot. I think this is, because it takes the absolute error instead of a relative one.

But, I don't think its okay to just connect things were adaptive_refinement fails, this is a really bad default in my opinion.

sage: f(x) = (floor(x)+0.5) / (1-(x-0.5)^2)                                                                                                                                         
sage: plot(f, (x, -3.5, 3.5), ymin=-5, ymax=5)                                                                                                                                      
Launched png viewer for Graphics object consisting of 1 graphics primitive

This thing isn't continuous and the only way to fix it, is to manually enter the points to exclude. However, the current code does a pretty good job in detecting those places, we just currently ignore everything that was obtained.

[kliem]

Changed branch from -remove-failures-of-adaptive-recursionpublic/29954- to public/29954-remove-failures-of-adaptive-recursionpublic/29954-

[kliem]

New commits:

67df47d

do not connect plots when adaptive recursion failed

[kliem]

Commit: 67df47d

[kliem]

Changed branch from public/29954-remove-failures-of-adaptive-recursionpublic/29954- to public/29954-remove-failures-of-adaptive-recursion

[kliem]

comment:16

But we could also just fix this bug here by changing from 2 times to 5 times as you suggested and move the other stuff to a seperate ticket, because in a way, it is a seperate issue.

[DaveWitteMorris]

comment:17

I did not look at the details yet, but I fully agree that the approach in this PR is the correct direction: we should keep track of the unplottable points, and use those to determine the gaps in the graph. It is much better than changing 2 times to 5 times, which does not actually solve the problem (just makes it less common). When you set this ticket to "needs review", I will look at it more carefully.

Let's get this PR merged, and open a separate ticket for additional improvements to the adaptive refinement. (I consider the issue in comment:12 to be a separate issue, unless this PR already fixes the problem as a side-effect.)

[kliem]

Changed commit from 67df47d to 5260baf

[kliem]

New commits:

f082fac	fix unstable plotting by keeping track of non-defined points
5260baf	documentation

[kliem]

Changed branch from public/29954-remove-failures-of-adaptive-recursion to public/29954-only-fix-bug

[kliem]

Author: Jonathan Kliem

[kliem]

comment:19

I think I seperated the bug fix from the behavior change.

[DaveWitteMorris]

comment:20

Thanks, this is excellent! I do have a few minor suggestions, though:

Would it be better to make excluded a keyword-only argument? (By changing excluded=False to *, excluded=False in the definitions of adaptive_refinement and generate_plot_points.)

These two lines (the definitions of adaptive_refinement and generate_plot_points) are excessively long, so please add a line break before the 80th character.

In the docstring of adaptive_refinement, the description of excluded in the "INPUT" section makes it sound like two lists will be returned ("add a list of discovered points"). So I think it would be better to say something like: "also return locations where it has been discovered that the function is not defined". (Or "locations where" could be changed to "x-values at which".)

The term "point" usually refers to an ordered pair (x,y) in the documentation of this file, so it is confusing when it is used to refer to a value of x. Therefore, in the description of excluded in the "OUTPUT" section of the docstring for adaptive_refinement, please change this to something like: "if excluded, then x-values for which the calculation failed are included in the list, with 'NaN' as the y-value.

For the same reason, in the INPUT section of the docstring for generate_plot_points, please change "a list of discovered points, for which" to "a list of discovered x-values, at which". And in the new doctest of this method, please change "Excluded points" to "Excluded x-values".

The term "value" usually refers to a value of the function, or, in other words, a y-value, so I find it confusing when this word is used for a value of x. Therefore, in the OUTPUT section of the docstring for generate_plot_points, please change "a list of not-defined values" to something like "a list of x-values at which the function is not defined". Please also change the name of the variable values to x_values (or something similar).

The file sometimes has two blank lines after "INPUT:" or "OUTPUT:", and sometimes only one. Please standardize this, even though this was not your fault. (I think there is only supposed to be one.)

(Let me know if you would like me to make these changes to the file for you.)

[DaveWitteMorris]

Reviewer: Dave Morris

[DaveWitteMorris]

comment:21

I opened ticket #31169 for additional improvements to (adaptive) plotting.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

bb285fb	reviewers comments
31dec06	somewhat adopt general conventions for documentation
ebc50c7	make excluded a keyword argument only

[sagetrac-git]

Changed commit from 5260baf to ebc50c7

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

4edd374	Merge branch 'public/29954-only-fix-bug' of git://trac.sagemath.org/sage into 29954unstableplot
d6e51f3	minor docstring edits

[sagetrac-git]

Changed commit from ebc50c7 to d6e51f3

[DaveWitteMorris]

comment:25

Thanks again! I made a few minor edits to some docstrings. If you agree with these changes, you can set to positive review on my behalf.

[kliem]

comment:26

Sure. Thank you.

[vbraun]

Changed branch from public/29954-only-fix-bug to d6e51f3