Extreme slowdown in polynomial factorization #71
Comments
|
Actually, I see the next number |
tueda
changed the title
|
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. |
|
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. |
|
It seems that the ordering of the variables affects the timing in the unlucky cases. I tried to change the variable order by
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 testpackage 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);
}
}
} |
|
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. |
|
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). |
|
Sure, I will make a release within this week! |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
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??The text was updated successfully, but these errors were encountered: