Home

Bertini User`s Manual - University of Notre Dame

1. NAME ACCEPTABLE VALUES DEFAULT VALUE SCREENOUT 0 1 0 OUTPUTLEVEL 1 0 1 2 3 0 STEPSFORINCREASE 21 5 MAXNEWTONITS gt 0 2 MAXSTEPSIZE gt 0 and 1 0 1 NBHDRADIUS gt 0 and 1 1e 100 ENDGAMEBDRY gt 0 and 1 0 1 TARGETTIME 20 and 1 0 MAXNUMBERSTEPS 20 10000 SAMPLEFACTOR gt 0 and 1 0 5 MAXCYCLENUM 21 6 AMPSAFETYDIGITS1 anything 1 AMPSAFETYDIGITS2 anything 1 MAXNUMPTSFORTRACE gt 0 5 MAXNUMMONLINEARS gt 0 5 MAXNUMBADLOOPSINMON gt 0 10 INTRINSICMULTIPLIER gt 0 and lt 1 0 75 REGENSTARTLEVEL gt 0 0 REGENREMOVEINF 0 1 1 SLICETOLBEFOREEG gt 0 le 7 SLICETOLDURINGEG gt 0 le 8 SLICEFINALTOL gt 0 le 11 MINCYCLETRACKBACK gt 0 4 55 Configurations TRACKTYPE Set to 0 for zero dimensional tracking 1 for numerical irreducible decomposition 2 for com ponent sampling 3 for the component membership test 4 for printing a witness set or 5 for witness projection MPTYPE Indicates the level of precision to be used Set to 0 for regular precision 1 for higher pre cision or 2 for adaptive precision If MPTYPE is 1 the user should also set PRECISION to the desired level of precision Note that in the case of MPTYPE is 2 Bertini will auto matically begin each path with regular precision regardless of the setting of PRECISION Also if MPTYPE is 2 COEFFBOUND DEGREEBOUND AMPSAFETYDIGITSI and AMPSAFETYDIGITS2 should be set up please refer to the descriptions of those settings for details
2. Figure 4 2 Running Bertini using input basic 26 jhauenst sleipnir BertiniExamples Eile Edit View Terminal Tabs Help Figure 4 3 Nonsingular solutions for input_basic jhauensto sleipnir BertiniExamples Edit View Terminal Tabs Help lv Elle Figure 4 4 input_basic with sharpening configuration jhauenst sleipnir BertiniExamples e Edit View Terminal Tabs Help Figure 4 5 Nonsingular solutions for input_basic with sharpening 4 4 2 Extended example Figure 4 6 presents an input file named input_extended1 that instructs Bertini to use all default settings to solve z 1 zy 1 0 on C By default Bertini automatically uses adaptive precision tracking 6 7 with truncation for paths appearing to be approaching solutions at infinity as shown in Figure 4 7 Figure 4 8 presents an input file named input extended2 that instructs Bertini to use solve the same polynomial system using secure path tracking SECURITYLEVEL 1 tighter tracking 27 jhauenst sleipnir BertiniExamples _ Eile Edit View Terminal Tabs Help CONFIG END INPUT variable group x y function f g f x2 1 g x y 1 END input extendedl 14L 91C 14 0 1 Figure 4 6 input extended1 v i REES Eile Edit View Terminal Tabs Help jhauenst sleipnir BertiniExamples bertini input extendedl _jhauenst sleipnir BertiniExamples NOTE You have requested to use a
3. 4 2 Output on the screen 43 Output in hles an io ERE ee be Bar ee RR EXE 4 4 Zero dimensional examples rh 4A Basic example 2 42320 al a ls 4 4 2 Extended example coul oko a a RUE EUR 4 4 3 Regeneration example less 5 Details about positive dimensional runs 5 1 How Bertini finds these solutions Eon nn nn 5 2 Output on the screen oaa 5 3 Outputzindfiles gag ig a ERG Ren REGE Slee ete ES d RAS Me Wed 5 4 Positive dimensional examples En nn nn nn 54 12 Basicexampl x sd aa Be a A e io ARA des 5 4 2 Twisted cubic E A ic ote A TOTO RR 5 4 3 Deflation example e 5 5 Component sampling and membership testing 22 2 2 cn Emmen 9 6 Primtang a witness Set u neck a E Wap a ee 5 7 Witness sets of projections ll s 6 Comments about running Bertini in parallel 7 A bit about how Bertini works 7 1 Data types and linear algebra Co oo nn 7 1 1 Basic data types ls 1 1 2 Linear leebrar sinn ra Wo ne 7 2 Preprocessing of input files in Bertini on on nn nn 7 2 1 Advantages of using straight line programs 7 2 2 Implementation details for straight line programs Bibliography A Configurations A 1 Optional configurations 4 ll less sss 34 34 35 35 35 36 38 38 42 42 42 43 44 44 44 45 46 46 47 49 53 Chapter 1 Introduction to Bertini Numerical algebraic geometry
4. 32 jhauenst sleipnir BertiniExamples Eile Edit View Terminal Tabs Help jhauenstOsleipnir BertiniExamples bertini input regeneration NOTE You have requested to use adaptive path tracking Please make sure that you have setup the following tolerances appropriately COEFFBOUND 1 000000000000e 03 DEGREEBOUND 5 000000000000e 00 AMPSAFETYDIGITS1 1 AMPSAFETYDIGITS2 1 AMPMAXPREC 1024 Tracking regeneration level O of 3 5 paths to track Tracking path O of 5 Sorting regeneration level O of 3 5 paths to sort Sorting 0 of 5 Preparing regeneration level 1 of 3 5 witness points to move Moving O of 5 Tracking regeneration level 1 of 3 6 paths to track Tracking path O of 6 Sorting regeneration level 1 of 3 6 paths to sort Sorting 0 of 6 Preparing regeneration level 2 of 3 7 witness points to move Moving O of 7 Tracking regeneration level 2 of 3 8 paths to track Tracking path O of 8 Sorting regeneration level 2 of 3 8 paths to sort Sorting 0 of 8 iefefeteieteoememiee Regeneration summary RREERRERERER ERR NOTE nonsingular vs singular is based on rank deficiency and identical endpoints level paths nonsing endpoints total discarded sing endpoints inf endpoints higher dim l other bad endpoints 0 2 4 14 I 15 17 Non singular Finite Solution Summary NOTE nonsingular vs singular is based on rank deficiency and identical endpoints Number of real solns Number of non real
5. f x 2 1 x y 1 un END Figure 4 1 Basic input file th Mi o jhauenstO sleipnir BertiniExamples File Edit View Terminal Tabs Help jhauenst sleipnir BertiniExamples bertini input basic NOTE You have requested to use adaptive path tracking Please make sure that you have setup the following tolerances appropriately COEFFBOUND 1 000000000000e 03 DEGREEBOUND 5 000000000000e 00 AMPSAFETYDIGITS1 1 AMPSAFETYDIGITS2 1 AMPMAXPREC 1024 Tracking path 0 of 2 Finite Solution Summary NOTE nonsingular vs singular is based on condition number and identical endpoints Number of real solns Number of non real solns Total Non singular 2 0 2 Singular 0 0 I 0 Total 2 0 2 Finite Multiplicity Summary Multiplicity Number of real solns Number of non real solns The following files may be of interest to you main_data A human readable version of the solutions main output file raw solutions A list of the solutions that can be used for reading into a program raw data Similar to the previous but with the points in Bertini s homogeneous coordinates along with more information about the solutions real finite solutions A list of all real finite solutions finite solutions A list of all finite solutions nonsingular solutions A list of all nonsingular solutions singular solutions A list of all singular solutions Paths Tracked 2 jhauenst sleipnir BertiniExamples a
6. so for example 8 5 6 becomes 43 8 5 6 Table 6 1 lists all currently supported operations and their corresponding codes Table 7 1 LEGAL OPERATIONS IN BERTINI Operation ASCII Code WE 43 binary 45 42 47 i 94 61 unary 78 for N sin 83 for S COS 67 for C exp 88 for X Thus the Bertini style straight line program for the current example would be 43 8 5 6 94 10 89 42 11 10 7 614 11 If m homogenization was being carried out during parsing Bertini would simply compare the degrees of each operand while parsing and add extra instructions corresponding to multiplication by a homogenizing variable as necessary Once the straight line program for a polynomial system has been created a function called diff reads through the straight line program one instruction at a time creating instructions for the Jacobian of the system as described above Finally Bertini concatenates the two straight line programs to make one complete straight line program for computing the function and derivative values of the polynomial system 48 Bibliography 1 N 10 11 12 E Allgower and K Georg Introduction to numerical continuation methods volume 45 of Clas sics in Applied Mathematics Society for Industial and Applied Mathematics SIAM Philadel phia PA 2003 Reprint of the 1990 Spring Verlag edition D Bates I Fotiou and P Rostalski A numerical algebraic ge
7. Starting with Bertini v1 2 DEGREEBOUND is computed and COEFFBOUND is approximated when not using a user defined homotopy The user provided bounds take precedence over the computed bounds PRECISION This indicates the level of precision to use in bits if MPTYPE 1 Standard settings include 64 bits roughly 19 decimal digits 96 28 128 38 160 48 192 57 224 67 and 256 77 In general N bits is equivalent to N mio decimal digits The maximum is 3328 bits roughly 1000 digits and this setting has no effect if MPTYPE 0 or 2 ODEPREDICTOR This indicates which ODE method to utilize to predict the next point on the path The available predictors are Euler 0 Heun Euler 3 Norsett 4 Fehlberg 5 Cash Karp 6 Dormand Prince 7 and Verner 8 See 4 for more details TRACKTOLBEFOREEG The desired tracking tolerance during the non endgame portion of the path In other words the goal of the corrector steps is to have two iterates within TRACKTOLBEFOREEG of each other using the infinity norm TRACKTOLDURINGEG The same as TRACKTOLBEFOREEG except that it is used in the endgame portion of the path FINALTOL This is the tolerance to which the endpoints of successful paths will be accurate For example if FINALTOL is 1e 11 the first 11 digits of the endpoint will be correct MAXNORM For post processing this is the cutoff for finite versus infinite endpoints Also for user defined homotopies if any point
8. 58 REDUCEDONLY Set to 1 to find only reduced components during a positive dimensional run 0 to find all components MAXCODIMENSION Set to 0 to consider all possible codimensions and set to a positive integer to not consider codimensions larger than the given value ENDGAMENUM Set to 1 to use the fractional power series endgame set to 2 to use the Cauchy endgame and set to 3 to use the Cauchy trackback endgame of 5 NUMSAMPLEPOINTS The number of sample points used in the endgame to create the approximation With 2 sample points the power series endgame generates a 3rd order approximation USEREGENERATION Set to 1 to use regeneration in a zero dimensional run 0 otherwise During a positive dimensional run setting to 1 uses regeneration to compute a witness superset SECURITYLEVEL Set to 0 to have Bertini truncate paths that appear to be headed to infinity 1 otherwise SECURITYMAXNORM When SECURITYLEVEL is 0 this is the cutoff to truncate paths That is if two successive approximations are larger than SECURITYMAXNORM the path is truncated SCREENOUT Set to 1 to have all output printed to the screen as well as to the appropriate output file Otherwise set to 0 A setting of 0 should suffice unless debugging OUTPUTLEVEL The levels 1 to 3 provide a different amount of path tracking information to the output file A setting of 0 should suffice unless debugging STEPSFORINCREASE This is the number of cons
9. Zhao Evaluation of jacobian matrices for newton s method with deflation for isolated singularities of polynomial systems In SNC 2005 Proc pages 19 28 2005 22 T Y Li Numerical solution of multivariate polynomial systems by homotopy continuation methods In Acta numerica 1997 volume 6 of Acta Numer pages 399 436 Cambridge Univ Press Cambridge 1997 23 Y Lu D Bates A Sommese and C Wampler Finding all real points of a complex curve Contemp Math 448 183 205 2007 24 A Morgan Solving polynomial systems using continuation for engineering and scientific prob lems Prentice Hall Inc Englewood Cliffs NJ 1987 25 A Morgan A Sommese and C Wampler Computing singular solutions to nonlinear analytic systems Numer Math 58 7 669 684 1991 26 A Morgan A Sommese and C Wampler Computing singular solutions to polynomial sys tems Adv in Appl Math 13 3 305 327 1992 27 A Morgan A Sommese and C Wampler A power series method for computing singular solutions to nonlinear analytic solutions Numer Math 63 3 391 409 1992 50 28 A Sommese J Verschelde and C Wampler Numerical decomposition of the solution sets of polynomial systems into irreducible components SIAM J Numer Anal 38 6 2022 2046 2001 29 A Sommese J Verschelde and C Wampler Homotopies for intersecting solution components of polynomial systems STAM J Numer Anal 42 4 1552 1571 2004 3
10. and yacc in general please refer to 11 To use lex and yacc or their variants one must produce two files that together describe how to convert the input structure into an output structure For example these files convert from Maple style input files to straight line programs in the form of a list of integers in Bertini The main part of the lex file contains descriptions of the tokens to be detected within the input file In the case of Bertini these include tokens such as integers floating point numbers string names and other implementation specific words such as variable group and END The main part of the yacc file consists of an ordered set of rules to which the tokens may be set There are a variety of nuances in creating such a yacc file but the main idea is to create a list of unambiguous rules that together completely specify the structure of the input file For example the first two rules of the Bertini yacc file specify that the input file should have the structure of a command followed by a command list or followed by the word END Each command is then a declaration or an assignment and so on The main part of this set of rules for Bertini is the definition of an expression the right hand side of a polynomial definition Each expression is a sum of terms each term is a product of monomials each monomial is some kind of primary and each primary is a number a name or another expression contained i
11. built in because many systems coming from engineering have symmetry so lumping many identical parts of the input file together into one subfunction results in increased efficiency in function evaluation Function and Jacobian evaluation are the most expensive parts of almost all runs Note that subfunctions are the only names in an input file that do not need to be declared Here is an example in which the subfunction appears in every function adapted from 33 variable group x y Z function f1 f2 f3 S x 2 5y 2 z272 1 f1 y x 2 S x 0 5 f2 z x 3 S y 0 5 f3 y x 2 z x 3 S z 0 5 END If you are reading through this manual from beginning to end you should now be prepared to run most zero dimensional examples just by using the format of the files in this section and perhaps referring to the syntax rules provided in the next chapter and the table of configurations provided in Appendix A 2 2 2 Positive dimensional examples The input files for positive dimensional runs are almost identical to those for zero dimensional runs In fact other than a few configuration settings it is impossible to distinguish between the two Here are the differences e To specify that Bertini should do a positive dimensional run rather than the default zero dimensional run the user must change the TRACKTYPE in the CONFIG portion of the input file For example TRACKTYPE 1 specifies a basic positive dimensional run 2 specifi
12. dimensional case Bertini will report an error message to the screen in the case of a suspected path crossing Bertini detects this by comparing path values at t 0 1 or some other endgame breakpoint as defined by the user This is not a foolproof way of detecting path crossing but it will catch many cases There is also a list of files of interest 5 3 Output in files The main output file of interest is called main data It contains all points in the witness set in a format that is easily readable by humans witness data is a file suited for automated reading by a program It contains all of the information needed to describe the witness set in particular the information used for component sampling and membership testing As of May 2011 when using the regenerative cascade 20 after each codimension Bertini prints the file regenSummary which provides information about the codimensions The format of the file is as follows The first line contains six integers namely the MPTYPE the number of codimensions the number of functions the number of variables the number of variables used for tracking and the system rank The next line is the integer which is the codimension that just finished The file then contains a line for each of the codimensions If the codimension has been completed the line contains eight integers namely the codimension the number of paths the number of points in the witness superset the number of nonsingular poin
13. is a young and burgeoning field of mathematical research It lies at the intersection of algebraic geometry and numerical analysis and addresses problems arising both in the sciences and engineering and also in pure algebraic geometry Bertini is a software package for computation in numerical algebraic geometry 1 1 What Bertini does Generally speaking numerical algebraic geometry provides algorithms for computing and manipu lating structures of an algebro geometric nature A number of these algorithms have been imple mented in Bertini and more are on the way For example Bertini can be used to produce all isolated solutions of a system of polynomials with complex coefficients These points can be com puted with up to several hundred digits of accuracy since Bertini makes use of multiple precision Even better the user does not need to know a priori the level of precision necessary to attain the desired accuracy because Bertini may be told to use adaptive precision changes Details about such zero dimensional solving may be found in Chapter 4 Another of Bertini s key capabilities is that it can find witness points on every irreducible component of the algebraic set corresponding to a system of polynomials with complex coefficients 33 is a good reference for the definitions theory and algorithms behind such witness sets The bottom line is that Bertini will detect the irreducible decomposition of the algebraic set by specifying at
14. least one point on each component Once such a witness set is computed the user may sample any component i e produce as many points on the component as desired and perform component membership i e specify a list of points and ask Bertini to determine whether any of the points lie on the algebraic set corresponding to the witness set Bertini allows the user to choose from several different types of runs and to specify a large number of tolerances although all tolerances come with reasonable default settings The point of this manual is to indicate how to use Bertini see 81 4 not the theory behind the algorithms If you are new to numerical algebraic geometry or would like a refresher on some of the latest algorithms here is a list of some of the more recent references mostly listed by date of publication e General references 22 30 33 e Finding isolated solutions 24 1 22 30 33 e Finding witness sets 28 30 33 e Endgames 25 26 27 e Sophisticated start systems 22 e Adaptive multiple precision 6 7 e Deflation 21 e Intersecting solution sets 29 e Equation by equation solving 32 19 e Applications within mathematics 12 8 23 9 10 e Applications in engineering and the sciences 39 40 33 2 41 37 e Related software 38 13 42 14 17 35 44 1 2 Where Bertini may be found The official Bertini website is http www nd
15. m groups Then when parsing the system into a straight line program as described in the next section for each operation one must simply compare the multidegrees of the operands and multiply in copies of the appropriate new homogenizing variables as needed For example if the operands of an addition have multidegrees 0 1 0 and 1 2 0 before recording the straight line instruction for this operation one must record two extra instructions corresponding to multiplying the first operand by the first and second homogenizing variables After a system is homogenized it is again just a matter of bookkeeping to produce the corresponding start system and to solve this start system in order to produce the set of start points Automatic differentiation is also very simple in the straight line program setting Please note that automatic differentiation is not the same as numerical or approximate differentiation the 46 result of automatic differentiation is as exact as the input even if the input is exact The idea of automatic differentiation is to produce a set of instructions for evaluating the derivative of a polynomial or other function given a straight line program for the evaluation of the original poly nomial or function There are many variations on the basic method but the most basic method called forward automatic differentiation is used within a pair of loops to produce instructions for evaluating the Jacobian of a polynomial syste
16. numbers in either standard notation e g 3 14159 or 0 0023 or scientific notation e g 3 14159el or 2 3e 3 No decimal point is needed in the case of an integer To define complex numbers simply use the reserved symbol I for Y 1 e g 1 35 0 98 I Please note that the multiplication symbol is always necessary i e concatenation does not mean anything to Bertini Since it is sometimes useful to have constants gathered in one location rather than scattered throughout the functions Bertini has a constant type If a constant type is to be used it must be both declared and assigned to Here is an example constant gi g2 gi 1 25 g2 0 75 1 13 I 19 Bertini will read in all provided digits and will make use of as many as possible in com putations depending on the working precision level If the working precision level exceeds the number of digits provided for a particular number all further digits are assumed to be 0 i e the input is always assumed to be exact This seems to be the natural accepted implementation choice but it could cause difficulty if the user truncates coefficients without realizing the impact of this action on the corresponding algebraic set e SUBFUNCTIONS Redundant subexpressions are common in polynomial systems coming from applications For example the subexpression x 2 1 0 may appear in each of ten polynomials One of Bertini s advantages is that it allows for the use of subfunctions To
17. on the path exceeds MAXNORM tracking will be terminated since the path appears to be going to infinity 56 MINSTEPSIZEBEFOREEG This is the smallest steplength that Bertini will allow during the non endgame portion of each path If a predictor corrector step fails and causes the steplength to drop below this level the path will be declared a failure Since adaptive precision verifies the precision is sufficient for the step size the user should not adjust this configuration when using adaptive precision MINSTEPSIZEDURINGEG The same as MINSTEPSIZEBEFOREEG except that it holds in the endgame portion of the path IMAGTHRESHOLD Endpoints are considered real if the imaginary parts of the coordinates are all less than IMAGTHRESHOLD in absolute value COEFFBOUND When using adaptive precision MP TYPE is 2 it is necessary to provide a bound on the sums of the absolute values of the coefficients of the polynomials In other words COEFFBOUND must bound the sum of the absolute values of the coefficients of every polynomial in the poly nomial system Starting with Bertini v1 2 COEFFBOUND is automatically approximated when not using a user defined homotopy with a user provided bound taking precedence over the computed bound DEGREEBOUND As with COEFFBOUND DEGREEBOUND must be provided whenever adaptive precision MPTYPE is 2 is used DEGREEBOUND is simply a bound on the degrees of the polynomi als in the system Starting with Bertini v
18. refer to the references listed in 81 1 The best way to learn how to use Bertini is through examples so this manual consists mostly of examples syntax rules and configuration options In particular Chapter 2 is key for first time users in that it provides very basic examples and a description of how to set up and carry out basic runs of various types Chapter 3 is intended mostly for reference and should be useful especially 83 2 when Bertini will not run due to a syntax error in the input file Chapters 4 and 5 give further details about and options for zero and positive dimensional runs respectively Algorithms and output are described in those two chapters and details regarding the special case of user defined homotopies are given in 82 2 3 A few details regarding the parallel versions of Bertini are provided in Chapter 6 and the inside workings of Bertini are provided in Chapter 7 Finally the appendix gives a detailed list of all user changeable options The best way to learn how to use Bertini is to try the simple problems included with the distribution using this manual as your guide as described above Daniel Bates gave a talk in October 2006 about using Bertini around the time the beta version was first released This talk took place at the IMA Institute for Mathematics and its Applications in Minneapolis MN USA It was videotaped and is available to the public by navigating through the IMA website http www ima umn edu
19. singular is based on rank deficiency and identical endpoints codim witness points nonsingular singular RERO VOR ee e e o oett fete ee eee o eee Calculating traces for codimension 2 Calculating 0 of 1 noce Witness Set Decomposition Wr wann dimension components classified unclassified eee Decomposition by Degree ttrstrreeuner Dimension 0 1 classified component degree 1 1 component EEE ELITE II ET ENTE Witness Points Deflated 1 jhauenst sleipnir BertiniExamples Figure 5 7 Running Bertini using input_Griewank_Osborne 41 5 5 Component sampling and membership testing For component sampling Bertini reads in information about the witness set corresponding to the target system in the input file from the witness data file It then queries the user about which component to sample and how many points to find After the user s choices are made Bertini simply moves the appropriate linears around as in monodromy and gathers the desired number of sample points These points are either printed to the screen or to a file For membership Bertini reads in information about the witness set as in the case of sampling It then reads in from the file member points all points that the user would like to test Bertini moves the appropriate slices around and reports to the screen whether any of the points lie on the algebraic set and if so on which component they reside 5 6 Printing a witness s
20. storage structure for polynomials in Bertini is the straight line program A straight line program of a polynomial or a function in general is a list of unary and binary operations that may be used to evaluate the polynomial or function For example the expression 2 y z may be broken into the following straight line program tj r cy to tj t3 tg Zz Then to evaluate the expression one may simply substitute in the values of x y and z as they are needed The next section describes several advantages to using straight line programs The section after that describes specifically how Bertini converts polynomials in input into straight line programs 7 2 1 Advantages of using straight line programs There are several advantages to using straight line programs for the representation of polynomial systems For one it allows for the use of subfunctions as described above Also it sidesteps the difficulty of expression swell by allowing for non standard expression representation e g many more operations are needed to evaluate the expansion of x y at least 17 operations than are needed when evaluating the factored form of the expression Finally the use of straight line programs makes automatic differentiation and homogenization very easy To homogenize a polynomial system given by a straight line program one must first record the breakup of the variables into m variable groups and add one new variable to each of the
21. the paths TRACKTOLBEFOREEG 1e 7 amp TRACKTOLDURINGEG le 7 tighter convergence tolerance for the endgame FINALTOL 1e 12 and sets the adaptive precision settings appropriately for the system COEFFBOUND 2 amp DEGREEBOUND 2 Bertini now computes the solutions at infinity using the settings requested as shown in Figure 4 9 jhauenst sleipnir BertiniExamples Edit View Terminal Tabs Help Figure 4 8 input extended2 We can exploit the 2 homogeneous structure in the system z 1 zy 1 0 by separating x and y into separate variable groups Figure 4 10 presents an input file named input extended3 that demonstrates how to do this with Figure 4 11 presenting the output of Bertini to the screen 29 Figure 4 9 Running Bertini using input extended2 jhauenst sleipnir BertiniExamples Edit View Terminal Tabs Help Figure 4 10 input extended3 30 lv jhauenst sleipnir BertiniExamples Ge ER Ver Tesis Tus dp Figure 4 11 Running Bertini using input extended3 3l 4 4 3 Regeneration example Figure 4 12 presents an input file named input regeneration to solve a system adapted from 33 with a subfunction S It computes the nonsingular isolated solution x y z 0 5 using regeneration 19 Output to the screen is presented in Figure 4 13 jhauenstc sleipnir BertiniExamples Eile Edit View Terminal Tabs Help Figure 4 12 input regeneration
22. the starting points are provided on separate lines by listing the real part and imaginary part of each coordinate The following input file defines a homotopy from x z to x in Pl CONFIG USERHOMOTOPY 2 END INPUT hom variable group x z function f pathvariable t parameter s constant gamma gamma 0 8 1 2 I s t f x 2 z 2 xgamma s x 2 1 s Note that only s appears not t END A start file for tracking both paths defined by this homotopy is as follows Note that Bertini automatically computes the representative of the homogeneous points on the randomly chosen patch 14 2 2 4 Parameter homotopies Starting with version 1 3 Bertini implements parameter homotopies for a linear parameter space The keyword PARAMETERHOMOTOPY has two relevant settings when the TRACKTYPE is set to 0 When PARAMETERHOMOTOPY is set to 1 Bertini replaces the parameters with random complex numbers and stores the values in the file start parameters Bertini solves the resulting polynomial system based on the other configuration settings When PARAMETERHOMOTOPY is set to 2 Bertini constructs a straight line parameter homotopy between the starting parameter values in the file start parameters and the target parameter values in the file final parameters The points in start provide the start points of the homotopy paths to track For example consider the parameterized polynomial f z p z p The input file to solv
23. when one extends precision in MPFR the added digits are chosen randomly Although this may cause concern in some contexts Bertini makes use of a refining function based on Newton s method to make certain the extended precision versions of all data types have adequate accuracy immediately following precision increases Note that this is not a concern with the numerical data in the input file Indeed integers in input are stored exactly and all floating point numbers are stored as rational numbers with denominators the appropriate factor of ten Then when straight line program evaluation begins these numbers are computed to the current working precision T he use of rational numbers to represent numerical data forces any digits added beyond the original precision of the input data to be set to zero working under the assumption that the user is providing exact or at least as exact as possible information 7 1 2 Linear algebra Although more sophisticated techniques could be employed e g Strassen like matrix multiplication formulas Bertini includes naive implementations of arithmetic and norms for matrices and vectors The infinity norm is used almost exclusively throughout Bertini Gaussian elimination with pivoting is used for matrix inversion and failure is declared in that subroutine if any pivot is smaller than some threshold that has been hardcoded in the source code as a formula based on precision As with the basic data types and most ot
24. 0 A Sommese J Verschelde and C Wampler Introduction to numerical algebraic geometry In Algorithms and Computation in Mathematics Volume 14 eds A Dickenstien and LZ Emiris pages 339 392 2005 31 A J Sommese and C W Wampler Numerical algebraic geometry In The mathematics of numerical analysis Park City UT 1995 volume 32 of Lectures in Appl Math pages 749 763 Amer Math Soc Providence RI 1996 32 A Sommese J Verschelde and C Wampler Solving polynomial systems equation by equation In IMA Volume 146 Algorithms in Algebraic Geometry eds A Dickenstein F Schreyer and A Sommese pages 133 152 2008 33 A Sommese and C Wampler The numerical solution of systems of polynomials arising in engineering and science World Scientific Publishing Co Pte Ltd Hackensack NJ 2005 34 G Stewart Matrix algorithms Vol I Basic decompositions Society for Industrial and Applied Mathematics Philadelphia PA 1998 35 H J Su J McCarthy M Sosonkina and L Watson Algorithm 857 POLSYS GLP A parallel general linear product homotopy code for solving polynomial systems of equations ACM Trans Math Software 32 4 561 579 2006 Software available at www vrac iastate edu haijunsu 36 L Trefethen and D Bau Numerical linear algebra Society for Industrial and Applied Math ematics Philadelphia PA 1997 37 T Turocy Towards a black box solver for finite games finding all Nash eq
25. 1 2 DEGREEBOUND is automatically computed when not using a user defined homotopy with a user provided bound taking precedence over the computed bound TARGETTOLMULTIPLIER Two endpoints will be considered equal if they differ by less than the final tolerance FINAL TOL times a factor named TARGETTOLMULTIPLIER AMPMAXPREC This is the maximum precision in bits allowed when using adaptive precision to avoid infinite loops CONDNUMTHRESHOLD For basic zero dimensional tracking this is the cutoff for determining singular versus non singular For regeneration and positive dimensional tracking singular versus non singular is based on the corank of the Jacobian rather than a fixed bound PRINTPATHMODULUS This is the frequency with which Bertini will print out path numbers while running It has no effect on the run The idea is that infrequent updates leaves the user wondering how the 57 run is progressing while frequent updates can be tedious Only path numbers divisible by PRINTPATHMODULUS will be printed unless it is set to 0 in which case path numbers are not printed RANDOMSEED If set to zero different random numbers will be chosen for each run Otherwise the random number generator will be seeded with RANDOMSEED allowing the user to repeat runs identically SINGVALZEROTOL A singular value will be considered zero if it is less than SINGVALZEROTOL in absolute value This effects the rank determination at the beginning o
26. 2 aunernnaroanenanro Cascade Summary i seseensaneseen NOTE nonsingular vs singular is based on rank deficiency and identical endpoints Please make sure that you have total 2 EHREETERANER HERERO NETRA RENO ERE ERRE EMER E RHEE HE dicente Witness Set Summary PYS www NOTE nonsingular vs singular is based on rank deficiency and identical endpoints leodim witness points nonsingular singular ta JOE HOHER E HOHER OCHO EHE UH E io Calculating traces for codimension 1 Calculating 0 of 2 Using monodromy to decompose codimension 1 Performing monodromy loops 2 points left to Performing monodromy loops 2 points left to Performing monodromy loops 2 points left to Performing monodromy loops 2 points left to Performing monodromy loops 2 points left to sss eerie Witness Set Decomposition esswesene dimension components classified unclassified s w99 9 9 Decomposition by Degree ereeeewas Dimension degree 2 1 component 1 classified component ANUROREMOMHNRO NOONE RURITOMERHEMOEMRTERMOLONRe ROO ESTEE jhauenstOsleipnir BertiniExamples Figure 5 2 Running Bertini 37 using input_sphere 5 4 2 Twisted cubic in P Figure 5 3 presents an input file named input_twisted_cubic that instructs Bertini to use dimension by dimension slicing 31 for witness superset generation to compute the numerical irreducible decomposition of the t
27. Bertini User s Manual Dan Bates with contributions from Jon Hauenstein January 19 2012 Contents 1 Introduction to Bertini 11 What Bertini does less sss 1 2 Where Bertini may be found len 13 Who is developing Bertini rs 14 Howto usethisman al 5 224 Rkexx A Row kc DR XO R3 1 5 Acknowledgements 2 223 2 eo mm a ae eben 2 Getting started 21 Basics of a Bertini run 29 299 bs Ro IER EU EG E 2 1 1 How to provide input 2 1 2 How torun B r nr 2 4 32 mu ds ore Roe be ue EROR rar 2 2 Some Arst examples 5i2 sue a a REA eui vRG 2 2 1 Zero dimensional examples 44s 2 2 2 Positive dimensional examples 2 2 3 User defined homotopies ooa 2 24 Parameter homotopies oaoa aa 3 Syntax for input files 3 1 The input fle zari Rx a acu Pedes dx Pius Rea 3 2 Common syntax errors in the input fle o 3 9 The start fle psa doon 2 ae a ow ooo sx Row Eos EIE TR doce Rs 4 Details and examples regarding zero dimensional runs 4 1 How Bertini finds these solutions nn ATA The basic Tdea 4 2 eom n re ee ea WE ld aS 4 1 2 Endpoint sharpening for zero dimensional runs 4 1 3 Sharpen during tracking 2n 4 1 4 Sharpen after tracking len 41 5 Defl tion is rei e dann un a ee e f 11 13 15 17 17 20 21 AAG Regeneration 6 49 Ar Een A AA SG ee
28. a system of polynomials and a witness point on a reduced component of the new system that corresponds to the given witness point Bertini as of December 2008 can also generate witness supersets via a dimension by dimension algorithm or regeneration Please refer to WITNESSGENTYPE in the appendix for details As of May 2011 the configuration setting WITNESSSUPERSETONLY allows the user to stop the computation after the witness superset generation Please refer to WITNESSSUPERSETONLY in the appendix for details 34 To break the pure dimensional witness sets into components Bertini employs a combination of monodromy and a test known as the linear trace test Details may be found in 33 Once the breakup is complete all data is reported to the user and also stored in a special file named witness data Component sampling and membership testing then just involve reading in this file and moving the linears around either to sample a given component or to test whether the points given in member points lie on an irreducible component of the algebraic set 5 2 Output on the screen There are two main parts of the output to the screen provided by Bertini in this case One is a table giving the number of components the total degree the number of unclassified singular solutions the number of paths and the number of failed paths in each dimension of the cascade The other is a table of components listed by dimension and by degree As with the zero
29. articular 0 means totally extrinsic and 1 means totally intrinsic REGENSTARTLEVEL If you are restarting a regeneration run use this setting to start at a previously completed regeneration level REGENREMOVEINF Set to 1 to remove infinite endpoints 0 otherwise SLICETOLBEFOREEG Similar to TRACKTOLBEFOREEG but for moving slices during regeneration SLICETOLDURINGEG Similar to TRACKTOLDURINGEG but for moving slices during regeneration SLICEFINALTOL Similar to FINALTOL but for moving slices during regeneration MINCYCLETRACKBACK Minimum cycle number to utilize the back tracking method of 5 61
30. aths to track Tracking path O of 4 Sorting 2 of 3 4 paths to sort Sorting O of 4 Finding witness superset for codimension 3 of 3 8 paths to track Tracking path O of amp Sorting codimension 3 of 3 8 paths to sort Sorting O of 8 5 5 Dimension by Dimension Summary NOTE nonsingular vs singular is based on rank deficiency and identical endpoints codimj paths witness superset nonsingular singular nonsolutions inf endpoints other bad endpoints a 2 0 o o 2 o o au I 3 13 FA qe AE o o ls A 8 o 13 AS 0o 0 total 14 Removing junk points from codimension 3 5 endpoints to check Checking O of 5 i t iiiit tef itt Witness Set Summary 9 5 e9 ex 4 NOTE nonsingular vs singular is based om rank deficiency and identical endpoints eodim witness points nonsingular singular pz 4 3 3 o I3 0 o o En a ki t diete Calculating traces for oodimension 2 Calculating O of 3 Using monodromy to decompose codimension 2 Performing monodromy loops 3 points left to classify St s ssi Dados ORDINE loups H reine TETE OO Mleslio Performing monodromy loops 3 points left to classify Using combinatorial trace test to decompose codimension 2 t Witness Set Decomposition t dimension components classified unclassified Ir x pm 3 o 4 Decomposition by Degree t ex Dimension 1 1 classified component degree 3 1 compone
31. d singular endpoints found using a zero dimensional run as well Currently the only way to deflate isolated singular endpoints is to use a positive dimensional run to find the isolated singular endpoints 23 4 1 6 Regeneration Regeneration is an equation by equation method currently implemented for finding the non singular isolated solutions For more information on regeneration and equation by equation methods see 19 32 To utilize regeneration simply set USEREGENERATION to 1 One feature of the equation by equation methods is that previous results affect future results That is if an error is made at a stage it will influence the final results Because of this Bertini allows for the regeneration to be restarted from a previous run at any stage that was previously completed To accomplish this simply set REGENSTARTLEVEL to the place where you want to restart the regeneration from a previous run As of May 2011 the file regenSummary is printed after each stage of regeneration which provides information about the stages The format of the file is as follows The first line contains four integers namely the number of stages the number of functions the number of variables and the number of variable groups The next line is the integer which is the stage that just finished The file then contains a line for each of the stages If the stage has been completed the line contains eight integers namely the stage the number of functions s
32. daptive path tracking Please make sure that you have setup the following tolerances appropriately COEFFBOUND 1 000000000000e 03 DEGREEBOUND 5 000000000000e 00 AMPSAFETYDIGITS1 1 AMPSAFETYDIGITS2 1 AMPMAXPREC 1024 Tracking path 0 of 4 Finite Solution Summary NOTE nonsingular vs singular is based on condition number and identical endpoints Number of real solns Number of non real solns Total Non singular 2 0 2 Singular 0 0 EX Total 2 0 Da Finite Multiplicity Summary Multiplicity Number of real soins Number of non real soins The following files may be of interest to you main data A human readable version of the solutions main output file raw solutions A list of the solutions that can be used for reading into a program raw data Similar to the previous but with the points in Bertini s homogeneous coordinates along with more information about the solutions real finite solutions A list of all real finite solutions finite solutions A list of all finite solutions nonsingular solutions A list of all nonsingular solutions singular solutions A list of all singular solutions Paths Tracked 4 Truncated infinite paths 2 try adjusting SECURITYMAXNORM or set SECURITYLEVEL to 1 in the input file Please see failed paths for more information about these paths jhauenst sleipnir BertiniExamples B Figure 4 7 Running Bertini using input extended1 28 tolerances all along
33. e f x p 0 for a random value of p is as follows CONFIG PARAMETERHOMOTOPY 1 END INPUT variable group x function f parameter p f x 2 p END We now rename the file nonsingular solutions as start replace the line PARAMETERHOMOTOPY 1 with PARAMETERHOMOTOPY 2 in the input file and create the final parameters file as follows 1 1 2 The first line indicates that there is one parameter Then the parameter values are provided on separate lines by listing the real part and imaginary part Running Bertini solves z 1 24 1 0 using a straight line parameter homotopy Changing the final parameters file to 15 0 0 and running Bertini solves z 0 16 Chapter 3 Syntax for input files Syntax errors might be one of the most annoying parts of using any software Care has been taken to provide some syntax checking in Bertini although the error message produced upon encountering a syntax error may be more general than hoped for by the user Fortunately the only input file with any sophisticated structure or rules is the input file which is described in the next section 83 2 might be useful if a syntax error message is reported Finally 83 3 covers the simple structure of the start and member points files Output files are described in Chapters 4 and 5 3 1 The input file As described in 82 2 1 the input file has two parts grouped as follows where the symbol is the comment character in the inp
34. e created in the directory from which the call is made i e the current working directory Of course the user must have write privileges in that directory Please note that when using Cygwin the executable may not actually be named bertini but rather bertini exe Suppose the directory in which the executable resides has the path bertini_dir the in put file of interest named my input is in input_files and the current directory is elsewhere Then the command bertini_dir bertini input files my input will run the polynomial system of interest and create all output files in elsewhere 2 2 Some first examples 2 2 1 Zero dimensional examples Let us first revisit the example function f variable group x fmx2 o145 END from 82 1 1 Note that the keyword for the variables in the above example is variable group and not just variable This is how Bertini knows to homogenize the input system but provide output in complex space rather than projective space Alternatively one may choose to provide homogenized input in which case the output is also given in projective space although no points at infinity are identified since there is no canonical sense of infinity The keyword for variables in that case is hom variable group The input file for a 1 homogenized form of z 1 where 1 indicates that we are working in a single projective space rather than a product is then function f hom variable gro
35. e endgame and correct to 11 digits when running the endgame and that you want the endgame to compute approximations of each solution until successive approximations agree to at least 14 digits Then the input file would be CONFIG TRACKTOLBEFOREEG 1e 8 TRACKTOLDURINGEG 1e 11 FINALTOL 1e 14 END INPUT variable group z1 variable group z2 function f1 f2 f1 29 16 z1 3 2 z1 z2 f2 z2 z172 END Suppose you then decide that you want even more accuracy 20 digits By default Bertini uses adaptive precision 6 7 and will increase the precision to allow successive approximations to agree to at least 20 digits Note that other configurations should be changed as well in order to maximize either the speed or the security of your run Please refer to the description of MPTYPE given in Appendix for details 10 Bertini allows for computations to be completed using fixed precision If you want com putations performed using double precision 16 digits or 52 bits of precision you could add the line MPTYPE 0 anywhere in the CONFIG section of the input file Bertini also allows for any precision which has the number of bits being a multiply of 32 and is between 64 and 3328 To use 128 bit precision 38 digits you could add the lines MPTYPE 1 PRECISION 128 anywhere in the CONFIG section of the input file Bertini also allows for the use of subfunctions when defining functions This capability was
36. e found in the examples later in this chapter and the exact syntax is given in the next chapter It should be noted though that the input file need not be named input any legal file name will suffice The name input is used here for convenience In almost all situations Bertini will automatically create a homotopy including a start sys tem and solve the start system to find the start points at the beginning of each path The only exceptional case is when the user provides his or her own homotopy It is impossible in that case for Bertini to find the solutions of the start system without homotoping to it from yet another system Thus when using a user defined homotopy the user must provide a set of starting points that are solutions to the start system in a file named start the syntax of which is given in 3 3 It should be noted though that as opposed to the input file the start file must actually be named start The member_points file is needed in addition to the input file in the case of component mem bership testing This file contains a list of all points to be tested as to which solution components the points lie is identical in structure to the start file and must be named member_points One more input file of interest that is automatically generated as output during a run is the witness_data file This is a terse form of the witness data of an algebraic set i e the witness points and the linear slices Although this file cou
37. e used to sharpen and display the non singular endpoints to any number of digits That is the paths are tracked based on the tracking tolerances and then all the non singular endpoints are sharpened to the requested number of digits To utilize the sharpening module during tracking simply set SHARPENDIGITS to the desired number of digits 4 1 4 Sharpen after tracking After zero dimensional tracking has completed the sharpening module uses the raw data file to reprocess the endpoints and sharpen the non singular ones to any number of digits When the user utilizes sharpening in this way a menu will be displayed that allows the user to either sharpen every endpoint sharpen only the endpoints whose corresponding path numbers are listed in a file or allows the user to manually enter the path numbers of the endpoints to sharpen When using a file of path numbers the path numbers can only be separated with white space If a non number is reached Bertini immediately stops reading in path numbers and attempts to sharpen the ones that were already read For advanced users that use redirected input please note that the input commands need to be put onto separate lines since buffer clearing is used for scanf stability To utilize the sharpening module after tracking simply set SHARPENONLY to 1 and follow the menu 4 1 5 Deflation Deflation has been implemented in Bertini for the positive dimensional case and will soon be avail able for the isolate
38. ecision 44 version must be able to recognize when higher precision is needed using for example the criteria developed in 6 7 Once the regular precision version of the function at hand runs out of precision it returns a special error code to the control function The control function then uses special MPFR functions for copying regular precision data into MPFR data types to convert all necessary data from regular precision to the minimum level 64 bits of multiple precision After the conversion of all data to multiple precision types the control function calls the multiple precision version of the function That version of the function may then use the criteria to judge whether higher precision is needed and if so it can handle the precision increase itself without reporting back to the control function There is at least one major drawback to this way of implementing the functions of numerical algebraic geometry Every function comes in several versions For example for the power series endgame there is currently a fixed regular precision version a fixed multiple precision version a version for regular precision that knows how to watch for precision problems an analogous version for multiple precision and a control function sitting over the adaptive precision versions Whenever a bug is found or an extension is made the developer must be very careful to correct or extend every version of the function It should also be noted that
39. ecutive successful predictor corrector steps taken before attempting to increase the steplength MAXNEWTONITS This is the maximum number of corrector steps allowed after any given predictor step Ex perience indicates that this should be set no higher than 3 and with 2 being more effective at avoiding pathcrossing 59 MAXSTEPSIZE This is the largest steplength that Bertini will allow during the run as well as the starting steplength NBHDRADIUS Tracking will halt if the value of the pathvariable comes within NBHDRADIUS of the target value of the pathvariable ENDGAMEBDRY This is the value of the pathvariable at which the tracking method being employed switches from basic path tracking to the indicated endgame TARGETTIME This is the desired value of the pathvariable almost always 0 MAXNUMBERSTEPS This is the most steps that may be taken during the endgame on any one path to avoid wasting computational power on paths that are not converging well SAMPLEFACTOR This is the factor used to determine the geometrically spaced sample points for all of the endgames For example if ENDGAMEBDRY is 0 1 and SAMPLEFACTOR is 0 5 the sample points will be 0 1 0 05 0 025 etc MAXCYCLENUM In the power series endgame this provides a basic idea of what cycle numbers to test AMPSAFETYDIGITS1 The first of the two safety digit settings for adaptive precision Bertini will go to higher preci sion the higher that these are set C
40. edu sommese bertini There you will find the current version of Bertini information regarding bug fixes and revisions a form for reporting bugs and providing feedback example input files and license information Scripts written in Maple Matlab and or C for creating input files and interpreting output files are or will be posted on the website of Daniel Bates Errors and suggested changes in this manual may also be reported on the Bertini website via the feedback form The developers of Bertini are aware of the many good reasons for going open source but only the executable is presently available to the public To download a copy of Bertini just go to the website find the version of the executable that best matches your computer and click the link to download it This will get you a tar gz file of a directory To unpack the directory just type tar zxvf FILE NAME at the command line in the directory in which you saved the file where FILE NAME is the name of the file you downloaded e g BertiniLinux32 beta tar gz The directory that is created will contain a copy of this user s manual the executable a directory containing several examples to get you started and a README file explaining the examples Cygwin users should already have GMP and MPFR installed If they are not there are directions for adding modules to Cygwin on the Cygwin webpage It is quite easy Other Linux users do not need to worry about installing GMP MPFR or any ot
41. ere declared e VARIABLES In all cases except user defined homotopies the variables are listed by group with one group per line with each line beginning with either the keyword variable group for complex variable groups against which the polynomials have not been homogenized or the keyword hom variable group for variable groups against which the polynomials have been homog enized Note that the user must choose one type of variable group for the entire input file i e mixing of variable groups is not allowed in this release of Bertini Also only one variable group may be used for a positive dimensional run For example if there are two nonhomogenized variable groups the appropriate syntax would be variable group z1 z2 variable group z3 In the case of user defined homotopies the keyword is variable and all variables should be defined in the same line e PATHVARIABLES The pathvariable often denoted by the letter t is the independent variable that is controlled during homotopy continuation In Bertini the homotopy always moves from the start system at t 1 to the target system at t 0 A pathvariable must be declared in the input file ONLY if the user is specifying the entire homotopy i e USERHOMOTOPY is set to 1 In that case it is also necessary to declare at least one parameter as described in the next item The keyword for pathvariables is pathvariable e PARAMETERS Homotopy continuation relies o
42. ersions of Bertini were written using MPI and compiled using the MPICH and MPICH 2 implementations of MPI 1 1 and MPI 2 0 respectively For more details on MPICH and MPICH2 see http www unix mcs anl gov mpi The general syntax for running Bertini in parallel is mpirun np NUM PROCESSES bertini FILE NAME where NUM PROCESSES is the number of processes to use and FILE NAME is the name of the input file If NUM PROCESSES is 1 Bertini runs in serial mode Otherwise Bertini uses 1 process as the head master process and the other processes as workers 43 Chapter 7 A bit about how Bertini works 7 1 Data types and linear algebra Of the available computational mathematics software packages e g Maple and Matlab and li braries e g Linpack and LAPack of which we are aware only Maple supports multiprecision floating point arithmetic However to maximize control over various other aspects of the software it was decided to write Bertini without relying on such existing software platforms As a result it was necessary to build basic data types and linear algebra subroutines which are the topic of this section 7 1 1 Basic data types The GMP based library called MPFR provides data types for arbitrary precision floating point numbers as well as basic declaration assignment and arithmetic functions The basic floating point type in MPFR is the mpf_t data type which contains a field for the precision of the instance and a seve
43. es sampling and 3 specifies membership testing 11 e The user may specify only one variable group i e the system may be defined over either a single complex space or a single projective space no products Starting with Bertini v1 0 the positive dimensional algorithms have been implemented in both fixed precision and adaptive multiple precision For example a witness set for the affine twisted cubic curve could be computed by Bertini using the following input file CONFIG TRACKTYPE 1 END INPUT variable group X y 2 function f1 f2 f1 x 2 y f2 x 3 z END Using this input file Bertini will produce three points on the affine twisted cubic curve Suppose you want a few more points say 200 Then simply change the TRACKTYPE line to TRACKTYPE 2 Upon calling Bertini assuming the witness data file from the previous run is still intact a catalog of all components in all dimensions will appear on the screen Bertini will prompt you to enter a codimension a component number and a number of points to which you would respond 2 1 and 200 respectively The final prompt asks where to print the sample points enter 0 to print the points to a file called sample points and enter 1 to print the points to the screen Bertini would then simply move the slices around and report all 200 desired points Finally suppose you have a point in C that you think might be on the twisted cubic curve You could place tha
44. et Starting with version 1 3 Bertini provides the functionality to print the linear polynomials and witness point set of a witness set for either an irreducible component or a pure dimensional com ponent Bertini reads in information about the witness set corresponding to the target system in the input file from the witness data file It then queries the user about what to print and where to print the data 5 7 Witness sets of projections Starting with version 1 3 Bertini provides the functionality to compute a witness set for the pro jection of an irreducible component 18 Bertini reads in information about the witness set cor responding to the target system in the input file from the witness data file The projection is read in the from the projection file which is described as a list of integers If the i variable is in the image of the projection then the i integer in the list is 1 otherwise it is 0 For example the projection file for the projection r 11 12 13 14 11 14 consists of the following line 1001 Bertini then queries the user about which irreducible component to project It verifies the compo nent is generically nonsingular and computes the witness set of the projection which is printed to the file witness data projection 42 Chapter 6 Comments about running Bertini in parallel Starting with the December 16 2008 release of Bertini 1 1 parallel versions of Bertini are avail able The parallel v
45. f each zero and positive dimensional run USERHOMOTOPY Set to 0 to use automatic homotopies 1 to use user defined homotopies on an affine space and 2 to use user defined homotopies on a multi homogeneous projective space PARAMETERHOMOTOPY Set to O to use automatic homotopies 1 to replace parameters with random constant values and 2 to use a straight line parameter homotopy SHARPENDIGITS When using the zero dimensional solver setting this to a positive integer will instruct Bertini to sharpen the non singular solutions to that many decimal digits When using component sampling setting this to a positive integer will instruct Bertini to sharpen the sample points to that many decimal digits SHARPENONLY Set to 0 to use regular tracking methods 1 to start the sharpening module The sharpening module uses either the witness data from a positive dimensional solve or the raw data from a zero dimensional solve to sharpen solutions to any number of digits WITNESSGENTYPE Set to 0 to use the standard cascade algorithm for witness superset generation 1 to have Bertini handle each dimension separately and 2 to have Bertini use the regenerative cascade WITNESSSUPERSERONLY Set to 1 to compute only a witness superset and set to 0 to additionally perform junk removal and the irreducible decomposition JUNKREMOVALTEST Set to 0 to use a membership test for junk removal and set to 1 to use the local dimension test of 3
46. g this family one chooses a path from the start system to the target system constructs a homotopy between the two and tracks the solution paths using predictor corrector methods e g Euler s method and Newton s method employing adaptive steplength This is a simplification of the true situation of course For complete details please refer to the references of 1 1 As described above Bertini will automatically m homogenize the target system if necessary and always performs automatic differentiation If m 1 Bertini also squares the system up to the number of variables in the case of zero dimensional runs Bertini also adds m random patch equations to the system so as to work on patches in each projective space Once all of this is done if necessary Bertini creates an m homogeneous start system solves it to obtain the start points except in the case of a user defined homotopy and attaches the start and target systems into a homotopy using the gamma trick which makes the appearance of singularities away from t 0 a probability zero occurrence At that point Bertini carries out path tracking on each path independently and reports the findings to the user as described in the next two sections Please be aware that some paths could fail during tracking possibly resulting in an incomplete set of solutions For example using fixed 128 bit precision but asking for 200 digits of accuracy will of course result in path failure Not al
47. generic point so that the system can be squared to the appropriate size potentially decreasing both the number of variables and the number of polynomials and so that the cascade will only run through dimensions that might have solutions The cascade algorithm produces a pure dimensional witness superset in each dimension of interest meaning it does not immediately find the desired witness sets but rather sets that may contain junk from higher dimensional components This first step of positive dimensional solving involves slicing the algebraic set of interest by generic hyperplane sections in the form of linear equations with randomly chosen coefficients As mentioned in 82 2 2 as of late December 2008 users may also ask Bertini to handle each dimension independently i e not in a cascade or use regeneration via the configuration setting WITNESSGENTYPE After witness superset generation is complete running from codimension 1 to the codimension determined by the rank test the junk is removed from each pure dimensional witness point superset either by using a membership test or by using the local dimension test 3 The configuration JUNKREMOVALTEST allows the user to select between the two junk removal algorithms Once the junk is removed Bertini has a witness point set for each dimension of interest Using the witness set the singular witness points are deflated That is for each witness point in the witness set Bertini creates
48. he highest level of importance are listed in Table A 1 while those that are also available but may not be of interest to the typical user are given in Table A 2 Additionally the description of each configuration is listed in the same order that they appear in the tables 53 Table A 1 Configuration settings of particular interest NAME ACCEPTABLE VALUES DEFAULT VALUE TRACKTYPE 0 1 2 3 4 5 0 MPTYPE 0 1 2 0 PRECISION gt 64 and 3328 96 ODEPREDICTOR 0 3 4 5 6 7 8 5 TRACKTOLBEFOREEG 20 1e 5 TRACKTOLDURINGEG 20 1e 6 FINALTOL 20 le 11 MAXNORM gt 0 le5 MINSTEPSIZEBEFOREEG gt 0 and lt MAXSTEPSIZE 1e 14 fixed precision MINSTEPSIZEDURINGEG gt 0 and lt MAXSTEPSIZE 1e 15 fixed precision IMAGTHRESHOLD 20 1e 8 COEFFBOUND 20 1000 DEGREEBOUND 20 5 TARGETTOLMULTIPLIER 21 10 AMPMAXPREC gt 64 and 3328 1024 CONDNUMTHRESHOLD 20 le8 PRINTPATHMODULUS gt 0 20 RANDOMSEED gt 0 0 SINGVALZEROTOL gt 0 1e 12 USERHOMOTOPY 0 1 2 0 PARAMETERHOMOTOPY 0 1 2 0 SHARPENDIGITS 20 0 SHARPENONLY 0 1 0 WITNESSGENTYPE 0 1 2 0 WITNESSSUPERSETONLY 0 1 0 JUNKREMOVALTEST 0 1 1 REDUCEDONLY 0 1 0 MAXCODIMENSION 20 0 ENDGAMENUM 1 2 3 1 NUMSAMPLEPOINTS 22 and lt 32 2 USEREGENERATION 0 1 0 SECURITYLEVEL 0 1 0 SECURITYMAXNORM 20 le4 54 Table A 2 Other configuration settings
49. her packages as we were able to make the links to the appropriate libraries static in that case There is a version of Bertini that works with the latest version of OS X on Macs Bertini has also been used on Windows machines without Cygwin by including appropriate dll s in the Jan Verschelde contains a lengthy list of polynomial systems coming from applications on his website including references to their original appearance in the literature directory containing the executable file However such usage has known problems and has not yet been fully tested Thus Bertini is only supported on Windows machines if Cygwin is used If no version of Bertini works on your machine please contact the development team as described on the website It might be possible to produce versions that can be used on other operating systems but we can make no such guarantees Details about how to use Bertini once it is downloaded are given in 82 1 2 1 9 Who is developing Bertini Bertini is under ongoing development by the development team which consists of Daniel J Bates Colorado State University Jonathan D Hauenstein Texas A amp M University Andrew J Sommese University of Notre Dame and Charles W Wampler II General Motors Research and Develop ment 1 4 How to use this manual As mentioned above this manual is designed to provide users with the knowledge necessary to use Bertini For background on numerical algebraic geometry please
50. her sorts of subroutines there are two copies of each linear algebraic operation one in regular precision and one in arbitrary precision One of the endgames the power series endgame makes use of interpolation Basic Hermite interpolation has been implemented since derivatives are readily available all along the path These implementations of interpolation allow for an arbitrary number of data points The most sophisticated linear algebra routine in Bertini is the computation of the SVD of a matrix The singular value decomposition of a matrix yields as a byproduct the condition number of the matrix which is just the ratio of the largest and the smallest nonzero interpreted numerically of course singular values An implementation of the numerical computation of the singular value decomposition of a matrix is included in Bertini 36 is another excellent resource regarding the 45 singular value decomposition 7 2 Preprocessing of input files in Bertini Before any actual tracking is carried out Bertini passes through a preprocessing stage It is during this part of the run that Bertini read in all of the data contained within the various input files and converts the polynomials of the input file to straight line format All such information is currently written to several files at the end of the preprocessing stage The main part of Bertini the tracker then reads in these files at the beginning of the tracking phase The fundamental
51. ia Sebastopol CA 1992 B Dayton Z Zeng Computing the multiplicity structure in solving polynomial systems In ISSAC 2005 Proc pages 116 123 2005 49 13 T Gao and T Y Li HOMAPS Software available at www csulb edu tgao 14 T Gao T Y Li and M Wu Algorithm 846 A software package for mixed volume computation ACM Trans Math Software 31 4 555 560 2005 Software avialable at www csulb edu tgao 15 A Griewank Evaluating derivatives principles and techniques of algorithmic differentiation volume 19 of Frontiers in Applied Mathematics Society for Industrial and Applied Mathematics SIAM Philadelphia PA 2000 16 A Griewank and M Osborne Analysis of Newton s method at irregular singularities STAM J Numer Anal 20 4 747 773 1983 17 T Gunji S Kim M Kojima A Takeda K Fujisawa and T Mizutani PHoM a polyhedral homotopy continuation method for polynomial systems Computing 73 1 55 77 2004 Software available at www is titech ac jp kojima 18 J Hauenstein and A Sommese Witness sets of projections Appl Math Comput 217 7 3349 3354 2010 19 J Hauenstein A Sommese and C Wampler Regeneration homotopies for solving systems of polynomials Math Comp 80 345 377 2011 20 J Hauenstein A Sommese and C Wampler Regenerative cascade homotopies for solving polynomial systems Appl Math Comput 218 4 1240 1246 2011 21 A Leykin J Verschelde and A
52. l causes of path failure are so clear but there is often a set of tolerances that will allow convergence of all paths The use of adaptive precision MPTYPE 2 plus some other settings please see the appendix will often help with convergence Bertini reports to the screen the number of path failures and there is a file named failed paths describing each of the failures 22 4 1 2 Endpoint sharpening for zero dimensional runs The sharpening module was designed to sharpen refine endpoints and display them to any number of digits The sharpening module can be utilized either during a tracking run or afterwards Since zero dimensional runs can not currently determine if a singular solution is isolated the sharpening module for zero dimensional runs can only sharpen non singular solutions When using fixed precision endpoints can only be sharpened to the number of digits of accuracy based on the precision Using adaptive precision allows Bertini to automatically adjust the precision so that endpoints can be successfully sharpened to any desired number of digits After sharpening the endpoint is displayed using the smallest precision that is large enough to handle the number of digits requested When the sharpening module is utilized all endpoints that fail to sharpen to the requested number of digits will be marked with a amp in main data 4 1 3 Sharpen during tracking During zero dimensional tracking the sharpening module can b
53. ld technically be produced manually the best way to create this file is by executing a positive dimensional Bertini run in which case the witness_data file is produced automatically Since the syntax of the witness_data file is so complicated and has so many cases the exact syntax will not be provided in this version of the manual As with the start file the witness_data file must have exactly that name and this file must be specified in order to use either component sampling or component membership testing 2 1 2 How to run Bertini Once all appropriate input files have been created typically just input running Bertini is sim ple From the command line in the directory containing the executable just type bertini FILE_NAME where FILE_NAME is either the name of a file in the same directory or the path to a file in another directory including the file name itself If no file is specified Bertini will use as input the file named input in the current working directory If no file is specified and input does not exist Bertini will exit after printing an error message to the screen One can specify the path to the executable as well so Bertini can be run in any directory to which the user has access Even better by placing the executable in a bin directory and perhaps logging out and then back into your account Bertini can be called from anywhere in the file tree just by typing bertini without a path In any case all output files ar
54. look for a link to talk materials then the 2006 Workshop on Software for Algebraic Geometry Please note that Chapter 7 is not maintained as frequently as the rest of this manual so a fair bit of the information in that chapter is actually out of date 1 5 Acknowledgements The development of Bertini has been supported generously by a number of sources including the Duncan Chair at the University of Notre Dame the University of Notre Dame National Science Foundation grants 0410047 and 0105653 General Motors the Institute for Mathematics and its Applications the Arthur J Schmitt Foundation the University of Notre Dame Center for Applied Mathematics the Fields Institute and Institut Mittag Leffler Chapter 2 Getting started 2 1 Basics of a Bertini run Bertini is mainly a text based program meaning that most of the input and most of the output may be found in files After providing the input files described in the next subsection and in detail in the next chapter the user calls Bertini as described in 2 1 2 and can find the output on the screen and in files as described in 84 2 and 84 3 for zero dimensional runs and in 85 2 and 85 3 for positive dimensional runs Special techniques such as user defined homotopies component sampling and component membership testing endpoint sharpening and deflation require a little extra work so they are treated separately 2 1 1 How to provide input For most types of runs Berti
55. m in Bertini For a good reference about automatic differentiation please refer to 15 After producing the straight line program for a polynomial system one may read through the set of instructions writing down appropriate derivative evaluation instructions for each evaluation instruction For example given an instruction x where x and y are memory locations one could produce a set of three instructions for evaluating the derivative of this instruction In particular the first instruction would be to multiply the derivative of x which should already have a memory location set aside by y the next would multiply x by the derivative of y and the third would add these two storing the result in the appropriate memory location Naturally there is a great deal of bookkeeping involved but that is just a matter of careful implementation 7 2 2 Implementation details for straight line programs Before Bertini performs path tracking techniques or any other methods it calls a parser to convert the Maple style human readable input file into straight line program This preprocessing stage also includes automatic m homogenization and automatic differentiation as described in the previous section Details of how to use lex and yacc or the variants flex and bison to parse polynomial sys tems into straight line programs and details about the actual straight line program data structure in Bertini are given in this section To learn about the use of lex
56. n a pair of parentheses Bertini does not only convert from Maple style input to straight line programs Consider the example of f x y x z given above By moving through the yace rules Bertini would first recognize z y Since x and y are variables that were presumably already declared before this statement they have already been assigned addresses in an evaluation array of the complex 47 numbers type A few constants like 0 1 J 1 and Pi 3 1415926 are so important that they are given the first few addresses in this array after which all other names and numbers that appear in the input file are given addresses Assuming f x y and z were already declared before this assignment statement the evaluation array would look like indx 0 1 2 3 4 5 6 7 name I Pi O 1 f x y z The first instruction is then t x y written t x y for convenience This is then converted into address notation as 8 5 6 i e the sum of the values in memory locations 5 and 6 is stored in memory location 8 When the 2 is encountered it is also assigned an address in the evaluation array In the end the array is as follows where IR means intermediate result index 0 1 2 3 4 5 6 7 8 9 10 11 name I PijO 1 f x y z IR 2 IR IR To save work all operations are assigned integer codes in particular their ASCII codes
57. n the ability to cast a given polynomial system as a member of a parameterized family of polynomial systems Such parameterized families especially those which occur naturally constitute one of the powerful advantages numerical methods in algebraic geometry have over symbolic methods Sometimes there is only one parameter involved but sometimes there are several Please note though that user defined parameters 18 should be used only in the case of user defined homotopies Regardless of the number of parameters each parameter depends directly upon the pathvariable As a result the user must both declare each parameter and assign to it an expression depending only upon the pathvariable to it Here is an example parameter pl p2 pi t 2 p2 t 3 For technical reasons in the case of a user provided homotopy Bertini always assumes that there is at least one parameter even if there is no apparent need for one In the case that the user wishes to build a homotopy depending only upon the pathvariable it is necessary to declare a parameter set it to the pathvariable in the assignments section and then to use only that parameter and NOT the pathvariable in the functions Here is an example pathvariable t parameter s s t No parameters should appear in the input file unless the homotopy is defined by the user and the pathvariable should never appear explicitly in any homotopy function CONSTANTS Bertini will accept
58. ni needs only one file the input file The input file consists of an optional list of configurations e g the desired accuracy of the solutions declarations for almost all names used in the definition of the polynomials e g all variables and the target polynomial system itself For example the following simple input file is appropriate for finding the isolated complex solutions of z 1 with no special configurations function f variable group x f x 2 1 END Note that each line must end with a semicolon and that the entire file is terminated with the keyword END All white space spaces tabs and blank lines is ignored by Bertini Since no configurations are listed all default settings for the user changeable tolerances of Appendix A will be used Suppose though that you would like the endgame to compute approximations of each solution until successive approximations agree to 8 digits rather than the default Then the input file would have the form CONFIG FINALTOL 1e 8 END INPUT function f variable group x f x 2 L END In this case the beginning of the input section was specified by including the keyword INPUT just before the declarations This was necessary because of the inclusion of the configuration section at the top of the file starting with the keyword CONFIG and ending with END The configurations are just listed one per line between those keywords More details about the input file can b
59. nt ee jhauenstOsleipnir BertiniExamples S B Figure 5 4 Running Bertini using input twisted cubic 39 Ea jhauenst Eile Edit View Terminal Tabs Help Figure 5 5 input Griewank Osborne jhauenst sleipnir BertiniExamples Edit View Terminal Tabs Help Figure 5 6 main_data file for input_Griewank_Osborne 40 WIDER _jhauenst sleipnir BertiniExamples _ TA gt Eile Edit View Terminal Tabs Help jhauenst sleipnir BertiniExamples bertini input Griewank Osborne NOTE You have requested to use adaptive path tracking Please make sure that you have setup the following tolerances appropriately COEFFBOUND 1 000000000000e 03 DEGREEBOUND 5 000000000000e 00 AMPSAFETYDIGITS1 1 AMPSAFETYDIGITS2 1 AMPMAXPREC 1024 Finding witness superset for codimension 1 of 2 6 paths to track Tracking path 0 of 6 Sorting codimension 1 of 2 6 paths to sort Sorting 0 of 6 Finding witness superset for codimension 2 of 2 3 paths to track Tracking path 0 of 3 Sorting codimension 2 of 2 3 paths to sort Sorting 0 of 3 diio Cascade Summary titten NOTE nonsingular vs singular is based on rank deficiency and identical endpoints codim paths witness superset nonsingular singular nonsolutions inf endpoints other endpoints bad endpoints lus ow 0 0 0 3 3 0 0 e 1 3 3 0 3 o0 0 Lo total 9 MAA dno eee Witness Set Summary Y rn NOTE nonsingular vs
60. olved at this stage the number of paths the number of singular endpoints the number of nonsingular endpoints the number of infinite endpoints the number of endpoints which lie on a higher dimensional component and the number of bad paths tracked If the stage has not been completed the line contains three integers namely the stage the number of function solved at this stage and an integer which describes if intrinsic or extrinsic slicing will be used Please see the appendix for other regeneration specific settings 4 2 Output on the screen Bertini will output to the screen one or more tables classifying the solutions that it found In particular it will provide the number of real solutions the number of nonsingular solutions and so on In the case that the user provides a nonhomogenized system Bertini will also classify the points as finite or infinite and provide the previously described data twice once for the finite solutions and once for the infinite solutions Since there is no obvious notion of infinity in the case of a homogenized target system Bertini will just treat all points as finite in this case The number of path crossings if there were any will also be reported to the screen There is also a table of the number of solutions of each multiplicity The classifications are based on the settings described in the appendix and may need adjusted based on your specific system Perhaps the most useful information reported to
61. ometry approach to nonlinear constrained optimal control Proceedings of the 2007 IEEE CDC Conference on Decision and Control D Bates J Hauenstein C Peterson and A Sommese A numerical local dimension test for points on the solution set of a system of polynomial equations SIAM J Numer Anal 47 5 3608 3623 2009 D J Bates J D Hauenstein and A J Sommese Efficient path tracking methods To appear in Numerical Algoritms D J Bates J D Hauenstein and A J Sommese A parallel endgame Preprint 2010 D Bates J Hauenstein A Sommese and C Wampler Adaptive multiprecision path tracking SIAM J Numer Anal 46 2 722 746 2008 D Bates J Hauenstein A Sommese and C Wampler Stepsize control for adaptive multi precision path tracking Contemp Math 496 21 31 2009 D Bates C Peterson and A Sommese A numerical symbolic algorithm for computing the multiplicity of a component of an algebraic set J Complexity 22 475 489 2006 D Bates C Peterson and A Sommese Applications of a numerical version of Terracini s Lemma for secants and joins In IMA Volume 146 Algorithms in Algebraic Geometry eds A Dickenstein F Schreyer and A Sommese pages 133 152 2008 D Bates C Peterson A Sommese and C Wampler Numerical computation of the genus of an irreducible curve within an algebraic set Preprint 2008 D Brown J Levine and T Mason lex amp yacc A Nutshell Handbook O Reilly Med
62. onversely setting these to be negative is not recommended but will likely make Bertini track the paths faster AMPSAFETYDIGITS2 See AMPSAFETYDIGITSI MAXNUMPTSFORTRACE Monodromy will be used to break pure dimensional witness sets into irreducible components until either the maximum number of monodromy loops see the next two settings is exceeded or the number of unclassified points drops below MAXNUMPTSFORTRACE Fither way the exhaustive trace test will then be called to finish the classification combinatorially MAXNUMMONLINEARS This is the maximum number of different linears to try during monodromy before giving up and going to the exhaustive trace test 60 MAXNUMBADLOOPSINMON This is the stopping criterion for using each monodromy linear In particular new loops will continue to be chosen using the same target linear until either all points are classified or at least enough are see MAXNUMPTSFORTRACE or there have been MAXNUM BADLOOPSINMON consecutive useless loops A loop is useless if it does not yield any new groupings among the points INTRINSICMULTIPLIER Regeneration and dimension by dimension slicing for numerical irreducible decomposition can use intrinsic slicing This setting determines when to switch from intrinsic slicing to extrinsic slicing For example a setting of 0 75 instructs Bertini to use intrinsic slicing when the ratio of variables using intrinsic versus extrinsic formulations is less than 0 75 In p
63. ral fields for the data itself Using MPFR bits may only be assigned in packets of 32 The use of MPFR data types and functions is very computationally expensive so it was necessary to have available in Bertini duplicate data types and functions One set of types and functions uses entirely basic C double data types while the other set of types and functions uses the MPFR types and functions Although this duality makes code writing and maintenance somewhat tedious it is a simple solution to the need for both types The most basic nontrivial data type in Bertini is the complex number which is a structure consisting of two of the basic floating point type double or mpf t named r and i for obvious reasons Vectors and the identical data type points and arrays are then built as structures consisting of an array of complex numbers and one or two integer fields containing the dimension s of the instance Many more advanced structures are included in Bertini Adaptive precision introduces a special problem obviously not present with fixed precision runs Bertini must somehow convert from regular precision types and functions to multiple precision versions The solution to this problem used in Bertini is to have both versions of any given function available and to build a control function sitting over these two functions When called the control function will begin by calling the regular precision version of the function The regular pr
64. rds variable_group and hom_variable_group It is also necessary to specify the name of the path variable i e the variable through which the homotopy moves and at least one parameter The path variable may not appear in the definition of the functions so if no parameter is actually desired it is necessary to declare one parameter and set it equal to the path variable Here is a simple input file to solve x by moving from x 1 via a linear homotopy CONFIG USERHOMOTOPY 1 END INPUT variable x function f pathvariable t parameter s constant gamma gamma 0 8 1 2 I s t f x72 1 gamma s x 2 1 s Note that only s appears not t END There are several things to note in this input file that have not come up previously First are the new keywords parameter and pathvariable Also this is the first time a comment has appeared in an input file in this manual Note that the 96 sign is the comment character for Bertini it causes Bertini to ignore the rest of that line until a newline character White space tabs and spaces is ignored in Bertini Finally recall that it is not sufficient to provide only an input file for a user defined homotopy The user must also provide the list of starting points in a file called start Here is the start file for tracking both of the homotopy paths for this example 2 1 0 0 0 13 1 0 0 0 The first line indicates that there are two paths to be followed Then
65. s a subfunction by including the statement i I e In scientific notation the base is represented by e e g 2 2e 4 Starting with Bertini v1 2 E is also acceptable e g 2 2E 4 e For multiplication is necessary concatenation is not enough e Exponentiation is designated by e All symbols except subfunctions must be declared e No symbol can be declared twice This error often occurs when copying and pasting in the creation of the input file e pathvariable and at least one parameter are needed for user defined homotopies Please refer to the previous section for details e So that you don t worry white space tabs spaces and new lines is ignored 3 3 The start file The structure of this file is very simple In fact it was described fully in 82 2 3 above so please refer to that section for the basic syntax and structure Although white space is ignored in the input file it is important not to add extra spaces and or lines to the start file The member points file uses the same syntax as the start file 21 Chapter 4 Details and examples regarding zero dimensional runs 4 1 How Bertini finds these solutions 4 1 1 The basic idea Bertini employs homotopy continuation to compute isolated solutions to polynomial systems The idea of this technique is to cast the target polynomial system in a parameterized family of systems one of which the start system has known or easily found solutions After choosin
66. solns Total Non singular 1 0 1 Total 1 0 H 3 The following files may be of interest to you main data A human readable version of the solutions main output file raw solutions A list of the solutions that can be used for reading into a program raw data Similar to the previous but with the points in Bertini s hcmogeneous coordinates along with more information about the solutions real finite solutions A list of all real finite solutions finite solutions A list of all finite solutions nonsingular solutions A list of all nonsingular solutions Summary for the last regeneration level Paths Tracked 8 Truncated infinite paths 4 try adjusting SECURITYMAXNORM or set SECURITYLEVEL to 1 in the input file Please see failed paths for more information about these paths jhauenstOsleipnir BertiniExamples Figure 4 13 Running Bertini using input regeneration 33 Chapter 5 Details about positive dimensional runs 5 1 How Bertini finds these solutions Bertini carries out many of the same operations in this case as it does in the case of zero dimensional tracking as described in 4 1 so users should read the previous chapter before proceeding Bertini by default also sets up the cascade homotopy see the references of 81 1 and uses a total degree start system at the top level to get the cascade going Before all of this though Bertini computes the rank of the target system via the SVD at a
67. t point into a file named member points with syntax identical to the start file described in 3 3 change TRACKTYPE to 3 and again ensure that the witness data file is intact Bertini would then perform the component membership test on that point and all points listed in the member points file and report which component the point appears to lie on up to the accuracy specified in FINALTOL A new development as of the December 16 2008 release of Bertini is that witness point superset generation may now be carried out in three different ways The default is the standard cascade algorithm as described in Chapter 5 The other options are to use dimension by dimension slicing with each dimension handled independently and regeneration The configuration setting WITNESSGENTYPE toggles between these options please see the appendix for details 12 2 2 3 User defined homotopies The user has the option of using Bertini to track a set of paths for a homotopy The user defines a square homotopy in the input file as well as provides a set of start points in the start file The important configuration keyword to do this is USERHOMOTOPY Starting with version 1 3 the user defined homotopy may either be tracked on an affine or multi homogeneous projective space For tracking on an affine space the variables are specified using the keyword variable For tracking on a multi homogeneous projective space the variables are specified using the keywo
68. the screen are a list of output files of interest and the number of paths that failed during the run 4 3 Output in files Depending on the case Bertini will provide a number of files T he main data file is of most interest to most users It contains information about the solutions in a format that is easily read by humans The file named raw data contains similar data but is better suited for manipulation by software 24 In particular the first two lines of raw data in order are the number of variables and the number 0 indicating the dimension and the last line is 1 to indicate the end of the file The interesting data lies between these lines and is broken into blocks with one block for each point Each block has the following structure solution number bits of precision for the endpoint the coordinates of the solution the norm of the function value at the endpoint an estimate of the condition number at the most recent step of the path the most recent Newton residual the most recent value of the path variable t the error between the most recent estimates at t 0 the value of the path variable when precision first increased the cycle number used for the most recent estimate success indicator 1 means successful otherwise indicates a convergence problem A number of other specialized files are produced in some cases The contents of these files should come as no surprise to the user given their names real sol
69. ts in the witness superset the number of singular points in the witness superset the number of nonsolutions the number of infinite endpoints and the number of bad paths tracked If the codimension has not been completed the line contains two integers namely the codimension and an integer which describes if intrinsic or extrinsic slicing will be used 5 4 Positive dimensional examples The following provides screenshots for using Bertini to compute the numerical irreducible decom position for a polynomial system 35 5 4 1 Basic example Figure 5 1 presents an input file named input sphere that instructs Bertini to use all default settings to compute the numerical irreducible decomposition of the sphere in C jhauenst sleipnir Bertiniexamples a Edit View Terminal Tabs Help Figure 5 1 input sphere By default Bertini automatically uses adaptive precision tracking 6 7 and computes the degree 2 surface in C as shown in Figure 5 2 36 Eile Edit View Terminal Tabs Help jhauenst sleipnir BertiniExamples bertini input sphere NOTE You have requested to use adaptive path tracking setup the following tolerances appropriately COEFFBOUND 1 000000000000e 03 DEGREEBOUND 5 000000000000e 00 AMPSAFETYDIGITS1 1 AMPSAFETYDIGITS2 1 AMPMAXPREC 1024 Finding witness superset for codimension 1 of 1 2 paths to track Tracking path 0 of 2 Sorting codimension 1 of 1 2 paths to sort Sorting 0 of
70. uilibria with Gambit and PHCpack To appear in IMA Volume on Software for Algebraic Geometry eds M Stillman N Takayama and J Verschelde 2008 38 J Verschelde Algorithm 795 PHCpack a general purpose solver for polynomial systems by homotopy continuation ACM Trans Math Software 25 2 251 276 1999 Software available at www math uic edu jan 39 J Verschelde and Y Wang Numerical homotopy algorithms for satellite trajectory control by pole placement In MTNS 2002 Proc CD 2002 40 J Verschelde and Y Wang Computing dynamic output feedback laws IEEE Trans Automatic Control 49 8 1393 1397 2004 41 C Wampler Numerical algebraic geometry and kinematics In SNC 20077 Proc 2007 42 C Wampler HomLab Homotopy continuation lab Software available at www nd edu cwamplel 51 43 J Wilkinson Rounding errors in algebraic processes Dover Publications Inc New York 1994 Reprint of the 1963 Prentice Hall original 44 Z Zeng Apa Tools A software toolbox for approximate polynomial algebra Software available at www neiu edu zzeng apatools htm 52 Appendix A Configurations A 1 Optional configurations Bertini is highly configurable by utilizing over 50 user changeable configurations which is beneficial for attacking a wide range of problems The list of possible configurations is presented below along with a brief description of each For convenience the configuration settings having t
71. up x y f x 2 y72 END This homogenized input also shows an advantage of using Bertini it can handle nonsquare systems i e systems for which the number of variables and the number of equations differ In fact before any tracking is carried out Bertini first computes the rank of the target system to check whether there could be any isolated solutions If so it squares the functions up to the number of variables which is reasonable by Bertini s Theorem If not Bertini immediately reports that there are no isolated solutions and exits in the case of zero dimensional runs Bertini can also handle systems defined over a product of complex or projective spaces In particular if there are m terms in the product the user must specify m variable groups in the form of m lines in the input file each designated by the appropriate keyword Starting with Bertini v1 2 projective and complex spaces can be mixed i e both hom variable group and variable group can be used in a single input file For projective spaces Bertini will automatically check the homogenization and in case of an error display an error message and quit Here is an example of an input file for a 2 homogenized target system adapted from 16 variable group z1 variable group z2 function f1 f2 fi 29 16 z1 3 2 z1 z2 f2 z2 z172 END Now suppose you want Bertini to follow the paths of this example very closely correct to 8 digits before th
72. use a subfunction simply choose a symbol assign the expression to the symbol and then use it in the functions There is no need to declare subfunctions and no way to do so anyway V x 2 1 0 f1 2 xV 2 4 0 e SIN COS PI AND EXP Starting with Bertini v1 2 the sine function sin cosine function cos and exponential function exp are built into Bertini Additionally Bertini uses Pi for the constant 7 To avoid confusion with scientific notation the constant e is not specifically built in Bertini but the user can define their own constant and set it equal to exp 1 as shown below constant EN Y Euler s number e EN exp 1 It is important to note that Bertini will return an error if the argument of sin cos or exp depends upon a variable when trying to solve a polynomial system There is no such restriction for user provided homotopies 3 2 Common syntax errors in the input file Common complaints about Bertini are that a the parser that reads in the input is very picky and b the error messages are often to general The development team agrees and will continue to work on this especially during an upcoming complete rewrite In the meantime here is a list of syntax rules that are commonly broken resulting in syntax errors e All lines except CONFIG and INPUT if used must end with a semicolon 20 e Bertini is case sensitive e The symbol for y 1 is I not i If you prefer to use i you may define i a
73. ut file as usual CONFIG 4 Lists of configuration settings optional END INPUT Symbol declarations Optional assignments parameters constants etc Function definitions END The upper portion of the file consists of a list of configuration settings Any configuration that is not listed in the input file will be set to its default value A table of all configuration settings that may be changed along with their default settings and acceptable ranges may be found in Appendix A The syntax for the configuration lines is straightforward It consists of the name of the setting in all caps followed by a colon a space the setting and a semicolon For example to change the tracking type to 1 the default is 0 simply include the following line in the CONFIG portion of the input file 17 TRACKTYPE 1 The lower portion of the input file begins with a list of symbol declarations for the variables functions constants and so on All such declarations have the same format KEYWORD al a2 a3 where KEYWORD depends upon the type of declaration All symbols used in the input file must be declared with the exception of subfunctions Here are details regarding each type of symbol that may be used in the input file e FUNCTIONS Regardless of the type of run all functions must be named and the names must be declared using the keyword function Also the functions must be defined in the same order that they w
74. utions finite solutions nonsingular solutions and so on The structure of those files is identical of start described in 83 3 4 4 Zero dimensional examples The following provides screenshots for using Bertini to compute a finite set of solutions that contain the zero dimensional solutions 4 4 1 Basic example Figure 4 1 presents a basic input file named input basic that instructs Bertini to use all default settings to solve z2 1 z y 1 0 on C By default Bertini automatically uses adaptive precision tracking 6 7 and computes the 2 solutions as shown in Figure 4 2 The file nonsingular solutions contains the coordinates for the numerical approximations for the 2 nonsingular solutions namely x 1 y 0 and xz 1 y 2 as displayed in Figure 4 3 By inserting the line SHARPENDIGITS 20 into input basic as shown in Figure 4 4 Bertini will automatically attempt to sharpen the nonsingular solutions so that they are correct to 20 as shown in Figure 4 5 The solution number does not necessarily correspond to the order of the start points in the case of a user defined homotopy The solutions are sorted after the run and the resulting order is the source of this solution number Each coordinate gets its own line with the real part listed before the imaginary part 25 Seal 810 Eile Edit View Terminal Tabs Help CONFIG END INPUT variable group x y function f g
75. wisted cubic in P Figure 5 4 presents the output to the screen of Bertini for computing this degree 3 curve E a 4 Eile Edit View Terminal Tabs Help CONFIG TRACKTYPE 1 WITNESSGENTYPE 1 END INPUT hom variable group w x Y Zi function fl f2 f3 fl x 2 wry f2 x y w z 3 x z yA2 END input twisted cubic 18L 163C 18 0 1 All gt Figure 5 3 input_twisted_cubic 5 4 3 Deflation example Figure 5 5 presents an input file named input_Griewank_Osborne 16 that instructs Bertini to compute the numerical irreducible decomposition and sharpen the witness points for each compo nent to 30 digits Bertini automatically deflates the components that are generically nonreduced Figure 5 7 presents the output to the screen of Bertini and Figure 5 6 displays the main_data file showing the isolated solution at the origin that is correct to at least 30 digits 38 Y i jhauenst sleipnir Bertiniexamples Eile Edit View Terminal Tabs Help jhauenstOsleipnir BertiniExamples bertini input twisted cubic NOTE You have requested to use adaptive path tracking Please make sure that you have setup the following tolerances appropriately 0000000000008 03 DEGREEBOUND Finding witness superset for codimension 1 of 3 2 paths to track Tracking path O of 2 Sorting codimension 1 of 3 2 paths to sort Sorting O of 2 Finding witness superset for codimension 2 of 3 4 p

Bertini User`s Manual - University of Notre Dame

Contents

Download Pdf Manuals

Related Search

Related Contents