Я реализую класс разреженной матрицы, используя вектор карты для хранения данных (карта представляет собой строку матрицы, в которой ключ — это индекс столбцов, а значение — это значение матрицы в этой позиции).
Я написал функцию для вычисления определителя, но я не знаю, есть ли способ вычислить это экономящее время (так как матрица является разреженной, и большая часть значения равна нулю)
вот моя реализация:
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 ;
}
}
Заранее спасибо за помощь
Вы должны иметь возможность конструировать несовершеннолетних без выделения новой копии всего; вам нужны второстепенные взгляды.
Незначительное представление имеет указатель на свою исходную матрицу и некоторый эффективный способ описания того, какие столбцы и строки пропускаются.
Вы хотите, чтобы можно было легко пропускать пустые столбцы / строки и выполнять быструю итерацию без проверки каждой записи. Таким образом, вы можете сохранить карту карты для запуска, а затем улучшить сжатые векторы и / или пропустить списки. Если матрица ypur действительно разреженная, проверка нуля для каждого индекса может доминировать в ваших вычислениях.
Других решений пока нет …