C++ Как решить очень большую систему разреженной линейной системы

Question

Я пытаюсь решить очень большую и разреженную систему линейных уравнений в C++. В настоящее время я использую BiCGSTAB от собственного. Он отлично работает для небольшой матрицы, но для матрицы требуемого размера требуется слишком много времени, что составляет 40804x40804 (в будущем это может быть даже больше).

У меня есть очень длинный сценарий, но я просто использовал следующий формат:

SparseMatrix<double> sj(40804,40804); 
VectorXd c_(40804), sf(40804); 
sj.reserve(VectorXi::Constant(40804,36)); //This is a very good estimate of how many non zeros in each column 
//...Fill in actual number in sj 
sj.makeCompressed(); 
BiCGSTAB<SparseMatrix<double> > handler; 
//...Fill in sj, only in the entries that have been initialized previously 
handler.analyzePattern(sj) 
handler.factorize(sj); 
c_.setZero(); 
c_=handler.solve(sf); 

Это занимает слишком много времени! И да, решение действительно существует. Редкая функция в Matlab, похоже, справляется с этим очень хорошо, но мне нужно это на C++ для подключения к серверу.

Я был бы очень признателен, если бы вы могли мне помочь!

Answer 1

Вы должны рассмотреть возможность использования одного из передовых разреженных прямых решателей: CHOLMOD

разреженных прямые решатели являются основным инструментом в вычислительном анализе, обеспечивая очень общий метод для получения высококачественных результатов практически любой проблемы. CHOLMOD - библиотека высокой производительности для редких Cholesky factorization.

Я гарантирую, что этот пакет определенно поможет вам. Кроме того, CHOLMOD поддерживает ускорение GPU с 2012 года с версией 4.0.0. В производительности SuiteSparse-4.3.1 было дополнительно улучшено, что обеспечило ускорение в 3 раза или выше по сравнению с процессором для операции разреженной факторизации.

Если ваши матрицы представлены в виде графиков, вы также можете рассмотреть METIS с комбинацией CHOLMOD. Это означает, что вы сможете делать разбиение на разделы/domainDecomposition в графах, а затем разрешать с помощью CHOLMOD.

SuiteSparse - мощный инструмент с поддержкой линейных (KLU) и прямых решателей.

Вот GitHub link, UserGuide и SuiteSparse's home page