Return to sagbi_results CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Schubert

Annotation of OpenXM_contrib/PHC/Ada/Schubert/sagbi_results, Revision 1.1.1.1

1.1       maekawa     1: Intersection of (n-d)*d random real (n-d-1)-planes in complex n-space.
                      2:
                      3: Root Counts :
                      4:
                      5: --------------------------------
                      6:   n\d   2     3    4    5  6  7
                      7: --------------------------------
                      8:    4    2     1
                      9:    5    5     5
                     10:    6   14    42   14
                     11:    7   42   462        42
                     12:    8  132  6006
                     13:    9  429
                     14: --------------------------------
                     15:
                     16: Timings on SunOS mars 5.6 Generic sun4u sparc SUNW,Ultra-1 :
                     17:
                     18:   Set-up : syzygies, bracket expansions, lifting to set up SAGBI homotopy
                     19:   Volume : dynamic lifting for triangulation and volume computation
                     20:   Polcon : polyhedral continuation to solve complex random system
                     21:   Fladef : flat deformation to solve random complex problem instance
                     22:   Cheat  : cheater's homotopy from random complex to random float
                     23:   Total  : total cpu time for solving the problem
                     24:
                     25: -----------------------------------------------------------------------------
                     26:   d=2  :  n = 4   n = 5     n = 6     n = 7        n = 8          n = 9
                     27: ----------------------------------------------------------------------------
                     28: #vars  :    4       6         8        10           12             14
                     29: #sols  :    2       5        14        42          132            429
                     30: -----------------------------------------------------------------------------
                     31: Set-up :   30ms  0s 60ms   0s170ms  0m 0s400ms   0m 0s790ms   0h 0m 1s580ms
                     32: Volume :    0ms  0s 10ms   0s 40ms  0m 0s190ms   0m 1s310ms   0h 0m 8s890ms
                     33: Polcon :   70ms  1s210ms   6s790ms  1m27s 10ms  10m16s880ms   1h15m 9s870ms
                     34: Fladef :   60ms  1s290ms   6s820ms  1m 5s990ms   7m 5s120ms   1h 1m38s280ms
                     35: Cheat  :  640ms  3s 90ms  26s740ms  2m33s570ms  22m24s270ms   2h14m33s590ms
                     36: Total  :  800ms  5s660ms  40s570ms  5m 7s190ms  39m48s420ms   4h31m32s290ms
                     37: -----------------------------------------------------------------------------
                     38:   d=3  :  n = 4   n = 5     n = 6       n = 7        n = 8
                     39: -----------------------------------------------------------------------------
                     40: #vars  :    3       6         9          12           15
                     41: #sols  :    1       5        42         462         6006
                     42: -----------------------------------------------------------------------------
                     43: Set-up :   30ms  0s140ms  0m 0s440ms
                     44: Volume :    0ms  0s  0ms  0m 0s170ms
                     45: Polcon :   20ms  0s600ms  1m 2s750ms
                     46: Fladef :   10ms  0s540ms  0m50s590ms
                     47: Cheat  :   30ms  1s830ms  2m47s910ms
                     48: Total  :   90ms  3s120ms  4m41s910ms
                     49: -----------------------------------------------------------------------------
                     50:
                     51: Observations:
                     52:   1) setting up the equations and computing the volume is minor
                     53:   2) cheater's homotopy is most time-consuming
                     54:   3) the complexity of the problem increases rapidly as n and d grow