심볼 숄스키 분해

이 글에는 출처가 없다 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "심볼릭 숄스키 분해" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2009년 12월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수치해석의 수학적 하위 영역에서 심볼 숄스키 분해는 숄스키 분해 또는 변형을 적용할 때 대칭 희소행렬의 L ${\displaystyle L}$ 인자에$$ 대한 0이 아닌 패턴을 결정하는 데 사용되는 알고리즘이다.

알고리즘.

Let ${\displaystyle A=(a_{ij})\in \mathbb {K} ^{n\times n}}$ be a sparse symmetric positive definite matrix with elements from a field ${\displaystyle \mathbb {K} }$, which we wish to factorize as ${\displaystyle A=LL^{T}\,}$.

효율적인 희소성 인자화를 구현하기 위해서는 수치 작업을 하기 전에 인자의 비영점 구조를 결정할 필요가 있는 것으로 밝혀졌다.알고리즘을 기록하기 위해 다음 표기법을 사용한다.

• $A{\displaystyle {\mathcal{}}_{}}$ ${\displaystyle i_{}}$ ${\$ 및 ${\displaystyle L_{}}$ j ${\$ {\mathcal${L}_{j}}}$을 행렬 A와 L의 열 i와 j(대각 원소만 포함)의 0이 아닌 패턴을 나타내는 세트로 한다$$.
• $최소$ ${\displaystyle {\mathcal{}}_{}}$ ${\displaystyle j_{}}$ ${\$을(를) 취하여 L j ${\$의 가장 작은 요소를 의미한다$.$
• 상위 함수 $\pi {\displaystyle }$ (${\displaystyle i}$) $displaystyle \pi (i)\,\!}$을(를) 사용하여$$ 행렬 내에서 제거 트리를 정의하십시오.

다음 알고리즘은 A의 효율적인 기호 인자화를 제공한다.

${\displaystyle {\based}&\pi(i):=0~{\mbox{{{\mbox{for}}~i:=1~{\mbox{to}~n\&\\qquad{\mathcal{L}_{i}:={\mathcal {A}}_{i}\\&\qquad {\mbox{For all}}~j~{\mbox{such that}}~\pi (j)=i\\&\qquad \qquad {\mathcal {L}}_{i}:=({\mathcal {L}}_{i}\cup {\mathcal {L}}_{j})\setminus \{j\}\\&\qquad \pi (i):=\min({\mathcal{L}_{i}\setminus \{i\}\end{aigned}}}}}}$