1 /** @file optimal_vars_finder.cpp
3 * Functions to optimize the choice of variable for multivariate GCD. */
6 * GiNaC Copyright (C) 1999-2015 Johannes Gutenberg University Mainz, Germany
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.
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.
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
23 #include "optimal_vars_finder.h"
36 // XXX: copy-pasted from normal.cpp.
38 * Statistical information about symbols in polynomials
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().
46 * @see get_symbol_stats */
49 /** Reference to symbol */
52 /** Highest degree of symbol in polynomial "a" */
55 /** Highest degree of symbol in polynomial "b" */
58 /** Lowest degree of symbol in polynomial "a" */
61 /** Lowest degree of symbol in polynomial "b" */
64 /** Maximum of deg_a and deg_b (Used for sorting) */
67 /** Maximum number of terms of leading coefficient of symbol in both polynomials */
68 std::size_t max_lcnops;
70 /** Commparison operator for sorting */
71 bool operator<(const sym_desc &x) const
73 if (max_deg == x.max_deg)
74 return max_lcnops < x.max_lcnops;
76 return max_deg < x.max_deg;
80 // Vector of sym_desc structures
81 typedef std::vector<sym_desc> sym_desc_vec;
83 // Add symbol the sym_desc_vec (used internally by get_symbol_stats())
84 static void add_symbol(const ex &s, sym_desc_vec &v)
86 sym_desc_vec::const_iterator it = v.begin(), itend = v.end();
88 if (it->sym.is_equal(s)) // If it's already in there, don't add it a second time
97 // Collect all symbols of an expression (used internally by get_symbol_stats())
98 static void collect_symbols(const ex &e, sym_desc_vec &v)
100 if (is_a<symbol>(e)) {
102 } else if (is_exactly_a<add>(e) || is_exactly_a<mul>(e)) {
103 for (size_t i=0; i<e.nops(); i++)
104 collect_symbols(e.op(i), v);
105 } else if (is_exactly_a<power>(e)) {
106 collect_symbols(e.op(0), v);
111 * @brief Find the order of variables which is optimal for GCD computation.
113 * Collects statistical information about the highest and lowest degrees
114 * of all variables that appear in two polynomials. Sorts the variables
115 * by minimum degree (lowest to highest). The information gathered by
116 * this function is used by GCD routines to find out the main variable
117 * for GCD computation.
119 * @param a first multivariate polynomial
120 * @param b second multivariate polynomial
121 * @param v vector of sym_desc structs (filled in) */
122 static void get_symbol_stats(const ex &a, const ex &b, sym_desc_vec &v)
124 collect_symbols(a, v);
125 collect_symbols(b, v);
126 sym_desc_vec::iterator it = v.begin(), itend = v.end();
127 while (it != itend) {
128 int deg_a = a.degree(it->sym);
129 int deg_b = b.degree(it->sym);
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);
138 std::sort(v.begin(), v.end());
140 // XXX: end copy-paste from normal.cpp
142 } // anonymous namespace of helper functions
144 exvector gcd_optimal_variables_order(const ex& a, const ex& b)
147 get_symbol_stats(a, b, v);
149 vars.reserve(v.size());
150 for (std::size_t i = v.size(); i-- != 0; )
151 vars.push_back(v[i].sym);