선형 시간대에 대칭 줄무늬 (대각선 7 개) 행렬을 뒤집을 가능성이 있습니까?

Question

나는 7 개의 대각선을 가진 pxp 대칭 띠 헤센 모체 H를 뒤집을 필요가있다. p는 매우 높을 수 있습니다 (= 1000 또는 10000).

H^{- 1}은 줄무늬로 간주 될 수 있으므로 전체 역행렬을 계산할 필요는 없습니다. 근사치입니다. (예를 들어 11 또는 13 개의 대각선이 있다고 가정 할 수 있습니다.) 병렬 처리를 의미하지는 않는 방법을 찾고 있습니다.

R을 사용하여 선형 시간으로 이러한 알고리즘을 구현할 가능성이 있습니까?

도움 주셔서 감사합니다.

Answer 1

제 생각에는 최선의 시간 알고리즘은 없습니다. 하지만 당신은 희망없이 완전히 아니에요 :

1. 귀하의 매트릭스 그렇게 합리적으로 빠른 p < 10K에 대한 수 있습니다 상대적으로 최적화 된 구현을 사용하여, 정말 큰되지 않습니다. 예를 들어, 밀도가 인 LU 분해에는 최대 값이 O(p^3) (p = 1000)이 필요하며 이는 1 초 미만입니다. 실제로 희소 행렬에 대한 구현은 희소성을 이용하여 훨씬 더 우수한 성능을 달성해야합니다.
2. 정말로, 정말로 역산을 계산해야합니까? 매우 자주 역함수를 명시 적으로 계산하는 것은 등가 선형 시스템을 푸는 것으로 대체 할 수 있습니다. 선형 시스템을 해결하는 반복 솔버 (예 : conjugate gradient)와 같은 일부 방법은 소스 행렬의 희소성 패턴이 보존되어 작업량이 줄어들 기 때문에 훨씬 효율적입니다. 역행렬을 계산할 때, 줄무늬 행렬로 근사화해도 문제가 없다는 것을 알더라도 여전히 충분한 양의 채우기가 있습니다 (0이 아닌 값이 추가됨)

함께 사용하면 매트릭스에 대한 R matrix package 사용 가능한 모든 시그니처를 시도하고 고성능 BLAS 구현이 설치되어 있는지 확인하십시오. 또한 역 계산하기 위해 전화를 다시 작성하려고 : 이것은 당신의 목적을 위해 더 미묘한 될 수있다

# e.g. rewrite... 
A_inverse = solve(A) 
x = y * A_inverse 
# ... as 
x = solve(A, y) 

을하지만, 패키지 문서에서 제안 당신이 그것을 할 수있을 것입니다 매우 높은 기회가있다 :

Matlab, Suite Sparse, PetSC, Eigen 또는 Intel MKL : 다른 모든 실패하면

solve(a, b, ...) ## *the* two-argument version, almost always preferred to 
solve(a)   ## the *rarely* needed one-argument version 

, 당신은에서 사용할 수있는보다 효율적인 구현을 시도 할 수 있습니다.