稀疏矩阵行列式

Question

我正在实现一个稀疏矩阵类，使用映射向量来存储数据（映射表示矩阵的一行，其中键是列的索引，值是该位置的maitrix的值）我已经编写了计算行列式的函数，但我不知道是否有一种方法可以计算这种节省的时间（因为矩阵是稀疏的，大多数值为零）在这里我的实现：

template <typename T>
T det(const SparseMatrix<T>& a )
{
      T d =0 ; // value of determinant ! 
      std::size_t row  = a.getRows() ;
      std::size_t cols = a.getCols() ;

      if(row == cols) // square Matrix;
      {     

         if(row == 1)   
         {
            d = a(1,1);  // matrix 1x1
         }
         else if(row == 2) 
         {
            d = a(1,1) * a(2,2) - a(2,1) * a (1,2);
         }
         else // 3x3 of greather ..
         {  
              for(std::size_t c = 1 ; c <= cols ; c++ )
              {
                  SparseMatrix<T> m = a.minors(1,c);
                  d += pow(-1,1+c) * a(1,c) * det(m) ;
              }
         }
      }
      else
      {
          throw std::runtime_error("Matrix must be square! Error occured in SparseMatrix::det()");   
      }
      return d ;
}

这是类接口

template <typename element_type>
class SparseMatrix {

  public:
   template<class T>
   friend SparseMatrix<T> operator+(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2 );  

   template<class T>
   friend SparseMatrix<T> operator-(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2 );  

   template <class T>
   friend SparseMatrix<T> operator*(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2  );

   template <class T>
   friend std::ostream& operator<<(std::ostream& out , const SparseMatrix<T>& m);

   template <class T>
   friend SparseMatrix<T> dot(const SparseMatrix<T>& m1 , const SparseMatrix<T>& m2  );

   template <class T>
   T det(const SparseMatrix<T>& a );




  public:
    // container type ;  
    using data_type = std::vector<std::map<std::size_t , element_type >> ;
    using it_rows   = typename std::map<std::size_t , element_type>::iterator ; 

    constexpr SparseMatrix(std::size_t rows , std::size_t cols) : rows{rows} , columns{cols}
    {
       data.resize(rows);     
    }

    SparseMatrix(std::initializer_list<std::initializer_list<element_type>> l );

    SparseMatrix(const std::string );  


    auto insert(std::size_t i , std::pair<std::size_t, element_type> p )
    { 
       assert( i < rows && p.first < columns); // , "Index out of bound" );
       data.at(i).insert(p);
    }

    auto insert(std::size_t i, std::size_t j, element_type val)
    {
      assert(i<rows && j <columns);
      data.at(i)[j] = val ;
    }

    auto identity() noexcept ;

    auto diag(const element_type& v) noexcept ;

    auto print() const noexcept ; 

    auto dataType() const noexcept ;

    auto traspose() noexcept ;

    auto printf()const noexcept ;

    constexpr auto getRows() const noexcept { return rows; }  

    constexpr auto getCols() const noexcept { return columns; } 

    SparseMatrix<element_type> operator*=(const SparseMatrix<element_type>) ;

    const element_type operator()(std::size_t , std::size_t) const noexcept ;  

    element_type operator()(std::size_t , std::size_t) noexcept ;  

    constexpr SparseMatrix<element_type> minors(const std::size_t , const std::size_t ) const;  

  private:

    std::size_t rows    ;
    std::size_t columns ;
      data_type data    ;     // vector containing row element 


};

我计算行列式的方式是什么？假设运算符（）以这种方式重载

template <typename T>
T SparseMatrix<T>::operator()(std::size_t i, std::size_t j) noexcept 
{
      i -= 1 ;
      j -= 1 ;
      if(data.at(i).find(j) != data.at(i).end()) 
      {
         return data.at(i).at(j) ;
      }
      else
      {
         return 0.0 ;    
      }
}

提前感谢您的帮助

Answer 1

你需要能够构造未成年人，而不需要分配所有内容的新副本；您需要次要视图。

次要视图有一个指向其源矩阵的指针，以及一些描述跳过哪些列和行的有效方法。

您希望能够轻松跳过空列/行，并且无需检查每个条目即可快速迭代。因此，您可能希望存储一个map以开始，然后改进为rle压缩向量和/或跳过列表。如果ypur矩阵确实稀疏，则在每个索引处检查零会主导您的计算。