Какой разреженный линейный решатель быстрее? SparseLU или BiCGSTAB?

Я протестировал методы Eigen SparseLU и BicGSTAB на некоторой разреженной матрице, размер плотных аналогов которой колеблется от 3000 * 3000 до 16000 * 16000. Все случаи показывают, что SparseLU примерно на 13% быстрее, чем метод BicGSTAB.

Я не скармливал BiCGSTAB разреженную матрицу RowMajor и не давал ему никаких предварительных условий. Это могло быть причиной медленного.

Итак, мне интересно, если я хорошо справляюсь с обоими методами, какой из них должен быть быстрее?

Как насчет того, чтобы размер матрицы увеличился до миллионов * миллионов?

Большое спасибо!


eigen sparse-matrix linear-algebra preconditions
person user43506    schedule 24.03.2016    source источник
comment
Моя матрица - это нерегулярная квадратная разреженная матрица   -  person user43506    schedule 24.03.2016

Ответы (2)


arrow_upward
0
arrow_downward

Вы уже упомянули основную причину разницы в производительности. Итерационные методы становятся намного быстрее, если вы выбираете «правильный» предобуславливатель.

Примерный список предварительных кондиционеров, к которым вы можете обратиться:

  • Якоби
  • SOR
  • ILU
  • Многосеточный

У каждого прекондиционера есть несколько параметров, которые также следует настроить.

person ztik    schedule 24.03.2016

arrow_upward
0
arrow_downward

Выбор линейного решателя во многом связан с распределением собственных значений / собственных векторов матрицы. Если у вас есть симметричная положительно определенная матрица, то сопряженный градиент - хороший вариант. Количество итераций зависит от числа условий (максимальное собственное значение / минимальное собственное значение). Для матрицы, полученной из эллиптического оператора, число обусловленности увеличивается с размером матрицы.

Прочтите эту статью Джонатана Шевчука, чтобы получить отличное объяснение компьютерной графики. (https://www.cs.cmu.edu/~quake-papers/ppain-conjugate-gradient.pdf).

Для других типов матриц вы можете использовать GMRES и т. Д. На основе собственных свойств. Ознакомьтесь с этим документом http://www.sam.math.ethz.ch/~mhg/pub/biksm.pdf

Надеюсь это поможет.

person sarc360    schedule 10.10.2016