Быстрый метод диагонализации разреженных матриц (Юлия): Почему arpack такой медленный?

Для моей задачи меня интересуют только несколько собственных состояний (с наименьшими собственными значениями) разреженной вещественной симметричной матрицы A. Насколько я вижу, arpack использует другой метод и должен быть намного быстрее, чем полная диагонализация пакета LinearAlgebra. Почему в моем примере это намного медленнее?

using LinearAlgebra, SparseArrays, Arpack    
A = sprand(5000,4995,0.01) # Matrix with 5-dimensional nullspace
H = sparse(Hermitian(A*A'))
@time E, v  = eigen(Matrix(H))
@time E, v  = eigs(H, nev=10, which=:SM)

> 12.059152 seconds (27 allocations: 764.733 MiB, 0.72% gc time)
> 37.628222 seconds (680 allocations: 1.424 GiB, 0.47% gc time)

julia linear-algebra arpack
person varantir    schedule 25.06.2020    source источник

Ответы (1)


arrow_upward
2
arrow_downward

При вычислении наименьших собственных значений с eigs необходимо вычислять (H - λ*I)\x для некоторого сдвига λ на каждой итерации алгоритма. В нашей реализации eigs это приводит к разреженной факторизации H - λ*I для каждой итерации, что дорого обходится. Кроме того, вычисление наименьшего значения иногда требует много итераций по сравнению с вычислением большого значения, но я подозреваю, что затраты на разреженные факторизации преобладают. Вы можете получить представление о затратах, вычислив which=:LM вместо :SM, поскольку первое требует только умножения матрицы на вектор.

person Andreas Noack    schedule 30.06.2020