FORM  4.2.1
polyfact.h
1 #pragma once
2 /* #[ License : */
3 /*
4  * Copyright (C) 1984-2017 J.A.M. Vermaseren
5  * When using this file you are requested to refer to the publication
6  * J.A.M.Vermaseren "New features of FORM" math-ph/0010025
7  * This is considered a matter of courtesy as the development was paid
8  * for by FOM the Dutch physics granting agency and we would like to
9  * be able to track its scientific use to convince FOM of its value
10  * for the community.
11  *
12  * This file is part of FORM.
13  *
14  * FORM is free software: you can redistribute it and/or modify it under the
15  * terms of the GNU General Public License as published by the Free Software
16  * Foundation, either version 3 of the License, or (at your option) any later
17  * version.
18  *
19  * FORM is distributed in the hope that it will be useful, but WITHOUT ANY
20  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
21  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
22  * details.
23  *
24  * You should have received a copy of the GNU General Public License along
25  * with FORM. If not, see <http://www.gnu.org/licenses/>.
26  */
27 /* #] License : */
28 
29 #include <vector>
30 #include <string>
31 
32 // First prime modulo which factorization is tried. Too small results
33 // in more unsuccesful attempts; too large is slower.
34 const int POLYFACT_FIRST_PRIME = 17;
35 
36 // Fraction of [1,p) that is used for substitutions of variables. Too
37 // small results in more unsuccesful attempts; too large is slower.
38 const int POLYFACT_IDEAL_FRACTION = 5;
39 
40 // Number of ideals that are tried before failure due to unlucky
41 // choices is accepted.
42 const int POLYFACT_MAX_IDEAL_TRIES = 3;
43 
44 // Number of confirmations for the minimal number of factors before
45 // Hensel lifting is started.
46 const int POLYFACT_NUM_CONFIRMATIONS = 3;
47 
48 // Maximum number of equations for predetermination of coefficients
49 // for multivariate Hensel lifting
50 const int POLYFACT_MAX_PREDETERMINATION = 10000;
51 
52 class poly;
53 
55  /* Class for representing a factorized polynomial
56  * The polynomial is given by: PRODUCT(factor[i] ^ power[i])
57  */
58 public:
59  std::vector<poly> factor;
60  std::vector<int> power;
61 
62  void add_factor(const poly &f, int p=1);
63  const std::string tostring () const;
64  friend std::ostream& operator<< (std::ostream &out, const poly &p);
65 };
66 
67 std::ostream& operator<< (std::ostream &out, const factorized_poly &a);
68 
69 namespace polyfact {
70 
71  // factorization routine
72  const factorized_poly factorize (const poly &a);
73 
74  // methods for squarefree factorization
75  const factorized_poly squarefree_factors (const poly &a);
76  const factorized_poly squarefree_factors_Yun (const poly &a);
77  const factorized_poly squarefree_factors_modp (const poly &a);
78 
79  // methods for choosing suitable reductions
80  const std::vector<poly> factorize_squarefree (const poly &a, const std::vector<int> &x);
81  WORD choose_prime (const poly &a, const std::vector<int> &x, WORD p=0);
82  WORD choose_prime_power (const poly &a, WORD p);
83  const std::vector<int> choose_ideal (const poly &a, int p, const factorized_poly &lc, const std::vector<int> &x);
84 
85  // methods for univariate factorization
86  const std::vector<std::vector<WORD> > Berlekamp_Qmatrix (const poly &a);
87  const std::vector<poly> Berlekamp_find_factors (const poly &a, const std::vector<std::vector<WORD> > &Q);
88  const std::vector<poly> combine_factors (const poly &a, const std::vector<poly> &f);
89 
90  // methods for Hensel lifting
91  const std::vector<poly> extended_gcd_Euclidean_lifted (const poly &a, const poly &b);
92  const std::vector<poly> solve_Diophantine_univariate (const std::vector<poly> &a, const poly &b);
93  const std::vector<poly> solve_Diophantine_multivariate (const std::vector<poly> &a, const poly &b, const std::vector<int> &x, const std::vector<int> &c, int d);
94  const std::vector<poly> lift_coefficients (const poly &a, const std::vector<poly> &f);
95  const std::vector<poly> lift_variables (const poly &a, const std::vector<poly> &f, const std::vector<int> &x, const std::vector<int> &c, const std::vector<poly> &lc);
96  void predetermine (int dep, const std::vector<std::vector<int> > &state, std::vector<std::vector<std::vector<int> > > &terms, std::vector<int> &term, int sumdeg=0);
97 
98 }
Definition: poly.h:49