Extreme slowdown in polynomial factorization

[tueda]

Hi, I have encountered another freeze with polynomial factorization, but this time I'm wondering if this is a problem in Rings or maybe some issue on my environment...

The following example tries to factorize a non-factorizable polynomial many times:

import cc.redberry.rings.bigint.BigInteger;
import cc.redberry.rings.poly.multivar.MultivariateFactorization;
import cc.redberry.rings.poly.multivar.MultivariatePolynomial;

var p = MultivariatePolynomial.parse("x12^2-7*x11*x12-x02*x12-x02*x11-x12^3+6*x11*x12^2-x03*x12^2+x02*x12^2+7*x11^2*x12+2*x10*x11*x12+2*x09*x11*x12+2*x08*x11*x12+4*x06*x11*x12+2*x04*x11*x12-x03*x11*x12+2*x02*x11*x12+4*x01*x11*x12+x02*x03*x12+x02*x11^2-2*x02*x06*x11+2*x02*x04*x11+x02*x03*x11-x09*x12^3+x08*x12^3+x07*x12^3-x06*x12^3-x05*x12^3+x04*x12^3-x10*x11*x12^2-3*x09*x11*x12^2-4*x06*x11*x12^2-3*x05*x11*x12^2+x04*x11*x12^2-4*x01*x11*x12^2+x02*x09*x12^2-x02*x08*x12^2-x02*x07*x12^2+2*x02*x06*x12^2+x02*x05*x12^2-2*x02*x04*x12^2-x10*x11^2*x12-2*x09*x11^2*x12-x08*x11^2*x12-x07*x11^2*x12-3*x06*x11^2*x12-2*x05*x11^2*x12-4*x01*x11^2*x12-x02*x10*x11*x12+x02*x09*x11*x12-2*x02*x08*x11*x12+3*x02*x06*x11*x12+3*x02*x05*x11*x12-6*x02*x04*x11*x12-x02^2*x06*x12+x02^2*x04*x12-x02*x10*x11^2-x02*x08*x11^2+x02*x07*x11^2+x02*x06*x11^2+2*x02*x05*x11^2-4*x02*x04*x11^2-x02^2*x06*x11+x02^2*x04*x11");

for (var i = 0; i < 100; i++) {
  System.out.println(i);
  var f = MultivariateFactorization.Factor(p);
}

In a "fresh" run in my environment, it stops printing numbers at 8. But if I insert some calculations before executing the above loop, the number can be changed. Is there a kind of "cache" in Rings that might give such behaviour??

[tueda]

Actually, I see the next number 9 after some minutes, and then 10...32 printed in one go after a few minutes. So it's like an extreme slowdown rather than a freeze.

[PoslavskySV]

Hi Takahiro!

Internally, Factorization and GCD algorithms use random number generator to generate random substitutions. For some input polynomials there is a higher probability to meet "bad" substitutions which cause to a longer computation. That's why you see so different computation time even for the same input. In fact, I spent a looot of time seeking for such inputs and trying to improve the algorithms and reduce the probability to meet "bad" substitutions). I'll look deeply on the polynomial you provided to figure out whether the algorithm may be improved more.

[tueda]

Thanks for your comment. I remember that FORM also has "unlucky cases" in its GCD algorithm, so I understand Rings may have a similar problem, too. It sounds a tough problem, but still it will be great if the algorithm could be improved to avoid such really slow cases.

[tueda]

It seems that the ordering of the variables affects the timing in the unlucky cases. I tried to change the variable order by renameVariables (on top of orderByDegrees in factorPrimitiveInZ) for the polynomial in the above example:

order	average timing in the unlucky cases (seconds)
original	176.86
descending in occurrence	25.08
ascending in occurrence	137.66

Maybe I should change the variable order on my side when I perform polynomial factorization, though I'm not sure if such a performance gain can always be expected in general.

Details of the test

package cc.redberry.rings;

import org.junit.Test;

import cc.redberry.rings.bigint.BigInteger;
import cc.redberry.rings.poly.multivar.AMultivariateTest;
import cc.redberry.rings.poly.multivar.Monomial;
import cc.redberry.rings.poly.multivar.MultivariateFactorization;
import cc.redberry.rings.poly.multivar.MultivariatePolynomial;
import cc.redberry.rings.util.ArraysUtil;

public class MyTest extends AMultivariateTest {
    @Test
    public void test1() {
        MultivariatePolynomial<BigInteger> p = MultivariatePolynomial.parse("x12^2-7*x11*x12-x02*x12-x02*x11-x12^3+6*x11*x12^2-x03*x12^2+x02*x12^2+7*x11^2*x12+2*x10*x11*x12+2*x09*x11*x12+2*x08*x11*x12+4*x06*x11*x12+2*x04*x11*x12-x03*x11*x12+2*x02*x11*x12+4*x01*x11*x12+x02*x03*x12+x02*x11^2-2*x02*x06*x11+2*x02*x04*x11+x02*x03*x11-x09*x12^3+x08*x12^3+x07*x12^3-x06*x12^3-x05*x12^3+x04*x12^3-x10*x11*x12^2-3*x09*x11*x12^2-4*x06*x11*x12^2-3*x05*x11*x12^2+x04*x11*x12^2-4*x01*x11*x12^2+x02*x09*x12^2-x02*x08*x12^2-x02*x07*x12^2+2*x02*x06*x12^2+x02*x05*x12^2-2*x02*x04*x12^2-x10*x11^2*x12-2*x09*x11^2*x12-x08*x11^2*x12-x07*x11^2*x12-3*x06*x11^2*x12-2*x05*x11^2*x12-4*x01*x11^2*x12-x02*x10*x11*x12+x02*x09*x11*x12-2*x02*x08*x11*x12+3*x02*x06*x11*x12+3*x02*x05*x11*x12-6*x02*x04*x11*x12-x02^2*x06*x12+x02^2*x04*x12-x02*x10*x11^2-x02*x08*x11^2+x02*x07*x11^2+x02*x06*x11^2+2*x02*x05*x11^2-4*x02*x04*x11^2-x02^2*x06*x11+x02^2*x04*x11");

        for (int i = 0; i < 100; i++) {
            System.out.print(i);
            long t0 = System.nanoTime();
            MultivariateFactorization.Factor(p);
            long dt = System.nanoTime() - t0;
            System.out.println(": " + dt / 1000000000.0);
        }
    }
    
    @Test
    public void test2() {
        MultivariatePolynomial<BigInteger> p = MultivariatePolynomial.parse("x12^2-7*x11*x12-x02*x12-x02*x11-x12^3+6*x11*x12^2-x03*x12^2+x02*x12^2+7*x11^2*x12+2*x10*x11*x12+2*x09*x11*x12+2*x08*x11*x12+4*x06*x11*x12+2*x04*x11*x12-x03*x11*x12+2*x02*x11*x12+4*x01*x11*x12+x02*x03*x12+x02*x11^2-2*x02*x06*x11+2*x02*x04*x11+x02*x03*x11-x09*x12^3+x08*x12^3+x07*x12^3-x06*x12^3-x05*x12^3+x04*x12^3-x10*x11*x12^2-3*x09*x11*x12^2-4*x06*x11*x12^2-3*x05*x11*x12^2+x04*x11*x12^2-4*x01*x11*x12^2+x02*x09*x12^2-x02*x08*x12^2-x02*x07*x12^2+2*x02*x06*x12^2+x02*x05*x12^2-2*x02*x04*x12^2-x10*x11^2*x12-2*x09*x11^2*x12-x08*x11^2*x12-x07*x11^2*x12-3*x06*x11^2*x12-2*x05*x11^2*x12-4*x01*x11^2*x12-x02*x10*x11*x12+x02*x09*x11*x12-2*x02*x08*x11*x12+3*x02*x06*x11*x12+3*x02*x05*x11*x12-6*x02*x04*x11*x12-x02^2*x06*x12+x02^2*x04*x12-x02*x10*x11^2-x02*x08*x11^2+x02*x07*x11^2+x02*x06*x11^2+2*x02*x05*x11^2-4*x02*x04*x11^2-x02^2*x06*x11+x02^2*x04*x11");

        // Swap variables in the ordering of occurrence.
        int[] occurrence = new int[p.nVariables];
        for (Monomial<BigInteger> t : p) {
            for (int i = 0; i < p.nVariables; i++) {
                if (t.exponents[i] >= 1) {
                    occurrence[i]--; // descending
                }
            }
        }
        int[] newVariables = new int[p.nVariables];
        for (int i = 0; i < newVariables.length; i++) {
            newVariables[i] = i;
        }
        ArraysUtil.timSort(occurrence, newVariables);
        p = MultivariatePolynomial.renameVariables(p, newVariables);

        for (int i = 0; i < 100; i++) {
            System.out.print(i);
            long t0 = System.nanoTime();
            MultivariateFactorization.Factor(p);
            long dt = System.nanoTime() - t0;
            System.out.println(": " + dt / 1000000000.0);
        }
    }
    
    @Test
    public void test3() {
        MultivariatePolynomial<BigInteger> p = MultivariatePolynomial.parse("x12^2-7*x11*x12-x02*x12-x02*x11-x12^3+6*x11*x12^2-x03*x12^2+x02*x12^2+7*x11^2*x12+2*x10*x11*x12+2*x09*x11*x12+2*x08*x11*x12+4*x06*x11*x12+2*x04*x11*x12-x03*x11*x12+2*x02*x11*x12+4*x01*x11*x12+x02*x03*x12+x02*x11^2-2*x02*x06*x11+2*x02*x04*x11+x02*x03*x11-x09*x12^3+x08*x12^3+x07*x12^3-x06*x12^3-x05*x12^3+x04*x12^3-x10*x11*x12^2-3*x09*x11*x12^2-4*x06*x11*x12^2-3*x05*x11*x12^2+x04*x11*x12^2-4*x01*x11*x12^2+x02*x09*x12^2-x02*x08*x12^2-x02*x07*x12^2+2*x02*x06*x12^2+x02*x05*x12^2-2*x02*x04*x12^2-x10*x11^2*x12-2*x09*x11^2*x12-x08*x11^2*x12-x07*x11^2*x12-3*x06*x11^2*x12-2*x05*x11^2*x12-4*x01*x11^2*x12-x02*x10*x11*x12+x02*x09*x11*x12-2*x02*x08*x11*x12+3*x02*x06*x11*x12+3*x02*x05*x11*x12-6*x02*x04*x11*x12-x02^2*x06*x12+x02^2*x04*x12-x02*x10*x11^2-x02*x08*x11^2+x02*x07*x11^2+x02*x06*x11^2+2*x02*x05*x11^2-4*x02*x04*x11^2-x02^2*x06*x11+x02^2*x04*x11");

        // Swap variables in the ordering of occurrence.
        int[] occurrence = new int[p.nVariables];
        for (Monomial<BigInteger> t : p) {
            for (int i = 0; i < p.nVariables; i++) {
                if (t.exponents[i] >= 1) {
                    occurrence[i]++; // ascending
                }
            }
        }
        int[] newVariables = new int[p.nVariables];
        for (int i = 0; i < newVariables.length; i++) {
            newVariables[i] = i;
        }
        ArraysUtil.timSort(occurrence, newVariables);
        p = MultivariatePolynomial.renameVariables(p, newVariables);

        for (int i = 0; i < 100; i++) {
            System.out.print(i);
            long t0 = System.nanoTime();
            MultivariateFactorization.Factor(p);
            long dt = System.nanoTime() - t0;
            System.out.println(": " + dt / 1000000000.0);
        }
    }
}

mvn test -Dtest=MyTest#test1

=====> test1
0: 0.07376372
1: 0.014621541
2: 0.010860844
3: 0.008875401
4: 0.008804217
5: 0.007605308
6: 0.009518571
7: 0.006920819
8: 197.308490092
9: 191.067706148
10: 0.004234122
11: 0.003747574
12: 0.003391099
13: 0.003463985
14: 0.003084134
15: 0.003175468
16: 0.003330125
17: 0.003238272
18: 0.004062669
19: 0.003268515
20: 0.003152959
21: 0.002781575
22: 0.002896663
23: 0.002955142
24: 0.002976685
25: 0.00268495
26: 0.002883111
27: 0.002776844
28: 0.00259033
29: 0.00263594
30: 0.002591985
31: 0.002687365
32: 186.27058497
33: 0.003092706
34: 179.132731072
35: 0.002768554
36: 0.002403566
37: 0.002469981
38: 0.002690879
39: 0.002670427
40: 149.647482709
41: 0.003102256
42: 0.002549881
43: 0.002471611
44: 0.002391318
45: 0.002293202
46: 0.002496277
47: 0.002518921
48: 145.690821442
49: 181.403473669
50: 183.270232262
51: 0.002201739
52: 0.002398173
53: 183.255332734
54: 0.003051846
55: 0.002919319
56: 0.002558816
57: 0.002808861
58: 0.002826645
59: 0.002813113
60: 0.002741599
61: 0.00274578
62: 182.388219622
63: 0.002476043
64: 0.002457568
65: 0.002154643
66: 0.002042487
67: 0.002203935
68: 0.004081067
69: 0.002519297
70: 0.00221388
71: 0.002271933
72: 0.002225954
73: 0.002068716
74: 183.806322924
75: 0.00296363
76: 0.002531368
77: 0.002634926
78: 182.775195432
79: 146.722604968
80: 0.002306564
81: 0.002122114
82: 0.00188994
83: 0.002025933
84: 0.00194343
85: 0.001859711
86: 0.002000978
87: 0.001976069
88: 0.001779567
89: 183.368757651
90: 0.002287749
91: 0.002194148
92: 0.001949804
93: 0.002343386
94: 0.002229792
95: 0.002071427
96: 0.002021948
97: 0.002183237
98: 0.002051868
99: 0.002033179
=====> test1   elapsed 2476s

mvn test -Dtest=MyTest#test2

=====> test2
0: 0.081365877
1: 0.011688586
2: 0.010743654
3: 0.009819582
4: 0.00905353
5: 0.008209971
6: 0.008778644
7: 0.006999531
8: 0.006914507
9: 0.006015486
10: 26.778404652
11: 0.004942124
12: 0.004097134
13: 0.004984292
14: 0.003883353
15: 0.003876693
16: 0.003886614
17: 0.003900457
18: 0.003480654
19: 0.003472879
20: 0.003353949
21: 25.235089718
22: 0.003492255
23: 0.003296968
24: 0.003052164
25: 0.002792401
26: 0.003176749
27: 0.003003138
28: 0.002935639
29: 0.003474299
30: 25.351953009
31: 0.003803902
32: 0.002775095
33: 0.00252404
34: 0.002654716
35: 0.002535835
36: 0.002524563
37: 0.002493832
38: 0.002495205
39: 0.00242247
40: 0.002427596
41: 0.002642493
42: 0.002339137
43: 0.002440325
44: 25.099107161
45: 24.683744791
46: 0.002440184
47: 0.002298186
48: 0.002242948
49: 0.002383915
50: 0.002414651
51: 0.002503272
52: 0.002326023
53: 0.002434714
54: 0.002598794
55: 25.100562743
56: 24.822347203
57: 0.002274756
58: 0.002300426
59: 0.002214283
60: 0.002216823
61: 0.002327572
62: 0.002228334
63: 0.002452498
64: 0.002095965
65: 0.002235068
66: 0.002225231
67: 0.002339113
68: 0.002262052
69: 0.00215243
70: 0.002303555
71: 25.084084419
72: 0.002625527
73: 0.002399213
74: 0.002447312
75: 0.002304361
76: 0.002233108
77: 0.00212554
78: 0.002059492
79: 0.002010056
80: 0.002267423
81: 25.409743859
82: 24.660632892
83: 24.580729398
84: 0.002531152
85: 0.002257465
86: 0.002115184
87: 24.662504057
88: 0.0022764
89: 0.002131402
90: 0.00201272
91: 0.003429151
92: 0.002501752
93: 24.833177587
94: 0.002360722
95: 0.002358717
96: 24.833454372
97: 0.00233716
98: 0.002362917
99: 0.002223104
=====> test2   elapsed 351s

mvn test -Dtest=MyTest#test3

=====> test3
0: 0.110006149
1: 0.016299088
2: 0.016490834
3: 148.936026966
4: 0.006982505
5: 144.791127194
6: 0.00529703
7: 145.827081312
8: 144.998967145
9: 0.004635236
10: 0.004204207
11: 0.003203034
12: 0.003566112
13: 0.003279009
14: 0.003243
15: 0.002911987
16: 0.003129228
17: 0.003007777
18: 0.004031487
19: 142.911397365
20: 145.538009614
21: 0.003426077
22: 0.003052327
23: 148.058752773
24: 0.002939167
25: 0.002419408
26: 0.002483596
27: 0.003006678
28: 0.00259792
29: 0.002562078
30: 0.002513054
31: 0.002599025
32: 0.002483446
33: 0.002736284
34: 147.043445908
35: 0.002860874
36: 0.002390645
37: 0.002351558
38: 0.002404848
39: 0.002385914
40: 0.024599301
41: 153.287441021
42: 0.002771361
43: 0.002538687
44: 0.002439564
45: 0.002445547
46: 0.002093774
47: 0.002228507
48: 107.890538983
49: 146.367420769
50: 0.002260746
51: 0.002054458
52: 0.002274844
53: 0.002304843
54: 0.002498291
55: 0.002395237
56: 0.002206822
57: 0.002377196
58: 0.002335134
59: 0.00208649
60: 0.002458643
61: 0.002368529
62: 0.002169968
63: 0.002279553
64: 0.002279631
65: 0.002171727
66: 0.002216525
67: 0.002201143
68: 0.002268846
69: 0.002212055
70: 0.002123309
71: 0.00231357
72: 0.002146
73: 145.840434397
74: 0.002486338
75: 0.002189689
76: 0.00217425
77: 0.002152585
78: 0.002026583
79: 0.002074577
80: 103.02491469
81: 0.002555603
82: 102.702630151
83: 0.002211907
84: 0.00205252
85: 0.002121825
86: 0.002048392
87: 0.002087853
88: 0.002058085
89: 0.002049887
90: 0.002046843
91: 0.002045892
92: 0.001926907
93: 0.001897797
94: 0.002229495
95: 0.001975443
96: 0.001957455
97: 0.001873246
98: 0.002106049
99: 0.002083967
=====> test3   elapsed 1927s

[PoslavskySV]

Hi Takahiro!

Thanks for your research on the problem and for the solution. I have finally implemented your idea with additional sort of variables by occurrences and it really speeds up some unlucky cases. The reason for this speed up is that when we reduce polynomial to its bivariate image during factorization, we may assume that (on average) the larger the number of terms in the image - the less the probability to meet "unlucky" bivariate factorization (e.g. when initial poly is irreducible while "unlucky" image is reducible); so it is better to choose unevaluated variables so that the image has more terms.

[tueda]

That sounds very nice! Though more testing may be needed, at some point, do you have a plan to make a release? I'm a Gradle user (example in my benchmark program) and it is the easiest to use pre-built JAR files for the Gradle build (though I could try to use source dependencies, which may work).

[PoslavskySV]

Sure, I will make a release within this week!