숫자 최적화 프로그램의 중간 단계로 N 선형 방정식 시스템을 풀어야합니다. 정확히 그렇게하기위한 AFAIK의 합리적으로 간단한 알고리즘은 O (N^3)입니다 (거대한 상수를 가진 O (N^2.8)과 같은 것으로 그것을 수행 할 수있는 수학 종이에서 상당히 복잡한 것을 보았습니다). 경우에 따라서는 N이 수천 개로 거대합니다.선형 방정식에 대한 빠른 근사 솔루션?
O (N^3) 미만의 선형 방정식 시스템에 대한 적절한 근사 해를 구하는 좋은 방법이 있습니까?
편집 : 전혀 도움이된다면
는 여기에 몇 가지 자세한 내용입니다.
내 매트릭스는 대칭이며 희소하지 않습니다.
뉴튼 - 라프 슨의 2 차 미분 행렬입니다. 2000 차원 공간에서 무언가를 최적화하려고합니다.
예, 계수에서 얻은 행렬이 희소 한 경우 예. 예를 들어 O (N)에서 작동하는 삼각형 대각선 행렬을 사용하는 경우 불가리아어로 정확한 번역에 대해 확실하지 않은 "올바른 레이아웃"방법이 있습니다. 여전히 O (N^3)이지만 다른 행렬이 필요로하는 불변량 (희소, 대각선, 삼각형 등)을 따르는 경우 놀라운 결과를 얻을 수있는 알고리즘이 있습니다.
불변량을 기반으로하는 특정 방법에 얽매여 있다면 일을 더욱 빠르게하는 유일한 방법은 멀티 스레드로 이동하는 것입니다.
시도 this 검색.
가 GMRES 등 대칭 행렬
코비, 가우스 - 자이 델, CG 같은 반복적 방법이있다의 conjugate gradient method 구현하기 간단하고, 다른 대부분의 반복적 인 방법을 상회한다 (예를 들면 가우스 - 자이 델, SOR). 메인 루프는 행렬 - 벡터 곱셈과 몇 가지 다른 벡터 연산으로 구성됩니다.
일단 작동 시키면 preconditioning을 사용하면 더욱 융통성을 향상시킬 수 있습니다.
LAPACK과 같은 입증 된 구현을 사용하지 않는 이유는 무엇입니까? http://en.wikipedia.org/wiki/LAPACK – Andrey
예, 많습니다. 어떤 것이 적절한지는 귀하의 특정 계수 행렬에 따라 다릅니다. 우리가 그 모습을 말해 준다면 우리는 특정 알고리즘을 제안 할 수있을 것입니다. – Thomas
[wikipedia] (http://en.wikipedia.org/wiki/Iterative_method)에는 몇 가지 설명이 있지만, 나는 그 중 아무 것도 사용하지 않았습니다. –