대형 라플라시안 매트릭스에 대한 간단한 단순 솔버 란 무엇입니까?

Question

저는 저항 네트워크 연구에서 발생하는 몇 가지 큰 (N ~ 1e6) 라플라시안 매트릭스를 해결해야합니다. 네트워크 분석의 나머지 부분은 부스트 ​​그래프로 처리되고 있으며 가능하다면 C++로 머물러보고 싶습니다. 많은 C++ 매트릭스 라이브러리가 있다는 것을 알고 있지만 아무도 속도 나 유용성면에서 확실한 리더가 아닌 것 같습니다. 또한 주제에 관한 많은 질문들이 여기와 다른 곳에서 유용성이 제한적인 세탁 목록으로 급속하게 옮겨가는 것처럼 보입니다. 나 자신과 다른 사람들을 도우려는 시도에서이 질문을 간결하고 답답하게 유지하려고 노력할 것입니다 :

다음 요구 사항을 효과적으로 처리 할 수있는 최상의 라이브러리는 무엇입니까?

• 매트릭스 형 : 대칭 대각선 우세/라플라시안
• 크기 : 극단 (행 당 최대 5 개 제로 용어/열)
• : 매우 큰 (N ~ 1E6)에는 동적 크기 조정
• 희소성을 불필요 필요한 연산 : A * x = b 및 mat/vec에서 x를 구하십시오.
• 언어 : C++ (C ok)
• 우선 순위 : 코드 작성의 속도와 단순성. 나는 정말로이 한 가지 문제에 대해 완전히 새로운 프레임 워크를 배우지 않거나 수동으로 너무 많은 도우미 코드를 작성해야하는 것을 피할 것입니다. 최소한의 작업 예와 답변에

추가 사랑 ...

Answer 1

관련 게시물이 많이있다, 당신은 모양을 가질 수있다. 나는 C++를 추천하고 밀어 것 :: ublas을 UMFPACK and BOOST's uBLAS Sparse Matrix

Answer 2

아이겐에서 사용은 사용하기 매우 좋은 가장 빠른 라이브러리 중 하나는 내가 알고

http://eigen.tuxfamily.org/dox/group__TutorialSparse.html

Answer 3

당신이 당신의 자신의 해석을 작성하려는 경우 단순성 측면에서 보면 Gauss-Seidel 반복 횟수를 맞추기가 어렵습니다. 업데이트 단계는 한 줄로되어있어 쉽게 병렬화 할 수 있습니다. Successive over-relaxation (SOR)은 약간 더 복잡하고 훨씬 빠르게 수렴합니다.

Conjugate gradient도 코드 작성이 쉽고 다른 반복 방법보다 훨씬 빠르게 수렴되어야합니다. 주목해야 할 중요한 점은 전체 행렬 A를 작성하지 않고 행렬 벡터 곱 A * b를 계산할 필요가 없다는 것입니다. 작동되면 SSOR (대칭 SOR)과 같은 전제 조건을 추가하여 수렴 속도를 다시 높일 수 있습니다.

아마도 자신을 쓰는 것이 가장 빠른 솔루션 방법은 푸리에 기반 솔버입니다. 본질적으로 우변의 FFT를 취하고, 각 값에 좌표의 함수를 곱한 다음, 역 FFT를 취하는 것을 포함합니다. FFTW과 같은 FFT 라이브러리를 사용하거나 직접 롤백 할 수 있습니다.

이 모두에 대한 참조는 Arieh Iserles의 A First Course in the Numerical Analysis of Differential Equations입니다.