本日のC.A.D.

CAD において，変数順序の選定は非常に重要です． 例えば

? projs([x1,x2,x3,x4],[-218 + 955*x1^2*x2*x3 + 520*x2*x3^3 + 1017*x3^4 + 250*x1*x2*x4 - 391*x2^3*x4 - 525*x1*x3*x4^2]);
 *** using Lazard's method (MPP17).
[x4,1]
[x3,3]
[x2,4]
[x1,4] 
time = 3min, 10,999 ms.

Random-c-5, A.W.Strzebonski "Cylindrical Algebraic Decomposition using validated numerics"

ですが，変数順序を変えると

? projs([x3,x2,x1,x4],[-218 + 955*x1^2*x2*x3 + 520*x2*x3^3 + 1017*x3^4 + 250*x1*x2*x4 - 391*x2^3*x4 - 525*x1*x3*x4^2]);
 *** using Lazard's method (MPP17).
[x4,1]
[x1,3]
[x2,4]
[x3,6]
time = 734 ms.

? projs([x3,x2,x4,x1],[-218 + 955*x1^2*x2*x3 + 520*x2*x3^3 + 1017*x3^4 + 250*x1*x2*x4 - 391*x2^3*x4 - 525*x1*x3*x4^2]);
 *** using Lazard's method (MPP17).
[x1,1]
[x4,2]
[x2,4]
[x3,7]
time = 686 ms.

といった結果を得ます．

変数（消去）順序については
１．次数が低い変数から
２．それを含む項の全次数の最大値が小さい変数から
３．出現が少ない変数から
とする heuristic (C.W.Brown "Companion to the Tutorial Cylindrical Algebraic Decomposition") が有名で，提唱者の Brown 博士の tarski ( https://github.com/chriswestbrown/tarski ) にも suggest-var-order として実装されています．

> (suggest-var-order [-218 + 955*x1^2*x2*x3 + 520*x2*x3^3 + 1017*x3^4 + 250*x1*x2*x4 - 391*x2^3*x4 - 525*x1*x3*x4^2 > 0])
( x3:sym x2:sym x4:sym x1:sym )

上記と同じ ISSAC 2004 ( http://www3.risc.jku.at/conferences/issac2004/program.html ) で発表された Redlog の heuristic ( https://www.researchgate.net/publication/2899124_Efficient_Projection_Orders_for_CAD ) は，各変数に対して，それを主変数とする projection を 1 step だけ求め，得られた全ての項の全次数の和が最小の変数を各 level 毎に選んでゆくものです．

Redlog Revision 5715 of 2021-03-11, 12:26:36Z
(c) 1992-2021 T. Sturm and A. Dolzmann (www.redlog.eu)

6: rlcadporder(-218 + 955*x1^2*x2*x3 + 520*x2*x3^3 + 1017*x3^4 + 250*x1*x2*x4 - 391*x2^3*x4 - 525*x1*x3*x4^2 > 0);
+++ Optimizing projection order.
+ input order by blocks: -> (x4 x3 x2 x1)
+ current input block: (x4 x3 x2 x1)
[x4:50] [x3:312] [x2:122] [x1:48] choose x1
[x4:309] [x3:880] [x2:428] choose x4
[x3:2146] [x2:1398] choose x2
+ reordered block: (x1 x4 x2 x3)
+ optimized order: -> (x1 x4 x2 x3)
{x1,x4,x2,x3}$

Time: 201330 ms  plus GC time: 18470 ms

比較：
https://www.cl.cam.ac.uk/~lp15/papers/Arith/Huang-3heuristics.pdf

ML の導入例：
https://arxiv.org/pdf/1904.11061.pdf