Why are these simple equations so slow to `Solve`?

Question

$Version
(*14.1.0 for Mac OS X ARM (64-bit) (July 16, 2024)*)

This set of equations is generated by other codes and hence is redundant:

eqs={-1+a,-1+b,-((-1+a) b),(1-a) b}==0//Thread

and to my surprise, MMA 14.1 cannot solve it directly

TimeConstrained[Timing[Solve[eqs,{a,b}]],10]
(*$Aborted*)

Solve[eqs//Simplify,{a,b}]//Timing
(*{0.000643`,{{a->1,b->1}}}*)

Solve[eqs,{a,b},MaxRoots->1]//Timing
(*{0.001684`,{{a->1,b->1}}}*)

Since Solve has been updated in version 14.1 (and I don't have older ones), is this a bug due to introducing MaxRoots?

Any other example?

Any ad hoc fixing? (I don't want to use Simplify since it's consuming in bad cases.)

Answer 1

The bug (a typo that leads to an infinite loop, fixed for the next version) affects certain systems with more equations than variables. More precisely, for every k <= the number of variables, the system needs to contain an equation that involves only the first k variables, and for some k there need to be at least two equations in k+1 variables that vanish identically on a solution for the first k variables. Here, both -((-1 + a) b) and (1 - a) b vanish for a->1. In such cases one can avoid the buggy code by calling Solve with Method->{"UseTriangularRoots"->False}.

In[2]:= Solve[eqs, {a, b}, Method->{"UseTriangularRoots"->False}]               
Out[2]= {{a -> 1, b -> 1}}

Answer 2

eqs = {-1 + a, -1 + b, -((-1 + a) b), (1 - a) b} == 0 // Thread
Timing[Solve[Union[Expand@eqs], {a, b}]]

If you expand the equations you see you have one equation repeated

 {-1 + a == 0, -1 + b == 0, b - a b == 0, b - a b == 0}

Doing Union removes the duplicated one. Now it is very fast. For some reason Solve did not see this.

Answer 3

$Version

(* "14.1.0 for Mac OS X ARM (64-bit) (July 16, 2024)" *)

Clear["Global`*"]

eqs = {-1 + a, -1 + b, -((-1 + a) b), (1 - a) b} == 0 // Thread

(* {-1 + a == 0, -1 + b == 0, -((-1 + a) b) == 0, (1 - a) b == 0} *)

Since you have more equations than Solve variables, use the option MaxExtraConditions

Solve[eqs, {a, b}, MaxExtraConditions -> All] // Timing

(* {0.000579, {{a -> 1, b -> 1}}} *)