Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Implift/drivers_for_implicit_lifting.adb, Revision 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>