Annotation of OpenXM_contrib/PHC/Ada/Root_Counts/Dynlift/drivers_for_dynamic_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_Integer_Vectors; use Standard_Integer_Vectors;
6: with Standard_Integer_Vectors_io; use Standard_Integer_Vectors_io;
7: with Standard_Floating_Vectors;
8: with Standard_Complex_Poly_Systems_io; use Standard_Complex_Poly_Systems_io;
9: with Lists_of_Integer_Vectors; use Lists_of_Integer_Vectors;
10: with Lists_of_Integer_Vectors_io; use Lists_of_Integer_Vectors_io;
11: with Lists_of_Vectors_Utilities; use Lists_of_Vectors_Utilities;
12: with Arrays_of_Integer_Vector_Lists; use Arrays_of_Integer_Vector_Lists;
13: with Arrays_of_Integer_Vector_Lists_io; use Arrays_of_Integer_Vector_Lists_io;
14: with Standard_Complex_Solutions_io; use Standard_Complex_Solutions_io;
15: with Power_Lists; use Power_Lists;
16: with Drivers_for_Vertex_Points; use Drivers_for_Vertex_Points;
17: with Integer_Lifting_Utilities; use Integer_Lifting_Utilities;
18: with Integer_Mixed_Subdivisions; use Integer_Mixed_Subdivisions;
19: with Integer_Mixed_Subdivisions_io; use Integer_Mixed_Subdivisions_io;
20: with Mixed_Volume_Computation; use Mixed_Volume_Computation;
21: with Simplices,Triangulations; use Simplices,Triangulations;
22: with Triangulations_io; use Triangulations_io;
23: with Dynamic_Triangulations; use Dynamic_Triangulations;
24: with Cayley_Trick; use Cayley_Trick;
25: with Driver_for_Minkowski_Polynomials;
26: with Flatten_Mixed_Subdivisions; use Flatten_Mixed_Subdivisions;
27: with Triangulations_and_Subdivisions; use Triangulations_and_Subdivisions;
28: with Dynamic_Mixed_Subdivisions; use Dynamic_Mixed_Subdivisions;
29: with Dynamic_Polyhedral_Continuation; use Dynamic_Polyhedral_Continuation;
30: with Driver_for_Polyhedral_Continuation;
31: with Pruning_Statistics;
32:
33: package body Drivers_for_Dynamic_Lifting is
34:
35: procedure Dynamic_Lifting_Info is
36:
37: i : array(1..6) of string(1..65);
38:
39: begin
40: i(1):=" Dynamic lifting can be used to compute mixed volumes";
41: i(2):="incrementally, i.e.: by adding the points repeatedly to the";
42: i(3):="already constructed subdivision. This method works efficiently";
43: i(4):="when all Newton polytopes are (almost) equal. The Cayley trick";
44: i(5):="is implemented by means of dynamic lifting. This trick computes";
45: i(6):="all cells in a mixed subdivision. ";
46: for k in i'range loop
47: put_line(i(k));
48: end loop;
49: end Dynamic_Lifting_Info;
50:
51: procedure Write_Type_of_Mixture
52: ( file : in file_type; mix,per : in Vector ) is
53:
54: -- DESCRIPTION :
55: -- Writes the information about the type of mixture on file
56: -- and the permutations in the support.
57:
58: begin
59: new_line(file);
60: put(file,"TYPE OF MIXTURE : ");
61: put(file,"#supports : "); put(file,mix'last,1);
62: put(file," occurrences : "); put(file,mix);
63: new_line(file);
64: put(file," permutation : "); put(file,per);
65: new_line(file);
66: end Write_Type_of_Mixture;
67:
68: procedure Driver_for_Dynamic_Mixed_Volume_Computation
69: ( file : in file_type; p : in Poly_Sys; byebye : in boolean;
70: q : out Poly_Sys; qsols : out Solution_List;
71: mv : out natural ) is
72:
73: welcome : constant string := "Mixed-Volume Computation by Dynamic Lifting";
74:
75: -- GLOBAL VARIABLES :
76:
77: supports : Array_of_Lists(p'range);
78: n : natural := p'last;
79: timer : timing_widget;
80: r,max : natural;
81: mix,perms : Link_to_Vector;
82: ans : character;
83: permp,qq : Poly_Sys(p'range);
84: qqsols : Solution_List;
85: subfile,solsft,qft : file_type;
86: vol : natural := 0;
87: mixsub : Mixed_Subdivision;
88:
89: -- GLOBAL SWITCHES :
90:
91: verpts : boolean; -- if the set of vertex points is computed
92: order : boolean; -- process points in fixed instead of random order
93: inter : boolean; -- if interior points are possible
94: conmv : boolean; -- if checks on zero contributions have to be made
95: caytrick : boolean; -- if the Cayley trick has to be applied
96: reportnew : boolean; -- if the new cells have to be reported
97: reportflat : boolean; -- if before flattening, reporting has to be done
98: subonfile : boolean; -- put the subdivision on separate file
99: tosolve : boolean; -- if the system needs to be solved
100: contrep : boolean; -- if intermediate output during continuation
101: ranstart : boolean; -- if random coefficient start system
102:
103: minkpoly : natural; -- 0 : no; 1 : only poly, > 1 : all subdivisions
104:
105: -- EXTRACT THE ADDITIONAL POINTS :
106:
107: function Is_In_Lifted ( pt : Link_to_Vector; lifted : List )
108: return boolean is
109:
110: -- DESCRIPTION :
111: -- Returns true if the point is in the lifted list.
112:
113: tmp : List := lifted;
114: lpt : Link_to_Vector;
115:
116: begin
117: while not Is_Null(tmp) loop
118: lpt := Head_Of(tmp);
119: if pt(pt'range) = lpt(pt'range)
120: then return true;
121: else tmp := Tail_Of(tmp);
122: end if;
123: end loop;
124: return false;
125: end Is_In_Lifted;
126:
127: function Difference ( supp,liftsupp : in List ) return List is
128:
129: res,res_last : List;
130: tmp : List := supp;
131: pt : Link_to_Vector;
132:
133: begin
134: tmp := supp;
135: while not Is_Null(tmp) loop
136: pt := Head_Of(tmp);
137: if not Is_In_Lifted(pt,liftsupp)
138: then Append(res,res_last,pt.all);
139: end if;
140: tmp := Tail_Of(tmp);
141: end loop;
142: return res;
143: end Difference;
144:
145: function Difference ( supp,liftsupp : in Array_of_Lists )
146: return Array_of_Lists is
147:
148: -- DESCRIPTION :
149: -- Returns a tuple of point lists, made of points in supp
150: -- that do not belong to the corresponding lifted supports.
151:
152: res : Array_of_Lists(supp'range);
153:
154: begin
155: for i in supp'range loop
156: res(i) := Difference(supp(i),liftsupp(i));
157: end loop;
158: return res;
159: end Difference;
160:
161: -- DETERMINING THE ORDER OF PROCESSING THE POINTS :
162:
163: function Determine_Order ( l : List ) return List is
164:
165: -- DESCRIPTION :
166: -- Interactive ordering of the points in the list.
167: -- This function displays all points and asks the user for a position.
168:
169: len : constant natural := Length_Of(l);
170: pos : vector(1..len);
171: res : List;
172:
173: function Read_New_Positions
174: ( l : List; length : natural ) return vector is
175:
176: -- DESCRIPTION :
177: -- Lists all points in the lists and prompts for a new position.
178: -- Returns the position vector.
179:
180: newpos : vector(1..length);
181: tmp : List := l;
182: cnt : natural := 0;
183:
184: begin
185: put("There are "); put(length,1); put_line(" points to order.");
186: put_line("Give for each separate point its new position :");
187: while not Is_Null(tmp) loop
188: cnt := cnt + 1;
189: loop
190: put(Head_Of(tmp)); put(" : ");
191: Read_Natural(newpos(cnt));
192: exit when (newpos(cnt) >= 1) and (newpos(cnt) <= length);
193: put("New position out of range 1.."); put(length,1);
194: put_line(". Please try again.");
195: end loop;
196: tmp := Tail_Of(tmp);
197: end loop;
198: return newpos;
199: end Read_New_Positions;
200:
201: function Get ( l : List; pos : natural ) return Link_to_Vector is
202:
203: -- DESCRIPTION :
204: -- Returns the point on the indicated position in the list l.
205:
206: tmp : List := l;
207: res : Link_to_Vector;
208:
209: begin
210: if not Is_Null(l)
211: then for i in 1..(pos-1) loop
212: tmp := Tail_Of(tmp);
213: exit when Is_Null(tmp);
214: end loop;
215: if not Is_Null(tmp)
216: then res := Head_Of(tmp);
217: end if;
218: end if;
219: return res;
220: end Get;
221:
222: function Sort ( l : in List; pos : in vector ) return List is
223:
224: -- DESCRIPTION :
225: -- Sorts the given list according to the given position vector:
226: -- pos(i) determines the new position of the ith point in the list.
227: -- If the returning list is empty, then the position vector was
228: -- not a permutation.
229:
230: empty,res,res_last : List;
231: index : natural;
232:
233: begin
234: for i in pos'range loop -- search index : pos(index) = i
235: index := 0;
236: for j in pos'range loop
237: if pos(j) = i
238: then index := j;
239: end if;
240: exit when (index /= 0);
241: end loop;
242: exit when (index = 0);
243: Append(res,res_last,get(l,index)); -- append the vector
244: end loop;
245: if index = 0
246: then return empty;
247: else return res;
248: end if;
249: end Sort;
250:
251: begin
252: if Is_Null(l)
253: then return l;
254: else loop
255: pos := Read_New_Positions(l,len);
256: res := Sort(l,pos);
257: exit when not Is_Null(res);
258: put_line("The given position vector was not a permutation.");
259: put_line("Please try again...");
260: end loop;
261: return res;
262: end if;
263: end Determine_Order;
264:
265: procedure Determine_Processing_Order
266: ( supports : in out Array_of_Lists; mix : in Link_to_Vector;
267: fixed : out boolean ) is
268:
269: choice : character;
270: cnt : natural;
271:
272: begin
273: new_line;
274: put_line("MENU for the Order of the points to add : ");
275: put_line(" 1. fixed order, given by the monomial ordering");
276: put_line(" 2. random order, generated by the algorithm");
277: put_line(" 3. interactively defined by you");
278: put("Type 1,2, or 3 : "); Ask_Alternative(choice,"123");
279: case choice is
280: when '1' => fixed := true;
281: when '2' => fixed := false;
282: when others => fixed := true;
283: cnt := supports'first;
284: for i in mix'range loop
285: supports(cnt) := Determine_Order(supports(cnt));
286: cnt := cnt + mix(i);
287: end loop;
288: end case;
289: end Determine_Processing_Order;
290:
291: -- INSTANTIATIONS OF THE GENERICS :
292:
293: procedure Report_New_Simplices
294: ( t : in Triangulation; point : in Vector ) is
295:
296: -- DESCRIPTION :
297: -- Writes the new simplices on file and computes their volume.
298:
299: v : natural;
300:
301: begin
302: new_line(file);
303: put(file,"The new simplices by adding "); put(file,point);
304: put_line(file," : ");
305: put(file,n,t,v);
306: put(file," with volume addition : ");
307: put(file,vol,1); put(file," + "); put(file,v,1);
308: vol := vol + v; put(file," = "); put(file,vol,1); put_line(file,".");
309: end Report_New_Simplices;
310: procedure R_Dynamic_Lifting is
311: new Dynamic_Triangulations.Dynamic_Lifting_with_New(Report_New_Simplices);
312:
313: procedure Collect_Flattening ( t : in Triangulation; l : List ) is
314:
315: -- DESCRIPTION :
316: -- Updates the subdivision mixsub with the flattened cells.
317: -- The triangulation on entry contains the whole triangulation,
318: -- not just the new cells.
319:
320: cells : Mixed_Subdivision;
321:
322: begin
323: if Is_Null(mixsub)
324: then cells := Deep_Create(n,t);
325: else cells := Non_Flat_Deep_Create(n,t);
326: Construct(Head_Of(mixsub),cells);
327: end if;
328: Flatten(cells);
329: mixsub := cells;
330: end Collect_Flattening;
331:
332: procedure Report_Flattening
333: ( t : in Triangulation; l : in List ) is
334:
335: -- DESCRIPTION :
336: -- Writes the list of lifted points and the triangulation on file
337: -- and updates the mixed subdivision.
338:
339: begin
340: new_line(file);
341: put_line(file,"The list of lifted points before flattening : ");
342: put(file,l);
343: new_line(file);
344: put_line(file,"The triangulation before flattening : ");
345: put(file,n,t,vol);
346: put(file," with volume "); put(file,vol,1); put_line(file,".");
347: Collect_Flattening(t,l);
348: end Report_Flattening;
349: procedure C_Dynamic_Lifting is
350: new Dynamic_Triangulations.Dynamic_Lifting_with_Flat(Collect_Flattening);
351: procedure F_Dynamic_Lifting is
352: new Dynamic_Triangulations.Dynamic_Lifting_with_Flat(Report_Flattening);
353: procedure FR_Dynamic_Lifting is
354: new Dynamic_Triangulations.Dynamic_Lifting_with_Flat_and_New
355: ( Before_Flattening => Report_Flattening,
356: Process_New_Simplices => Report_New_Simplices);
357:
358: procedure Report_New_Cells
359: ( mixsub : in out Mixed_Subdivision;
360: i : in natural; point : in Vector ) is
361:
362: -- DESCRIPTION :
363: -- Writes the new mixed cells on file and computes the mixed volume.
364:
365: v : natural;
366:
367: begin
368: if not Is_Null(mixsub)
369: then
370: new_line(file);
371: put(file,"The new mixed cells by adding "); put(file,point);
372: new_line(file);
373: put(file," to the "); put(file,i,1); put_line(file,"th component : ");
374: put(file,n,mix.all,mixsub,v);
375: put(file," with volume addition : ");
376: put(file,vol,1); put(file," + "); put(file,v,1);
377: vol := vol + v; put(file," = "); put(file,vol,1); new_line(file);
378: end if;
379: end Report_New_Cells;
380: procedure R_Dynamic_Cayley is
381: new Cayley_Trick.Dynamic_Cayley_with_New(Report_New_Cells);
382: procedure Rt_Dynamic_Cayley is
383: new Cayley_Trick.Dynamic_Cayley_with_Newt(Report_New_Cells);
384: procedure R_Dynamic_Lifting is
385: new Dynamic_Mixed_Subdivisions.Dynamic_Lifting_with_New(Report_New_Cells);
386:
387: procedure Report_Flattening
388: ( mixsub : in out Mixed_Subdivision;
389: lifted : in Array_of_Lists ) is
390:
391: -- DESCRIPTION :
392: -- Writes the list of lifted points and the subdivision on file.
393:
394: begin
395: new_line(file);
396: put_line(file,"The list of lifted points before flattening : ");
397: for i in lifted'range loop
398: put(file," points of "); put(file,i,1);
399: put_line(file,"th component : ");
400: put(file,lifted(i));
401: end loop;
402: new_line(file);
403: put_line(file,"The mixed subdivision before flattening : ");
404: put(file,n,mix.all,mixsub,vol);
405: put(file," with volume "); put(file,vol,1); put_line(file,".");
406: end Report_Flattening;
407: procedure F_Dynamic_Cayley is
408: new Cayley_Trick.Dynamic_Cayley_with_Flat(Report_Flattening);
409: procedure Ft_Dynamic_Cayley is
410: new Cayley_Trick.Dynamic_Cayley_with_Flatt(Report_Flattening);
411: procedure FR_Dynamic_Cayley is
412: new Cayley_Trick.Dynamic_Cayley_with_Flat_and_New
413: (Before_Flattening => Report_Flattening,
414: Process_New_Cells => Report_New_Cells);
415: procedure FRt_Dynamic_Cayley is
416: new Cayley_Trick.Dynamic_Cayley_with_Flat_and_Newt
417: (Before_Flattening => Report_Flattening,
418: Process_New_Cells => Report_New_Cells);
419:
420: procedure Report_Flattening
421: ( mixsub : in out Mixed_Subdivision;
422: fs : in Face_Structures ) is
423:
424: -- DESCRIPTION :
425: -- Writes the list of lifted points and the subdivision on file.
426:
427: begin
428: new_line(file);
429: put_line(file,"The lists of lifted points before flattening : ");
430: for i in fs'range loop
431: put(file," points of "); put(file,i,1);
432: put_line(file,"th component : ");
433: put(file,fs(i).l);
434: end loop;
435: new_line(file);
436: put_line(file,"The mixed subdivision before flattening : ");
437: put(file,n,mix.all,mixsub,vol);
438: put(file," with volume "); put(file,vol,1); put_line(file,".");
439: end Report_Flattening;
440: procedure F_Dynamic_Lifting is
441: new Dynamic_Mixed_Subdivisions.Dynamic_Lifting_with_Flat
442: (Report_Flattening);
443: procedure FR_Dynamic_Lifting is
444: new Dynamic_Mixed_Subdivisions.Dynamic_Lifting_with_Flat_and_New
445: (Before_Flattening => Report_Flattening,
446: Process_New_Cells => Report_New_Cells);
447:
448: -- MAIN CONSTRUCTORS :
449:
450: procedure Compute_Triangulation is
451:
452: -- DESCRIPTION :
453: -- Application of the dynamic lifting algorithm
454: -- to compute a triangulation of one polytope.
455:
456: t : Triangulation;
457: support,lifted,lifted_last : List;
458: arlifted : Array_of_Lists(mix'range);
459:
460: begin
461: support := supports(supports'first);
462: if verpts
463: then Vertex_Points(file,support);
464: end if;
465: new_line(file);
466: put_line(file,"CREATION OF THE TRIANGULATION :");
467: new_line(file);
468: tstart(timer);
469: if reportnew
470: then
471: if reportflat
472: then FR_Dynamic_Lifting(support,order,inter,max,lifted,lifted_last,t);
473: else R_Dynamic_Lifting(support,order,inter,max,lifted,lifted_last,t);
474: end if;
475: elsif reportflat
476: then
477: F_Dynamic_Lifting(support,order,inter,max,lifted,lifted_last,t);
478: elsif subonfile
479: then
480: C_Dynamic_Lifting
481: (support,order,inter,max,lifted,lifted_last,t);
482: else
483: Dynamic_Lifting(support,order,inter,max,lifted,lifted_last,t);
484: end if;
485: tstop(timer);
486: new_line(file);
487: print_times(file,timer,"computing the triangulation");
488: new_line(file);
489: put_line(file,"THE LIFTED SUPPORTS :"); new_line(file);
490: put(file,lifted);
491: new_line(file);
492: put_line(file,"THE TRIANGULATION :"); new_line(file);
493: tstart(timer);
494: put(file,n,t,vol);
495: tstop(timer);
496: new_line(file);
497: put(file,"The volume : "); put(file,vol,1); new_line(file);
498: new_line(file);
499: print_times(file,timer,"computing the volume");
500: if subonfile
501: then if Is_Null(mixsub)
502: then put(subfile,n,1); new_line(subfile);
503: put(subfile,1,1); new_line(subfile); -- type of mixture
504: put(subfile,n,t);
505: else declare
506: lastcells : Mixed_Subdivision := Non_Flat_Deep_Create(n,t);
507: begin
508: Construct(Head_Of(mixsub),lastcells);
509: mixsub := lastcells;
510: put(subfile,n,mix.all,mixsub);
511: end;
512: end if;
513: Close(subfile);
514: end if;
515: mv := vol;
516: end Compute_Triangulation;
517:
518: procedure Compute_Cayley_Triangulation is
519:
520: -- DESCRIPTION :
521: -- Application of the dynamic lifting algorithm to compute a mixed
522: -- subdivision of a tuple of polytopes by means of the Cayley trick.
523:
524: supp,lifted : Array_of_Lists(1..r);
525: t : Triangulation;
526: numtri,mr : natural;
527: newperms : Link_to_Vector;
528:
529: begin
530: if verpts
531: then Vertex_Points(file,mix,supports);
532: Clear(mix);
533: Compute_Mixture(supports,mix,newperms);
534: Write_Type_of_Mixture(file,mix.all,newperms.all);
535: end if;
536: mr := mix'last;
537: supp(1..mr) := Typed_Lists(mix.all,supports);
538: new_line(file);
539: put_line(file,"CREATION OF THE MIXED SUBDIVISION :");
540: new_line(file);
541: tstart(timer);
542: if reportnew
543: then
544: if reportflat
545: then
546: if minkpoly > 0
547: then FRt_Dynamic_Cayley
548: (n,mix.all,supp(1..mr),order,inter,max,lifted(1..mr),t);
549: else FR_Dynamic_Cayley
550: (n,mix.all,supp(1..mr),order,inter,max,
551: lifted(1..mr),mixsub,numtri);
552: end if;
553: else
554: if minkpoly > 0
555: then Rt_Dynamic_Cayley
556: (n,mix.all,supp(1..mr),order,inter,max,lifted(1..mr),t);
557: else R_Dynamic_Cayley
558: (n,mix.all,supp(1..mr),order,inter,max,lifted(1..mr),
559: mixsub,numtri);
560: end if;
561: end if;
562: elsif reportflat
563: then
564: if minkpoly > 0
565: then Ft_Dynamic_Cayley
566: (n,mix.all,supp(1..mr),order,inter,max,lifted(1..mr),t);
567: else F_Dynamic_Cayley
568: (n,mix.all,supp(1..mr),order,inter,max,
569: lifted(1..mr),mixsub,numtri);
570: end if;
571: else
572: if minkpoly > 0
573: then Dynamic_Cayley
574: (n,mix.all,supp(1..mr),order,inter,max,lifted(1..mr),t);
575: else Dynamic_Cayley
576: (n,mix.all,supp(1..mr),order,inter,max,
577: lifted(1..mr),mixsub,numtri);
578: end if;
579: end if;
580: tstop(timer);
581: new_line(file);
582: print_times(file,timer,"Computing the mixed subdivision");
583: new_line(file);
584: put_line(file,"THE LIFTED SUPPORTS :");
585: new_line(file);
586: put(file,lifted);
587: if minkpoly > 0
588: then declare
589: alltri : boolean := (minkpoly > 1);
590: begin
591: Driver_for_Minkowski_Polynomials(file,n,mix.all,t,alltri,mixsub);
592: numtri := Length_Of(t);
593: end;
594: end if;
595: new_line(file);
596: put_line(file,"THE MIXED SUBDIVISION :");
597: new_line(file);
598: tstart(timer);
599: put(file,n,mix.all,mixsub,vol);
600: tstop(timer);
601: new_line(file);
602: put(file,"The mixed volume equals : "); put(file,vol,1);
603: new_line(file);
604: put(file,"Number of cells in auxiliary triangulation : ");
605: put(file,numtri,1); new_line(file);
606: new_line(file);
607: print_times(file,timer,"Computing the mixed volume");
608: if subonfile
609: then put(subfile,n,mix.all,mixsub);
610: Close(subfile);
611: end if;
612: mv := vol;
613: end Compute_Cayley_Triangulation;
614:
615: procedure Report_Results
616: ( file : in file_type; n : in natural; mix : in Link_to_Vector;
617: mixsub : in out Mixed_Subdivision;
618: fs : in Face_Structures ) is
619: begin
620: new_line(file);
621: put_line(file,"THE LIFTED SUPPORTS :");
622: new_line(file);
623: for i in fs'range loop
624: put(file,fs(i).l); new_line(file);
625: end loop;
626: put_line(file,"THE MIXED SUBDIVISION :");
627: new_line(file);
628: tstart(timer);
629: if r = 1
630: then put(file,n,fs(fs'first).t,vol);
631: else put(file,n,mix.all,mixsub,vol);
632: end if;
633: tstop(timer);
634: new_line(file);
635: put(file,"The mixed volume equals : "); put(file,vol,1); new_line(file);
636: new_line(file);
637: print_times(file,timer,"Computing the mixed volume");
638: if subonfile
639: then put(subfile,n,mix.all,mixsub);
640: Close(subfile);
641: end if;
642: mv := vol;
643: end Report_Results;
644:
645: procedure Compute_Mixed_Subdivision is
646:
647: -- DESCRIPTION :
648: -- Application of the dynamic lifting algorithm
649: -- to compute a mixed subdivision of a tuple of polytopes.
650:
651: supp,lifted : Array_of_Lists(1..r);
652: fs : Face_Structures(1..r);
653: nbsucc,nbfail : Standard_Floating_Vectors.Vector(1..r) := (1..r => 0.0);
654: mr : natural;
655: newperms : Link_to_Vector;
656:
657: begin
658: if verpts
659: then Vertex_Points(file,mix,supports);
660: Clear(mix);
661: Compute_Mixture(supports,mix,newperms);
662: Write_Type_of_Mixture(file,mix.all,newperms.all);
663: end if;
664: mr := mix'last;
665: supp(1..mr) := Typed_Lists(mix.all,supports);
666: new_line(file);
667: put_line(file,"CREATION OF THE MIXED SUBDIVISION :");
668: new_line(file);
669: tstart(timer);
670: if reportnew
671: then
672: if reportflat
673: then FR_Dynamic_Lifting
674: (n,mix.all,supp(1..mr),order,inter,conmv,max,mixsub,
675: fs(1..mr),nbsucc(1..mr),nbfail(1..mr));
676: else R_Dynamic_Lifting
677: (n,mix.all,supp(1..mr),order,inter,conmv,max,mixsub,
678: fs(1..mr),nbsucc(1..mr),nbfail(1..mr));
679: end if;
680: elsif reportflat
681: then F_Dynamic_Lifting
682: (n,mix.all,supp(1..mr),order,inter,conmv,max,mixsub,
683: fs(1..mr),nbsucc(1..mr),nbfail(1..mr));
684: else Dynamic_Lifting
685: (n,mix.all,supp(1..mr),order,inter,conmv,max,mixsub,
686: fs(1..mr),nbsucc(1..mr),nbfail(1..mr));
687: end if;
688: tstop(timer);
689: Pruning_Statistics(file,nbsucc(1..mr),nbfail(1..mr));
690: new_line(file);
691: print_times(file,timer,"Computing the mixed subdivision");
692: Report_Results(file,n,mix,mixsub,fs(1..mr));
693: end Compute_Mixed_Subdivision;
694:
695: procedure Solve_Coefficient_System is
696:
697: -- DESCRIPTION :
698: -- Application of the dynamic lifting algorithm
699: -- to compute a mixed subdivision of a tuple of polytopes and
700: -- to solve a start system, with randomized coefficients.
701:
702: supp : Array_of_Lists(1..r);
703: fs : Face_Structures(1..r);
704: lifted : Array_of_Lists(1..r);
705: numtri : natural := 0;
706: lif,lif_last : List;
707: nbsucc,nbfail : Standard_Floating_Vectors.Vector(1..r) := (1..r => 0.0);
708: mr : natural;
709: newperms : Link_to_Vector;
710:
711: begin
712: if verpts
713: then Vertex_Points(file,mix,supports);
714: if r > 1
715: then Clear(mix);
716: Compute_Mixture(supports,mix,newperms);
717: Write_Type_of_Mixture(file,mix.all,newperms.all);
718: qq := Permute(qq,newperms);
719: for i in supports'range loop
720: qq(i) := Select_Terms(qq(i),supports(i));
721: end loop;
722: end if;
723: end if;
724: mr := mix'last;
725: supp(1..mr) := Typed_Lists(mix.all,supports);
726: new_line(file);
727: put_line(file,"SOLVING THE RANDOM COEFFICIENT SYSTEM :");
728: new_line(file);
729: tstart(timer);
730: if mix'last = mix'first
731: then
732: Dynamic_Unmixed_Solve
733: (file,n,supp(supp'first),order,inter,max,fs(fs'first).l,
734: fs(fs'first).last,fs(fs'first).t,qq,qqsols);
735: else
736: if caytrick
737: then
738: Dynamic_Cayley_Solve(file,n,mix.all,supp(1..mr),order,inter,max,
739: lifted(1..mr),mixsub,numtri,qq,qqsols);
740: for i in 1..mr loop
741: fs(i).l := lifted(i);
742: end loop;
743: else
744: Dynamic_Mixed_Solve
745: (file,n,mix.all,supp(1..mr),order,inter,conmv,max,mixsub,
746: fs(1..mr),nbsucc(1..mr),nbfail(1..mr),qq,qqsols);
747: end if;
748: end if;
749: tstop(timer);
750: if mix'last > mix'first and not caytrick
751: then Pruning_Statistics(file,nbsucc(1..mr),nbfail(1..mr));
752: end if;
753: new_line(file);
754: print_times(file,timer,"Computing the solution list");
755: Report_Results(file,n,mix,mixsub,fs(1..mr));
756: q := qq; qsols := qqsols;
757: if not ranstart
758: then put(solsft,qqsols);
759: Close(solsft);
760: end if;
761: if ranstart
762: then new_line(qft); put_line(qft,"THE SOLUTIONS :"); new_line(qft);
763: put(qft,Length_Of(qqsols),n,qqsols);
764: Close(qft);
765: end if;
766: end Solve_Coefficient_System;
767:
768: begin
769: new_line; put_line(welcome);
770: -- READING GENERAL INPUT INFORMATION :
771: supports := Create(p);
772: new_line;
773: put("Do you want to enforce a type of mixture ? (y/n) ");
774: Ask_Yes_or_No(ans);
775: if ans /= 'y'
776: then Compute_Mixture(supports,mix,perms); r := mix'last;
777: else put("Give number of different supports : "); Read_Natural(r);
778: put("Give vector of occurrences : "); get(r,mix);
779: perms := new Vector(1..n);
780: for i in perms'range loop
781: perms(i) := i;
782: end loop;
783: end if;
784: Write_Type_of_Mixture(file,mix.all,perms.all);
785: -- DETERMINE THE GLOBAL SWITCHES :
786: put("Do you first want to extract the vertex points ? (y/n) ");
787: Ask_Yes_or_No(ans);
788: verpts := (ans = 'y');
789: inter := not verpts;
790: put("Do you have a maximum lifting value ? (y/n) ");
791: Ask_Yes_or_No(ans);
792: if ans = 'y'
793: then put(" Give the maximum lifting value : ");
794: Read_Positive(max);
795: else max := 0;
796: end if;
797: Determine_Processing_Order(supports,mix,order);
798: if (r > 1)
799: then new_line;
800: put_line("MENU for Cayley trick : ");
801: put_line(" 0. No Cayley trick, pruning for mixed cells.");
802: put_line(" 1. Cayley trick : auxiliary triangulation.");
803: put_line(" 2. Cayley trick with Minkowski-polynomial.");
804: put_line(" 3. Cayley trick with all subdivisions.");
805: put("Type 0,1,2, or 3 : ");
806: Ask_Alternative(ans,"0123");
807: caytrick := not (ans = '0');
808: case ans is
809: when '2' => minkpoly := 1;
810: when '3' => minkpoly := 2;
811: when others => minkpoly := 0;
812: end case;
813: if not caytrick
814: then put("Do you want online checks on zero contributions ? (y/n) ");
815: Ask_Yes_or_No(ans);
816: conmv := (ans = 'y');
817: else conmv := false;
818: end if;
819: else caytrick := false; conmv := false;
820: end if;
821: put("Do you want to have the subdivision on separate file ? (y/n) ");
822: Ask_Yes_or_No(ans);
823: if ans = 'y'
824: then subonfile := true;
825: put_line("Reading the name of the file.");
826: Read_Name_and_Create_File(subfile);
827: else subonfile := false;
828: end if;
829: new_line;
830: put("Are the cells to be written on file, during computation ? (y/n) ");
831: Ask_Yes_or_No(ans);
832: reportnew := (ans = 'y');
833: put("Are the cells to be written on file, before flattening ? (y/n) ");
834: Ask_Yes_or_No(ans);
835: reportflat := (ans = 'y');
836: permp := Permute(p,perms);
837: Driver_for_Polyhedral_Continuation
838: (file,permp,0,byebye,qq,qft,solsft,tosolve,ranstart,contrep);
839: -- HANDLING THE UNMIXED AND THE MIXED CASE SEPARATELY :
840: if not tosolve
841: then if r = 1
842: then Compute_Triangulation;
843: else if caytrick
844: then Compute_Cayley_Triangulation;
845: else Compute_Mixed_Subdivision;
846: end if;
847: end if;
848: else Solve_Coefficient_System;
849: end if;
850: end Driver_for_Dynamic_Mixed_Volume_Computation;
851:
852: end Drivers_for_Dynamic_Lifting;
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>