NumericalCertification -- certify the solution for the square system using alpha theory or interval arithmetic

Description

This package provides two different types of root certification for the square polynomial system. 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 introduced in "alphaCertified: certifying solutions to polynomial systems" (2012).

In the case of Krawczyk method, this package follows the theory suggested in "Introduction to Interval Analysis" (2009).

Ceritification Methods:

• certifySolution

• krawczykMethod

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)

• alpha theory

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

i1 : R = QQ[x1,x2,y1,y2];

i2 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -7/2, x1^2 + y1^2 -1, x2^2 + y2^2 -1};

i3 : p1 = point{{.95, .32, -.30, .95}};

i4 : p2 = point{{.9, .3, -.3, 1}}; -- poorly approximated solution

i5 : P = {p1,p2};

It shows the result of certification.

i6 : certifySolution(f,P)

o6 = ({p1}, {(.0505356, .00526407, 9.60011)})

o6 : Sequence

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

i7 : p1 = point{{.95,.32,-.30,.95}};

i8 : p2 = point{{.65,.77,.76,-.64}};

i9 : certifyDistinctSoln(f,p1,p2)

o9 = true

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

i10 : p = point{{.954379, .318431, -.298633, .947949}};

i11 : certifyRealSoln(f,p)

o11 = true

• Krawczyk method

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

i12 : R = QQ[x1,x2,y1,y2];

i13 : f = polySystem {3*y1 + 2*y2 -1, 3*x1 + 2*x2 -7/2, x1^2 + y1^2 -1, x2^2 + y2^2 -1};

i14 : (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 function intervalOptionList.

i15 : o = intervalOptionList {("x1" => "I1"), ("x2" => "I2"), ("y1" => "I3"), ("y2" => "I4")};

i16 : krawczykOper(f,o)

o16 = {{[.954149, .954609]}, {[.318086, .318777]}, {[-.298824, -.298442]},
      -----------------------------------------------------------------------
      {[.947663, .948236]}}

o16 : IntervalMatrix

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

i17 : krawczykMethod(f,o)
given interval contains a unique solution

o17 = true

Author

Kisun Lee <klee669@gatech.edu>

Version

This documentation describes version 1.0 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
- Interval -- a class of all intervals
- IntervalMatrix -- a class of all interval matrices
- IntervalOptionList -- a class of lists for options related to intervals
Functions and commands
- certifyCount -- executes alpha-certification on a given system and list of points
- certifyDistinctSoln -- determine whether given points are distinct approximate solutions to the system
- certifyRealSoln -- determine whether a given point is an real approximate solution to the system
- certifySolution -- certify whether a given point is an approximate solution to the system
- computeConstants -- compute the auxilary quantities related to alpha theory
- identityIntMat -- compute the identity diagonal interval matrix.
- interval -- construct an interval
- intervalMatrix -- construct an interval matrix from the given list
- intervalMatrixNorm -- compute the infinity norm for interval matrix.
- intervalOptionList -- convert a list type object to list of options for intervals
- krawczykMethod -- certify the interval box for square polynomial system
- krawczykOper -- compute the Krawczyk operator
- newtonOper -- apply Newton's method on a given point.
- pointNorm -- compute the "projectivized" norm of the given point
- polyNorm -- compute the "Bombieri-Weyl" norm of the given polynomial
- polySysNorm -- compute the norm of the given polynomial system
Methods
- interval(Interval), see interval -- construct an interval
- interval(RingElement,Interval), see interval -- construct an interval
- intervalMatrixNorm(IntervalMatrix), see intervalMatrixNorm -- compute the infinity norm for interval matrix.
- intervalNorm(Interval) -- compute a norm of an interval
- krawczykMethod(PolySystem,IntervalOptionList), see krawczykMethod -- certify the interval box for square polynomial system
- krawczykOper(PolySystem,IntervalOptionList), see krawczykOper -- compute the Krawczyk operator
- mInterval(Interval) -- compute a midpoint of an interval
- wInterval(Interval) -- compute a width of an interval.
Symbols
- InvertibleMatrix, see krawczykMethodOptions -- invertible matrix for computing Krawczyk operator (option for "krawczykOper" and "krawczykMethod")
- krawczykMethodOptions -- invertible matrix for computing Krawczyk operator (option for "krawczykOper" and "krawczykMethod")