share/contrib/sarag/readme.txt

   1 ---------------------------------------------------------------
   2 ---------------------------------------------------------------
   3                          S A R A G
   4
   5        SOME ALGORITHMS IN REAL ALGEBRAIC GEOMETRY
   6
   7                        Version 1.3
   8
   9 ---------------------------------------------------------------
  10 maintained and developed by Fabrizio Caruso
  11
  12 under the scientific guidance of Marie-Francoise Roy
  13
  14 at the University of Rennes 1, France
  15
  16 with support from the RAAG network
  17
  18 further developed
  19
  20 at the University of Pisa, Italy
  21
  22 The code for the multivariate certificate of positivity
  23
  24 has been developed by Richard Leroy.
  25
  26 The code for quick sign determination has been developed
  27
  28 by Mathieu Kohli.
  29
  30 ---------------------------------------------------------------
  31
  32 Please report bugs to:
  33 caruso@science.unitn.it
  34 marie-francoise.roy@univ-rennes1.fr
  35
  36 ---------------------------------------------------------------
  37 Also part of the book
  38
  39 "Algorithms in Real Algebraic Geometry"
  40
  41 by Saugata Basu, Richard Pollack, Marie-Françoise Roy
  42
  43 Springer-Verlag, Berlin, 2003 (second edition 2006)
  44
  45 which together with SARAG is available for download at
  46
  47 http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html
  48
  49 ---------------------------------------------------------------
  50 ---------------------------------------------------------------
  51 THE SARAG LIBRARY
  52
  53 ---------------------------------------------------------------
  54
  55 This is a free open source Maxima library for
  56 real algebraic geometry.
  57 As of this version it focuses on
  58 univariate real root counting and isolation,
  59 topology of bivariate polynomials and
  60 certificates of positivity (computer-generated simple proof
  61 for the positivity/negativity of a univariate and multivariate
  62 polynomial)
  63
  64
  65 In particular SARAG provides functions for
  66 (1) linear algebra,
  67 (2) theory of subresultants,
  68 (3) Cauchy Index and its application to real root counting,
  69 (4) isolation of real roots,
  70 (5) sign determination and Thom encodings,
  71 (6) study of the topology of bivariate polynomials
  72 (7) certificate of positivity for univariate and
  73 multivariate polynomials
  74
  75 ---------------------------------------------------------------
  76 ---------------------------------------------------------------
  77 REQUIREMENTS
  78
  79 ---------------------------------------------------------------
  80
  81 - MAXIMA (5.9.2 or above)
  82 The library has been developed and tested
  83 with Maxima version 5.9.2 and 5.9.3.
  84 SARAG with the only exception of plotting
  85 (e.g., "drawTopology") also works on Maxima 5.9.1.
  86 The latest version of Maxima is available on line at
  87 http://maxima.sourceforge.net/
  88
  89 - GNUPLOT (5.0 or above for SARAG 1.3 and 3.7.x, 4.0.x for previous versions of SARAG)
  90 The function "drawTopology" in this library uses
  91 Gnuplot for plotting graphs
  92 and it has been tested successfully on Gnupolot 5.0.
  93
  94
  95 ---------------------------------------------------------------
  96 ---------------------------------------------------------------
  97 LOADING THE FILES
  98
  99 sarag.mac
 100 ---------------------------------------------------------------
 101
 102 The library is contained in the following files:
 103
 104 sarag.mac (it loads all the files)
 105
 106 sarag_settings.mac (general settings)
 107 constants.mac
 108 sarag_initialization.mac
 109 aliases.mac (name conventions)
 110 lowLevel.mac (low level routines)
 111 sarag_linear_algebra.mac (linear algebra and matrix manipulation)
 112 rootCounting.mac (real root counting)
 113 rootIsolation.mac (root isolation by De Casteljau method)
 114 signDetermination.mac (sign determination)
 115 quickSignDetermination.mac (quick sign determination)
 116 intervalArithmetic.mac (interval arithmetic)
 117 topology.mac (topology of curves)
 118 certificateOfPositivity.mac (univariate certificate of positivity)
 119 multiCertificateOfPositivity.mac (multivariate certificate of positivity)
 120
 121 rtest_arag.mac (test file for "Alg. in Real Alg. Geom.")
 122 rtest_arag_hard.mac (heavy test files with mostly topology computations)
 123 other_test.mac (test of functions not included in the book)
 124
 125 readme.txt (this manual)
 126
 127 This library is included in the latest versions of Maxima
 128 and it is simply loaded by the command
 129 load(sarag).
 130
 131 The last version on line can be found on
 132 http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html
 133 in the compressed directory saragcur and loaded by
 134 load("./saragcur/saragcur.mac").
 135
 136
 137 In order to test the library use:
 138 batch(<path>/rtest_arag.mac,test);
 139 and
 140 batch(<path>/rtest_arag_hard.mac,test);
 141 and
 142 batch(<path>/other_test.mac,test);
 143
 144 ---------------------------------------------------------------
 145 ---------------------------------------------------------------
 146 THE MANUAL
 147
 148 readme.txt
 149 ---------------------------------------------------------------
 150
 151 This manual describes the high level functions ("main functions")
 152 of the SARAG library and the most important auxiliary functions.
 153
 154 For more details and for the theory behind the algorithms
 155 we refer to "Algorithms in Real Algebraic Geometry"
 156 by S. Basu, R. Pollack, M.-F. Roy
 157 which together with SARAG is available for download at
 158 http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted3.html
 159 or to a few specific papers quoted inside the text.
 160
 161 A more detailed manual with examples, saragmanuel.pdf,  can also be
 162 downloaded there.
 163
 164 ATTENTION:
 165
 166 (-) Items marked with this symbol are not fully tested
 167 or are missing some minor features.
 168
 169 (--) These items are not available, yet, but will
 170 be included soon.
 171
 172 ---------------------------------------------------------------
 173 ---------------------------------------------------------------
 174 SETTINGS
 175
 176 sarag_settings.mac
 177 ---------------------------------------------------------------
 178
 179 The library contains some settings in the file "sarag_settings.mac".
 180
 181 The main settings and their default values are:
 182
 183 - DEFAULT_VERBOSITY [0 (non-verbose)] (--)
 184 Verbosity level of the commands.
 185
 186 - LINEAR_SOLVER [linsolve (built-in Maxima linear solver)]
 187 Solver of linear systems used in some routines.
 188
 189 - MOD_TEST_PRIME [2]
 190 Prime used in some modular tests.
 191
 192 - NORM_ALGORITHM [lambda([x],ratexpand)]
 193 Normal form computed in "sSubRes" and related algorithms
 194
 195 - ASSUME_EXPANDED [false]
 196 Assunption on whether the polynomial input of the main functions
 197 is in expanded form
 198
 199 - WARNINGS [true]
 200 Warnings
 201
 202 - ASSUME_GENERIC_POSITION  [false];
 203 Assumption on the generic position of curves
 204
 205 - PLOT_STYLE ["set noxtics; set noytics; set nokey;"]
 206 Preamble to be fed to gnuplot to set its style
 207
 208 - PS_OUTPUT  [false]
 209 Printable file output for "drawTopology"
 210
 211 - PS_OUTPUT_FILE_NAME  ["test.eps"]
 212 Name of the postscript file output for "drawTopology"
 213
 214
 215 For the other settings we refer to file
 216 sarag_settings.mac
 217
 218 ---------------------------------------------------------------
 219 ---------------------------------------------------------------
 220 NAMING CONVENTIONS
 221
 222 aliases.mac
 223 ---------------------------------------------------------------
 224
 225 The names of main functions are formed by adding
 226 prefixes to specify the method/algorithm to be used and
 227 suffixes to specify an alternative version of the
 228 function or output.
 229 Auxiliary functions may not follow such conventions.
 230
 231 Therefore the general name convention for the names
 232 of the high level functions is the following:
 233
 234 METHOD | WHAT IS TO BE COMPUTED | MODIFIER
 235
 236 When a prefix is added capitalization
 237 of the function is used to distinguish the
 238 parts of the new name.
 239
 240 When no prefix or no suffix is used the
 241 default version of function with the
 242 default method/algorithm will be called
 243 as set in the file: "aliases.mac"
 244
 245 NOTE:
 246 In this manual some possible modifiers will appear
 247 in brackets.
 248
 249 Examples:
 250
 251 tarskiQuery [computes the Tarski query over all R with
 252 the default algorithm]
 253
 254 sRemTarskiQueryBetween [computes the Tarski query
 255 over an interval using the signed remainder sequence]
 256
 257 det [computes the determinant of a matrix with the
 258 default algorithm]
 259
 260 bareissDet [computes the determinant of a matrix
 261 by using Bareiss method]
 262
 263 sSubRes [computes the signed subresultant sequence]
 264
 265 sSubResExt [computes the extended signed subresultant sequence]
 266
 267
 268 ---------------------------------------------------------------
 269 ---------------------------------------------------------------
 270 COMMANDS
 271 ---------------------------------------------------------------
 272
 273 Here we describe the most important functions:
 274 all the "main functions" and some
 275 important "auxiliary functions".
 276
 277 REMARK:
 278 Our naming conventions and the
 279 global variables DEFAULT_VERBOSITY and ASSUME_EXPANDED
 280 only apply to "main functions".
 281
 282 When multiple methods are available for a
 283 main function  we list all of them.
 284 They are accessible by adding the name
 285 of the method as a prefix and by capitalizing
 286 the first letter of the name of the function.
 287 For more details on names of functions read
 288 the section on naming conventions.
 289
 290
 291 ATTENTION:
 292
 293 -------------------------------------------------
 294 Polynomial Input in Expanded Form
 295
 296 If ASSUME_EXPANDED is set to TRUE then
 297 whenever the input of a main function contains polynomials
 298 we are always assuming that they are in EXPANDED FORM.
 299
 300 Independently on the value of ASSUME_EXPANDED
 301 we will always assume that the polynomial
 302 input of auxiliary functions is in EXPANDED FORM.
 303
 304 Therefore, in these cases,
 305 when defining a polynomial use for instance:
 306
 307 p : expand(...);
 308
 309 -------------------------------
 310 Form of the Output
 311
 312 The output of all functions of the library is a Maxima expression.
 313 Maxima uses brakets "[", "]" to describe couples and lists
 314 (e.g. an open interval (a,b) is described by a couple
 315 containing the ends, which in Maxima is "[a,b]")
 316
 317
 318 ---------------------------------------------------------------
 319 LINEAR ALGEBRA
 320
 321 sarag_linear_algebra.mac
 322 ---------------------------------------------------------------
 323
 324 This file contains functions related to Gaussian elimination
 325 and matrix manipulations.
 326
 327 ---------------------------------------------------------------
 328 Auxiliary functions
 329
 330
 331 - matrixProd(a,b)
 332 INPUT : a and b are lists of lists representing the rows
 333 of two matrices such that a has the same number of columns
 334 as b as rows
 335 OUTPUT : the row-column product matrix of a, b
 336
 337 ---------------------------------------------------------------
 338 Main functions
 339
 340 - det(m)
 341 INPUT : m is a list of lists representing the rows of a matrix
 342 METHOD :
 343 -- gauss [basic Gaussian elimination],
 344 -- bareiss [Bareiss method]
 345 OUTPUT : the determinant
 346
 347
 348 - elim(m)
 349 INPUT : m is a list of lists representing the rows of a matrix
 350 METHOD :
 351 -- gauss [Gaussian elimination with no pivot optimization],
 352 -- bareiss [Bareiss method] (--)
 353 OUTPUT : [t,c,z]
 354 where
 355 1) t is an upper triangular equivalent form of m
 356 with possibly some zero rows computed by Gaussian
 357 elimination with divisions and columns exchanges
 358 2) c is the list of couples describing the columns
 359 exchanges
 360 3) z is the list of zero rows
 361
 362
 363 -----------------------------------------------------------------
 364 CHARACTERISTIC POLYNOMIAL
 365
 366 sarag_linear_algebra.mac
 367 -----------------------------------------------------------------
 368
 369 -----------------------------------------------------------------
 370 Auxiliary functions
 371
 372 - getCoeffFromNewton(ns)
 373 INPUT : a list containing the the Newton sums of
 374 a given polynomial
 375 OUTPUT : an array containing the coefficients of the
 376 corresponding polynomial
 377
 378 -----------------------------------------------------------------
 379 Main functions
 380
 381 - charPol(A,var)
 382 INPUT : A is a list of lists representing the rows of a matrix,
 383 an indeterminate var
 384 METHOD :
 385 -- gauss [basic Gaussian elimination], (--)
 386 -- bareiss [Bareiss method], (--)
 387 -- babyGiant [baby step, giant step trace-based method]
 388 OUTPUT : the characteristic polynomial of A in the indeterminate var
 389
 390
 391 -----------------------------------------------------------------
 392 SIGNED REMAINDER SEQUENCE
 393
 394 rootCounting.mac
 395 -----------------------------------------------------------------
 396
 397 -----------------------------------------------------------------
 398 Main functions
 399
 400 - sRem(a,b,x)
 401 INPUT : a, b polynomials in the x indeterminate
 402 OUTPUT : list containing signed remainder sequence
 403
 404 - sRemExt(a,b,x)
 405 INPUT : a, b polynomials in the x indeterminate
 406 OUTPUT : [r,u,v] forming the extended signed remainder sequence
 407 where r is the signed remainder sequence and u and v are
 408 the corresponding sequences of cofactors
 409
 410 -----------------------------------------------------------------
 411 SIGNED SUBRESULTANTS
 412
 413 rootCounting.mac
 414 -----------------------------------------------------------------
 415
 416 -----------------------------------------------------------------
 417 Main functions
 418
 419 - sSubRes(a,b,var)
 420 INPUT : a,b polynomials in the x indeterminate with deg(a)>deg(b)
 421 OUTPUT : [sSubRes,s] where
 422 1) sSubRes is a list containing the signed subresultant sequence
 423 2) s is the list of the corresponding coefficients
 424
 425
 426 - sSubResExt(a,b,var)
 427 INPUT : a,b polynomials in the x indeterminate with deg(a)>deg(b)
 428 OUTPUT : [sSubRes,s,u,v] where
 429 1) sSubRes is a list containing the signed subresultant sequence
 430 2) s is the list of the corresponding coefficients
 431 3) u, v are the corresponding cofactors
 432
 433 --------------------------------------
 434 GCD and GCD-free part by subresultants
 435
 436 - gcdFreePart(P,Q,var) (-)
 437 INPUT : polynomials P,Q in var
 438 OUTPUT : a couple [g,f]
 439 where g is gcd(P,Q) and
 440 f is the gcd-free part of P with respect to Q,
 441 both the gcd and the gcd-free are considered up
 442 to a constant multiple
 443
 444 -----------------------------------------------------------------
 445 ROOTS COUNTING
 446
 447 rootCouting.mac
 448 rootIsolation.mac (De Casteljau-based method)
 449 -----------------------------------------------------------------
 450
 451
 452 -----------------------------------------------------------------
 453 Auxiliary functions
 454
 455 - sturmSequence(p,x)
 456 INPUT : polynomial p in the x indeterminate
 457 OUTPUT : the Sturm sequence of p
 458
 459 -----------------------------------------------------------------
 460 Main functions
 461
 462
 463 ----------------------------------------------
 464 Cauchy Index on the real line
 465
 466 - cauchyIndex(q,p,x)
 467 INPUT : q,p polynomials in the x indeterminate,
 468 METHOD :
 469 -- sRem [signed remainder sequence]
 470 -- sSubRes [signed subresultants]
 471 OUTPUT : Cauchy index of q/p in the whole real line
 472
 473 - tarskiQuery(q,p,x)
 474 INPUT : q,p polynomials in the x indeterminate,
 475 METHOD :
 476 -- sRem [signed remainder sequence]
 477 -- sSubRes [signed subresultants]
 478 OUTPUT : Tarski query of q,p in the whole real line
 479
 480 - numberOfRoots(p,x)
 481 INPUT : p polynomials in the x indeterminate
 482 METHOD :
 483 -- sRem [signed remainder sequence]
 484 -- sSubRes [signed subresultants]
 485 -- deCasteljau [De Casteljau method for isolation]
 486 -- monomial [monomial method for isolation] (--)
 487 OUTPUT : number of real roots of p
 488
 489 --------------------------------------------------
 490 Cauchy Index on an open interval
 491
 492 Remark: Here we assume that a and b are not roots
 493 of the denominator of the rational function
 494
 495
 496 - cauchyIndexBetween(num,den,x,a,b)
 497 INPUT : num,den polynomials in the x indeterminate,
 498 a,b are either real or -INFINITY or +INFINITY
 499 METHOD :
 500 -- sRem [signed remainder sequence]
 501 -- sSubRes [signed subresultants]
 502 OUTPUT : Cauchy index of num/den in the interval ]a,b[
 503
 504 - tarskiQueryBetween(q,p,x,a,b)
 505 INPUT : q,p polynomials in the x indeterminate,
 506 a,b are either real or -INFINITY or +INFINITY
 507 METHOD :
 508 -- sRem [signed remainder sequence]
 509 -- sSubRes [signed subresultants]
 510 OUTPUT : Tarski query of  q,p in ]a,b[
 511
 512 - numberOfRootsBetween(p,x,a,b)
 513 INPUT : p polynomials in the x indeterminate,
 514 a,b are either real or -INFINITY or +INFINITY
 515 METHOD :
 516 -- sRem [signed remainder sequence]
 517 -- sSubRes [signed subresultants]
 518 -- deCasteljau [De Casteljau method for isolation] (--)
 519 -- monomial [monomial method for isolation] (--)
 520 OUTPUT : number of real roots of p in the interval ]a,b[
 521
 522 -----------------
 523 Hankel Signature
 524
 525 - hankelSignature(seq) (-)
 526 INPUT : sequence seq of odd length of elements of an integral domain
 527 OUTPUT : signature of the Hankel quadratic form for seq
 528
 529 -----------------
 530 Complex Roots with positive/negative real part
 531
 532 - posNegDiff(p,x)
 533 INPUT : polynomial p in x
 534 OUTPUT : difference between the number of roots of p with
 535 positive real part and those with negative real part
 536
 537 -----------------
 538 Bezoutian related
 539
 540 - bez(p,q,var,x,y)
 541 INPUT : p,q polynomials in var, variables x,y
 542 OUTPUT : Bezoutian of p,q with respect to x,y
 543
 544 -----------------------------------------------------------------
 545 ISOLATION OF ROOTS
 546
 547 rootIsolation.mac
 548 -----------------------------------------------------------------
 549
 550 The routines contained in this files deal with
 551 the problem of isolation of real roots by
 552 using the conversion to the Bernstein basis
 553 and De Casteljau's method.
 554
 555 -----------------------------------------------------------------
 556 Auxiliary functions
 557
 558 --------------------------
 559 Cauchy Bounds
 560
 561 - cauchyRootUpperBound(pol,x)
 562 INPUT : polynomial pol in x
 563 OUTPUT : upper bound for the absolute values of all its real roots
 564
 565 - cauchyRootLowerBound(pol,x)
 566 INPUT : polynomial pol in x
 567 OUTPUT : lower bound for the absolute values of
 568 all its non-zero real roots
 569
 570 - primeCauchyRootUpperBound(pol,x)
 571 INPUT : polynomial pol in x
 572 OUTPUT : (alternative) upper bound for the
 573 absolute values of all its real roots
 574
 575 - primeCauchyRootLowerBound(pol,x)
 576 INPUT : polynomial pol in x
 577 OUTPUT : (alternative) lower bound for the
 578 absolute values of all its non-zero real roots
 579
 580 ---------------------------
 581 Bernstein Basis
 582
 583 - convert2Bernstein(p,d,x,l,r)
 584 INPUT : polynomial p in the x indeterminate of degree at most d, parameters l,r
 585 OUTPUT : list containing the coefficients of p in the
 586 Bernstein basis of degree d for l,r
 587
 588 - bernsteinCoeffList(p,x,l,r)
 589 INPUT : polynomial p  in the x indeterminate, parameters l,r
 590 OUTPUT : list containing the coefficients of p in the
 591 Bernstein basis of degree deg(P) for l,r
 592
 593 - bernsteinSplit(coeffList, l,r,m)
 594 INPUT : list coeffList containing the coefficients of a polynomial
 595 in the Bernstein basis of degree d for l,r
 596 parameters l,r,m
 597 OUTPUT : [bern_lm, bern_mr]
 598 where
 599 1) bern_lm is a list containing the coefficients
 600 in the Bernstein basis of degree d for l,m and
 601 2) bern_mr is a list containing the coefficients
 602 in the Bernstein basis of degree d for m,r
 603
 604 - specialBernsteinSplit(coeffList,l,r)
 605 INPUT : list coeffList containing the coefficients of a polynomial P
 606 in the Bernstein basis of degree deg(P) for l,r,
 607 parameters l,r
 608 OUTPUT : [bern_first,bern_second]
 609 where
 610 bern_first is a list containing the coefficients
 611 in the Bernstein basis for l,(l+r)/2 of 2^deg(P) P
 612 bern_second is a list containing the coefficients
 613 in the Bernstein basis for (l+r)/2,r of 2^deg(P) P
 614
 615 -----------------------------------------------------------------
 616 Main functions
 617
 618 - isolateRoots[withZ](pol,x)
 619 INPUT : polynomial pol in x
 620 METHOD:
 621 -- deCasteljau [De Casteljau method for root isolation]
 622 -- monomial [root isolation in the monomial basis] (--)
 623 MODIFIER:
 624 -- withZ : it only computes integer Bernstein coefficients
 625 OUTPUT : list of elements
 626 of the form either
 627 a) [pt]
 628 describing the real root pt
 629 or
 630 b) [a,b]
 631 describing the open interval "(a,b)"
 632
 633
 634 - isolateRootsBetween[withZ](pol,x,search_interval)
 635 INPUT : polynomial pol in x, the open interval search_interval
 636 METHOD:
 637 -- deCasteljau [De Casteljau method for root isolation]
 638 -- monomial [root isolation in the monomial basis] (--)
 639 MODIFIER:
 640 -- withZ : it only computes integer Bernstein coefficients
 641 OUTPUT : list of elements
 642 describing roots in the interval search_interval
 643 of the form either
 644 a) [pt]
 645 describing the real root pt
 646 or
 647 b) [a,b]
 648 describing the open interval "(a,b)"
 649
 650
 651
 652
 653 - findRoots[withZ](pol,x,threshold)
 654 INPUT : polynomial pol in x, threshold for the intervals
 655 METHOD:
 656 -- deCasteljau [De Casteljau method for root isolation]
 657 -- monomial [root isolation in the monomial basis] (--)
 658 MODIFIER:
 659 -- withZ : it only computes integer Bernstein coefficients
 660 OUTPUT : list of elements
 661 of the form either
 662 a) [pt]
 663 describing the real root pt
 664 or
 665 b) [a,b]
 666 describing the open interval (a,b) smaller then threshold
 667
 668
 669 - findRootsBetween[withZ](pol,x,threshold)
 670 INPUT : polynomial pol in x, threshold for the intervals
 671 METHOD:
 672 -- deCasteljau [De Casteljau method for root isolation]
 673 -- monomial [root isolation in the monomial basis] (--)
 674 MODIFIER:
 675 -- withZ : it only computes integer Bernstein coefficients
 676 OUTPUT : list of elements describing roots in the
 677 open interval search_interval
 678 of the form either
 679 a) [pt]
 680 describing the real root pt
 681 or
 682 b) [a,b]
 683 describing the open interval "(a,b)" smaller then threshold
 684
 685
 686 - rootsSign(isInt,p,q,x)
 687 INPUT : polynomials p,q in x,
 688 isolating list isInt for the real roots of p in the
 689 same form as in the output of "isolateRealRoots"
 690 METHOD:
 691 -- deCasteljau [De Casteljau method for root isolation]
 692 -- monomial [root isolation in the monomial basis] (--)
 693 OUTPUT : [[nCPtList,nCIntList],[cPtList,cIntList]]
 694 where
 695 1) nCPtList, cPtList are lists of couples
 696 describing a real root and the sign of q
 697 at this real root
 698 2) nCIntList,cIntList are lists of couples
 699 describing an open interval containing exactly one
 700 the real-root of p, and describing the sign of q
 701 at this root
 702
 703 - compareRoots(p,q,x)
 704 INPUT : polynomials p,q in x
 705 METHOD:
 706 -- deCasteljau [De Casteljau method for root isolation]
 707 -- monomial [root isolation in the monomial basis] (--)
 708 OUTPUT : [com,signNComP,signNComQ]
 709 where
 710 1) com is an isolating list for the common real roots
 711 of p and q
 712 2) signNComP is an isolating list with signs of q for the
 713 real roots of p that are not roots of q
 714 3) signNComQ is an isolating list with signs of p for the
 715 real roots of q that are not roots of p
 716 Remark: all these one intervals and points isolate
 717 the union of the zeros of p and q, i.e. also have
 718 empty intersection among themselves.
 719
 720 -----------------------------------------------------------------
 721 SIGN DETERMINATION
 722
 723 signDetermination.mac
 724 quickSignDetermination.mac
 725 -----------------------------------------------------------------
 726
 727 NOTE: When we refer to an algorithm that computes the
 728 Tarski query of polynomials we assume that it has
 729 the same input/output format as
 730 "tarskiQuery" (see "ROOT COUNTING")
 731
 732 -----------------------------------------------------------------
 733 Auxiliary functions
 734
 735 - matrixOfSigns(adaExpList,signCondList)
 736 INPUT : list adaExpList of t-uples of exponents,
 737 list of of t-uples signs (-1,0,1), where adaExpList is adapted to sign
 738 determination for a set of t elements (polynomials) on signCondList
 739 OUTPUT : the corresponding matrix of signs
 740
 741 - tarskiQueryVector(adaExpList,polList,var,SQ,ptSet)
 742 INPUT : list adaExpoList of t-uples of exponents,
 743 list of polynomials in var,
 744 description of a finite set of points ptSet,
 745 algorithm SQ to compute
 746 the Tarski query with respect to ptSet
 747 OUTPUT : vector containing the Tarski Queries
 748 with respect to ptSet of
 749 the polynomials in polList with exponents given
 750 by adaExpList
 751
 752 -----------------------------------------------------------------
 753 Main functions
 754
 755 - signDetermination(polList,ptSet,sqAlg,var)
 756 INPUT : list polList of polynomials in var,
 757 a description of a finite set of points,
 758 an algorithm sqAlg to compute the Tarski query of polynomials
 759 in polList
 760 with respect to ptSet
 761 METHOD :
 762 -- naive [brute force method on a huge matrix of signs]
 763 -- smart [a method that uses much smaller matrices of signs]
 764 -- quick [an optimization of smart]
 765 OUTPUT : a list representing
 766 a subset of  the all elements of {0,-1,1}^polList
 767 describing the possible signs of the polynomials
 768 in polList at ptSet
 769
 770 And similar functions for zero-nonzero determination
 771 based on results in D. Perrucci, M.-F. Roy. Zero-nonzero and real-nonreal sign determination, Linear
 772 Algebra and Its Applications 439 (2013), no. 10, pp. 3016-3030 (preliminary version,arXiv:1305.4131).
 773 The main ones are
 774
 775 - invertibilityQuery(q,p,x)
 776 INPUT : q,p polynomials in the x indeterminate,
 777 METHOD :
 778 -- gcd
 779 OUTPUT : number of complex roots of p where q is nonzero
 780
 781 - zerononzeroDetermination(polylist,p,Qu,var)
 782 INPUT : list polList of polynomials in var, a description of a finite set of points, an algorithm Qu to compute the Invertibility
 783 query
 784 OUTPUT : a list representing a subset of the all elements of {0,-1,1}^polList describing the possible zero nonzero conditions
 785 of the polynomials in polList at the complex zeroes of p
 786
 787 - zerononzeroDeterminationwithcardinals(polylist,p,Qu,var)
 788 INPUT : list polList of polynomials in var, a description of a finite set of points, an algorithm Qu to compute the Invertibility
 789 query
 790 OUTPUT : a list representing a subset of the all elements of {0,-1,1}^polList describing the possible zero nonzero conditions
 791 of the polynomials in polList at the complex zeroes of p and the corresponding cardinals
 792
 793 -----------------------------------------------------------------
 794 THOM ENCODINGS
 795
 796 signDetermination.mac
 797 -----------------------------------------------------------------
 798
 799 Note: Here we refer to "extended Thom-encoding" for P with
 800 respect to Q as to the sign determination for Q, all the
 801 derivatives of Q, all the derivatives of P at the roots of P
 802
 803 -----------------------------------------------------------------
 804 Auxiliary functions
 805
 806 - thomLess(lhs,rhs)
 807 INPUT : Thom encodings lhs, rhs
 808 OUTPUT : TRUE if lhs<rhs, FALSE otherwise
 809
 810 - thomSort(thomList)
 811 INPUT : list of Thom-encodings
 812 OUTPUT : order list of Thom-encodings
 813
 814 - extThomEncoding(P,Q,var)
 815 INPUT : polynomials P,Q in var
 816 OUTPUT : a list of "extended Thom-encodings" for P w.r.t. Q,
 817
 818 - extThomMerge(lhs,lhsDeg,rhs,rhsDeg)
 819 INPUT : lhs, rhs are "extended Thom-encodings" for two polynomials
 820 one with respect to the other,
 821 lhsDeg, rhsDeg are the degrees of the polynomials
 822 OUTPUT : a list containing
 823 elements of the form [owner,thomInf] with
 824 the following possibilities
 825 a) [0,thomP,thomQ]
 826 for a common root of P
 827 with Thom encoding thomP
 828 and of Q with Thom encoding thomQ
 829 b) [1,thomP]
 830 for a root of P not of Q with Thom encoding thomP
 831 c) [2,thomQ]
 832 for a root of Q not of P
 833 with Thom encoding thomQ
 834 -----------------------------------------------------------------
 835 Main functions
 836
 837 - thomEncoding(P,var)
 838 INPUT : polynomial P in var
 839 OUTPUT : a list containing the Thom encoding of the real roots of P
 840
 841 - thomCompare(P,Q,var)
 842 INPUT : polynomials P,Q in var
 843 OUTPUT : a list containing
 844 elements of the form [owner,thomInf] with
 845 the following possibilities
 846 a) [0,thomP,thomQ]
 847 for a common root of P
 848 with Thom encoding thomP
 849 and of Q with Thom encoding thomQ
 850 b) [1,thomP]
 851 for a root of P not of Q with Thom encoding thomP
 852 c) [2,thomQ]
 853 for a root of Q not of P
 854 with Thom encoding thomQ
 855
 856
 857 - thomSignsAtRoots(P,Q,var)
 858 INPUT : polynomials P,Q in var
 859 OUTPUT : a list of couples containing
 860 for each root of P its Thom encodings
 861 and the corresponding sign of q
 862
 863
 864 -----------------------------------------------------------------
 865 TOPOLOGY
 866
 867 topology.mac
 868 -----------------------------------------------------------------
 869
 870 NOTE: When we refer to an algorithm for isolating real roots
 871 in an archimedean real closed field we assume
 872 that has the same input/output format as
 873 "isolateRoots" (see ROOT ISOLATION).
 874
 875 -----------------------------------------------------------------
 876 Main functions
 877
 878 - archimedeanTopology(P,isolAlg,x,y)
 879 INPUT : a square free polynomial P in x and y,
 880 algorithm "isolAlg" for the
 881 isolation of real roots in an archimedean real closed field
 882 FLAG: "DRAW_TOPOLOGY" (set to false by default) when set to true it will trigger "drawTopology" to display the topology diagram automatically. Remark: if a diagram is displayed, you need to close the pop-up window to get the result.
 883 OUTPUT : a couple containing
 884
 885 i) the number "a" of changes of
 886 system of coordinates in order to obtain a
 887 curve in generic position, i.e. we assume that the
 888 system has been changed by x -> x+a*y,
 889
 890 ii) the topology with respect to the x-axis
 891 of the curve, which is represented as a sequence
 892 alternating numbers and couples
 893 where
 894
 895 ii.1) the numbers describe the number of intersections
 896 of the curve with projections to the x-axis in intervals
 897 between critical points
 898
 899 ii.2) the couples (numInt, critPos) contain:
 900 ii.2.1) the number of intersections numInt
 901 with projections to the x-axis on critical points
 902 ii.2.2) the position critPos of the critical point on the projection
 903 (in bottom-up order).
 904
 905
 906 -drawTopology(tpg) (-)
 907 INPUT : the topology of the curve (as in the second
 908 element of the output of archimedean topology or alternatively since SARAG 1.3 as the full output of archimedean topology)
 909 OUTPUT : number of critical points
 910 EFFECT: it uses gnuplot (3.7.x, 4.0.x or above) to draw the topological graph
 911 corresponding to description in tpg
 912
 913
 914 -----------------------------------------------------------------
 915 INTERVAL ARITHMETIC
 916
 917 intervalArithmetic.mac (-)
 918 -----------------------------------------------------------------
 919
 920 - evaluatePolAt(P,var,interval)
 921 INPUT : polynomial P in var, an interval describing a root of P
 922 OUTPUT : an interval describing the value of P at the root
 923 described by the input
 924
 925 -----------------------------------------------------------------
 926 CERTIFICATE OF POSITIVITY
 927
 928 certificateOfPositivity.mac
 929 -----------------------------------------------------------------
 930 Based on F. Boudaoud, F. Caruso M.-F. Roy Certificates of positivity in the
 931 Bernstein basis, Discrete and Computational Geometry 39 4 639-655 (2008)
 932
 933 Note:
 934
 935 [0] A certificate is an elementrary proof of the positivity
 936 of a given polynomial in a given interval.
 937
 938 [1] A certificate of positivity/negativity for a polynomial
 939 P in a given interval R is
 940 a LIST of :
 941 [<sub-interval of R>, C, <Bernstein basis of C P>]
 942 where the sub-intervals cover entirely R.
 943
 944
 945 [2] The output of the main functions for a given polynomial P
 946 are of the following form:
 947
 948 (a) When the polynomial P has a root in the considered interval:
 949 [ 0,
 950 <interval [a,b] such that Q(a)Q(b)<0 for a polynomial divisor Q>,
 951 <A polynomial divisor Q of P>]
 952
 953 (b) When the polynomial P is positive/negative in the given interval:
 954 [ 1/-1,
 955 <list of certificates covering the considered interval>]
 956
 957
 958 -----------------------------------------------------------------
 959
 960 Auxiliary functions
 961
 962 - sqFreeCertificate(pol,var)
 963
 964 INPUT : square-free polynomial in var
 965 MODIFIER :sqFreeCertificateBetween(pol,var,search_interval)
 966 OUTPUT : list of local "certificates" of positivity/negativity
 967 that cover the default interval ([-1]).
 968
 969
 970 - bernsteinMerge(lhsBern, rhsBern)
 971
 972 INPUT : certificates lhsBern, rhsBern
 973 OUTPUT : a certificate for the interval covering both lhsBern and rhsBern
 974
 975
 976 - compressCertificate(cert_list)
 977
 978 INPUT  : a list of certificates
 979 OUTPUT : a possibly shorter and equivalent list of certificates
 980
 981 -----------------------------------------------------------------
 982 Main functions
 983
 984
 985 - certificate(pol,var)
 986 INPUT : polynomial in var
 987 OPTIONAL PARAMETERS:
 988 - if 3 parameters are used, the third parameter specifies the interval;
 989 - if 4 parameters are used they are interpreted as the left and right end of the interval;
 990 OUTPUT : list of local "certificates" of positivity/negativity
 991 that cover entirely the default interval ([-1,1]).
 992
 993
 994 - certificateProof(pol,var,search_interval)
 995 INPUT : a polynomial in var, a search interval (ex. [-1,-1])
 996 OUTPUT : number of subintervals used for proving the positivity/negativity
 997 EFFECT : it prints a formal proof of positivity/negativity of pol in
 998 search_interval or of the existence of a root.
 999
1000
1001 -----------------------------------------------------------------
1002 MULTIVARIATE CERTIFICATE OF POSITIVITY
1003
1004 multivariateCertificateOfPositivity.mac
1005
1006 Based on R. Leroy, Certificats de positivité et minimisation polynomiale dans
1007 la base de Bernstein multivariée http://tel.archives-ouvertes.fr/tel-00349444/fr/
1008 -----------------------------------------------------------------
1009
1010 - multiCertificate(P,V,vars,d,sub,cert)
1011 INPUT:
1012 polynomial P in vars,
1013 simplex in V,
1014 list of variables "vars",
1015 degree d,
1016 subdivision algorithm "sub",
1017 type of certificate "cert"
1018 EXAMPLE:
1019 f:9*y^2-24*x*y+12*y+16*x^2-16*x+5;
1020 Cf:certificate(f,[[0,0],[1,0],[0,1]],[x,y],2,bisection,pos);
1021
1022 - (wx)drawMultiCertificate(C,sc)
1023 INPUT: output of "multiCertificate", scale sc
1024 EFFECT: it draws the subdivision corresponding to the certificate C