MuPAD File `Elimination.mu` -- Documentation

Description

This file contains the algorithmical parts of the parametric Gaussian Elimination package. It provides a function elim that determines the solution set of a parametric linear system over all the partitions of its parameter space.

The algorithm is customizable by setting particular flags. Those flags are listed below.

COLUMN_SWAP_ALLOWED
TRUE to allow column swapping during the elimination process.
USE_MARKOWITZ
TRUE to use an adapted version of the Markowitz criterion for pivot selection.
USE_COLUMN_SIMPLIFICATION
TRUE to simplify a column if no constant pivot is found. The idea is to try to reduce the degree of the entries in a particular column in order to recieve an entry with zero degree which then can serve as a pivot element.
SIMPLIFY_AFTER_BRANCH
TRUE to specify that affecting the constraint store will lead to a simplification of all the polynomial entries of the remaining submatrix. Note that this option may lead to a fill-in of new variables.
USE_FURTHER_IMPROVEMENTS
TRUE to allow a number of non-documented heuristics which slightly improve the algorithm's efficiency.

By default, all the above flaged are set to TRUE.

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")

Index

`COLUMN_SWAP_ALLOWED`	:
`SIMPLIFY_AFTER_BRANCH`	:
`USE_COLUMN_SIMPLIFICATION`	:
`USE_FURTHER_IMPROVEMENTS`	:
`USE_MARKOWITZ`	:
`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 elim.
`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

Declaration

elim normalizes a matrix w.r.t. a set of constraints by means of Gaussian Elimination.

Parameters

`elim(A, C)`
`A`	:	matrix with entries `e` that are liftable to `DOM_POLY` via `poly(e)`
`C`	:	(optional) set of constraints given as a ConstraintStore object

Description

If no C is given, C is assumed to be empty.

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'.

top, index

elimRec an auxiliary method used by elim.

Parameters

`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

Description

elimRec returns a list of pairs [A', C'] where C' is a specialization of the given constraints and A' is the normal form of the given matrix with respect to C'.

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.

top, index

choosePivot manages the choose of a privot element

Parameters

`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

Description

choosePivot returns the index of a proper pivot element. The pivot index is returned as a sequence r, c containing the row index and the column index.

The selection strategie is as follows:

Select p := row, col as temporary pivot.
If the Markowitz criterion is allowed, update p to the Markowitz' suggestion. If p is constant w.r.t. the ConstraintStore, return p as final selection.
Otherwise, try to find a strict constant entry in p's column. If there is one, return this item as final selection.
Otherwise, if column simplifcation is allowed, simplify p's column. After that, try again to find a non-zero entry of degree 0 in the current column. If there is one, return this item as final selection.
Otherwise, ask the constraint store whether one of the polynomials in the current row represents a constant. If so, return such an entry as final selection.
Otherwise, if the markowitz suggestion was not zero w.r.t the constraint store, return that value.
Otherwise, try to find the simplest polynomial which is not zero with respect to the constraint store. If you find one, return this item as final selection.
Otherwise, the whole column does only contain zero entries. In this case, return an arbitrary entry.

Note that selecting a pivot may affect the matrix, if column simplification is allowed. That's why we don't take the matrix as a parameter value but rather as a gobal variable. The matrix is assumed to be found in the identifier mat.

top, index

markowitz selecting a pivot element with minimum fillin

Parameters

`markowitz(row, col)`
`row`	:	row where the submatrix starts
`col`	:	column where the submatrix starts

Description

markowitz determines the nonzero element of the specified submatrix that produces the least symbolic fillin and constant fillin.

top, index

markowitzSingleColumn Markowitz criterion where column swap is not allowed.

Parameters

`markowitzSingleColumn(row, col)`
`row`	:	top row of submatrix
`col`	:	left col of submatrix

Description

This is just like markowitz except that you'll always get an element of the col column as pivot. You should use this method iff COLUMN_SWAP_ALLOWED is FALSE.

top, index

simpler compares the complexity of two polynomials

Parameters

`simpler(p, q)`
`p`	:	one polynomial
`q`	:	one polynomial

Description

This method compares two polynomials and returns TRUE iff p is simpler than q.

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.

top, index

simplifySubmatrix simplifies the submatrix with respect to the current constraints

Parameters

`simplifySubmatrix(row, col, constraints)`
`row`	:	top row of submatrix to simplify
`col`	:	left column of submatrix to simplify
`constraints`	:	a constraint store