]> www.ginac.de Git - ginac.git/blob - ginac/polynomial/optimal_vars_finder.cpp
Fix power::subs() in some special cases.
[ginac.git] / ginac / polynomial / optimal_vars_finder.cpp
1 /** @file optimal_vars_finder.cpp
2  *
3  *  Functions to optimize the choice of variable for multivariate GCD. */
4
5 /*
6  *  GiNaC Copyright (C) 1999-2022 Johannes Gutenberg University Mainz, Germany
7  *
8  *  This program is free software; you can redistribute it and/or modify
9  *  it under the terms of the GNU General Public License as published by
10  *  the Free Software Foundation; either version 2 of the License, or
11  *  (at your option) any later version.
12  *
13  *  This program is distributed in the hope that it will be useful,
14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  *  GNU General Public License for more details.
17  *
18  *  You should have received a copy of the GNU General Public License
19  *  along with this program; if not, write to the Free Software
20  *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
21  */
22
23 #include "optimal_vars_finder.h"
24 #include "add.h"
25 #include "mul.h"
26 #include "power.h"
27 #include "symbol.h"
28 #include "numeric.h"
29
30 #include <algorithm>
31 #include <cstddef>
32
33 namespace GiNaC {
34
35 namespace {
36 // XXX: copy-pasted from normal.cpp.
37 /*
38  *  Statistical information about symbols in polynomials
39  */
40
41 /** This structure holds information about the highest and lowest degrees
42  *  in which a symbol appears in two multivariate polynomials "a" and "b".
43  *  A vector of these structures with information about all symbols in
44  *  two polynomials can be created with the function get_symbol_stats().
45  *
46  *  @see get_symbol_stats */
47 struct sym_desc 
48 {
49         /** Initialize symbol, leave other variables uninitialized */
50         sym_desc(const ex& s)
51           : sym(s), deg_a(0), deg_b(0), ldeg_a(0), ldeg_b(0), max_deg(0), max_lcnops(0)
52         { }
53
54         /** Reference to symbol */
55         ex sym;
56
57         /** Highest degree of symbol in polynomial "a" */
58         int deg_a;
59
60         /** Highest degree of symbol in polynomial "b" */
61         int deg_b;
62
63         /** Lowest degree of symbol in polynomial "a" */
64         int ldeg_a;
65
66         /** Lowest degree of symbol in polynomial "b" */
67         int ldeg_b;
68
69         /** Maximum of deg_a and deg_b (Used for sorting) */
70         int max_deg;
71
72         /** Maximum number of terms of leading coefficient of symbol in both polynomials */
73         std::size_t max_lcnops;
74
75         /** Comparison operator for sorting */
76         bool operator<(const sym_desc &x) const
77         {
78                 if (max_deg == x.max_deg)
79                         return max_lcnops < x.max_lcnops;
80                 else
81                         return max_deg < x.max_deg;
82         }
83 };
84
85 // Vector of sym_desc structures
86 typedef std::vector<sym_desc> sym_desc_vec;
87
88 // Add symbol the sym_desc_vec (used internally by get_symbol_stats())
89 static void add_symbol(const ex &s, sym_desc_vec &v)
90 {
91         for (auto & it : v) {
92                 if (it.sym.is_equal(s))  // If it's already in there, don't add it a second time
93                         return;
94         }
95         v.push_back(sym_desc(s));
96 }
97
98 // Collect all symbols of an expression (used internally by get_symbol_stats())
99 static void collect_symbols(const ex &e, sym_desc_vec &v)
100 {
101         if (is_a<symbol>(e)) {
102                 add_symbol(e, v);
103         } else if (is_exactly_a<add>(e) || is_exactly_a<mul>(e)) {
104                 for (size_t i=0; i<e.nops(); i++)
105                         collect_symbols(e.op(i), v);
106         } else if (is_exactly_a<power>(e)) {
107                 collect_symbols(e.op(0), v);
108         }
109 }
110
111 /**
112  * @brief Find the order of variables which is optimal for GCD computation.
113  *
114  * Collects statistical information about the highest and lowest degrees
115  * of all variables that appear in two polynomials. Sorts the variables
116  * by minimum degree (lowest to highest). The information gathered by
117  * this function is used by GCD routines to find out the main variable
118  * for GCD computation.
119  *
120  *  @param a  first multivariate polynomial
121  *  @param b  second multivariate polynomial
122  *  @param v  vector of sym_desc structs (filled in) */
123 static void get_symbol_stats(const ex &a, const ex &b, sym_desc_vec &v)
124 {
125         collect_symbols(a, v);
126         collect_symbols(b, v);
127         for (auto & it : v) {
128                 int deg_a = a.degree(it.sym);
129                 int deg_b = b.degree(it.sym);
130                 it.deg_a = deg_a;
131                 it.deg_b = deg_b;
132                 it.max_deg = std::max(deg_a, deg_b);
133                 it.max_lcnops = std::max(a.lcoeff(it.sym).nops(), b.lcoeff(it.sym).nops());
134                 it.ldeg_a = a.ldegree(it.sym);
135                 it.ldeg_b = b.ldegree(it.sym);
136         }
137         std::sort(v.begin(), v.end());
138 }
139 // XXX: end copy-paste from normal.cpp
140
141 } // anonymous namespace of helper functions
142
143 exvector gcd_optimal_variables_order(const ex& a, const ex& b)
144 {
145         sym_desc_vec v;
146         get_symbol_stats(a, b, v);
147         exvector vars;
148         vars.reserve(v.size());
149         for (std::size_t i = v.size(); i-- != 0; )
150                 vars.push_back(v[i].sym);
151         return vars;
152 }
153
154 } // namespace GiNaC