Macaulay2 » Documentation
Packages » NumericalCertification :: NumericalCertification
next | previous | forward | backward | up | index | toc

NumericalCertification -- certify a numerical solution for a square system

Description

This package provides symbolic-numeric approaches to certify roots for a square polynomial system.

For regular roots, the package has two different approaches. The first is Smale's alpha theory and the second is Krawczyk method via interval arithmetic. Both methods are based on Newton's method and they all describe the specific region containing a unique root of the system.

In the case of alpha theory, this package follows the algorithms of alpha theory established in "alphaCertified: certifying solutions to polynomial systems" (2012). In the case of Krawczyk method, this package follows the theory introduced in "Introduction to Interval Analysis" (2009). These two methods also support not only floating-point arithmetic over the real and complex numbers, but also the exact computation with inputs of rational numbers.

Moreover, the package has a function certifying regular roots via a software "alphaCertified".

For singular roots, the concept of the iterated deflation established in "Newton's method with deflation for isolated singularities of polynomial systems" (2006) is implemented. For a given system and a point, the package provides a function constructing a system having a given point as a regular solution and certifies it via alpha theory or interval arithmetic.

Certifying a list of solutions :

$\bullet$ certifySolutions

For a direct use of the package, a given polynomial system and a list of numerical solutions can be given.

i1 : R = CC[x1,x2,y1,y2];
i2 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -3.5, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
i3 : sols = solveSystem f

o3 = {{.652548, .771177, .757747, -.63662}, {.95437, .318445, -.298627,
     ------------------------------------------------------------------------
     .947941}}

o3 : List
i4 : c = certifySolutions(f, sols, Strategy => "alphaTheory");
i5 : peek c

o5 = MutableHashTable{alphaValues => {2.07811e-30, 1.97423e-40}                                                        }
                      certifiedDistinct => {{.652548, .771177, .757747, -.63662}, {.95437, .318445, -.298627, .947941}}
                      certifiedReal => {{.652548, .771177, .757747, -.63662}, {.95437, .318445, -.298627, .947941}}
                      certifiedRegular => {{.652548, .771177, .757747, -.63662}, {.95437, .318445, -.298627, .947941}}
                      certifiedSingular => {}
                      nonCertified => {}

For possible options for certification, see CertificationOptions.

Regular Root Certification Methods:

$\bullet$ certifyRegularSolution

$\bullet$ krawczykTest

Examples

The following example shows how to certify the roots of solutions for the square polynomial system. This example is suggested in "Certifying solutions to square systems of polynomial-exponential equations" (2017)

$\bullet$ alpha theory

A set of points for certification should be given in advance using other system solvers.

i6 : R = RR[x1,x2,y1,y2];
i7 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -3.5, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
i8 : p1 = point{{.95, .32, -.30, .95}};
i9 : p2 = point{{.9, .3, -.3, 1}}; -- poorly approximated solution

It shows the results of the certification.

i10 : certifyRegularSolution(f,p1)

o10 = true
i11 : certifyRegularSolution(f,p2) -- not an approximate solution

o11 = false

Also, if we have other solutions of the system, alpha theory suggests an algorithm for distinguishing these solutions.

i12 : p1 = point{{.95,.32,-.30,.95}};
i13 : p2 = point{{.65,.77,.76,-.64}};
i14 : certifyDistinctSolutions(f,p1,p2)

o14 = true

In the case of real polynomial system, we can certify that a given solution is real or not.

i15 : p = point{{.954379, .318431, -.298633, .947949}};
i16 : certifyRealSolution(f,p)

o16 = true

Even more, when the polynomial and a point are given exact numbers over the rational number, the package computes auxiliary quantities exactly and performs an exact certification.

i17 : R = QQ[x1,x2,y1,y2]

o17 = R

o17 : PolynomialRing
i18 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -7/2, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
i19 : p = point{{95/100,32/100,-30/100,95/100}}; -- an input over the rational numbers
i20 : computeConstants(f,p)

        21324026093882418049     17681521    120600632116900
o20 = (----------------------, ------------, ---------------)
       3432333340166716036800  638081440000    537914617947

o20 : Sequence
i21 : certifyRegularSolution(f,p)

o21 = true

$\bullet$ Krawczyk method

Intervals for certification should be given in advance using other system solvers.

i22 : R = RR[x1,x2,y1,y2];
i23 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -3.5, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
i24 : (I1, I2, I3, I4) = (interval(.94,.96), interval(.31,.33), interval(-.31,-.29), interval(.94,.96));

We set the relationships between variables and intervals using the matrix aligning entries in the order of variables of the polynomial ring.

i25 : krawczykOperator(f,matrix{{I1,I2,I3,I4}})

o25 = | [.954149,.954609] [.318086,.318777] [-.298824,-.298442]
      -----------------------------------------------------------------------
      [.947663,.948236] |

                  1          4
o25 : Matrix RRi    <-- RRi
                53         53

The function krawczykTest automatically checks whether the Krawczyk operator is contained in the input interval box.

i26 : krawczykTest(f,matrix{{I1,I2,I3,I4}})

o26 = true

For a given point, the function pointToInterval provides a proper complex interval box for the input. For constructing a complex interval and a matrix with complex interval entries, see CCi and CCiMatrix.

i27 : R = RR[x1,x2,y1,y2];
i28 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -3.5, x1^2 + y1^2 -1, x2^2 + y2^2 -1};
i29 : p = point{{.954379, .318431, -.298633, .947949}};
i30 : I = pointToInterval(f,p)

o30 = |  [.878643,1.03011] + [0,0]*ii [.200731,.436131] + [0,0]*ii
      -----------------------------------------------------------------------
      [-.343878,-.253388] + [0,0]*ii [.884177,1.01172] + [0,0]*ii |

o30 : CCiMatrix
i31 : krawczykTest(f,I)

o31 = true

Multiple Root Certification Method:

$\bullet$ certifySingularSolution

It is known that an isolated singular solution is regularized within finitely many steps by the iterated first order deflation (e.g. see "Newton's method with deflation for isolated singularities of polynomial systems" (2006)). The function certifySingularSolution determines if a given point is associated to a singular solution of a given system using the deflation method.

i32 : 
      R = CC[x,y,z];
i33 : f = polySystem {x^2+y+z-1,x+y^2+z-1,x+y+z^2-1};
i34 : p = point{{1e-7-1e-7*ii,1e-7+1e-7*ii,1+1e-7}};
i35 : certifySingularSolution(f,p)

o35 = true

Authors

Version

This documentation describes version 1.6 of NumericalCertification.

Source code

The source code from which this documentation is derived is in the file NumericalCertification.m2. The auxiliary files accompanying it are in the directory NumericalCertification/.

Exports

  • Types
    • CCi -- a class of all complex intervals
    • CCiMatrix -- a class of matrices of complex intervals
  • Functions and commands
    • alphaCertified -- certify a list of numerical solutions via alphaCertified
    • alphaTheoryCertification -- executes alpha-certification on a given system and list of points
    • intervalCCi -- see CCi -- a class of all complex intervals
    • midpointCCi -- see CCi -- a class of all complex intervals
    • matrixCCi -- see CCiMatrix -- a class of matrices of complex intervals
    • certifyDistinctSolutions -- determine whether given points are distinct approximate solutions to the system
    • certifyRealSolution -- determine whether a given point is an real approximate solution to the system
    • certifyRegularSolution -- certify whether a given point is an approximate solution to the system
    • certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySolutions -- executes certification on a given system and list of points
    • computeConstants -- compute the square of the auxiliary quantities related to alpha theory
    • krawczykOperator -- compute the Krawczyk operator
    • krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykTest -- certify the interval box for square polynomial system
    • pointToInterval -- finds an interval box from a given point
  • Methods
    • alphaCertified(PolySystem,List) -- see alphaCertified -- certify a list of numerical solutions via alphaCertified
    • alphaTheoryCertification(PolySystem,List) -- see alphaTheoryCertification -- executes alpha-certification on a given system and list of points
    • imaginaryPart(CCi) -- see CCi -- a class of all complex intervals
    • intersect(CCi,CCi) -- see CCi -- a class of all complex intervals
    • intersect(CCi,RRi) -- see CCi -- a class of all complex intervals
    • intersect(RRi,CCi) -- see CCi -- a class of all complex intervals
    • intervalCCi(CCi) -- see CCi -- a class of all complex intervals
    • isSubset(CCi,CCi) -- see CCi -- a class of all complex intervals
    • midpointCCi(CCi) -- see CCi -- a class of all complex intervals
    • norm(CCi) -- see CCi -- a class of all complex intervals
    • realPart(CCi) -- see CCi -- a class of all complex intervals
    • entries(CCiMatrix) -- see CCiMatrix -- a class of matrices of complex intervals
    • norm(CCiMatrix) -- see CCiMatrix -- a class of matrices of complex intervals
    • numColumns(CCiMatrix) -- see CCiMatrix -- a class of matrices of complex intervals
    • numRows(CCiMatrix) -- see CCiMatrix -- a class of matrices of complex intervals
    • transpose(CCiMatrix) -- see CCiMatrix -- a class of matrices of complex intervals
    • certifyDistinctSolutions(PolySystem,AbstractPoint,AbstractPoint) -- see certifyDistinctSolutions -- determine whether given points are distinct approximate solutions to the system
    • certifyDistinctSolutions(PolySystem,Matrix,Matrix) -- see certifyDistinctSolutions -- determine whether given points are distinct approximate solutions to the system
    • certifyRealSolution(PolySystem,AbstractPoint) -- see certifyRealSolution -- determine whether a given point is an real approximate solution to the system
    • certifyRealSolution(PolySystem,Matrix) -- see certifyRealSolution -- determine whether a given point is an real approximate solution to the system
    • certifyRegularSolution(PolySystem,AbstractPoint) -- see certifyRegularSolution -- certify whether a given point is an approximate solution to the system
    • certifyRegularSolution(PolySystem,Matrix) -- see certifyRegularSolution -- certify whether a given point is an approximate solution to the system
    • certifySingularSolution(PolySystem,AbstractPoint) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySingularSolution(PolySystem,AbstractPoint,Number) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySingularSolution(PolySystem,CCiMatrix) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySingularSolution(PolySystem,CCiMatrix,Number) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySingularSolution(PolySystem,Matrix) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySingularSolution(PolySystem,Matrix,Number) -- see certifySingularSolution -- certify if a given point is a singular solution for a given system using the deflation method.
    • certifySolutions(PolySystem,List) -- see certifySolutions -- executes certification on a given system and list of points
    • certifySolutions(PolySystem,List,Number) -- see certifySolutions -- executes certification on a given system and list of points
    • computeConstants(PolySystem,AbstractPoint) -- see computeConstants -- compute the square of the auxiliary quantities related to alpha theory
    • computeConstants(PolySystem,Matrix) -- see computeConstants -- compute the square of the auxiliary quantities related to alpha theory
    • krawczykOperator(Matrix,AbstractPoint) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykOperator(Matrix,CCiMatrix) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykOperator(Matrix,Matrix) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykOperator(PolySystem,AbstractPoint) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykOperator(PolySystem,CCiMatrix) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykOperator(PolySystem,Matrix) -- see krawczykOperator -- compute the Krawczyk operator
    • krawczykRealnessTest(Matrix,AbstractPoint) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykRealnessTest(Matrix,CCiMatrix) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykRealnessTest(Matrix,List) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykRealnessTest(PolySystem,AbstractPoint) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykRealnessTest(PolySystem,CCiMatrix) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykRealnessTest(PolySystem,List) -- see krawczykRealnessTest -- certify the realness of the associated solution for the square polynomial system from the given interval box
    • krawczykTest(Matrix,AbstractPoint) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(Matrix,CCiMatrix) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(Matrix,List) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(Matrix,Matrix) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(PolySystem,AbstractPoint) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(PolySystem,CCiMatrix) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(PolySystem,List) -- see krawczykTest -- certify the interval box for square polynomial system
    • krawczykTest(PolySystem,Matrix) -- see krawczykTest -- certify the interval box for square polynomial system
    • pointToInterval(AbstractPoint,Number) -- see pointToInterval -- finds an interval box from a given point
    • pointToInterval(PolySystem,AbstractPoint) -- see pointToInterval -- finds an interval box from a given point
  • Symbols

For the programmer

The object NumericalCertification is a package.