13 static pair<matrix,matrix> RowReduce(matrix mat) {
15 int &v_max = fermat.vmax;
19 for(const_preorder_iterator i = tree.preorder_begin(); i != tree.preorder_end(); ++i) {
21 if(is_a<symbol>(e) || e.match(
a(
w))) rep_vs.append(e);
30 for(
auto vi : rep_vs) {
31 auto name =
"v" + to_string(fvi);
32 v2f[vi] = Symbol(name);
39 cout << rep_vs << endl;
40 throw Error(
"Fermat: Too many variables.");
43 for(
int i=v_max; i<fvi; i++) ss <<
"&(J=v" << i <<
");" << endl;
44 fermat.Execute(ss.str());
50 int nrow = mat.rows();
51 int ncol = mat.cols();
53 ss <<
"Array m[" << nrow <<
"," << ncol+1 <<
"];" << endl;
54 fermat.Execute(ss.str());
59 for(
int c=0; c<ncol; c++) {
60 for(
int r=0; r<nrow; r++) {
61 ss << mat(r,c).subs(
iEpsilon==0).subs(v2f) <<
",";
65 for(
int r=1; r<nrow; r++) ss <<
",0";
67 fermat.Execute(ss.str());
72 if(nrow>1100) sparse =
true;
73 if(sparse) fermat.Execute(
"Sparse([m]);");
74 fermat.Execute(
"Redrowech([m],[t]);");
75 ss <<
"&(U=1);" << endl;
76 matrix mr(nrow, ncol);
78 if(sparse) ss <<
"![m]" << endl;
79 else ss <<
"![m" << endl;
80 auto ostr = fermat.Execute(ss.str());
85 if(ostr[ostr.length()-1]!=
'0')
throw Error(
"RowReduce, last char is NOT 0.");
86 ostr = ostr.substr(0, ostr.length()-1);
89 ostr.erase(0, ostr.find(
":=")+2);
90 size_t sn = ostr.length();
92 for(
size_t i=0; i<sn; i++) {
96 if(sparse && i>0 && lc==
'}') ostr[i-1] =
',';
97 }
else if(c==
']') c =
'}';
98 else if(sparse && (c==
' '||c==
'\t'||c==
'\n'||c==
'\r'))
continue;
103 auto res = fp.Read(ostr);
105 for(
auto const & item : res) {
107 for(
auto const & it : item) {
108 if(r==-1) r =
ex2int(it)-1;
110 int c =
ex2int(it.op(0))-1;
116 for(
int r=0; r<nrow; r++) {
117 auto cur = res.op(r);
118 for(
int c=0; c<ncol; c++) mr(r,c) = cur.op(c);
122 matrix mt(nrow, nrow);
124 if(sparse) ss <<
"![t]" << endl;
125 else ss <<
"![t" << endl;
126 auto ostr = fermat.Execute(ss.str());
131 if(ostr[ostr.length()-1]!=
'0')
throw Error(
"Solver::Export, last char is NOT 0.");
132 ostr = ostr.substr(0, ostr.length()-1);
135 ostr.erase(0, ostr.find(
":=")+2);
136 size_t sn = ostr.length();
138 for(
size_t i=0; i<sn; i++) {
142 if(sparse && i>0 && lc==
'}') ostr[i-1] =
',';
143 }
else if(c==
']') c =
'}';
144 else if(sparse && (c==
' '||c==
'\t'||c==
'\n'||c==
'\r'))
continue;
148 auto res = fp.Read(ostr);
150 for(
auto const & item : res) {
152 for(
auto const & it : item) {
153 if(r==-1) r =
ex2int(it)-1;
155 int c =
ex2int(it.op(0))-1;
161 for(
int r=0; r<nrow; r++) {
162 auto cur = res.op(r);
163 for(
int c=0; c<nrow; c++) mt(r,c) = cur.op(c);
168 ss <<
"&(U=0);" << endl;
169 ss <<
"@([m],[t]);" << endl;
170 ss <<
"&_G;" << endl;
171 fermat.Execute(ss.str());
174 return make_pair(mr,mt);
181 int &v_max = fermat.
vmax;
184 for(
auto const & rv : smat)
for(
auto const & cv : rv.second) {
186 for(const_preorder_iterator i = tree.preorder_begin(); i != tree.preorder_end(); ++i) {
188 if(is_a<symbol>(e) || e.match(
a(
w))) rep_vs.append(e);
198 for(
auto vi : rep_vs) {
199 auto name =
"v" + to_string(fvi);
207 cout << rep_vs << endl;
208 throw Error(
"Fermat: Too many variables.");
211 for(
int i=v_max; i<fvi; i++) ss <<
"&(J=v" << i <<
");" << endl;
219 int nrow=-1, ncol=-1;
220 int rcur = 0, rtot = smat.size();
222 for(
auto const & rv : smat) {
224 if(rv.second.size()<1)
continue;
227 oss <<
"[" << r+1 <<
",";
228 int ccur = 0, ctot = rv.second.size();
229 for(
auto const & cv : rv.second) {
233 oss <<
"[" << c+1 <<
"," << cv.second.subs(
iEpsilon==0).subs(v2f) <<
"]";
234 if(ccur!=ctot) oss <<
",";
237 if(rcur!=rtot) oss <<
"`" << endl;
238 else oss <<
"];" << endl;
243 ss <<
"Array m[" << nrow <<
"," << ncol+1 <<
"] Sparse;" << endl;
248 ss <<
"[m]:=" << oss.str();
253 if(pn>0) fermat.
Execute(
"Redrowech([m],,,"+to_string(pn)+
");");
254 else fermat.
Execute(
"Redrowech([m]);");
255 ss <<
"&(U=1);" << endl;
258 ss <<
"![m]" << endl;
259 auto ostr = fermat.
Execute(ss.str());
264 if(ostr[ostr.length()-1]!=
'0')
throw Error(
"RowReduce, last char is NOT 0.");
265 ostr = ostr.substr(0, ostr.length()-1);
268 ostr.erase(0, ostr.find(
":=")+2);
269 size_t sn = ostr.length();
271 for(
size_t i=0; i<sn; i++) {
275 if(i>0 && lc==
'}') ostr[i-1] =
',';
276 }
else if(c==
']') c =
'}';
277 else if(c==
' '||c==
'\t'||c==
'\n'||c==
'\r')
continue;
282 auto res = fp.
Read(ostr);
283 for(
auto const & item : res) {
285 for(
auto const & it : item) {
286 if(r==-1) r =
ex2int(it)-1;
288 int c =
ex2int(it.op(0))-1;
289 smat[r][c] = it.op(1);
295 ss <<
"&(U=0);" << endl;
296 ss <<
"@([m]);" << endl;
297 ss <<
"&_G;" << endl;
311 for(
int i=0; i<pdim; i++) {
312 for(
int j1=0; j1<n; j1++)
for(
int j2=0; j2<n; j2++) {
313 ibps.append(ibps.op(i).subs(lst{a(j1)==a(j1)+1}).subs(lst{a(j2)==a(j2)-1}));
320 for(
int i=0; i<pdim; i++) {
321 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(
a(i)==
a(i)+1));
328 for(
int i=0; i<pdim; i++) {
329 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(
a(i)==
a(i)-1));
337 find(ibps, F(
w), fs);
341 for(
int i=0; i<fi.op(0).nops(); i++) a2a[
a(i)] = fi.op(0).op(i);
342 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(a2a));
346 for(
int i=0; i<fi.op(0).nops(); i++) a2a[
a(i)] = fi.op(0).op(i)+1;
347 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(a2a));
351 for(
int i=0; i<fi.op(0).nops(); i++) a2a[
a(i)] = fi.op(0).op(i)-1;
352 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(a2a));
357 vector<int> nfix(pdim);
358 for(
int i=0; i<pdim; i++) nfix[i] = 0;
360 for(
auto const & kv : n2n) {
363 if(k<0) k = pdim + k;
364 a2n[
a(k)] = kv.second;
367 int nibps = ibps.nops();
368 for(
int i=0; i<nibps; i++) ibps.let_op(i) = ibps.op(i).subs(a2n);
372 map<ex,lst,ex_is_less> cons_vec;
373 while(ibps.nops()>0) {
378 find(ibps,F(
w),fset);
379 map<int,exvector> fmap_vec;
380 for(
auto fi : fset) {
381 int psum = 0, nsum = 0;
383 for(
int i=0; i<pdim; i++) {
384 auto ni = ns.op(i).subs(
a(i)==0,
nopat);
385 if(sector.op(i)==1) {
386 if(nfix[i]==1 && ni<=0) psum -= 100000;
387 else psum +=
ex2int(ni)-1;
389 if(nfix[i]==1 && ni>0) nsum +=
ex2int(ni);
394 fmap_vec[-key].push_back(fi);
397 map<ex,int,ex_is_less> f2n;
399 exvector fvec(fset.size());
401 for(
auto const & ev : fmap_vec) {
402 if(next_gi<1) next_gi = ev.second.size();
403 for(
auto const & v : ev.second) {
413 cout <<
"+----------------------------------------" << endl;
414 cout <<
"| IBPs: " << nr <<
", Fs: " << next_gi <<
"/" << nc << endl;
415 cout <<
"+----------------------------------------" << endl;
419 for(
int r=0; r<nr; r++) {
420 auto ibp = ibps.op(r);
422 for(
auto & cv : cvs) {
423 int c = f2n[cv.op(1)];
425 if(!cc.is_zero()) smat[r][c] = cc;
428 RowReduce(smat,next_gi);
431 for(
auto const & rv : smat) {
432 int next_sol_ibp = -1;
436 for(
auto const & cv : rv.second) {
437 if(next_sol_ibp==-1) {
438 if(cv.first<next_gi) {
440 if(!is_zero(cv.second-1))
throw Error(
"Solver::SolveSparse, NOT 1.");
441 ns = fvec[cv.first].op(0).subs(
a(
w)==0);
442 for(
int i=0; i<pdim; i++) {
443 if(nfix[i]==0) amap[
a(i)] =
a(i)-ns.op(i);
445 fc = fvec[cv.first].subs(amap,
nopat);
446 for(
int i=0; i<pdim; i++) {
449 if(sector.op(i)==1 && nv[i]<1)
goto next_row;
450 else if(sector.op(i)!=1 && nv[i]>0)
goto next_row;
451 }
else nv[i] = (sector.op(i)==1 ? 1 : 0);
454 }
else next_sol_ibp = 2;
457 if(next_sol_ibp==0) {
458 if(cv.first<next_gi)
goto next_row;
463 ex f = fvec[cv.first];
465 if(next_sol_ibp==1) {
466 f = f.subs(amap,
nopat);
467 nd = nd.subs(amap,
nopat);
470 ns = f.op(0).subs(
a(
w)==0);
471 for(
int i=0; i<pdim; i++) {
472 if(sector.op(i)!=1) {
475 if(nsi>0)
goto next_row;
481 ex cci = num.subs(
a(i)==1+nsi);
482 if(!cci.is_zero() || nsi>=nv[i])
break;
485 if(nsi<nv[i]) nv[i] = nsi;
489 if(!is_a<mul>(den)) den = lst{ den };
490 for(
const auto & item : den) {
492 if(is_a<power>(it)) it = it.op(0);
493 if(!it.has(
a(
w)) || it.has(
d))
continue;
497 cout <<
"size is NOT 1: " << it << endl;
498 throw Error(
"Solver::SolveSparse, error occured.");
500 ex aw = *(
as.begin());
501 if(it.degree(aw)!=1) {
502 cout <<
"degree is NOT 1: " << it << endl;
503 throw Error(
"Solver::SolveSparse, error occured.");
505 ex a0 = -it.coeff(aw,0)/it.coeff(aw,1);
506 int an =
ex2int(aw.op(0));
507 if(sector.op(an)!=1) {
508 if(a0<=nv[an]) nv[an] = a0-1;
510 if(a0>=nv[an]) nv[an] = a0+1;
518 if(next_sol_ibp==1) {
519 for(
int i=0; i<pdim; i++) {
520 if(nfix[i]==1 && fc.op(0).op(i)!=nv[i]) {
521 cout << i <<
": " << fc << endl << nv << endl;
522 throw Error(
"Solver::SolveSparse, error occured.");
523 }
else if(nfix[i]==0 && fc.op(0).op(i)!=
a(i)) {
524 cout << i <<
": " << fc << endl << nv << endl;
525 throw Error(
"Solver::SolveSparse, error occured.");
530 int psum = 0, nsum = 0;
531 for(
int i=0; i<pdim; i++) {
532 if(nfix[i]==1)
continue;
533 if(sector.op(i)==1 && !nv[i].is_equal(1)) psum++;
534 if(sector.op(i)!=1 && !nv[i].is_zero()) nsum++;
536 if(psum<=1 && nsum<=1) {
539 cons_vec[con].append(sol);
542 }
else ibps.append(sol);
549 cout << cons << endl << endl;
550 for(
auto & item : cons) {
551 if(item==lst{1,1,1,1,1,1,1,1,1,1,0,0}) {
552 cout << endl << cons_vec[item] << endl << endl;
577 for(
auto ii :
Internal) InExternal.append(ii);
578 for(
auto ii :
External) InExternal.append(ii);
582 for(
auto ii : InExternal)
ISP.append(it*ii);
588 if(
ISP.nops() > pdim) {
589 cout <<
"ISP = " <<
ISP << endl;
590 cout <<
"Propagator = " <<
Propagator << endl;
591 throw Error(
"Solver::IBP: #(ISP) > #(Propagator).");
596 for(
auto item :
ISP) {
598 Symbol si(
"P"+to_string(_pic));
600 sp2s.append(
w*item==
w*si);
601 sp2s.append(item==si);
602 s2sp.append(si==item);
606 for(
int i=0; i<
ISP.nops(); i++) {
610 if(eq.has(iWF(
w)))
throw Error(
"Solver::IBP, iWF used in eq.");
611 leqns.append(eq == iWF(i));
613 auto s2p = lsolve(leqns, ss);
614 if(s2p.nops() !=
ISP.nops())
throw Error(
"Solver::IBP, lsolve failed.");
620 for(
auto p2 : InExternal)
621 DSP.append(lst{p1,p2});
627 for(
int i=0; i<
Internal.nops(); i++)
628 DSP.append(lst{Internal.op(i), Internal.op(i==Internal.nops()-1 ? 0 : i+1)});
629 for(
auto p2 : InExternal)
DSP.append(lst{
Internal.op(0), p2});
635 for(
int i=0; i<pdim; i++) nsa.append(
a(i));
642 for(
int i=0; i<pdim; i++) {
644 ns.let_op(i) = nsa.op(i) + 1;
645 auto dp =
Propagator.op(i).subs(ilp==ss).diff(ss).subs(ss==ilp);
646 ibp -= (
a(i)+
Shift[i]) * F(ns) * dp;
651 ibp = ibp.subs(sp2s);
656 for(
int i=0; i<pdim; i++) {
657 auto ci = ibp.coeff(iWF(i), 1);
659 if(!e.has(F(
w)))
return e;
660 else if(e.match(F(
w))) {
661 lst tmp = ex_to<lst>(e.op(0));
662 tmp.let_op(i) = tmp.op(i)-1;
664 }
else return e.map(
self);
668 res += ibp.subs(lst{iWF(
w)==0});
669 auto cilp = iep.coeff(ilp);
670 if(!is_zero(cilp)) res +=
d*cilp*F(nsa);
688 for(
int i=0; i<pdim; i++) {
689 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(
a(i)==
a(i)+1));
696 for(
int i=0; i<pdim; i++) {
697 for(
int j=0; j<n; j++) ibps.append(ibps.op(j).subs(
a(i)==
a(i)-1));
704 find(ibps, F(
w1,
w2), fs);
710 vector<int> nfix(pdim);
711 for(
int i=0; i<pdim; i++) nfix[i] = 0;
712 for(
auto const & kv : n2n) nfix[kv.first] = 1;
714 for(
auto const & kv : n2n) {
716 if(k<0) k = pdim + k;
717 a2n[
a(k)] = kv.second;
719 int nibps = ibps.nops();
720 for(
int i=0; i<nibps; i++) ibps.let_op(i) = ibps.op(i).subs(a2n);
723 map<ex,lst,ex_is_less> cons_vec;
724 while(ibps.nops()>0) {
730 find(ibps,F(
w),fset);
731 int nmax = -10000000, pmax = -10000000;
732 for(
auto fi : fset) {
733 int psum = 0, nsum = 0;
735 for(
int i=0; i<pdim; i++) {
736 auto ni = ns.op(i).subs(
a(i)==0,
nopat);
737 if(sector.op(i)==1) {
738 if(nfix[i]==1 && ni<=0) psum -= 100000;
739 else psum +=
ex2int(ni)-1;
741 if(nfix[i]==1 && ni>0) nsum +=
ex2int(ni);
746 if(psum+nsum<pmax+nmax)
continue;
747 if(psum+nsum>pmax+nmax) {
757 int nr = ibps.nops();
758 int nc = fvec.size();
762 cout <<
"+----------------------------------------" << endl;
763 cout <<
"| IBPs: " << nr <<
", Fs: " << nc << endl;
764 cout <<
"+----------------------------------------" << endl;
768 for(
int r=0; r<nr; r++) {
769 auto ibp = ibps.op(r);
770 for(
int c=0; c<nc; c++) {
772 ibp = ibp.subs(fvec[c]==0,
nopat);
773 mat(r,c) = (mat(r,c)-ibp).coeff(fvec[c]);
779 auto rt = RowReduce(mat);
790 for(
int c=0; c<nc; c++) {
791 if(mr(r,c).is_zero())
continue;
792 if(mr(r,c)==1 && cc==-1) cc = c;
797 auto ns = fvec[cc].op(0).
subs(
a(
w)==0);
799 for(
int i=0; i<pdim; i++) {
800 if(nfix[i]==0) amap[
a(i)] =
a(i)-ns.op(i);
802 fvec[cc] = fvec[cc].subs(amap,
nopat);
803 auto sol = bvec(r,0).subs(amap,
nopat);
807 for(
int i=0; i<pdim; i++) {
810 if(sector.op(i)==1 && nv[i]<1)
goto next_row;
811 else if(sector.op(i)!=1 && nv[i]>0)
goto next_row;
812 }
else nv[i] = (sector.op(i)==1 ? 1 : 0);
815 ex num = sol.numer();
818 for(
auto const & f : fset) {
820 ns = f.op(0).subs(
a(
w)==0);
821 for(
int i=0; i<pdim; i++) {
822 if(sector.op(i)!=1) {
825 if(nsi>0)
goto next_row;
831 ex cci = cc.subs(
a(i)==1+nsi);
832 if(!cci.is_zero() || nsi>=nv[i])
break;
835 if(nsi<nv[i]) nv[i] = nsi;
840 ex den = sol.denom();
841 if(!is_a<mul>(den)) den = lst{den};
842 for(
const auto & item : den) {
844 if(is_a<power>(it)) it = it.op(0);
845 if(!it.has(
a(
w)) || it.has(
d))
continue;
849 cout <<
"size is NOT 1: " << it << endl;
850 throw Error(
"Solver::Solve, error occured.");
852 ex aw = *(
as.begin());
853 if(it.degree(aw)!=1) {
854 cout <<
"degree is NOT 1: " << it << endl;
855 throw Error(
"Solver::Solve, error occured.");
857 ex a0 = -it.coeff(aw,0)/it.coeff(aw,1);
858 int an =
ex2int(aw.op(0));
859 if(sector.op(an)!=1) {
860 if(a0<=nv[an]) nv[an] = a0-1;
862 if(a0>=nv[an]) nv[an] = a0+1;
866 for(
int i=0; i<pdim; i++) {
867 if(nfix[i]==1 && fvec[cc].op(0).op(i)!=nv[i]) {
868 cout << fvec << endl << nv << endl;
869 throw Error(
"Solver::Solve, error occured.");
870 }
else if(nfix[i]==0 && fvec[cc].op(0).op(i)!=
a(i)) {
871 cout << fvec << endl << nv << endl;
872 throw Error(
"Solver::Solve, error occured.");
877 int psum = 0, nsum = 0;
878 for(
int i=0; i<pdim; i++) {
879 if(nfix[i]==1)
continue;
880 if(sector.op(i)==1 && !nv[i].is_equal(1)) psum++;
881 if(sector.op(i)!=1 && !nv[i].is_zero()) nsum++;
883 if(nsum<=1 && psum<=1) con = lst{
vec2lst(nv), sol };
884 }
else if(!bvec(r,0).is_zero()) ibp = bvec(r,0).numer();
886 return lst{ibp, con};
890 for(
int r=0; r<nr; r++) {
891 auto const & item = ibp_con_sol_vec[r];
892 if(!item.op(0).is_zero()) ibps.append(item.op(0));
893 if(is_a<lst>(item.op(1))) {
894 cons.append(item.op(1).op(0));
895 cons_vec[item.op(1).op(0)].append(item.op(1).op(1));
901 cout << cons << endl << endl;
909 for(
auto & k : cons) {
911 cons_vec[k].unique();
913 cout << cons_vec[k] << endl << endl;
915 cout << endl << cons << endl;
class used to wrap error message
interface to communicate with Fermat program
class to wrap map_function of GiNaC
class to parse for string or file, helpful with Symbol class
ex Read(const string &instr, bool s2S=true)
void Run() override
invoke kira program for reduction
void Solve(const ex §or, const map< int, int > &a2n={})
void Import() override
import kira result
void Export() override
Export input data for KIRA.
void SolveSparse(const ex §or, const map< int, int > &a2n={})
class extended to GiNaC symbol class, represent a positive symbol
ex sp(const ex &a, const ex &b)
translated the vector dot a.b to a*b, useful in SecDec
ex factor_flint(const ex &e, bool nd=true)
ex collect_ex(ex const &expr_in, std::function< bool(const ex &)> has_func, int opt)
the collect function like Mathematica
map< int, map< int, ex > > SparseMatrix
ex normal_flint(const ex &expr, int opt=o_flint)
lst collect_lst(ex const &expr_in, std::function< bool(const ex &)> has_func, int opt)
the collect function like Mathematica, reture the lst { {c1,v1}, {c2,v2}, ... }
void sort_lst(lst &ilst, bool less=true)
sort the list in less order, or the reverse
lst vec2lst(const exvector &ev)
convert exvector to lst
exvector GiNaC_Parallel(int ntotal, std::function< ex(int)> f, const string &key)
GiNaC Parallel Evaluation using fork.
void string_trim(string &str)
int ex2int(ex num)
ex to integer
ex subs(const ex &e, init_list sl)