Annotation of OpenXM_contrib/PHC/Ada/Main/black_box_root_counting.adb, Revision 1.1.1.1
1.1 maekawa 1: with integer_io; use integer_io;
2: with Timing_Package; use Timing_Package;
3: with Communications_with_User; use Communications_with_User;
4: with Standard_Integer_Vectors; use Standard_Integer_Vectors;
5: with Standard_Complex_Poly_Systems; use Standard_Complex_Poly_Systems;
6: with Standard_Complex_Poly_Systems_io; use Standard_Complex_Poly_Systems_io;
7: with Arrays_of_Integer_Vector_Lists; use Arrays_of_Integer_Vector_Lists;
8: with Standard_Complex_Solutions_io; use Standard_Complex_Solutions_io;
9: with Total_Degree_Start_Systems; use Total_Degree_Start_Systems;
10: with Partitions_of_Sets_Of_Unknowns; use Partitions_of_Sets_of_Unknowns;
11: with Partitions_of_Sets_Of_Unknowns_io; use Partitions_of_Sets_of_Unknowns_io;
12: with m_Homogeneous_Bezout_Numbers; use m_Homogeneous_Bezout_Numbers;
13: with m_Homogeneous_Start_Systems; use m_Homogeneous_Start_Systems;
14: with Set_Structure,Set_Structure_io;
15: with Degree_Sets_Tables; use Degree_Sets_Tables;
16: with Random_Product_System;
17: with Random_Product_Start_Systems; use Random_Product_Start_Systems;
18: with Integer_Mixed_Subdivisions; use Integer_Mixed_Subdivisions;
19: with Black_Mixed_Volume_Computations; use Black_Mixed_Volume_Computations;
20:
21: procedure Black_Box_Root_Counting
22: ( file : in file_type;
23: p : in out Poly_Sys; rc : out natural;
24: q : out Poly_Sys; qsols : out Solution_List;
25: rocotime,hocotime : out duration ) is
26:
27: function Set_Structure_Bound ( p : Poly_Sys ) return natural is
28: begin
29: Random_Product_Start_Systems.Build_Set_Structure(p);
30: return Permanent(Degree_Sets_Tables.Create);
31: end Set_Structure_Bound;
32:
33: procedure Count_Roots
34: ( file : in file_type; p : in out Poly_Sys;
35: tode,mhbz,setb,mivo : out natural;
36: zz : out Partition; nz : out natural;
37: lifsup : out Link_to_Array_of_Lists;
38: mix : out Link_to_Vector; mixsub : out Mixed_Subdivision ) is
39:
40: -- DESCRIPTION :
41: -- Computes four different root counts for the system p.
42:
43: -- ON ENTRY :
44: -- file output file;
45: -- p a polynomial system.
46:
47: -- ON RETURN :
48: -- tode total degree;
49: -- mhbz m-homogeneous Bezout number;
50: -- setb bound based on set structure;
51: -- mivo mixed volume;
52: -- zz partition used to compute mhbz;
53: -- nz number of sets in partition zz;
54: -- lifsup lifted supports of the system;
55: -- mix type of mixture;
56: -- mixsub mixed subdivision used to compute mivo.
57:
58: timer : timing_widget;
59: n : constant natural := p'length;
60: d,bz,m,bs,mv : natural;
61: z : Partition(1..n);
62:
63: begin
64: tstart(timer);
65: d := Total_Degree(p);
66: PB(p,bz,m,z);
67: bs := Set_Structure_Bound(p);
68: Black_Box_Mixed_Volume_Computation(p,mix,lifsup,mixsub,mv);
69: tstop(timer);
70: new_line(file);
71: put_line(file,"ROOT COUNTS :");
72: new_line(file);
73: put(file,"total degree : ");
74: put(file,d,1); new_line(file);
75: put(file,m,1); put(file,"-homogeneous Bezout number : ");
76: put(file,bz,1); new_line(file);
77: put(file," with partition : "); put(file,z(1..m)); new_line(file);
78: put(file,"general linear-product Bezout number : ");
79: put(file,bs,1); new_line(file);
80: put_line(file," based on the set structure :");
81: Set_Structure_io.put(file);
82: put(file,"mixed volume : "); put(file,mv,1); new_line(file);
83: new_line(file);
84: print_times(file,timer,"Root Counting");
85: tode := d; mhbz := bz; setb := bs; mivo := mv;
86: zz := z; nz := m;
87: rocotime := Elapsed_User_Time(timer);
88: end Count_Roots;
89:
90: function Is_Minimum ( a,b,c,x : natural ) return boolean is
91:
92: -- DESCRIPTION :
93: -- Returns true if x <= a, x <= b, and x <= c.
94:
95: begin
96: return (x <= a) and (x <= b) and (x <= c);
97: end Is_Minimum;
98:
99: procedure Construct_Start_System
100: ( file : in file_type; p : in out Poly_Sys;
101: d,bz,bs,mv : in natural; z : in Partition;
102: mix : in Vector; lifted : in Array_of_Lists;
103: mixsub : in Mixed_Subdivision; roco : out natural;
104: qq : in out Poly_Sys; qqsols : in out Solution_List ) is
105:
106: -- DESCRIPTION :
107: -- Constructs a start system for the minimal root count and least
108: -- amount of work.
109:
110: -- ON ENTRY :
111: -- file output file;
112: -- p polynomial system;
113: -- d total degree;
114: -- bz m-homogeneous Bezout number;
115: -- bs Bezout number based on set structure;
116: -- mv mixed volume;
117: -- z partition that corresponds with bz;
118: -- mix type of mixture of the supports;
119: -- mixsub mixed subdivision used to computed mv.
120:
121: -- ON RETURN :
122: -- roco minimum(d,bz,bs,mv);
123: -- qq start system;
124: -- qqsols solutions of qq.
125:
126: timer : timing_widget;
127: n : constant natural := p'length;
128: nl : natural;
129:
130: begin
131: new_line(file);
132: tstart(timer);
133: if Is_Minimum(bz,bs,mv,d)
134: then put_line(file,"START SYSTEM BASED ON TOTAL DEGREE :");
135: roco := d;
136: Start_System(p,qq,qqsols);
137: elsif Is_Minimum(d,bs,mv,bz)
138: then put(file,z'length,1);
139: put_line(file,"-HOMOGENEOUS START SYSTEM :");
140: roco := bz;
141: m_Homogeneous_Start_System(p,z,qq,qqsols);
142: elsif Is_Minimum(d,bz,mv,bs)
143: then put_line(file,"LINEAR-PRODUCT START SYSTEM : ");
144: roco := bs;
145: Random_Product_System.Init(n);
146: Build_Random_Product_System(n);
147: qq := Random_Product_System.Polynomial_System;
148: Random_Product_System.Solve(qqsols,nl);
149: Set_Structure.Clear;
150: Random_Product_System.Clear;
151: else put_line(file,"RANDOM COEFFICIENT START SYSTEM :");
152: roco := mv;
153: Black_Box_Polyhedral_Continuation
154: (p,mix,lifted,mixsub,qq,qqsols);
155: end if;
156: tstop(timer);
157: new_line(file);
158: put_line(file,qq);
159: new_line(file);
160: put_line(file,"START SOLUTIONS : ");
161: new_line(file);
162: put(file,Length_Of(qqsols),Head_Of(qqsols).n,qqsols);
163: new_line(file);
164: print_times(file,timer,"Construction of Start System");
165: hocotime := Elapsed_User_Time(timer);
166: end Construct_Start_System;
167:
168: procedure Main is
169:
170: d,bz,bs,mv : natural;
171: z : partition(p'range);
172: nz : natural;
173: mix : Standard_Integer_Vectors.Link_to_Vector;
174: mixsub : Mixed_Subdivision;
175: lifsup : Link_to_Array_of_Lists;
176: qq : Poly_Sys(p'range);
177: qqsols : Solution_List;
178:
179: begin
180: Count_Roots(file,p,d,bz,bs,mv,z,nz,lifsup,mix,mixsub);
181: Construct_Start_System
182: (file,p,d,bz,bs,mv,z(1..nz),mix.all,lifsup.all,mixsub,rc,qq,qqsols);
183: q := qq; qsols := qqsols;
184: Clear(z);
185: Clear(mix);
186: Deep_Clear(lifsup);
187: Deep_Clear(mixsub);
188: end Main;
189:
190: begin
191: Main;
192: end Black_Box_Root_Counting;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>