Matrix-vector multiplication multivariable polynomials

edgarcosta commented 7 years ago

On a machine with a 2.3 GHz Intel Xeon E5 v3 with sage compiled from the source

If you run the following code

p = 107
R = Integers(p**2)
Rpoly = PolynomialRing(R, 2, "z")
d = 64;
M0 = Matrix(R, [[R.random_element() for _ in range(d)] for _ in range(d)])
G = vector(Rpoly, [R.random_element() for _ in range(d)])
for k in range(p):
    G = M0*G;

on Sage 7.5.1 it will run much slower than on previous versions, e.g., 7.3.

Sage 7.3:


real    0m4.474s
user    0m4.196s
sys     0m0.276s

Sage 7.5:

real    1m25.435s
user    1m24.888s
sys     0m0.464s

Here are the flags

cpuflags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology eagerfpu pni pclmulqdq ssse3 fma cx16 sse4_1 sse4_2 x2apic movbe popcnt aes xsave avx f16c rdrand hypervisor lahf_lm abm fsgsbase bmi1 avx2 smep bmi2 erms xsaveopt

I suspect that the underlying library stop taking advantage of some flag. Let me know if there is anything else I can do to help out to figure out this.

I also ran the same code on my desktop, with a 3.3GHz Intel Core i5-4590, and there the running times from Sage 6.9 to 7.5 (built or not built from source) are all around the 16min mark.

The CPU flags in that case are:

machdep.cpu.features: FPU VME DE PSE TSC MSR PAE MCE CX8 APIC SEP MTRR PGE MCA CMOV PAT PSE36 CLFSH DS ACPI MMX FXSR SSE SSE2 SS HTT TM PBE SSE3 PCLMULQDQ DTES64 MON DSCPL VMX SMX EST TM2 SSSE3 FMA CX16 TPR PDCM SSE4.1 SSE4.2 x2APIC MOVBE POPCNT AES PCID XSAVE OSXSAVE SEGLIM64 TSCTMR AVX1.0 RDRAND F16C
machdep.cpu.leaf7_features: SMEP ERMS RDWRFSGS TSC_THREAD_OFFSET BMI1 HLE AVX2 BMI2 INVPCID RTM FPU_CSDS
machdep.cpu.extfeatures: SYSCALL XD 1GBPAGE EM64T LAHF LZCNT RDTSCP TSCI

Component: build: configure

Keywords: speed, matrix

Issue created by migration from https://trac.sagemath.org/ticket/22330

edgarcosta commented 7 years ago

comment:1

For future me: pin down the commit that makes the difference (perhaps with git bisect)

and use git trac find to figure out what caused the change.

fchapoton commented 5 years ago

Changed keywords from none to speed, matrix

sagemath / sage

Matrix-vector multiplication multivariable polynomials #22330