Определитель разреженной матрицы

Я реализую класс разреженной матрицы, используя вектор карты для хранения данных (карта представляет собой строку матрицы, в которой ключ — это индекс столбцов, а значение — это значение матрицы в этой позиции).
Я написал функцию для вычисления определителя, но я не знаю, есть ли способ вычислить это экономящее время (так как матрица является разреженной, и большая часть значения равна нулю)
вот моя реализация:

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 ;
}
}

Заранее спасибо за помощь

0

Решение

Вы должны иметь возможность конструировать несовершеннолетних без выделения новой копии всего; вам нужны второстепенные взгляды.

Незначительное представление имеет указатель на свою исходную матрицу и некоторый эффективный способ описания того, какие столбцы и строки пропускаются.

Вы хотите, чтобы можно было легко пропускать пустые столбцы / строки и выполнять быструю итерацию без проверки каждой записи. Таким образом, вы можете сохранить карту карты для запуска, а затем улучшить сжатые векторы и / или пропустить списки. Если матрица ypur действительно разреженная, проверка нуля для каждого индекса может доминировать в ваших вычислениях.

0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector