GSoC 2019 - Week 1

This was the first week meeting with the GSoC mentors which was scheduled on Sunday 2nd June, 2019 between 11:30 AM - 12:30 PM (IST). Me, Amit and Yathartha were the attendees of the meeting. In this meeting we mainly discussed about the problems and implementation for my pull request #16890 to complete the lambert solver.
As Amit requested changes at the pull request to describe the problem in detail, to give proof of correctness and describe the plan more briefly. So here below are the all details for what I am trying to achieve and how I am trying to achieve this:-

Current Implementation

Let me show here code from _lambert function to show the current implementation so that I could describe the problem in detail:-

u = Dummy('rhs')
sol = []
# check only real solutions:
for k in [-1, 0]:
    l = LambertW(d/(a*b)*exp(c*d/a/b)*exp(-f/a), k)
    # if W's arg is between -1/e and 0 there is
    # a -1 branch real solution, too.
    if k and not l.is_real:
        continue
    rhs = -c/b + (a/d)*l

    solns = solve(X1 - u, x)
    for i, tmp in enumerate(solns):
        solns[i] = tmp.subs(u, rhs)
        sol.append(solns[i])
return sol

Explanation of for loop:

1. k == -1 :- In this case all the real solutions are considered due to not l.is_real.
2. k == 0 :- In this case all the solutions come out to be real as always.

What solutions are missed?

The solutions are missed due to the argument inside the LambertW function of value

l = LambertW(d/(a*b)*exp(c*d/a/b)*exp(-f/a), k)

While converting all lambert solvable equations to this form F(X, a..f) = a*log(b*X + c) + d*X + f = 0 some solutions get missed.

For eg: Consider the equation (a/x + exp(x/2)).diff(x) = 0 which is -a/x**2 + exp(x/2)/2 = 0(Please take note of the x**2 in denominator of a). And we can also write this equation as -a/(-x)**2 + exp(x/2)/2 = 0. What sympy do is to convert this equation to this form:

F(X, a..f) = a*log(b*X + c) + d*X + f = 0

which will be 2*log(x) + x/2 - log(a) = 0 and 2*log(-x) + x/2 - log(a) = 0 respectively: So solutions corresponding to both equations are:

2*log(x) + x/2 - log(a) = 0 --> [4*LambertW(sqrt(2)*sqrt(a)/4)] --> this is currently included
2*log(-x) + x/2 - log(a) = 0 --> [4*LambertW(-sqrt(2)*sqrt(a)/4)] --> this is missed

What type of lambert type equation it is for?

This is for the equations where the changing of cofficients of the target equation doesn’t change the original equation just like the above case.

What’s the current algorithm to solve such type of equation and what’s wrong with current logic?

Current implementation is shown above and what is wrong is that it is not considering the other logarithm equations which are originated from the original equation. 2*log(-x) + x/2 - log(a) = 0 in case of (a/x + exp(x/2)).diff(x) = 0.

What’s the proposed solution?

This problem can be solved by two methods as follows:

• Combining all the logarithm forms generated by the original equation(by taking abs)

  2*log(x) + x/2 - log(a) = 0 + 2*log(-x) + x/2 - log(a) = 0
                        \      /
                         \    /
                          \  /
            2*log(abs(x)) + x/2 - log(a) = 0                     
  

  I think this method is not viable at this time as it will be very complex to solve the equation invloving abs with log.

• This method I propose to solve this problem i.e considering all solutions and eliminating by substitution. For example for this equation (1/x + exp(x/2)).diff(x) = 0 Possible solutions considered [4*LambertW(-sqrt(2)*sqrt(a)/4), 4*LambertW(sqrt(2)*sqrt(a)/4), \ 4*LambertW(-sqrt(2)*sqrt(a)/4, -1), 4*LambertW(sqrt(2)*sqrt(a)/4, -1)] Solutions after filtering from checksol [4*LambertW(-sqrt(2)*sqrt(a)/4), 4*LambertW(sqrt(2)*sqrt(a)/4)].

Why is the proposed solution better and how it won’t effect the other equations (no side effects)?

This method involves less computation to solve this problem i.e considering all solutions and eliminating by substitution rather than first converting the given equation to target equation in which we doesn’t know about coffecient of logarithmic equation and solving it again by making different equations from it in case of abs taken.

This doesn’t effect other equation because the only thing we are doing is considering all solutions and not changing code for other type of equations. And we are using checksol to check the correct solutions.

What is the testing strategy to verify that the proposed solution works?

Testing strategy should be to involve the cases where current implementation is missing other logarithmic equations.

Which examples/equations are we going to use to make sure that those are necessary and sufficient for testing purposes?

According to me these tests are sufficient test this strategy:

assert solve((a/x + exp(x/2)).diff(x), x) == \
        [4*LambertW(-sqrt(2)*sqrt(a)/4), 4*LambertW(sqrt(2)*sqrt(a)/4)]
assert solve(x*log(x) + 3*x + 1, x) == \
        [exp(-3 + LambertW(-exp(3))), exp(-3 + LambertW(-exp(3), -1))]
assert solve((1/x + exp(x/2)).diff(x, 2), x) == \
            [6*LambertW((-1)**(S(1)/3)/3), 6*LambertW((-1)**(S(1)/3)/3, -1)]
assert solve(-x**2 + 2**x, x) == [2, 4, -2*LambertW(log(2)/2)/log(2)]
# issue 4271
assert solve((a/x + exp(x/2)).diff(x, 2), x) == \
            [6*LambertW(-(-1)**(S(1)/3)*a**(S(1)/3)/3),
            6*LambertW((-1)**(S(1)/3)*a**(S(1)/3)/3),
            6*LambertW(-(-1)**(S(1)/3)*a**(S(1)/3)/3, -1),
            6*LambertW((-1)**(S(1)/3)*a**(S(1)/3)/3, -1)]
assert solve(x**2 - y**2/exp(x), x, y, dict=True) == \
                [{x: 2*LambertW(-y/2)}, {x: 2*LambertW(y/2)}]

Some test cases that fail due to some other reasons

• assert solve((1/x + exp(x/2)).diff(x), x) == \
  [4*LambertW(-sqrt(2)/4), 4*LambertW(sqrt(2)/4), 4*LambertW(-sqrt(2)/4, -1)]
  assert solve(x**2 - 2**x, x) == [2, 4]
  

  These tests are failing because checksol returns false but expected to return true Although _lambert is returning correct solutions of equation.

• assert solve(a/x + exp(x/2), x) == [2*LambertW(-a/2), 2*LambertW(a/2)] In this case 2*LambertW(a/2) which is not a solution is included because checksol returns none.

• >>>solve((1/x + exp(x/2)).diff(x, 2), x)
  [6*LambertW((-1)**(1/3)/3), 6*LambertW((-1)**(1/3)/3, -1)]
  

  here (-1)**1/3 can have these values -1, 1/6(1 - I*3**1/3), 1/6(1 + I*3**1/3) but sympy only take (-1)**1/3 to be 1/6(1 - I*3**1/3) whereas real solutions are [6*LambertW(-1/3), 6*LambertW(-1/3, -1)]

Why including checksol in _solve_lambert ?

Due to this test case:

p = symbols('p', positive=True)
eq = 4*2**(2*p + 3) - 2*p - 3
assert _solve_lambert(eq, p, _filtered_gens(Poly(eq), p)) == [
    -S(3)/2 - LambertW(-4*log(2))/(2*log(2))]

To remove the solutions which were supposed to be checked by checksol later in solve.

Pardon me if I missed a thing!!