(42S) matrix permanent

[Albert Chan]

(01-15-2024 12:33 PM)Werner Wrote:  timing:
order   42S     DM42
 5        0:18     0.05s
 7        1:31     0.22s
 9        7:10     1.03s
12  1:06:15     9.39s

The timing of order 12 for the 42S is but an estimate, fitting a logarithmic curve through the three data points (x=time/n, y=n), yielding a .99999.. correlation, so should be pretty good.

XCas> Digits := 5
XCas> N := float([5,7,9])
XCas> T := float([18,91,430])
XCas> correlation(N, ln(T/N))                      → 0.99999
XCas> c := linear_regression(N, ln(T/N))      → (0.64641,-1.954)

ln(t/n) = c[0]*n + c[1]
t/n = exp(c[1]) * exp(c[0])^n

--> time (sec) ≈ 0.14170 * n * 1.9087^n
--> n=12 time ≈ 3976 sec = 1:06:16

Fit is excellent, but formula does not make sense.
We would expect time proportional to number of terms = 2^(n-1)
Each term, time to update v's and get its product, plus getting j and d.

Below does not produce as good correlation, but make more sense.

XCas> correlation(N, T/2^N)                      → 0.99917
XCas> c := linear_regression(N, T/2^N)      → (0.069336,0.21908)

t/2^n = c[0]*n + c[1] = c[0] * (n + c[1]/c[0])

--> time (sec) ≈ 0.069336 * (n + 3.1596) * 2^n
--> n=12 time ≈ 4305 sec = 1:11:45