스카이라인 행렬

스카이라인 행렬(Skyline matrix)은 밴드 행렬과 성긴 행렬의 특징을 보유한 특수한 형태의 행렬이다.

성긴 행렬 자료구조 저장법과 관련하여 컴퓨팅 및 IT 분야등에서 중요하게 다루어진다.

표현 예

$\left(\begin{array}{ccccc}11& 0& 22& 0& 0\\ 0& 33& 44& 0& 0\\ 0& 77& 55& 66& 0\\ 0& 99& 0& 88& 44\\ 0& 0& 0& 22& 99\end{array}\right)$

컴퓨터 응용

피봇팅과 상관없이 대칭 행렬에서 보다 더 효율적인 스카이라인 저장 형식은 직접적으로 성긴 행렬 자료구조 저장의 경우 중요하며, 스카이라인행렬 응용은 피벗팅이 필요하지 않은 경우에서도 촐레스키(Cholesky) 분해 또는 LU 분해에 적합하다.

컴퓨팅 및 프로그래밍에서 스카이라인 저장 형식은 성긴 행렬의 자료구조 저장법에서처럼 데이터 값과 인덱싱(indexing) 포인터 그리고 행 압축정보같은 배열을 다루는데 때로는 이 형식은 데이터 값과 인덱싱(indexing) 포인터의 두 배열로도 구현이 가능하다.

특히 삼각형 행렬의 삼각형 부분만 저장하거나 대칭 행렬의 대칭 부분이 중복 생략되도록 효율적으로 압축할 수도 있다.

$\left(\begin{array}{ccccc}11& 0& 22& 0& 0\\ 0& 33& 44& 0& 0\\ 22& 44& 55& 66& 0\\ 0& 0& 66& 88& 44\\ 0& 0& 0& 44& 99\end{array}\right)$

• 상삼각행렬 = U

데이터 = [ 11 , 33 , 22 , 44 , 55 , 66 , 88 , 44 , 99 ]

인텍스 포인터 = [ 0 , 1 , 2 , 5 , 7 , 9 ]

• 하삼각행렬 = L

데이터 = [ 11 , 33 , 22 , 44 , 55 , 66 , 88 , 44 , 99 ]

인텍스 포인터 = [ 0 , 1 , 2 , 5 , 7 , 9 ]

이처럼 훨씬 적은 필인 (fill-in)으로 인해 매우 큰 문제에 더 효율적인 면이 있다.

같이 보기

• 실베스터 관성법칙
• 대칭행렬
• 커틸-맥키 알고리즘

각주

• [1] 234murphy
• University of Toronto 보관됨 2018-01-18 - 웨이백 머신