Opened 7 years ago

Last modified 5 years ago

#14229 needs_work enhancement

Remove vacuous solutions from solve

Reported by: ppurka Owned by: burcin
Priority: major Milestone: sage-6.4
Component: symbolics Keywords:
Cc: kcrisman, jondo Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jondo)

Sometimes solve and its variants tend to report vacuous solutions. A recent one from ask.sagemath is the following:

sage: x,y = var('x,y')
sage: solve([x^2*y^2 <= x^2*y, x^2*y^2 > x^2*y],[x,y])
[[x == 0, 1 < y, 0 != 0], [x == 0, y < 0, 0 != 0]]

Shouldn't we remove these meaningless solutions? The attached patch contains a potential solution. If it seems reasonable, then similar changes could be introduced in solve_ineq.

The output of the above command after this patch is as expected:

sage: x,y = var('x,y')
sage: solve([x^2*y^2 <= x^2*y, x^2*y^2 > x^2*y],[x,y])
[]

If you can translate this to maxima proper, please feel free to do so and submit a patch upstream.


Workaround: call maxima_calculus("domain: real") before solve (see comment 12).

Attachments (1)

trac_14229-remove_vacuous_solutions.patch (2.2 KB) - added by ppurka 7 years ago.
Apply to devel/sage

Download all attachments as: .zip

Change History (18)

Changed 7 years ago by ppurka

Apply to devel/sage

comment:1 Changed 7 years ago by ppurka

  • Description modified (diff)

comment:2 Changed 7 years ago by ppurka

  • Description modified (diff)

comment:3 Changed 7 years ago by kcrisman

  • Cc kcrisman added

comment:4 Changed 7 years ago by ppurka

  • Status changed from new to needs_review

comment:5 Changed 7 years ago by nbruin

This kind of change should really be made to maxima, not to sage's postprocessing of what maxima returns.

comment:6 Changed 7 years ago by ppurka

  • Description modified (diff)
  • Status changed from needs_review to needs_work
  • Work issues set to port to upstream

If someone knows how to translate this to maxima, please feel free to put this upstream. Thanks! [ I can not spend time in learning maxima right now. :( ]

comment:7 Changed 7 years ago by ncohen

Helloooooooo !!

You remove equations that do not contain a variable, but couldn't 0=0 appear from time to time ? Secondly, can't the expression "bool(solution_list)" be costly from time to time ?

You could also write, later in the patch

sol_list = filter(_test_solution, string_to_list_of_solutions(repr(s)))

Nathann

comment:8 Changed 7 years ago by ppurka

0==0 can appear, but bool(0==0) should evaluate to True. Which is fine by me. The point is to remove solutions which are clearly false. Anyway, this patch is going nowhere since nbruin suggests putting this upstream (I can not do that now).

EDIT: bool(solution_list) is done only when a symbolic expression (i.e., not a list of symbolic expressions) is input and there are no variables in the symbolic expression. This shouldn't introduce a significant slowdown. The solve function itself will probably take way more time than what these boolean checks will take.

Last edited 7 years ago by ppurka (previous) (diff)

comment:9 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:10 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:12 Changed 5 years ago by nbruin

These vacuous solutions seem to arise from the fact that solving inequalities with domain: complex gives some problems, which is to be expected. So rather than trying to clean up the mess afterwards, we should find a way of setting domain: real in maxima before solving inequalities:

sage: sage: x,y = var('x,y')
sage: maxima_calculus("domain: real")
real
sage: sage: solve([x^2*y^2 <= x^2*y, x^2*y^2 > x^2*y],[x,y])
[]

See sage-devel too.

comment:13 Changed 5 years ago by jondo

  • Cc jondo added

comment:14 follow-up: Changed 5 years ago by nbruin

One may be concerned with performance when we have to set these flags all the time. On the expect interface that's probably silly anyway, and on the library interface we can reach a little deeper and save some time:

sage: maxima_calculus(1) # make sure maxima_lib is initialized
sage: from sage.libs.ecl import EclObject,ecl_eval
sage: set_complex=ecl_eval("(defun sc () (setf $DOMAIN '$COMPLEX))")
sage: set_real=ecl_eval("(defun sc () (setf $DOMAIN '$REAL))")
sage: %timeit set_complex()
100000 loops, best of 3: 2.14 µs per loop
sage: %timeit maxima_calculus("domain: complex")
10000 loops, best of 3: 146 µs per loop

For comparison:

sage: %timeit solve([x<y],[x,y])
100 loops, best of 3: 4.6 ms per loop

so I think we can afford a little set_real.eval(); ...solve iquality; set_complex.eval();. We could keep a flag on what we set last and be lazy with flipping, but I expect that solving inequalities is relatively rare, and always slow, so we shouldn't slow down other operations with testing for a flag. To give you an idea, the following does call into maxima:

sage: %timeit integrate(x,x)
1000 loops, best of 3: 693 us per loop
Last edited 5 years ago by nbruin (previous) (diff)

comment:15 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:16 in reply to: ↑ 14 Changed 5 years ago by jondo

Replying to nbruin:

so I think we can afford a little set_real.eval(); ...solve iquality; set_complex.eval();.

So do you think this should be done in the Sage solve function when it detects inequalities?

comment:17 Changed 5 years ago by jondo

  • Description modified (diff)
  • Work issues port to upstream deleted
Note: See TracTickets for help on using tickets.