17
$\begingroup$

While answering Trouble getting FindInstance to return multiple results for certain constraints it became clear that for this problem FindInstance would be better starting with small numbers, but it does not.

The function has the Method option:

Options[FindInstance, Method]   (*  Out: {Method -> Automatic}  *)

Yet, I cannot find documentation for the methods (and methods sub-options) that it accepts.

  • What Method values does FindInstance accept?
  • Will any of them scan an Integer search space small-values first?
$\endgroup$
6
  • $\begingroup$ A perusal of ??System`InstanceDump`* might provide a few clues, I think. $\endgroup$ Jun 14, 2012 at 12:43
  • $\begingroup$ Related> Here there are a few options for FindInstance[] mentioned reference.wolfram.com/mathematica/tutorial/… $\endgroup$ Jun 14, 2012 at 12:59
  • $\begingroup$ @J.M. that command yields Information::nomatch: No symbol matching System`InstanceDump`* found. >> on my system. $\endgroup$
    – Mr.Wizard
    Jun 14, 2012 at 13:13
  • $\begingroup$ @belisarius I see the low-level (and wide effect) SystemOptions, but not Method options. Am I overlooking something? $\endgroup$
    – Mr.Wizard
    Jun 14, 2012 at 13:13
  • $\begingroup$ Ech, I keep forgetting that you're on version seven... $\endgroup$ Jun 14, 2012 at 13:14

1 Answer 1

10
$\begingroup$

Here is a partial answer. I believe for Method -> {opts}, opts may be any of the following, and they will have whatever effect they have:

Internal`InequalitySolverOptions[]
Internal`ReduceOptions[]
Internal`NSolveOptions[]
(*
{"ARSDecision" -> False, "BrownProjection" -> True, "CAD" -> True, 
 "CADAlgebraicCoefficients" -> True, "CADBacksubstitution" -> Automatic,
 "CADCombineCells" -> True, "CADConstruction" -> Automatic,
 "CADDefaultPrecision" -> 30.103, "CADExtraPrecision" -> 30.103, "CADMethod" -> Automatic, 
 "CADNRootsMethod" -> Automatic, "CADSortVariables" -> Automatic, 
 "CADZeroTest" -> {0, ∞}, "EquationalConstraintsCAD" -> Automatic, 
 "FGLMBasisConversion" -> False, "FGLMElimination" -> Automatic, 
 "GenericCAD" -> True, "GroebnerCAD" -> True, 
 "LinearDecisionMethodCrossovers" -> {0, 30, 20, Automatic}, 
 "LinearEquations" -> True, "LinearQE" -> True, "LWDecision" -> True, 
 "LWPreprocessor" -> Automatic, "ProjectAlgebraic" -> Automatic, 
 "ProveMultiplicities" -> True, "QuadraticQE" -> Automatic, 
 "QVSPreprocessor" -> False, "ReducePowers" -> Automatic, 
 "RootReduced" -> False, "Simplex" -> True, 
 "SimplifyInequalities" -> Automatic, "ThreadOr" -> True, "ZengDecision" -> False}

{"ADDSolveBound" -> 8, "AlgebraicNumberOutput" -> True, 
 "BDDEliminate" -> Automatic, "BooleanInstanceMethod" -> Automatic, 
 "BranchLinearDiophantine" -> False, "CacheReduceResults" -> Automatic,
 "DiscreteSolutionBound" -> 10, "ExhaustiveSearchMaxPoints" -> {1000, 10000}, 
 "FactorEquations" -> Automatic, "FactorInequalities" -> False, 
 "FinitePrecisionGB" -> False, "ImplicitIntegerSolutions" -> Automatic, 
 "IntervalRootsOptions" -> {"AllowIncomplete" -> True, "FailDepth" -> 20,
   "MaxDepth" -> 50, "MaxFailures" -> 100, "MaxIncomplete" -> 1000,
   "MaxSimplified" -> 1000, "MaxSteps" -> 100000, "MinPrecision" -> 12}, 
 "LatticeReduceDiophantine" -> True, "LinearEliminationMaxDepth" -> ∞, 
 "MaxFrobeniusGraph" -> 1000000, "MaxModularPoints" -> 1000000, 
 "MaxModularRoots" -> 1000000, "MaxPrimeIndex" -> 1000000000, 
 "NIntegrateTimeConstraint" -> 60, "PresburgerQE" -> Automatic, 
 "QuickReduce" -> False, "RandomInstances" -> Automatic, 
 "RealRootsOptions" -> {"MaxExtensionDegree" -> 5, "MaxFactorSquareFreeDegree" -> 10000, 
   "MaxNestedRootsDegree" -> 100, "SparsityThreshold" -> 0.02}, 
 "ReorderVariables" -> Automatic, "SieveMaxPoints" -> {10000, 1000000}, 
 "SolveDiscreteSolutionBound" -> 1000000, "SyntacticSolveAssumptions" -> False, 
 "TranscendentalRecursionLimit" -> 12, "UseNestedRoots" -> Automatic, 
 "UseOldReduce" -> False, "UseTranscendentalRoots" -> Automatic, 
 "UseTranscendentalSolve" -> True}

{"ComplexEquationMethod" -> Automatic, "MonomialOrder" -> Automatic, 
 "ReorderVariables" -> True, "SelectCriterion" -> (True &), 
 "Tolerance" -> 0, "UseSlicingHyperplanes" -> True}
*)

I do not know if there are other settings that may be used. Building on comments by belisarius and Mr. Wizard, many (or maybe all) of the above are SystemOptions that may be passed via the Method option to FindInstance. I do not know what all these options do. Here is an example to show they, or at least one of them, have an effect when passed through the Method option (see the discussion of the "SieveMaxPoints" option in Diophantine Polynomial Systems for an example that was the basis for this one):

FindInstance[x^2 + 21 y^3 - 17 z^4 == 632, {x, y, z}, Integers]

FindInstance::nsmet: The methods available to FindInstance are insufficient to find the requested instances or prove they do not exist. >>

FindInstance[x^2 + 21 y^3 - 17 z^4 == 632, {x, y, z}, Integers, 
 Method -> {"SieveMaxPoints" -> {10^4, 10^8}}]
(*  {{x -> -944, y -> 22, z -> 16}}  *)

Update - another example. This one is from Real Polynomial Systems mentioned by @belisarius. It is the last example in the tutorial and it is supposed to show a case in which "ZengDecision" -> True improves the timing. In that respect things seem to have changed, but the option still has an effect.

FindInstance[
  x^4 + y^4 + z^4 + w^4 - 5 x y z w + x^2 + y^2 + z^2 + w^2 + 1 < 0,
  {x, y, z, w}, Reals] // AbsoluteTiming
(*  {0.140519, {{x -> -6, y -> -5, z -> -6, w -> -4}}}  *)

FindInstance[
  x^4 + y^4 + z^4 + w^4 - 5 x y z w + x^2 + y^2 + z^2 + w^2 + 1 < 0,
  {x, y, z, w}, Reals, Method -> "ZengDecision" -> True] // AbsoluteTiming
(*  {0.4111, {{x -> -(7/2), y -> -4, z -> -3, w -> -3}}}  *)

Note: There are other Internal`*Options with corresponding Internal`Set*Options, which might be used in certain cases of FindInstance. And if not in FindInstance, then perhaps they can be used in other functions with an obscure Method option. Each with one exception corresponds to a group of SystemOptions[].

$\endgroup$
3
  • $\begingroup$ At least some of those look like they're supposed to be options for CylindricalDecomposition[] $\endgroup$ Jul 29, 2015 at 15:02
  • $\begingroup$ Thanks Michael! About time this old question got an answer. :-) +1 Necromancer for you. $\endgroup$
    – Mr.Wizard
    Jul 29, 2015 at 17:31
  • $\begingroup$ @Mr.Wizard Thanks for the accept. I added a little more information that might be used in other Method questions, if there are any. $\endgroup$
    – Michael E2
    Jul 29, 2015 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.