prclibo / gaps Goto Github PK
View Code? Open in Web Editor NEWGAPS: A Generator for Automatic Polynomial Solvers
License: BSD 3-Clause "New" or "Revised" License
gaps's People
Stargazers
Watchers
gaps's Issues
Trying GAPs on a nine variable problem; generated solver is inaccurate
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
Error in cg_extract_solutions for 7 variable system
Hello,
I have a system with 7 variables, and on Mcaulay2, I can generate a zero dim Ideal from it. However, when I run the generate_solver.m function, I get the error:
Error using assert
Assertion failed.
Error in cg_extract_solutions (line 7)
assert(numel(unk_vars) == numel(scheme));
Full trace:
Problem Config:
rand_seed: 23
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
u_3: u_3
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
u_3: u_3
u_4: u_4
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
u_3: u_3
in =
struct with fields:
a_3: a_3
a_4: a_4
u_1: u_1
u_2: u_2
u_3: u_3
u_4: u_4
Sampling Zp instances
...In total 8 terms
...Evaluating instances for 8
Elapsed time is 0.841998 seconds.
-- Sampled.
-------------------------------------------------
generate_solverChecking for symmetry. max_p = 2
Elapsed time is 1.300600 seconds.
-- Found 0 symmetries.
./cache/find_monomial_basis.solver_VLVP_problem_woA.1.m2
Macaulay2, version 1.21
with packages: ConwayPolynomials, Elimination, IntegralClosure, InverseSystems,
Isomorphism, LLLBases, MinimalPrimes, OnlineLookup,
PrimaryDecomposition, ReesAlgebra, Saturation, TangentCone
Problem has (at most) 1 solutions.
Quotient ring basis (degree = 1)
B = [ 1 ]
Action monomial = [ a_1 a_2 v_1 v_2 v_3 l_1 l_2 ]
Elapsed time is 0.134153 seconds.
Monomials to reduce: (7 monomials)
R = [ a_1, a_2, v_1, v_2, v_3, l_1, l_2 ]
Finding elimination templates ... ./cache/find_template.solver_VLVP_problem_woA.1.m2
Macaulay2, version 1.21
with packages: ConwayPolynomials, Elimination, IntegralClosure, InverseSystems,
Isomorphism, LLLBases, MinimalPrimes, OnlineLookup,
PrimaryDecomposition, ReesAlgebra, Saturation, TangentCone
OK
Found 7 elimination templates.
action_a_1 - 49 rows, 1 basis, 1 reducible,
action_a_2 - 47 rows, 1 basis, 1 reducible,
* action_v_1 - 23 rows, 1 basis, 1 reducible,
action_v_2 - 23 rows, 1 basis, 1 reducible,
action_v_3 - 23 rows, 1 basis, 1 reducible,
action_l_1 - 48 rows, 1 basis, 1 reducible,
action_l_2 - 48 rows, 1 basis, 1 reducible,
Extracting template coefficients... OK (47 found)
Building solver (solver_VLVP_problem_woA_action_v_1)
Warning: unable to extract: x1 x2 x4 x5 x6 x7
> In find_extraction_scheme>extract_variables (line 142)
In find_extraction_scheme (line 30)
In finalize_template (line 7)
In generate_solver (line 199)
Elimination template size = [23,38], nnz = 136
Error using assert
Assertion failed.
Error in cg_extract_solutions (line 7)
assert(numel(unk_vars) == numel(scheme));
Error in generate_code (line 36)
str = [str cg_extract_solutions(solv,template,opt)];
Error in generate_solver (line 219)
solv.templates{tk} = generate_code(name,solv,solv.templates{tk},opt);
Do you have an idea on why this happens?
For reference, the Mcaulay2 code:
load "EigenSolver.m2"
gbTrace = 3
R = QQ[l_1..l_2, v_1..v_3,a_1..a_4,u_1..u_4]
vars R
-- -- Ideal with all a, and u as variables
I = ideal(-l_1*v_3*a_1*u_1-l_2*v_3*a_1*u_2-l_1*v_3*u_3+l_1*v_1-v_3*a_1-a_1+1,-l_1*v_3*a_2*u_1-l_2*v_3*a_2*u_2-l_1*v_3*u_4+l_1*v_2-v_3*a_2-a_2,-l_1*v_3*a_3*u_1-l_2*v_3*a_3*u_2-l_2*v_3*u_3+l_2*v_1-v_3*a_3-a_3,-l_1*v_3*a_4*u_1-l_2*v_3*a_4*u_2-l_2*v_3*u_4+l_2*v_2-v_3*a_4-a_4+1,l_1*v_1+l_2*v_2+v_3,l_1*v_2*u_1+(l_2*v_2+1)*u_2+v_2-(l_1*v_3*u_1+l_2*v_3*u_2+v_3+1)*u_4,-(l_1*v_1+1)*u_1-l_2*v_1*u_2-v_1+(l_1*v_3*u_1+l_2*v_3*u_2+v_3+1)*u_3,((l_1*v_1+1)*u_1+l_2*v_1*u_2+v_1)*u_4-(l_1*v_2*u_1+(l_2*v_2+1)*u_2+v_2)*u_3)
dim I, degree I -- (6,105)
r1 = flatten entries random(R^1, R^6)
s1 = apply(toList(a_1,a_2,u_1,u_2,u_3,u_4), r1, (x,v)->x=>v)
R2 = QQ[l_1..l_2, v_1..v_3,a_3..a_4]
J = sub(sub(I, s1),R2)
dim J, degree J -- (0,1)
S = flatten apply(zeroDimSolve(J),x->x.Coordinates)
netList {flatten entries vars R2, S}
I've also attached my .m code
VLVP_problem_woA.txt
Issue with examples
Using Matlab2019b to run gen_pc_relpose_5p_nulle_ne__simple.m results in following error:
Error using cell2struct
Number of field names must match number of fields in new structure.
Error in problem.unpack_pars (line 173)
var_subs = cell2struct(vals, pars);
Error in problem/rand_eq_zp (line 69)
unk_zp = obj.unpack_pars(obj.out_subs, out_zp);
Error in generate_solver (line 17)
[solv.eqs_zp{i}, in_zp, out_zp] = prob.rand_eq_zp(opt.prime_field);
Error in gen_pc_relpose_5p_nulle_ne__simple (line 6)
[solv, opt] = generate_solver(prob_fn, opt);
4 variable problem and the solver is inaccurate
here is my gen code:
% 80 solutions, but I also cal a Q. [664,744]
clc
clear all
close all
cd ('/home/xbh/gaps');
setpath
opt = default_options();
opt.M2_path = '/usr/bin/M2';
opt.optimize_coefficients = true;
%opt.use_sym = true;%
opt.use_sym = false;
%opt.eigen_solver = 'sturm';
%opt.default_opt.syzygy_reduction = 0;
%default_opt.find_sym = 0;
%default_opt.cg_max_stack_alloc_size = 10000;
%random seed len = 5
%opt.use_sym = true;%bohuan,change here
%opt.prime_field = 999983
% opt.force_vars_in_reducibles = true;
%opt.remove_extra_columns = false;
% opt.find_upper_trianglar = true;
opt.M2_gbTrace = 3;
config.rand_seed = 4;
prob_fn = @() prob_sQPEP_pTop_merge_scale_opt(config);
[solv, opt] = generate_solver(prob_fn, opt);
solv_fun = str2func(['solver_' solv.name]);
stats = benchmark_solver(solv_fun,solv.prob,1);
stats.res_mean
and here is prob code
classdef prob_sQPEP_pTop_merge_scale_opt < problem
methods
function [in_subs, out_subs] = gen_arg_subs(obj)
in_subs.V = sym('V%d', [4, 24]); %W
out_subs.q = sym('q', [4, 1]);
end
function [eqs_sym, abbr_subs] = gen_eqs_sym(obj)
[in, out] = obj.gen_arg_subs();
q0 = out.q(1); q1 = out.q(2); q2 = out.q(3); q3 = out.q(4);
V = in.V;
mon = [q0^3, q0^2*q1, q0^2*q2, q0^2*q3, q0*q1^2, q0*q1*q2, q0*q1*q3, q0*q2^2, q0*q2*q3, q0*q3^2, q0, q1^3, q1^2*q2, q1^2*q3, q1*q2^2, q1*q2*q3, q1*q3^2, q1, q2^3, q2^2*q3, q2*q3^2, q2, q3^3, q3];
eqs_sym = sym(zeros(1, 4));
eqs_sym(1:4) = V*mon.';
abbr_subs = struct;
end
function [in_zp, out_zp] = rand_arg_zp(obj, p)
%in_zp.W = sym(randi(p,[4, 364]) - 1);
pnum = firstNPrimes(3000);
in_zp.V = sym(reshape(pnum(end-96+1:end),4,24));
%in_zp.V = reshpae(in_zp.V, 4,24);
%in_zp.V = sym(randi(p,[1, 85]) - 1);
out_zp = struct;
return;
end
function [in_rl, out_rl] = rand_arg_rl(obj)
load gap_test_coef.mat
load gap_test_q.mat
in_rl.V = eval(gap_test_coef);
out_rl.q = (gap_test_q);
%out_rl.q(1) = 5;
%out_rl.q = rand(4,1);
return;
end
end
end
and I also have a test code
`
function [ret] = test_raw_sQPEP_pTop_merge_scale_opt(q, V)
q0 = q(1); q1 = q(2); q2 = q(3); q3 = q(4);
mon = [q0^3, q0^2*q1, q0^2*q2, q0^2*q3, q0*q1^2, q0*q1*q2, q0*q1*q3, q0*q2^2, q0*q2*q3, q0*q3^2, q0, q1^3, q1^2*q2, q1^2*q3, q1*q2^2, q1*q2*q3, q1*q3^2, q1, q2^3, q2^2*q3, q2*q3^2, q2, q3^3, q3];
eqs_sym = sym(zeros(1, 4));
eqs_sym(1:4) = V*mon.';
ret = eqs_sym(1:4);
end
`
here is the input q and coefs for test:
q=[ 1.96311188200896 -4.30421002705708 0.489905513962989 -1.54271201754741];
gap_test_coef =
[ 1.4076645091570793962010288424835, 0.000000000000000006661338147750939242541715621793, 4.3108136395448599947899381845673, 0.000000000000000053290705182007513940334310560157, 12.247142407671135946323204279906, -0.00000000000000064837024638109141960740054151673, 3.5735565960713346966848291685892, 10.539531399935745601403880300495, -0.00000000000000049737991503207013010978708097689, -0.5732433005076007176414876198578, -32.034416345755692316632501359663, 0.000000000000000048849813083506887778639787426689, 0.8422582412477041224896368021291, -0.00000000000000068833827526759705506265216686219, 0.00000000000000010214051826551440171897416672894, -1.0000956079901343853677531114954, -0.00000000000000018651746813702629879117012666774, 91.44232599024140386523296086807, -1.1333355319246022700763187884831, 0.00000000000000035083047578154946677386777609401, -1.7530652850187575819695950940513, -102.68918282876377806700496364556, -1.946123307254305948098875645273e-41, 5.5144855338041046968755587442956]
[0.0000000000000000022204460492503130808472385405977, 12.247142407671135946323204279906, -0.00000000000000032418512319054570980370027075837, 1.7867782980356673483424145842946, 0.00000000000000014654943925052066333591936228007, 1.6845164824954082449792736042582, -0.0000000000000013766765505351941101253043337244, 0.00000000000000010214051826551440171897416672894, -1.0000956079901343853677531114954, -0.00000000000000018651746813702629879117012666774, 91.44232599024140386523296086807, 1.6028662771392940157726722354148, 0.00000000000000023980817331903381273150446148718, 2.6794279003955300068329226093056, -0.0060847964642836838145001365774078, 0.00000000000000024868995751603506505489356344732, 9.3867675919457851885230326161036, -42.808146834907816889233961310524, -0.000000000000000059952043329758453182876112143203, -0.78384809634842548597966072065901, 0.00000000000000043964831775156199000775823607288, 1.222937027661787420251826574713, -1.2274527006942574247627675276817, -97.648788369199031787898368506262]
[ 1.4369378798482866649299793948558, -0.00000000000000032418512319054570980370027075837, 10.539531399935745601403880300495, -0.00000000000000024868995751603506505489354048845, 0.8422582412477041224896368021291, 0.00000000000000020428103653102880343794833345789, -1.0000956079901343853677531114954, -3.4000065957738068102289563654494, 0.00000000000000070166095156309893354773555218802, -1.7530652850187575819695950940513, -102.68918282876377806700496364556, 0.000000000000000079936057773011270910501487162393, -0.0060847964642836838145001365774078, 0.00000000000000012434497875801753252744678172366, -0.00000000000000017985612998927535954862833642961, -1.567696192696850971959321441318, 0.00000000000000043964831775156199000775823607288, 1.222937027661787420251826574713, 1.2135224215174643009689219984998, 0.00000000000000032640556923979602288454768149052, 12.26241016654666465379719397788, 37.557016213761340110936087777205, -0.0000000000000000044408920985006261616945229989434, -91.136182312818443795321421418976]
[ 0.000000000000000017763568394002504646778103520052, 1.7867782980356673483424145842946, -0.00000000000000024868995751603506505489354048845, -0.5732433005076007176414876198578, -0.00000000000000068833827526759705506265216686219, -1.0000956079901343853677531114954, -0.00000000000000037303493627405259758234025333549, 0.00000000000000035083047578154946677386777609401, -3.5061305700375151639391901881027, -5.8383699217629178442966269358191e-41, 5.5144855338041046968755587442956, 0.89314263346517666894430753643519, 0.00000000000000012434497875801753252744678172366, 9.3867675919457851885230326161036, -0.78384809634842548597966072065901, 0.00000000000000087929663550312398001551647214576, -3.6823581020827722742883025830452, -97.648788369199031787898368506262, 0.00000000000000010880185641326534096151589383017, 12.26241016654666465379719397788, -0.00000000000000001332267629550187848508356899683, -91.136182312818443795321421418976, 1.786829858861890293411645025401, 37.285546966902169835345048909403]
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.