|
The slightly non-standard term variety in this section refers to the (finite)
solution set of the system of polynomials that make up an ideal.
It can also be thought of as the set of points of a zero-dimensional affine scheme
over a specified field extension of the polynomial ring base field.
For more general functionality for
schemes of arbitrary dimension, see the chapters on Algebraic and
Arithmetic Geometry. The functions here also work for higher-dimensional
ideals if the base field is finite, when the solution set is again finite
(over the base or a finite extension of the base).
The functions compute solutions over the base field of the polynomial
ring or over an extension field L. Magma's algebraically closed
fields (see Chapter ALGEBRAICALLY CLOSED FIELDS) may be used to get all solutions
if so desired when an explicit splitting field is not known for the
system. L should be an exact field over which Magma has a root-finding
algorithm for univariate polynomials or a real or complex field.
For the corresponding functions with argument a zero-dimensional scheme
which may not be affine, see the Section Rational Points and Point Sets in the Schemes
chapter.
Variety(I, L) : RngMPol, Rng -> [ ModTupFldElt ]
Al: MonStgElt Default: em "Default"
Eval: RngIntElt Default:
Given an ideal I of a polynomial ring P, return the affine variety
of I over its coefficient field K as a sequence of tuples.
Each tuple is of length n, where n is the rank of P,
and corresponds to an assignment of the n variables of P (in order) such
that all polynomials in I vanish with this assignment.
If K is not a finite field then the ideal must be the full polynomial
ring or be zero-dimensional so that the variety is known to be finite.
If a superfield L of K is also given, the variety is computed over
L instead, so the entries of the tuples lie in L.
Al := "Wiedemann":
This parameter selects the Wiedemann algorithm and is
applicable to computing the variety of a generic zero-dimensional ideal I
over K, where K is a moderately sized finite
field. The degree D of I is the dimension of the quotient
algebra R/I, and as D grows large (particularly above 10000),
computing the variety of I becomes very difficult since it involves
computing a minimal polynomial of degree D. The Wiedemann algorithm
is effective when it is impractical to store a fully dense D x D
matrix in memory.
See http://magma.maths.usyd.edu.au/users/allan/densef4/#CC for a
very large example.
Al := "KellerGehrig":
This parameter selects the Keller-Gehrig algorithm, which
is similar to the Wiedemann algorithm in that
it finds the minimal polynomial of a matrix to compute a
variety of a zero-dimensional ideal, but it uses the Keller-Gehrig
algorithm to compute this minimal polynomial by mapping
the problem to several matrix multiplications.
This method typically takes more memory than the Wiedemann algorithm
but may be faster for dimensions in the thousands, particularly when
a GPU is available.
Al := "ExhaustiveSearch":
This parameter selects the Exhaustive Search algorithm
for solving quadratic multivariate polynomial systems over GF(2).
For a system with n variables, the algorithm simply
enumerates all 2n possible assignments of the variables and
determines the set of all such assignments which simultaneously
satisfy all the polynomial equations.
Despite the obvious exponential complexity of this brute force
approach, the algorithm is highly optimised: for a quadratic input
system, the algorithm covers 1010 possible solutions in
1.47 seconds on a typical 3.2GHz Intel Xeon processor and an
arbitrary quadratic system with 40 variables is solved in
162 seconds.
The algorithm is preferable to other algorithms for certain types of
input system. For example, in the case of an arbitrary generic dense
quadratic system with no structure (such as a random system), the
exhaustive search algorithm is typically faster than both the Gröbner
basis and SAT algorithms by a factor of more than 100. This is because
all algorithms have exponential complexity for this type of input,
but the associated constant is much better for the exhaustive search.
Eval := e:
If Eval is set to a small positive integer e, then the function
works by evaluating the input polynomials at the last e variables
to all possible constants in K (so there are qe cases enumerated)
and then computing the variety of each simplified ideal and combining
all the results. This algorithm can be parallelised by the use
of SetNthreads and StartWorkers.
VarietySequence(I, L) : RngMPol, Rng -> [ [ RngElt ] ]
Given a zero-dimensional ideal I of a polynomial ring P whose order is of
lexicographic type, return the variety of I over its coefficient field
K as a sequence of sequences of elements of K.
Each inner sequence is of length n, where n is the rank of P,
and corresponds to an assignment of the n variables of P (in order) such
that all polynomials in I vanish with this assignment.
The parameters and other conditions are the same as for Variety
above.
Given an ideal I of a polynomial ring P over a field
K, return the size of the variety of I over K. The parameters
are the same as for the function Variety.
We construct an ideal I of the polynomial ring GF(27)[x, y], and
then find the variety V = V(I). We then check that I vanishes on V.
> K<w> := GF(27);
> P<x, y> := PolynomialRing(K, 2);
> I := ideal<P | x^8 + y + 2, y^6 + x*y^5 + x^2>;
> Groebner(I);
> I;
Ideal of Polynomial ring of rank 2 over GF(3^3)
Order: Lexicographical
Variables: x, y
Inhomogeneous, Dimension 0
Groebner basis:
[
x + 2*y^47 + 2*y^45 + y^44 + 2*y^43 + y^41 + 2*y^39 + 2*y^38 + 2*y^37 +
2*y^36 + y^35 + 2*y^34 + 2*y^33 + y^32 + 2*y^31 + y^30 + y^28 + y^27 +
y^26 + y^25 + 2*y^23 + y^22 + y^21 + 2*y^19 + 2*y^18 + 2*y^16 + y^15 +
y^13 + y^12 + 2*y^10 + y^9 + y^8 + y^7 + 2*y^6 + y^4 + y^3 + y^2 + y +
2,
y^48 + y^41 + 2*y^40 + y^37 + 2*y^36 + 2*y^33 + y^32 + 2*y^29 + y^28 +
2*y^25 + y^24 + y^2 + y + 1
]
> V := Variety(I);
> V;
[ <w^14, w^12>, <w^16, w^10>, <w^22, w^4> ]
> // Check that the original polynomials vanish:
> [
> <x^8 + y + 2, y^6 + x*y^5 + x^2> where x is v[1] where y is v[2]: v in V
> ];
[ <0, 0>, <0, 0>, <0, 0> ]
> // Note that the variety of I would be larger over an extension field of K:
> VarietySizeOverAlgebraicClosure(I);
48
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|