스카이라인 행렬 문서 원본 보기

{{위키데이터 속성 추적}}
'''스카이라인 행렬'''(Skyline matrix)은 [[밴드 행렬]]과 [[성긴 행렬]]의 특징을 보유한 특수한 형태의 [[행렬]]이다.<ref>[http://www.netlib.org/utk/people/JackDongarra/etemplates/node378.html Netlib Repository at UTK and ORNL]</ref>

성긴 행렬 [[자료구조]] 저장법과 관련하여 컴퓨팅 및 IT 분야등에서 중요하게 다루어진다.<ref>[https://software.intel.com/en-us/mkl-developer-reference-c-sparse-blas-skyline-matrix-storage-format 인텔 문서]</ref>

== 표현 예 ==
:<math>
\begin{pmatrix}
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{pmatrix}
</math>

== 컴퓨터 응용 ==
[[피봇|피봇팅]]과 상관없이 [[대칭 행렬]]에서 보다 더 효율적인 스카이라인 저장 형식은 직접적으로 성긴 행렬 자료구조 저장의 경우 중요하며, 스카이라인행렬 응용은 [[피벗|피벗팅]]이 필요하지 않은 경우에서도 [[촐레스키 분해|촐레스키(Cholesky) 분해]] 또는 [[LU 분해]]에 적합하다.<ref name="George">{{인용|title=Computer solution of large sparse positive definite systems|last1=George|first1=Alan|last2=Liu|first2=Joseph W. H.|publisher=Prentice-Hall Inc.|year=1981|isbn=0-13-165274-5}}. The book also contains the description and source code of simple sparse matrix routines, still useful even if long superseded.</ref><ref>{{인용|last1=Duff|first1=Iain S.|last2=Erisman|first2=Albert M.|last3=Reid|first3=John K.|title=Direct methods for sparse matrices|publisher=Oxford University Press|year=1986|isbn=0-19-853408-6}}</ref>

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

특히 [[삼각행렬|삼각형 행렬]]의 삼각형 부분만 저장하거나 [[대칭 행렬]]의 대칭 부분이 중복 생략되도록 효율적으로 압축할 수도 있다.<ref>{{인용|title=Templates for the solution of linear systems|last1=Barrett|first1=Richard|last2=Berry|last3=Chan|last4=Demmel|last5=Donato|last6=Dongarra|last7=Eijkout|last8=Pozo|last9=Romine|last10=Van der Vorst|chapter=Skyline Storage (SKS)|publisher=SIAM|year=1994|isbn=0-89871-328-5| chapterurl=http://www.netlib.org/linalg/html_templates/node96.html|url=http://www.netlib.org/linalg/html_templates/Templates.html}}</ref>

:<math>
\begin{pmatrix}
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{pmatrix}
</math>
* 상삼각행렬 = 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)으로 인해 매우 큰 문제에 더 효율적인 면이 있다.

== 같이 보기 ==
* [[실베스터 관성법칙]]
* [[대칭행렬]]
* [[커틸-맥키 알고리즘]] <!-- Cuthill–McKee algorithm  -->

== 각주 ==
{{각주}}
* [https://234satwant.wordpress.com/2014/08/29/skyline-method-for-sparse-matrices/] [https://234satwant.wordpress.com/2014/08/26/skyline-method/ 234murphy]
* [http://www.dgp.toronto.edu/~tu/thesis/node57.html University of Toronto] {{웹아카이브|url=https://web.archive.org/web/20180118015502/http://www.dgp.toronto.edu/~tu/thesis/node57.html}}

[[분류:성긴 행렬]]