FORM 4.3
polyfact.h
1#pragma once
2/* #[ License : */
3/*
4 * Copyright (C) 1984-2022 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.
34const 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.
38const int POLYFACT_IDEAL_FRACTION = 5;
39
40// Number of ideals that are tried before failure due to unlucky
41// choices is accepted.
42const int POLYFACT_MAX_IDEAL_TRIES = 3;
43
44// Number of confirmations for the minimal number of factors before
45// Hensel lifting is started.
46const int POLYFACT_NUM_CONFIRMATIONS = 3;
47
48// Maximum number of equations for predetermination of coefficients
49// for multivariate Hensel lifting
50const int POLYFACT_MAX_PREDETERMINATION = 10000;
51
52class poly;
53
55 /* Class for representing a factorized polynomial
56 * The polynomial is given by: PRODUCT(factor[i] ^ power[i])
57 */
58public:
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
67std::ostream& operator<< (std::ostream &out, const factorized_poly &a);
68
69namespace 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