Trying GAPs on a nine variable problem; generated solver is inaccurate

[snsinha]

I was wondering if anyone has tried using the generator on somewhat large problem sizes (i.e. in terms of #variables) and whether the behavior I’m seeing is consistent with what can be expected.

I have nine quadratic equations in nine variables. GAPS takes about 3 hours to generate a solver (in Matlab). When I test that solver, I get a Matlab warning (Warning: Rank deficient, rank = 13095, tol = 6.999104e-11) and the correct solution is not close to any of the computed solutions. In contrast, my previous experiment was with a system of six quadratic equations. In that case, GAPS took under a minute to run and when I tested the generated solver, it was quite accurate.

Below, is the Matlab output from running GAPS (on the nine quadratic example). The number of monomials to reduce is indeed quite large, the rate of exponential growth with #variables was a surprise for me.

I am interested if anyone has some thoughts and ideas on how to address the issue.

Thanks,
Sudipta

------------------Output of GAPS ---------------
Sampling Zp instances
...In total 9 terms
...Evaluating instances for 9
eq_zp veritfied to be: [[0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]]
...In total 9 terms
...Evaluating instances for 9
eq_zp veritfied to be: [[0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]]
...In total 9 terms
...Evaluating instances for 9
eq_zp veritfied to be: [[0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]; [0]]
Elapsed time is 3.870332 seconds.
-- Sampled.

generate_solverChecking for symmetry. max_p = 2
Elapsed time is 5.119122 seconds.
-- Found 1 symmetries.
c = [ 1 1 1 1 1 0 0 0 0 ], p = 2
./cache/find_monomial_basis.solver_prob_exp9.1.m2
./cache/find_monomial_basis.solver_prob_exp9.2.m2
./cache/find_monomial_basis.solver_prob_exp9.3.m2
Problem has (at most) 512 solutions.
Quotient ring basis (degree = 512)
B = [ 1 x1 x1x5 x1x5x6 x1x5x6x9 ……………. x9^8 ]
Action monomial = [ x1 x2 x3 x4 x5 x6 x7 x8 x9 ]
Elapsed time is 79.627846 seconds.
Monomials to reduce: (1655 monomials)
R = [ x1^2, x1^2x5, x1^2x5x6, x1^2x5x6x9, ………………, x9^9 ]
Finding elimination templates ...
./cache/find_template.solver_prob_exp9.1.m2
./cache/find_template.solver_prob_exp9.2.m2
./cache/find_template.solver_prob_exp9.3.m2
OK
Found 9 elimination templates.
action_x1 - 20392 rows, 512 basis, 443 reducible,
action_x2 - 20392 rows, 512 basis, 441 reducible,
action_x3 - 20391 rows, 512 basis, 441 reducible,
action_x4 - 20391 rows, 512 basis, 420 reducible,
action_x5 - 20391 rows, 512 basis, 355 reducible,
action_x6 - 21157 rows, 512 basis, 374 reducible,
action_x7 - 21157 rows, 512 basis, 326 reducible,
action_x8 - 21157 rows, 512 basis, 255 reducible,
action_x9 - 21157 rows, 512 basis, 132 reducible,
Extracting template coefficients... OK (162 found)
Building solver (solver_prob_exp9_action_x5)
Elimination template size = [13163,13679], nnz = 213587
Writing to "solvers/solver_solver_prob_exp9.m"... OK

[prclibo]

Hi @snsinha

I just reply your Email in this thread.

1. Rank deficiency. I had similar experiences with certain problems. However, I did not find specific reasons yet. This seems related with the problem structure (easily ill-posed or not) and complexity. From your output, the problem has Quotient ring basis (degree = 512), meaning it "equivalent" to a univariate polynomial with 512 roots. This is an extremely large problem. The template size template size = [13163,13679] is also the largest I have ever met. So I am not surprise if we meet numerical issues with it. I think the usual problem size should be degree < 100 and template size < 500. See the tables in [1] or [2] for the summary of sizes of some common problems.

2. Solver speed. I am not surprised that such a large problem will be slow to solve. However, There is still a small hint: Setting opt.optimize_coefficients = true reduces output solver complexity by avoiding duplicated coefficients but may take time long. Setting the opposite saves time but outputs inefficient solvers.

[1] http://openaccess.thecvf.com/content_cvpr_2017/papers/Larsson_Efficient_Solvers_for_CVPR_2017_paper.pdf
[2] https://arxiv.org/pdf/2007.07686.pdf

[prclibo]

Another config to try.

-- Found 1 symmetries.
c = [ 1 1 1 1 1 0 0 0 0 ], p = 2

This means there is some symmetric structure in the unknowns. Although not optimistic for such large size, try flipping opt.use_sym and see if there is any different results.