### D.8.8 rootisolation_lib

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

Overview:
  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.

References:
  [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

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

Procedures:

> D.8.8.1 bounds |  | creates a new interval with given bounds
> D.8.8.2 length |  | returns Euclidean length of interval
> D.8.8.3 boxSet |  | returns box B with B[i]==I
> D.8.8.4 ivmatInit |  | returns m x n [0,0]-matrix
> D.8.8.5 ivmatSet |  | returns matrix A where A[i][j]=I
> D.8.8.6 unitMatrix |  | returns m x m unit matrix where 1 = [1,1]
> D.8.8.7 ivmatGaussian |  | computes M^(-1) using Gaussian elimination for intervals
> D.8.8.8 evalPolyAtBox |  | returns evaluation of polynomial at a box
> D.8.8.9 evalJacobianAtBox |  | jacobian matrix of A where polynomials are evaluated at B
> D.8.8.10 rootIsolationNoPreprocessing |  | computes boxes containing unique roots of I lying in L
> D.8.8.11 rootIsolation |  | slims down input box B and calls rootIsolationNoPreprocessing
> D.8.8.12 rootIsolationPrimdec |  | runs a primary decomposition primdecGTZ before root isoation

See also: interval_lib.

User manual for Singular version 4.4.1, 2025, generated by texi2html.