최소도 알고리즘

수치 분석에서 최소도 알고리즘은 숄스키 분해를 적용하기 전에 대칭 희소 행렬의 행과 열을 허용하여 숄스키 인자의 비 0 수를 줄이는 데 사용되는 알고리즘이다.이는 저장 요건을 감소시키고, 숄스키 인자를 산술 연산을 더 적게 적용할 수 있음을 의미한다. (예를 들어, 전제 조건인 결합 구배 알고리즘에서 사전 조건으로 사용되는 불완전한 숄스키 인자와도 관련될 수 있다.)

최소도 알고리즘은 부분 미분방정식의 계수보다는 메쉬의 위상에 따라서만 노드의 순서를 변경할 수 있는 유한요소법에 자주 사용되어, 다양한 계수 값에 동일한 메쉬를 사용할 때 효율 절감을 초래한다.

선형 시스템 지정

${\displaystyle \mathbf {A} \mathbf {x} =\mathbf {b}}$

여기서 A는 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}$ ${\displaystyle n\times n}$ 실제$$ 대칭 희소 제곱 행렬이다.숄스키 인자 L은 일반적으로 A의 상위 삼각형보다 0이 아닌 것을 더 많이 갖는 '채우기'를 겪게 된다.또한 대칭인 $P{\displaystyle {\mathbf{}}^{}}$ ${\displaystyle T\mathbf{}}$ A ${\displaystyle {}^{}}$ ${\$\mathbf {P}} 매트릭스가 Cholesky 인수에서 가능한 최소 채우기를 갖도록 순열 매트릭스 P를 구한다$.$우리는 재주문 시스템을 해결한다.

${\displaystyle \left(\mathbf {P} ^{T}\mathbf {P} \오른쪽)\left(\mathbf {P} ^{T}\mathbf {x} \right)=\mathbf {P}\mathbf {bf {b}.$

최상의 순서를 찾는 문제는 NP-완전한 문제여서 난치성 때문에 휴리스틱 방법을 대신 사용한다.최소도 알고리즘은 1959년 비대칭 선형 프로그래밍 문제에 대해 마코위츠가 처음 제안한 방법에서 도출한 것으로, 이 방법은 다음과 같이 느슨하게 기술되어 있다.가우스 제거 행의 각 단계에서 피벗 행과 컬럼의 OFF 대각선 비 0의 수를 최소화하기 위해 열 순열이 수행된다.마코위츠 방법의 대칭 버전은 1967년 Tinney와 Walker에 의해 설명되었고, 나중에 Rose는 인자화가 시뮬레이션만 되는 알고리즘의 그래프 이론적 버전을 도출했고, 이것이 최소도 알고리즘으로 명명되었다.참조된 그래프는 정점이 n개인 그래프인데, 정점 ${\displaystyle \mathrm{i}}$와 j는 ${\displaystyle i_{}}$ ${\displaystyle j_{}}$ ${\displaystyle {}_{}}$ 0 ${\displaystyle a_{ij}\neq$ 0$\}$일 때 에지로 연결되며, 정도는 정점 수준이다.그러한 알고리즘의 중요한 측면은 번호를 다시 매길 수 있는 선택이 있을 때 동점 파괴 전략이다.

최소 도 알고리즘 버전은 MATLAB 함수 symmmd(여기서 MMD는 다중 최소 도를 의미함)에서 구현되었지만, 이제 더 빠른 대칭 근사치 다중 최소 도 함수 symamd로 대체되었다.이는 이론적 분석에 의해 확인되는데, 이는 n 꼭지점과 m 가장자리의 그래프의 경우 MMD의 실행 시간에 O$$${\displaystyle ({}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle$ O$(n^{2}m)$의 엄격한 상한 값이 있는 반면, AMD의 경우 $O{\displaystyle (n}$ ${\displaystyle m}$) ${\displaystyle$ O$(nm)$가 고정되어 있다는 것을 보여준다.

참조

• Markowitz, H. M. (1957). "The elimination form of the inverse and its application to linear programming". Management Science. 3 (3): 255–269. doi:10.1287/mnsc.3.3.255. JSTOR 2627454.
• George, Alan; Liu, Joseph (1989). "The evolution of the Minimum Degree Ordering Algorithm". SIAM Review. 31 (1): 1–19. doi:10.1137/1031001. JSTOR 2030845.
• Tinney, W. F.; Walker, J. W. (1967). "Direct solution of sparse network equations by optimally ordered triangular factorization". Proc. IEEE. 55 (11): 1801–1809. doi:10.1109/PROC.1967.6011.
• Rose, D. J. (1972). "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations". In Read, R. C. (ed.). Graph Theory and Computing. New York: Academic Press. pp. 183–217. ISBN 0-12-583850-6.
• Heggernes, P.; Eisenstat, S. C.; Kumfert, G.; Pothen, A. (December 2001), The Computational Complexity of the Minimum Degree Algorithm (PDF) (Technical report), Institute for Computer Applications in Science and Engineering