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-2015 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         /** Reference to symbol */
  50         ex sym;
  51
  52         /** Highest degree of symbol in polynomial "a" */
  53         int deg_a;
  54
  55         /** Highest degree of symbol in polynomial "b" */
  56         int deg_b;
  57
  58         /** Lowest degree of symbol in polynomial "a" */
  59         int ldeg_a;
  60
  61         /** Lowest degree of symbol in polynomial "b" */
  62         int ldeg_b;
  63
  64         /** Maximum of deg_a and deg_b (Used for sorting) */
  65         int max_deg;
  66
  67         /** Maximum number of terms of leading coefficient of symbol in both polynomials */
  68         std::size_t max_lcnops;
  69
  70         /** Commparison operator for sorting */
  71         bool operator<(const sym_desc &x) const
  72         {
  73                 if (max_deg == x.max_deg)
  74                         return max_lcnops < x.max_lcnops;
  75                 else
  76                         return max_deg < x.max_deg;
  77         }
  78 };
  79
  80 // Vector of sym_desc structures
  81 typedef std::vector<sym_desc> sym_desc_vec;
  82
  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)
  85 {
  86         for (auto & it : v) {
  87                 if (it.sym.is_equal(s))  // If it's already in there, don't add it a second time
  88                         return;
  89         }
  90         sym_desc d;
  91         d.sym = s;
  92         v.push_back(d);
  93 }
  94
  95 // Collect all symbols of an expression (used internally by get_symbol_stats())
  96 static void collect_symbols(const ex &e, sym_desc_vec &v)
  97 {
  98         if (is_a<symbol>(e)) {
  99                 add_symbol(e, v);
 100         } else if (is_exactly_a<add>(e) || is_exactly_a<mul>(e)) {
 101                 for (size_t i=0; i<e.nops(); i++)
 102                         collect_symbols(e.op(i), v);
 103         } else if (is_exactly_a<power>(e)) {
 104                 collect_symbols(e.op(0), v);
 105         }
 106 }
 107
 108 /**
 109  * @brief Find the order of variables which is optimal for GCD computation.
 110  *
 111  * Collects statistical information about the highest and lowest degrees
 112  * of all variables that appear in two polynomials. Sorts the variables
 113  * by minimum degree (lowest to highest). The information gathered by
 114  * this function is used by GCD routines to find out the main variable
 115  * for GCD computation.
 116  *
 117  *  @param a  first multivariate polynomial
 118  *  @param b  second multivariate polynomial
 119  *  @param v  vector of sym_desc structs (filled in) */
 120 static void get_symbol_stats(const ex &a, const ex &b, sym_desc_vec &v)
 121 {
 122         collect_symbols(a, v);
 123         collect_symbols(b, v);
 124         for (auto & it : v) {
 125                 int deg_a = a.degree(it.sym);
 126                 int deg_b = b.degree(it.sym);
 127                 it.deg_a = deg_a;
 128                 it.deg_b = deg_b;
 129                 it.max_deg = std::max(deg_a, deg_b);
 130                 it.max_lcnops = std::max(a.lcoeff(it.sym).nops(), b.lcoeff(it.sym).nops());
 131                 it.ldeg_a = a.ldegree(it.sym);
 132                 it.ldeg_b = b.ldegree(it.sym);
 133         }
 134         std::sort(v.begin(), v.end());
 135 }
 136 // XXX: end copy-paste from normal.cpp
 137
 138 } // anonymous namespace of helper functions
 139
 140 exvector gcd_optimal_variables_order(const ex& a, const ex& b)
 141 {
 142         sym_desc_vec v;
 143         get_symbol_stats(a, b, v);
 144         exvector vars;
 145         vars.reserve(v.size());
 146         for (std::size_t i = v.size(); i-- != 0; )
 147                 vars.push_back(v[i].sym);
 148         return vars;
 149 }
 150
 151 } // namespace GiNaC