Home Online Manual
Back: addnondegeneratevariables
Forward: bounds
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.15.30 rootisolation_lib

implements an algorithm for real root isolation using interval arithmetic
Dominik Bendle (bendle@rhrk.uni-kl.de)
Janko Boehm (boehm@mathematik.uni-lk.de), supervisor Fachpraktikum
Clara Petroll (petroll@rhrk.uni-kl.de)

In this library the interval arithmetic from interval.so is used. The new type ivmat, a matrix consisting of intervals, is implemented as newstruct. There are various functions for computations with interval matrices implemented, such as Gaussian elimination for interval matrices.

Interval arithmetic, the interval Newton Step and exclusion methods are used to implement the procedure rootIsolation, an algorithm which finds boxes containing elements of the vanishing locus of an ideal. This algorithm is specialised for zero-dimensional radical ideals. The theory about the interval Newton Step is detailed in [2].

Note that interval arithmetic and the aforementioned procedures are intended for rational or real polynomial rings.

[1] Cloud, Kearfott, Moore: Introduction to Interval Analysis, Society for Industrial and Applied Mathematics, 2009
[2] Eisenbud, Grayson, Herzog, Stillman, Vasconcelos: Computational Methods in Commutative Algebra and Algebraic Geometry, Springer Verlag Berlin-Heidelberg, 3. edition 2004
[3] Andrew J. Sommese and Charles W. Wampler: The Numerical Solution of Systems of Polynomials - Arising in Engineering and Science, World Scientific Publishing Co. Pte. Ltd., 2005

[ ivmatGet indexing
print ivmatPrint printing
nrows ivmatNrows number of rows
ncols ivmatNcols number of columns
* ivmatMultiplyGeneral matrix multiplication


D.15.30.1 bounds  creates a new interval with given bounds
D.15.30.2 length  returns Euclidean length of interval
D.15.30.3 boxSet  returns box B with B[i]==I
D.15.30.4 ivmatInit  returns m x n [0,0]-matrix
D.15.30.5 ivmatSet  returns matrix A where A[i][j]=I
D.15.30.6 unitMatrix  returns m x m unit matrix where 1 = [1,1]
D.15.30.7 ivmatGaussian  computes M^(-1) using Gaussian elimination for intervals
D.15.30.8 evalPolyAtBox  returns evaluation of polynomial at a box
D.15.30.9 evalJacobianAtBox  jacobian matrix of A where polynomials are evaluated at B
D.15.30.10 rootIsolationNoPreprocessing  computes boxes containing unique roots of I lying in L
D.15.30.11 rootIsolation  slims down input box B and calls rootIsolationNoPreprocessing
D.15.30.12 rootIsolationPrimdec  runs a primary decomposition primdecGTZ before root isoation