The algorithm is customizable by setting particular flags. Those flags are listed below.
It is easy to analyze the behaviour of this implementation by use of the methods defined in
Test.mu. Those methods are based on some portions of code that were inserted into
the methods of this file. In particular, the implementation here calls methods of
Test.mu to pass several statistical results to the testing architecture. Each line
of code in this file that exists for the purpose just described ends with the character
sequence "// ###". So if you want to slightly speed up the implementation,
you can feel free to delete all the lines ending with "// ###" -- they are
not a part of the algorithm. (Design pattern "Template Method")
|choosePivot||:||manages the choose of a privot element|
|elim||:||normalizes a matrix w.r.t. a set of constraints by means of Gaussian Elimination.|
|elimRec||:||an auxiliary method used by
|markowitz||:||selecting a pivot element with minimum fillin|
|markowitzSingleColumn||:||Markowitz criterion where column swap is not allowed.|
|simpler||:||compares the complexity of two polynomials|
|simplifySubmatrix||:||simplifies the submatrix with respect to the current constraints|
|elim||normalizes a matrix w.r.t. a set of constraints by means of Gaussian Elimination.|
|A||:||matrix with entries e that are liftable to DOM_POLY via poly(e)|
|C||:||(optional) set of constraints given as a ConstraintStore object|
elim is the user interface to invoke the Gaussian Elimination on a matrix A. The method returns a list of pairs [A', C'] where C' are specialisations of C and A' is the Gaussian normal form of A with respect to C'.
|elimRec||an auxiliary method used by
|elimRec(matrix, constraints, row, col)|
|matrix||:||the whole polynomial matrix that is to be normalized at the moment|
|constraints||:||ConstraintStore object representing the set of currently active constraints|
|row||:||row index of the top left element of the submatrix currently active|
|col||:||column index of the top left element of the submatrix currently active|
This method is for internal use only -- no checking is done.
Though the method is declared to use for recursive use, most of the work will be done iteratively. Recursive calls are only needed if no proper pivot element is found, i.e. the selected pivot is neither zero nor constant w.r.t. the current constraint store. In this case, one of the two branches is done by a recursive call of elimRec, while the calling procedure will continue to process the other branch itself.
|choosePivot||manages the choose of a privot element|
|choosePivot(constraints, row, col)|
|constraints||:||ConstriantStore object with the set of current constriants.|
|row||:||the row of the top left element of the submatrix of interest|
|col||:||the column of the top left element of the submatrix of interest|
The selection strategie is as follows:
|markowitz||selecting a pivot element with minimum fillin|
|row||:||row where the submatrix starts|
|col||:||column where the submatrix starts|
|markowitzSingleColumn||Markowitz criterion where column swap is not allowed.|
|row||:||top row of submatrix|
|col||:||left col of submatrix|
|simpler||compares the complexity of two polynomials|
What is the simpler polynom?
If degree(p) * monomials(p) < degree(q) * monomials(q), then p is simpler. If those values are equal and degree(p) < degree(q), then p is simpler. If even the degrees are equal and monomials(p) < monomials(q), then p is simpler. If these numbers are also equal and the leading monomial of p is less than the leading monomial of q (w.r.t. DegInvLexOrder), then p is simpler.
|simplifySubmatrix||simplifies the submatrix with respect to the current constraints|
|simplifySubmatrix(row, col, constraints)|
|row||:||top row of submatrix to simplify|
|col||:||left column of submatrix to simplify|
|constraints||:||a constraint store|