ginac/polynomial/optimal_vars_finder.cpp

   1 #include <algorithm>
   2 #include <cstddef>
   3 #include "optimal_vars_finder.h"
   4 #include "add.h"
   5 #include "mul.h"
   6 #include "power.h"
   7 #include "symbol.h"
   8 #include "numeric.h"
   9
  10 namespace GiNaC
  11 {
  12 namespace
  13 {
  14 // XXX: copy-pasted from normal.cpp.
  15 /*
  16  *  Statistical information about symbols in polynomials
  17  */
  18
  19 /** This structure holds information about the highest and lowest degrees
  20  *  in which a symbol appears in two multivariate polynomials "a" and "b".
  21  *  A vector of these structures with information about all symbols in
  22  *  two polynomials can be created with the function get_symbol_stats().
  23  *
  24  *  @see get_symbol_stats */
  25 struct sym_desc
  26 {
  27         /** Reference to symbol */
  28         ex sym;
  29
  30         /** Highest degree of symbol in polynomial "a" */
  31         int deg_a;
  32
  33         /** Highest degree of symbol in polynomial "b" */
  34         int deg_b;
  35
  36         /** Lowest degree of symbol in polynomial "a" */
  37         int ldeg_a;
  38
  39         /** Lowest degree of symbol in polynomial "b" */
  40         int ldeg_b;
  41
  42         /** Maximum of deg_a and deg_b (Used for sorting) */
  43         int max_deg;
  44
  45         /** Maximum number of terms of leading coefficient of symbol in both polynomials */
  46         std::size_t max_lcnops;
  47
  48         /** Commparison operator for sorting */
  49         bool operator<(const sym_desc &x) const
  50         {
  51                 if (max_deg == x.max_deg)
  52                         return max_lcnops < x.max_lcnops;
  53                 else
  54                         return max_deg < x.max_deg;
  55         }
  56 };
  57
  58 // Vector of sym_desc structures
  59 typedef std::vector<sym_desc> sym_desc_vec;
  60
  61 // Add symbol the sym_desc_vec (used internally by get_symbol_stats())
  62 static void add_symbol(const ex &s, sym_desc_vec &v)
  63 {
  64         sym_desc_vec::const_iterator it = v.begin(), itend = v.end();
  65         while (it != itend) {
  66                 if (it->sym.is_equal(s))  // If it's already in there, don't add it a second time
  67                         return;
  68                 ++it;
  69         }
  70         sym_desc d;
  71         d.sym = s;
  72         v.push_back(d);
  73 }
  74
  75 // Collect all symbols of an expression (used internally by get_symbol_stats())
  76 static void collect_symbols(const ex &e, sym_desc_vec &v)
  77 {
  78         if (is_a<symbol>(e)) {
  79                 add_symbol(e, v);
  80         } else if (is_exactly_a<add>(e) || is_exactly_a<mul>(e)) {
  81                 for (size_t i=0; i<e.nops(); i++)
  82                         collect_symbols(e.op(i), v);
  83         } else if (is_exactly_a<power>(e)) {
  84                 collect_symbols(e.op(0), v);
  85         }
  86 }
  87
  88 /**
  89  * @brief Find the order of variables which is optimal for GCD computation.
  90  *
  91  * Collects statistical information about the highest and lowest degrees
  92  * of all variables that appear in two polynomials. Sorts the variables
  93  * by minimum degree (lowest to highest). The information gathered by
  94  * this function is used by GCD routines to find out the main variable
  95  * for GCD computation.
  96  *
  97  *  @param a  first multivariate polynomial
  98  *  @param b  second multivariate polynomial
  99  *  @param v  vector of sym_desc structs (filled in) */
 100 static void get_symbol_stats(const ex &a, const ex &b, sym_desc_vec &v)
 101 {
 102         collect_symbols(a, v);
 103         collect_symbols(b, v);
 104         sym_desc_vec::iterator it = v.begin(), itend = v.end();
 105         while (it != itend) {
 106                 int deg_a = a.degree(it->sym);
 107                 int deg_b = b.degree(it->sym);
 108                 it->deg_a = deg_a;
 109                 it->deg_b = deg_b;
 110                 it->max_deg = std::max(deg_a, deg_b);
 111                 it->max_lcnops = std::max(a.lcoeff(it->sym).nops(), b.lcoeff(it->sym).nops());
 112                 it->ldeg_a = a.ldegree(it->sym);
 113                 it->ldeg_b = b.ldegree(it->sym);
 114                 ++it;
 115         }
 116         std::sort(v.begin(), v.end());
 117 }
 118 // XXX: end copy-paste from normal.cpp
 119
 120 } // anonymous namespace of helper functions
 121
 122 exvector gcd_optimal_variables_order(const ex& a, const ex& b)
 123 {
 124         sym_desc_vec v;
 125         get_symbol_stats(a, b, v);
 126         exvector vars;
 127         vars.reserve(v.size());
 128         for (std::size_t i = v.size(); i-- != 0; )
 129                 vars.push_back(v[i].sym);
 130         return vars;
 131 }
 132
 133 } // namespace GiNaC
 134