Branch data     Line data    Source code

       1                 :            : /******************************************************************************
       2                 :            :  * Top contributors (to current version):
       3                 :            :  *   Gereon Kremer, Aina Niemetz
       4                 :            :  *
       5                 :            :  * This file is part of the cvc5 project.
       6                 :            :  *
       7                 :            :  * Copyright (c) 2009-2025 by the authors listed in the file AUTHORS
       8                 :            :  * in the top-level source directory and their institutional affiliations.
       9                 :            :  * All rights reserved.  See the file COPYING in the top-level source
      10                 :            :  * directory for licensing information.
      11                 :            :  * ****************************************************************************
      12                 :            :  *
      13                 :            :  * Implements utilities for coverings projection operators.
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "theory/arith/nl/coverings/projections.h"
      17                 :            : 
      18                 :            : #ifdef CVC5_POLY_IMP
      19                 :            : 
      20                 :            : #include "base/check.h"
      21                 :            : 
      22                 :            : namespace cvc5::internal {
      23                 :            : namespace theory {
      24                 :            : namespace arith {
      25                 :            : namespace nl {
      26                 :            : namespace coverings {
      27                 :            : 
      28                 :            : using namespace poly;
      29                 :            : 
      30                 :      69282 : void PolyVector::add(const poly::Polynomial& poly, bool assertMain)
      31                 :            : {
      32         [ +  + ]:     155296 :   for (const auto& p : poly::square_free_factors(poly))
      33                 :            :   {
      34         [ +  + ]:      86014 :     if (poly::is_constant(p)) continue;
      35         [ +  + ]:      81464 :     if (assertMain)
      36                 :            :     {
      37 [ -  + ][ -  + ]:       2794 :       Assert(main_variable(poly) == main_variable(p));
                 [ -  - ]
      38                 :            :     }
      39                 :      81464 :     std::vector<poly::Polynomial>::emplace_back(p);
      40                 :            :   }
      41                 :      69282 : }
      42                 :            : 
      43                 :      14253 : void PolyVector::reduce()
      44                 :            : {
      45                 :      14253 :   std::sort(begin(), end());
      46                 :      14253 :   erase(std::unique(begin(), end()), end());
      47                 :      14253 : }
      48                 :            : 
      49                 :       2251 : void PolyVector::makeFinestSquareFreeBasis()
      50                 :            : {
      51         [ +  + ]:      12706 :   for (std::size_t i = 0, n = size(); i < n; ++i)
      52                 :            :   {
      53         [ +  + ]:      33039 :     for (std::size_t j = i + 1; j < n; ++j)
      54                 :            :     {
      55                 :      45168 :       Polynomial g = gcd((*this)[i], (*this)[j]);
      56         [ +  + ]:      22584 :       if (!is_constant(g))
      57                 :            :       {
      58                 :         24 :         (*this)[i] = div((*this)[i], g);
      59                 :         24 :         (*this)[j] = div((*this)[j], g);
      60                 :         24 :         add(g);
      61                 :            :       }
      62                 :            :     }
      63                 :            :   }
      64                 :            :   auto it = std::remove_if(
      65                 :      12730 :       begin(), end(), [](const Polynomial& p) { return is_constant(p); });
      66                 :       2251 :   erase(it, end());
      67                 :       2251 :   reduce();
      68                 :       2251 : }
      69                 :      11469 : void PolyVector::pushDownPolys(PolyVector& down, poly::Variable var)
      70                 :            : {
      71                 :            :   auto it =
      72                 :      62058 :       std::remove_if(begin(), end(), [&down, &var](const poly::Polynomial& p) {
      73         [ +  + ]:      36783 :         if (main_variable(p) == var) return false;
      74                 :      25275 :         down.add(p);
      75                 :      25275 :         return true;
      76                 :      11469 :       });
      77                 :      11469 :   erase(it, end());
      78                 :      11469 : }
      79                 :            : 
      80                 :          1 : PolyVector projectionMcCallum(const std::vector<Polynomial>& polys)
      81                 :            : {
      82                 :          1 :   PolyVector res;
      83                 :            : 
      84         [ +  + ]:          3 :   for (const auto& p : polys)
      85                 :            :   {
      86         [ +  + ]:          4 :     for (const auto& coeff : coefficients(p))
      87                 :            :     {
      88                 :          2 :       res.add(coeff);
      89                 :            :     }
      90                 :          2 :     res.add(discriminant(p));
      91                 :            :   }
      92         [ +  + ]:          3 :   for (std::size_t i = 0, n = polys.size(); i < n; ++i)
      93                 :            :   {
      94         [ +  + ]:          3 :     for (std::size_t j = i + 1; j < n; ++j)
      95                 :            :     {
      96                 :          1 :       res.add(resultant(polys[i], polys[j]));
      97                 :            :     }
      98                 :            :   }
      99                 :            : 
     100                 :          1 :   res.reduce();
     101                 :          1 :   return res;
     102                 :            : }
     103                 :            : 
     104                 :            : }  // namespace coverings
     105                 :            : }  // namespace nl
     106                 :            : }  // namespace arith
     107                 :            : }  // namespace theory
     108                 :            : }  // namespace cvc5::internal
     109                 :            : 
     110                 :            : #endif