make_dynamic_cache()

int DetComputation::make_dynamic_cache ( )

private

Definition at line 94 of file det.cpp.

{
  // Traverse through matrix entries, find nonzero entries
  int nonzero = -1;
  for (int i = 0; i < M->n_rows(); ++i)
    {
      bool flag = false;
      for (int j = 0; j < M->n_cols(); ++j)
        {
          if (!R->is_zero(M->elem(i, j)))
            {
              if (!flag)
                {
                  flag = true;
                  dynamic_cache[0][++nonzero] = {};
                  row_lookup[i] = nonzero;
                }
              dynamic_cache[0][nonzero][{{i}, {j}}] = M->elem(i, j);
            }
        }
    }
  int n_nonzero_rows = dynamic_cache[0].size();
  for (int minor_size = 1; minor_size < p; ++minor_size)
    {
      for (int top_row = p - (minor_size + 1);
           top_row <= n_nonzero_rows - minor_size;
           ++top_row)
        {
          dynamic_cache[minor_size].insert({top_row, {}});
          for (const auto &[pp, map] : dynamic_cache[minor_size - 1])
            {
              if (system_interrupted())
                return COMP_INTERRUPTED;  // Allow interruption
              if (pp <= top_row)
                {
                  continue;
                }  // top_row wouldn't be the top row, so skip
              for (auto x : dynamic_cache[0][top_row])
                {
                  for (const auto &[Didx, Dval] : map)
                    {
                      // Check if x and D live on distinct columns
                      const std::vector<int> &Dcols = Didx.second;
                      int xcol = x.first.second[0];
                      auto col_find =
                          std::find(Dcols.begin(), Dcols.end(), xcol);
                      if (col_find != Dcols.end())
                        {
                          continue;
                        }  // xcol found in Dcols, so skip
                      // if no skip, compute a term in the cofactor
                      ColRowIndices newKey = Didx;
                      newKey.first.insert(newKey.first.begin(),
                                          x.first.first[0]);
                      // Get iterator to future location of xcol
                      auto xcol_position = std::upper_bound(
                          newKey.second.begin(), newKey.second.end(), xcol);
                      newKey.second.insert(xcol_position, xcol);
                      bool negate =
                          ((xcol_position - newKey.second.begin()) % 2 != 0);
                      // Insert, add or negate cofactor term
                      auto search =
                          dynamic_cache[minor_size][top_row].find(newKey);
                      if (search == dynamic_cache[minor_size][top_row].end())
                        {  // not found
                          dynamic_cache[minor_size][top_row].insert(
                              {newKey, R->mult(x.second, Dval)});
                          if (negate)
                            {
                              R->negate_to(
                                  dynamic_cache[minor_size][top_row][newKey]);
                            }
                        }
                      else
                        {  // found
                          if (!negate)
                            {
                              R->add_to(
                                  dynamic_cache[minor_size][top_row][newKey],
                                  R->mult(x.second, Dval));
                            }
                          else
                            {
                              R->subtract_to(
                                  dynamic_cache[minor_size][top_row][newKey],
                                  R->mult(x.second, Dval));
                            }
                        }
                    }
                }
            }
        }
    }
  return COMP_DONE;
}

References COMP_DONE, COMP_INTERRUPTED, dynamic_cache, end(), M, p, R, row_lookup, system_interrupted(), and x.

Referenced by step().