An improved characteristic set algorithm for solving Boolean polynomialsystems is pro- posed. This algorithm is based on the idea of converting allthe polynomials into monic ones by zero decomposition, and using additions toobtain pseudo-remainders. Three important techniques are applied in thealgorithm. The first one is eliminating variables by new gener- ated linearpolynomials. The second one is optimizing the strategy of choosing polynomialfor zero decomposition. The third one is to compute add-remainders to eliminatethe leading variable of new generated monic polynomials. By analyzing the depthof the zero decompo- sition tree, we present some complexity bounds of thisalgorithm, which are lower than the complexity bounds of previouscharacteristic set algorithms. Extensive experimental results show that thisnew algorithm is more efficient than previous characteristic set algorithms forsolving Boolean polynomial systems.
展开▼
