This module is about computing the right kernel of matrices with polynomial entries. It provides various general purpose tools for constructing solvers.
By a solver, we mean a function of the following form:
- nullspace.solver(mat, degrees=[], infolevel=0)¶
INPUT:
- mat – a matrix \(A\) over some polynomial ring
- degrees – list of nonnegative integers, providing, for each variable \(x\), a bound on the degree with which \(x\) is going to appear in the output. This data is optional. If set to [], the solver has to figure out the degrees by itself.
- infolevel – a nonnegative integer indicating the desired verbosity (default=0), or a pair (u, v) where u indicates the desired verbosity and v specifies how many leading spaces should be added to the printed lines (default=0).
OUTPUT:
- list of vectors \(v\) such that \(A*v=0\)
Depending on the application from which a polynomial matrix arises, the preferred way of computing its nullspace may be different. The purpose of this module is not to provide a single solver which is good for every possible input, but instead, it provides a collection of functions by which solvers can be composed.
For example, gauss is a function for constructing a solver using fraction free Gaussian elimination. It works for most polynomial domains.
sage: my_solver = gauss()
sage: A = MatrixSpace(ZZ['x'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
sage: A = MatrixSpace(GF(1093)['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
Several other functions create solvers which reduce the nullspace problem to one or more nullspace problems over simpler domains which are then solved by another solver. This solver can be chosen by the user.
For example, kronecker is a function for constructing a solver for matrices of multivariate polynomials. It requires as parameter a solver for matrices of univariate polynomials, for instance a solver created by gauss.
sage: my_solver = kronecker(gauss())
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
For large random examples, the solver created by kronecker(gauss()) is likely to be significantly faster than the solver created by gauss(). Even faster, for matrices of polynomials with integer coefficients, is a solver using chinese remaindering combined with kronecker substitution combined with gaussian elimination:
sage: my_solver = cra(kronecker(gauss()))
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
Alternatively:
sage: my_solver = kronecker(cra(gauss()))
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
Here is the same example with a variant of the same solver (not necessarily faster).
sage: my_solver = cra(kronecker(lagrange(sage_native, start_point=5), newton(sage_native)), max_modulus = 2^16, proof=True, ncpus=4)
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 5).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
A particular solver will typically only be applicable to matrices with entries in a domain for which it was designed for. Below is an overview of the functions provided in this module, together with the supported input domains, and the input domains of the subsolvers they require. The notation \(K[x,...]\) refers to univariate or multivariate polynomial ring, understanding the same reading (unvariate vs. multivariate) in corresponding rows of the 2nd and 3rd column.
method input domain requires subsolver for cra \(K[x,...]\) where \(K\) is \(ZZ\), \(QQ\), or \(GF(p)\) \(GF(p)[x,...]\) galois \(QQ(alpha)[x,...]\) \(GF(p)[x,...]\) clear \(K(x,...)\) \(K[x,...]\) clear \(K[x,...]\) where \(K\) is the fraction field of \(R\) \(R[x,...]\) compress \(K[x,...]\) or \(K(x,...)\) same domain and \(GF(p)\) kronecker \(K[x,...]\) \(K[x]\) and \(GF(p)[x]\) gauss \(K[x,...]\) None wiedemann \(K[x,...]\) or \(K(x,...)\) None lagrange \(K[x]\) or \(K(x)\) where \(K\) is a field \(K\) hermite \(K[x]\) where \(K\) is a field None newton \(K[x]\) where \(K\) is a field \(K\) merge \(K[x,...][y,...]\) \(K[x,...,y,...]\) quick_check \(K[x,...]\) where \(K\) is \(ZZ\), \(QQ\), or \(GF(p)\) same domain and \(GF(p)\) sage_native \(K[x,...]\) or \(K(x,...)\) or \(K\) None
AUTHOR:
- Manuel Kauers (2012-09-16)
Constructs a solver which clears denominators in a given matrix over \(FF(R)[x..]\) or \(FF(R[x..])\) and then calls a subsolver on a matrix over \(R[x..]\)
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(ZZ['x'].fraction_field(), 4, 5).random_element()
sage: my_solver = clear(gauss())
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
sage: A = MatrixSpace(QQ['x'], 4, 5).random_element()
sage: my_solver = clear(gauss())
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
For turning a matrix over \(QQ(x)\) to one over \(ZZ[x]\), you need to clear twice: once the denominator of the rational functions, and then once more the denominators of the coefficients
sage: A = MatrixSpace(QQ['x'].fraction_field(), 4, 5).random_element()
sage: my_solver = clear(clear(gauss()))
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM: clears denominators and then applies the subsolver.
Warning
For unstructured matrices, clearing denominators may significantly increase the size of the system. In such situations, consider using nullspace.lagrange .
Constructs a solver which throws away unnecessary rows and columns and then applies the subsolver
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(ZZ['x'], 7, 4).random_element()*MatrixSpace(ZZ['x'], 4, 5).random_element()
sage: my_solver = compress(gauss())
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0, 0, 0, 0)
ALGORITHM:
Creates a subsolver based on chinese remaindering for matrices over \(K[x]\) or \(K[x,y,..]\) where \(K\) is \(ZZ\) or \(QQ\) or \(GF(p)\).
INPUT:
OUTPUT:
EXAMPLES:
sage: A = MatrixSpace(ZZ['x', 'y'], 4, 7).random_element(degree=3)
sage: my_solver = cra(kronecker(gauss()))
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM:
Creates a subsolver based on chinese remaindering for matrices over \(K[x]\) or \(K[x,y,..]\) where \(K\) is a single algebraic extension of \(QQ\)
INPUT:
OUTPUT:
EXAMPLES:
sage: R.<x> = QQ['x']
sage: K.<a> = NumberField(x^3-2, 'a')
sage: A = MatrixSpace(K['x'], 4, 5).random_element(degree=3)
sage: my_solver = galois(gauss())
sage: ##V = my_solver(A)
sage: ##A*V[0]
##(0, 0, 0, 0)
ALGORITHM:
Creates a solver based on fraction free gaussian elimination.
INPUT:
pivot – a function which takes as input: a matrix mat (as list of list of ring elements), four integers \(r\), \(n\), \(c\), \(m\) specifying the index range mat[r:n][c:m], and the zero element of the ring, and returns and a pair \((i, j)\) such that mat[i][j]!=zero and \((i, j)\) is a good choice for a pivot. The function returns None iff there are no nonzero elements in the given range of the matrix.
The default function chooses \((i,j)\) such that mat has many zeros in row \(i\) and column \(j\), and mat[i][j] has a small number of terms.
ncpus – maximum number of cpus that may be used in parallel by this solver
fun – if different from None, at the beginning of each iteration of the outer loops of forward and backward elimination, the solver calls fun(mat, idx), where mat is the current matrix (as list of lists of elements) and idx is a counter. This functionality is intended for analyzing the elimination process, e.g., for inspecting how well the solver succees in maintaining the sparsity of the matrix. The solver assumes that the function won’t modify the matrix.
OUTPUT:
EXAMPLES:
sage: A = MatrixSpace(GF(1093)['x'], 4, 7).random_element(degree=3)
sage: my_solver = gauss()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM: fraction-free gaussian elimination with heuristic content removal and Markoviz pivot search.
Creates a solver which computes a nullspace basis of minimal degree.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = MatrixSpace(GF(1093)['x'], 4, 7).random_element(degree=3)
sage: my_solver = hermite()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM: Hermite-Pade approximation
Creates a solver for matrices of multivariate polynomials over some domain \(K\), based on a given solver for matrices over univariate polynomials
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(GF(1093)['x','y'], 4, 7).random_element(degree=3)
sage: mysolver = kronecker(gauss())
sage: V = mysolver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM:
Creates a solver for matrices of univariate polynomials or rational functions over some field \(K\), based on a given solver for matrices over \(K\), using evaluation+interpolation.
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(GF(1093)['x'], 4, 7).random_element(degree=3)
sage: my_solver = lagrange(sage_native)
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM:
Note
Constructs a solver which first merges towers of polynomial or rational function extensions into a single one and then applies the subsolver.
INPUT:
OUTPUT:
EXAMPLES:
sage: my_solver = merge(kronecker(gauss()))
sage: A = MatrixSpace(ZZ['x']['y'], 3, 4).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0)
sage: my_solver = merge(clear(kronecker(gauss())))
sage: A = MatrixSpace(ZZ['x'].fraction_field()['y'], 3, 4).random_element()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0)
Constructs a solver based on x-adic lifting for matrices with entries over \(K[x]\) where \(K\) is a field.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = MatrixSpace(GF(1093)['x'], 4, 7).random_element(degree=3)
sage: my_solver = newton(sage_native)
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM:
Note
It is assumed that the subsolver returns a nullspace basis which is normalized so that when the basis vectors are viewed as the columns of a matrix, this matrix contains every possible unit vector as row
Constructs a solver which first tests in a homomorphic image whether the nullspace is empty and applies the subsolver only if it is not.
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(ZZ['x'], 4, 5).random_element()
sage: my_solver = quick_check(gauss())
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
sage: V = my_solver(A.transpose())
sage: len(V)
0
Computes the nullspace of the given matrix using Sage’s native method.
INPUT:
OUTPUT:
EXAMPLES:
sage: A = MatrixSpace(GF(1093)['x'], 4, 7).random_element(degree=3)
sage: V = sage_native(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM: just calls right_kernel_matrix() on mat and converts its output to a list of vectors
Constructs a solver using Wiedemann’s algorithm
INPUT:
OUTPUT:
EXAMPLE:
sage: A = MatrixSpace(ZZ['x'], 4, 5).random_element()
sage: my_solver = wiedemann()
sage: V = my_solver(A)
sage: A*V[0]
(0, 0, 0, 0)
ALGORITHM: Wiedemann’s algorithm.
Note