next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
NumericalImplicitization :: numericalImageDegree

numericalImageDegree -- computes a pseudo-witness set for the image of a variety

Synopsis

Description

This method computes the degree of the image of a variety, along with a pseudo-witness set (cf. Definition 4 in [1]) for it, by tracking monodromy loops with homotopy continuation and then applying the trace test. If the trace test fails, only a lower bound for the degree and an incomplete pseudo-witness set is returned. This technique circumvents the calculation of the kernel of the associated ring map.

The following computes the degree of the Grassmannian Gr(3,5) of P2’s in P4.

i1 : R = CC[x_(1,1)..x_(3,5)];
i2 : F = (minors(3, genericMatrix(R, 3, 5)))_*;
i3 : W = numericalImageDegree(F, ideal 0_R)
Sampling point in source ...
Tracking monodromy loops ...
Points found: 1
Points found: 2
Points found: 3
Points found: 4
Points found: 4
Points found: 5
Points found: 5
Points found: 5
Points found: 5
Running trace test ...

o3 = a pseudo-witness set, indicating
     the degree of the image is 5

o3 : PseudoWitnessSet
i4 : W.isCompletePseudoWitnessSet

o4 = true
i5 : W.imageDegree

o5 = 5

This method can also handle cases where the parameterization has positive dimensional fibers. In the example below, we verify that the variety of 3 x 3 x 3 tensors of border rank <= 4, i.e. the 4th secant variety of P2 x P2 x P2, has degree 9. This is a hypersurface, with defining equation known as Strassen’s invariant, and it is also a defective secant variety (meaning its dimension is less than expected). Here, the parametrization has 10 dimensional fibers.

i6 : R = CC[a_(0,0)..a_(3,2), b_(0,0)..b_(3,2), c_(0,0)..c_(3,2)];

i7 : F = toList apply((0,0,0)..(2,2,2), (i,j,k) ->
        a_(0,i)*b_(0,j)*c_(0,k) +
        a_(1,i)*b_(1,j)*c_(1,k) +
        a_(2,i)*b_(2,j)*c_(2,k) +
        a_(3,i)*b_(3,j)*c_(3,k));

i8 : numericalImageDegree(F, ideal 0_R, repeats => 2)
Sampling point in source ...
Tracking monodromy loops ...
Points found: 1
Points found: 2
Points found: 3
Points found: 5
Points found: 7
Points found: 9
Points found: 9
Points found: 9
Running trace test ...

o8 = a pseudo-witness set, indicating
    the degree of the image is 9

o8 : PseudoWitnessSet

Finally, this method has a large number of optional inputs which may be specified by the user to fit a particular problem instance.

repeats sets the maximum number of consecutive repetitive monodromy loops when computing a pseudo-witness set. A repetitive monodromy loop is one where no new points in the image are discovered. After this many consecutive repetitive monodromy loops occur, the trace test is applied to determine if a complete pseudo-witness set has been found. The default value is 3.

maxAttempts sets the maximum number of times the trace test will be attempted when computing a pseudo-witness set. After a trace test fails, a new slice is chosen, the previous points are tracked to the new slice, and monodromy is performed anew. If the trace test has failed maxAttempts many times, an incomplete pseudo-witness set is returned. The default value is 10.

Here is an example in which a badly chosen random seed results in a failed trace test on the first attempt. In later attempts, the trace test passes and the degree of the twisted cubic is correctly computed to be 3.

i6 : setRandomSeed 6

o6 = 6
i7 : R = CC[s,t];
i8 : F = basis(3, R);
-- warning: experimental computation over inexact field begun
--          results not reliable (one warning given per session)

             1       4
o8 : Matrix R  <--- R
i9 : numericalImageDegree(F, ideal 0_R)
Sampling point in source ...
Tracking monodromy loops ...
Points found: 1
Points found: 1
Points found: 1
Running trace test ...
Failed trace test! Trace: .312948
Tracking monodromy loops ...
Points found: 2
Points found: 2
Points found: 2
Points found: 2
Running trace test ...
Failed trace test! Trace: 1.01842
Tracking monodromy loops ...
Points found: 3
Points found: 3
Points found: 3
Points found: 3
Running trace test ...

o9 = a pseudo-witness set, indicating
     the degree of the image is 3

o9 : PseudoWitnessSet

We compare this with the native Macaulay2 function degree (using symbolic computation).

i10 : degree ker map(QQ[s,t], QQ[y_0..y_3], {s^3,s^2*t,s*t^2,t^3})

o10 = 3

traceThreshold sets the threshold for a pseudo-witness set to pass the trace test. The trace test for a complete exact pseudo-witness set is 0; large nonzero values indicate failure (the larger the value, the worse the failure). The default value is 1e-5. Caution: setting the value of this threshold too high may result in the trace test returning false positives.

pointEqualityThreshold sets the threshold for determing point equality. If this option has value n, then two points are considered equal iff their first n significant digits agree (equivalently, in scientific notation, the exponents and first n digits of the mantissa agree). The default value is 5.

Reference

[1] J. D. Hauenstein and A. J. Sommese, Witness sets of projections. Appl. Math. Comput. 217(7) (2010), 3349-3354.

[2] V. Strassen, The asymptotic spectrum of tensors. J. Reine. Angew. Math. 384 (1988), 102-152.

See also

Ways to use numericalImageDegree :