Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Implift/drivers_for_implicit_lifting.adb, Revision 1.1.1.1
1.1 maekawa 1: with integer_io; use integer_io;
2: with Communications_with_User; use Communications_with_User;
3: with Timing_Package; use Timing_Package;
4: with Numbers_io; use Numbers_io;
5: with Standard_Natural_Vectors;
6: with Standard_Complex_Poly_Systems_io; use Standard_Complex_Poly_Systems_io;
7: with Standard_Complex_Solutions_io; use Standard_Complex_Solutions_io;
8: with Set_Structure,Set_Structure_io;
9: with Drivers_for_Vertex_Points; use Drivers_for_Vertex_Points;
10: with Trees_of_Vectors; use Trees_of_Vectors;
11: with Trees_of_Vectors_io; use Trees_of_Vectors_io;
12: with Set_Structures_and_Volumes; use Set_Structures_and_Volumes;
13: with Generic_Position;
14: with Driver_for_Polyhedral_Continuation;
15:
16: package body Drivers_for_Implicit_Lifting is
17:
18: procedure Implicit_Lifting_Info is
19:
20: i : array(1..20) of string(1..65);
21:
22: begin
23: i( 1):=" The mixed volume of the tuple of Newton polytopes gives an";
24: i( 2):="upper bound for the number of complex isolated solutions with";
25: i( 3):="nonzero coefficients. This BKK bound (called after Bernshtein,";
26: i( 4):="Koushnirenko and Khovanskii) is exact when the coefficients are";
27: i( 5):="sufficiently chosen at random or when the polytopes are in";
28: i( 6):="generic position w.r.t. each other. ";
29: i( 7):=" By implicit lifting, the mixed volume is computed by lifting up";
30: i( 8):="the origin of the first polytope and by computing those facets of";
31: i( 9):="the lower hull of the Minkowski sum that are spanned by edge-edge";
32: i(10):="combinations. This procedure to compute the mixed volume uses";
33: i(11):="recursion on the dimension. ";
34: i(12):=" A random coefficient start system has the same Newton polytopes";
35: i(13):="as the target system, but all coefficients are randomly chosen";
36: i(14):="complex numbers. To solve a random coefficient start system,";
37: i(15):="homotopy continuation is invoked in a recursive way, similar to";
38: i(16):="the computation of the mixed volume. ";
39: i(17):=" By constructing a set structure for the first k equations and";
40: i(18):="computing the mixed volumes of the remaining n-k equations";
41: i(19):="obtained after elimination, a combined Bezout-BKK bound is";
42: i(20):="computed. ";
43: for k in i'range loop
44: put_line(i(k));
45: end loop;
46: end Implicit_Lifting_Info;
47:
48: procedure Driver_for_Mixture_Bezout_BKK
49: ( file : in file_type; p : in Poly_Sys; byebye : in boolean;
50: q : out Poly_Sys; qsols : out Solution_List;
51: b : out natural ) is
52:
53: welcome : constant string := "Mixed-Volume Computation by Implicit Lifting";
54:
55: -- VARIABLES :
56:
57: n,bkk,k : natural;
58: ans : character;
59: timer : timing_widget;
60: tdft,gft,solsft : file_type;
61: td : Tree_of_Vectors;
62: pp,qq : Poly_Sys(p'range);
63: qqsols : Solution_List;
64:
65: -- SWITCHES TO BE SET :
66:
67: verpts : boolean; -- to extract the vertex points
68: havetd : boolean; -- already a tree of directions available
69: wanttd : boolean; -- put a tree of directions on separate file
70: tosolve : boolean; -- a system has to be solved
71: ranstart : boolean; -- for random coefficient start system
72: contrep : boolean; -- reporting during continuation
73:
74: begin
75: new_line; put_line(welcome);
76: n := p'length;
77: new_line;
78: put("Do you first want to extract the vertex points ? (y/n) ");
79: Ask_Yes_or_No(ans);
80: verpts := (ans = 'y');
81: if verpts
82: then put_line("Computing the vertex points...");
83: Copy(p,pp);
84: Vertex_Points(file,pp);
85: else pp := p;
86: end if;
87: new_line;
88: put_line("MENU for Mixture between Bezout and BKK Bound :");
89: put_line(" k = 0 : for computation of the BKK bound;");
90: put(" k = "); put(n,1); put_line(" : for a generalized Bezout number;");
91: put(" 0 < k < "); put(n,1); put_line(" : gives a mixed Bezout BKK bound.");
92: put("Give the number k between 0 and "); put(n,1); put(" : ");
93: Read_Natural(k);
94: if k > 0
95: then new_line;
96: put_line("Do you have a good set structure");
97: put("for the first "); put(k,1); put(" polynomials ? (y/n) ");
98: Ask_Yes_or_No(ans);
99: if ans = 'y'
100: then declare
101: ns : Standard_Natural_Vectors.Vector(p'range);
102: begin
103: for i in 1..k loop
104: put(" Give the number of sets for polynomial ");
105: put(i,1); put(" : "); Read_Natural(ns(i));
106: end loop;
107: ns(k+1..n) := (k+1..n => 0);
108: Set_Structure.Init(ns);
109: put_line("Give the set structure :");
110: Set_Structure_io.get;
111: end;
112: else Build_RPS(k,n,pp);
113: end if;
114: new_line(file);
115: put_line(file,
116: "******* MIXTURE BETWEEN BEZOUT AND BKK BOUND *******");
117: new_line(file);
118: put(file,"Set structure for the first "); put(file,k,1);
119: put_line(file," polynomials : ");
120: Set_Structure_io.put(file);
121: end if;
122: new_line;
123: put("Do you have a tree of useful directions ? (y/n) "); Ask_Yes_or_No(ans);
124: if ans = 'y'
125: then put_line("Reading the name of the file where the tree is.");
126: declare
127: tdf : file_type;
128: begin
129: Read_Name_and_Open_File(tdf);
130: get(tdf,n-k,td);
131: Close(tdf);
132: havetd := true;
133: exception
134: when others =>
135: put_line("There is something wrong with your tree ...");
136: havetd := false;
137: end;
138: else havetd := false;
139: end if;
140: if not havetd
141: then put("Do you want the useful directions on separate file ? (y/n) ");
142: Ask_Yes_or_No(ans);
143: wanttd := (ans = 'y');
144: if wanttd
145: then put_line("Reading a name of a file to write tree on.");
146: Read_Name_and_Create_File(tdft);
147: end if;
148: else wanttd := false;
149: end if;
150: Driver_for_Polyhedral_Continuation
151: (file,pp,k,byebye,qq,gft,solsft,tosolve,ranstart,contrep);
152: tstart(timer);
153: if tosolve
154: then new_line(file);
155: put_line(file,"INTERMEDIATE RESULTS :");
156: new_line(file);
157: if havetd
158: then Mixed_Solve(file,k,n,pp,td,bkk,qq,qqsols);
159: elsif wanttd
160: then Bezout_BKK(k,n,pp,td,bkk);
161: put(tdft,td); Close(tdft);
162: Mixed_Solve(file,k,n,pp,td,bkk,qq,qqsols);
163: else Bezout_BKK(k,n,pp,td,bkk);
164: Mixed_Solve(file,k,n,pp,td,bkk,qq,qqsols);
165: end if;
166: if k > 0
167: then put(gft,qq'last,qq);
168: new_line(file);
169: put_line(file,"THE START SYSTEM : ");
170: new_line(file);
171: put_line(file,qq);
172: end if;
173: if ranstart
174: then new_line(gft); put_line(gft,"THE SOLUTIONS :"); new_line(gft);
175: put(gft,Length_Of(qqsols),n,qqsols);
176: Close(gft);
177: else put(solsft,Length_Of(qqsols),n,qqsols); Close(solsft);
178: end if;
179: q := qq; qsols := qqsols;
180: else if havetd
181: then bkk := Bezout_BKK(k,n,pp,td);
182: elsif wanttd
183: then Bezout_BKK(k,n,pp,td,bkk);
184: put(tdft,td);
185: Close(tdft);
186: else Bezout_Bkk(k,n,pp,td,bkk);
187: end if;
188: end if;
189: tstop(timer);
190: b := bkk;
191: new_line(file);
192: if k > 0
193: then put(file,"The mixed Bezout BKK bound equals ");
194: else put(file,"The BKK bound equals ");
195: end if;
196: put(file,bkk,1); put_line(file,".");
197: new_line(file);
198: if not Is_Null(td)
199: then put_line(file,"The tree of useful directions : ");
200: put(file,td);
201: new_line(file);
202: if k = 0
203: then
204: if Generic_Position(pp,td)
205: then put_line(file,"The polytopes may be in generic position.");
206: else put_line(file,"The polytopes are not in generic position.");
207: end if;
208: new_line(file);
209: end if;
210: end if;
211: print_times(file,timer,"mixed homotopy method");
212: new_line(file);
213: if ans = 'y'
214: then new_line(file);
215: put_line(file,"RANDOM COEFFICIENT START SYSTEM :");
216: new_line(file);
217: put(file,qq'last,qq);
218: new_line(file);
219: put_line(file,"THE SOLUTIONS : ");
220: put(file,Length_Of(qqsols),n,qqsols);
221: end if;
222: if verpts
223: then Clear(pp);
224: end if;
225: end Driver_for_Mixture_Bezout_BKK;
226:
227: end Drivers_for_Implicit_Lifting;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>