성긴 행렬

성긴 행렬의 예 ${\begin{pmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{pmatrix}}$
위 성긴 행렬은 35개중 26개가 0이고 9개만이 0이 아니다

성긴 행렬(sparse matrix) 또는 희소행렬은 행렬의 값이 대부분 0인 경우를 가리키는 표현이다.^[1] 그와 반대되는 표현으로는 밀집행렬(dense matrix), 조밀행렬이 사용된다. 개념적으로 성김은 시스템들이 약하게 연결된 것에 해당한다. 한 줄로 나열된 공과 공이 스프링으로 양 옆으로 하나씩 연결되었을 때 이것은 성긴 시스템이다. 그와 반대로 한 줄의 공들이 여러 방향의 공들과 스프링으로 연결되었을 때 이 시스템은 밀집 행렬이 될 수 있다. 성김의 개념은 조합론과 네트워크 이론 등과 같은 응용분야에서 유용하다.

성긴 행렬의 자료구조 저장법

Dictionary of keys

사전식 키(Dictionary of keys,DOK)방법은 행렬을 매핑된 연관 배열로 저장한다. 이때 키는 (행번호, 열번호)가 되며, 그에 대응하는 값은 행렬의 해당 값이 된다. 이때 행렬값이 0인 키는 저장하지 않는다.일반적으로이 형식으로 행렬을 구성한 다음 처리를 위해 보다 효율적인 다른 형식으로 변환하는 것이 가능하다.^[2]

List of lists (LIL)

LIL(List of lists)은 링크드 리스트 알고리즘을 이용한 저장 기법으로 내용의 추가와 삭제가 용이하지만 CSR과 CSC에 비해 메모리가 낭비 되는 단점이 있다.^[3]

Coordinate list (COO)

좌표리스트(Coordinate list ,COO)는 COO는 (행, 열, 값)의 튜플 목록으로 저장된다. 이상적으로, 이러한 튜플목록의 항목들은 임의 액세스 시간을 향상시키기 위해 (행 색인 다음에 열 색인별로) 정렬될수있다. 이는 점진적 행렬 구성에 유용한 또 다른 형식이다.^[4]

Compressed sparse row (CSR or CRS)

가로의 순서대로 재정렬하는 방법으로 행에 관여하여 정리 압축한 것을 CSR이라고 한다.^[5]^[6]

A_{IJ}={\begin{pmatrix}{\underset {({\color {Blue}0},{\color {Green}0})}{10}}&0&0&{\underset {({\color {Blue}0},{\color {Green}3})}{12}}&0\\0&0&{\underset {({\color {Blue}1},{\color {Green}2})}{11}}&0&{\underset {({\color {Blue}1},{\color {Green}4})}{13}}\\0&{\underset {({\color {Blue}2},{\color {Green}1})}{16}}&0&0&0\\0&0&{\underset {({\color {Blue}3},{\color {Green}2})}{11}}&0&{\underset {({\color {Blue}3},{\color {Green}4})}{13}}\\\end{pmatrix}}

{\begin{matrix}{\text{데 이 터 }}(A)&=&\left({\underset {({\color {Blue}0},{\color {Green}0})}{10}}\right.&{\underset {({\color {Blue}0},{\color {Green}3})}{12}}&{\underset {({\color {Blue}1},{\color {Green}2})}{11}}&{\underset {({\color {Blue}1},{\color {Green}4})}{13}}&{\underset {({\color {Blue}2},{\color {Green}1})}{16}}&{\underset {({\color {Blue}3},{\color {Green}2})}{11}}&\left.{\underset {({\color {Blue}3},{\color {Green}4})}{13}}\right)\\{\text{열  인 텍 스  값 }}(JA)&=&\left({\underset {({\color {Blue}0}\,}{\color {Green}0}}\right.&{\underset {\ \,)}{\color {Green}3}}&{\underset {({\color {Blue}1}\,}{\color {Green}2}}&{\underset {\ \,)}{\color {Green}4}}&{\underset {({\color {Blue}2})}{\color {Green}1}}&{\underset {({\color {Blue}3}\,}{\color {Green}2}}&\left.{\underset {\ \,)}{\color {Green}4}}\,\right)\\{\text{행  압 축  정 보 }}(IA)&=&\left({\underset {({\color {Blue}0})}{0}}\right.&{\underset {({\color {Blue}1})}{2}}&{\underset {({\color {Blue}2})}{4}}&{\underset {({\color {Blue}3})}{5}}&\left.{\underset {({\color {Blue}4})}{7}}\right)&&\end{matrix}}

행압축정보의 배열은 [최초시작행번호,시작행에서의 데이터 개수,두번째 행에서의 데이터 누적 개수,...,마지막행에서의 데이터 누적개수]이다.

{\begin{pmatrix}0&0&0&0\\5&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}

{\begin{matrix}A=[5,8,3,6]\\JA=[0,1,2,1]\\IA=[0,0,2,3,4]\\\end{matrix}}

{\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}

{\begin{matrix}A=[10,20,30,40,50,60,70,80]\\JA=[0,1,1,3,2,3,4,5]\\IA=[0,2,4,7,8]\\\end{matrix}}

예일포맷(Yale format)은 행 압축 성긴 행렬(Compressed sparse row ,CSR , CRS)의 인스턴스이다.

Compressed sparse column (CSC or CCS)

가로와 세로의 순서대로 재정렬하는 방법으로 행에 관여하여 정리한 것을 CSR 열에 관하여 정렬한 것을 CSC라고 이름한다. 저장 알고리즘은 동일하다. LIL에 비하여 메모리를 70%이상 줄일 수 있는 장점이 있고, 단점으로는 추가와 삭제가 용이 하지 않다.

성긴 자료

하드 디스크 등 저장 매체에 저장되는 자료가 공백, 0 값 요소, 비영 요소의 잔존이 비선형적 형식을 통해 이루어진 것을 말한다. 성긴 선형 체계 분석은 데이터의 두가지 타입을 포함한다.: 행렬과 벡터.

행렬

행렬은 공백 또는 0 값을 가진 대부분의 요소와 비영 요소의 잔존이 비선형적 형식의 행렬을 통해 이루어질 때, '성기다(희소하다, 듬성듬성하다, 드문드문하다)'라고 말한다. 그 자연적 형식에서 많은 양의 성긴 행렬을 저장하고 분석하기란 컴퓨터 리소스의 상당한 비효율적 사용이다. 이러한 비효율성을 피하기 위해서 수학자들은 오직 비영 요소만을 남겨둔 채, 0 요소를 제거함으로써 성긴 행렬을 조밀한 배열로 압축하는 수적 방법을 개발했다. 각각의 이러한 수적 방법은 데이터 요소를 배열 안에서 새로운 위치로 옮기고 어디에 비영 요소가 성긴 행렬에서 원래 저장되었었는지를 가리키는 지표를 사용한다. 아직까지는 괜찮다. 그러나 계산 수행의 문제는 이러한 성긴 선형 분석 방법이 어떻게 일반 목적 컴퓨터 메모리로부터 검색 데이터 추출을 다룰 것인가에 대해 강제될 때 발생한다. 모든 일반 목적 컴퓨터는 블록의 메인 메모리로부터 데이터를 검색 추출하고 중앙 처리 장치(CPU)에 의해 고속으로 접근할 수 있는 로컬 캐시 메모리의 블록을 저장하기에 최적화되어있다. 대부분의 수행에서 이러한 과정은 잘 진행되고 전체적으로 연산을 추진한다. 이 데이터 타입에서 수행되는 수학적 연산들은 두 가지 방법 중 하나에서 메모리로부터 데이터 요소를 연속적이거나 비연속적으로 가져온다.

벡터

연산의 종류가 수행되는 것에 따라서, 하나의 피연산자에 대한 데이터는 연속적으로, 반면 다른 피연산자에 대한 데이터는 비연속적으로 접근될 것이다. 예를 들어, 성긴 행렬-벡터 산출이라고 알려진 특정 수학적 연산에서, 조밀한 배열의 열에서 비영 요소는 연속적으로 검색 추출된다. 반면, 벡터 요소는 비연속적으로 배열 요소의 인덱스에 기초하여 검색 추출된다. 얼마나 원래 행렬이 생겼는가에 따라서, 각각의 벡터 데이터 블록은 오직 하나의 유효 데이터 요소만을 포함한 캐시를 불러낼 것이다. 연산의 다음 단계는 벡터 데이터의 다른 블록 내에 위치한 벡터 요소를 검색 추출하기 위한 CPU를 필요로 할 것이다. 이 블록은 이전 블록에 재위치하는 캐시로 검색 추출될 것이다. 계속적으로 데이터가 메인메모리로부터 검색 추출되기를 기다림으로써 CPU를 감속시킬 뿐만 아니라 캐시메모리의 효율성이 끊임없이 부적합한 데이터를 채워넣음으로써 감소된다. 이러한 캐시의 축적적인 영향력은 시스템 전체에 걸친 감퇴를 야기하는 대량의 메모리 장애를 야기한다.

성긴 파일

성긴 파일은 0으로 이루어진 큰 데이터 섹션과 마찬가지로 중요한 데이터를 포함하고 있는 파일에 할당된 디스크 공간을 저장하기 위한 방법을 제공한다. 만약 NTFS 파일이 성긴하다는 특성이 있고, NTFS는 디스크 클러스터를 정확하게 오직 응용 프로그램에 지정된 데이터에 대해 할당한다. 파일의 지정되지 않은 범위는 디스크 상의 할당되지 않은 공간으로 표현된다. 성긴 파일이 할당된 범위로부터 읽어질 때, 데이터는 저장된 곳으로 돌아온다. 비할당 범위로부터 데이터 읽기는 0으로 복귀된다. 성긴 파일을 이용하는 프로그램의 예는 NTFS 볼륨에 성긴 파일로써 목록을 저장하는 인덱싱 서비스이다.

파일 시스템 응용 프로그램 인터페이스(API)들은 파일이 복사되는 것 또는 실제 비트와 성긴 스트림 범위로 후퇴되는 것을 허용한다. 파일 시스템 APIs는 또한 할당 범위를 조회(querying)하는 것을 허용한다. 이러한 APIs를 제공하는 프로그램은 오직 파일 내의 모든 데이터를 복구하기 위해 할당된 범위를 읽기 위해 필요하다. 결과는 효율적 파일 시스템 저장과 접근이다. 아래 그림은 어떻게 데이터가 성긴 자료 속성 집합으로, 성긴 자료 속성 집합 아닌 것으로 저장되는지 보여준다.

같이 보기

각주

↑ 매스월드
↑ (scipy.sparse.dok_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.dok_matrix.html
↑ (scipy.sparse.lil_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html
↑ (scipy.sparse.coo_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html
↑ www.netlib.org
↑ Bank, Randolph E.; Douglas, Craig C. (1993), “Sparse Matrix Multiplication Package (SMMP)” (PDF), 《Advances in Computational Mathematics》 1, 2014년 12월 21일에 원본 문서 (PDF)에서 보존된 문서, 2017년 11월 29일에 확인함

(Numerical Recipes in FORTRAN: The Art of Scientific Computing)Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Sparse Linear Systems." §2.7 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 63-82, 1992.

외부 링크

위키미디어 공용에 성긴 행렬 관련 미디어 분류가 있습니다.

[1] 매스월드

[2] (scipy.sparse.dok_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.dok_matrix.html

[3] (scipy.sparse.lil_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.lil_matrix.html

[4] (scipy.sparse.coo_matrix) http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.coo_matrix.html

[5] www.netlib.org

[6] Bank, Randolph E.; Douglas, Craig C. (1993), “Sparse Matrix Multiplication Package (SMMP)” (PDF), 《Advances in Computational Mathematics》 1, 2014년 12월 21일에 원본 문서 (PDF)에서 보존된 문서, 2017년 11월 29일에 확인함

[1]

[2]

[3]

[4]

[5]

[6]

v t e 수치선형대수학
핵심	부동소수점 수치적 안정성
문제	연립 일차 방정식 행렬 분해 행렬 곱셈 (알고리즘) 행렬 분리 희소문제
하드웨어	CPU 캐시 변환 색인 버퍼(TLB) 캐시 망각 알고리즘 SIMD 멀티프로세싱
소프트웨어	MATLAB 기본 선형대수 서브프로그램(BLAS) LAPACK 라이브러리 범용 소프트웨어