성긴 행렬

3. 특수한 경우

성긴 행렬 중에는 특정한 구조를 가져서 저장 공간을 절약하거나 계산 속도를 높이는 등 더 효율적으로 다룰 수 있는 경우가 있다. 이러한 행렬들은 특정 문제 해결에 유용하게 사용된다. 대표적인 예로는 띠 행렬, 대각 행렬, 대칭 희소 행렬, 블록 대각 행렬 등이 있으며, 각각의 구조적 특징을 활용하여 최적화된 알고리즘을 적용할 수 있다.

3. 1. 띠 행렬 (Banded Matrix)

3. 1. 1. 대각 행렬 (Diagonal Matrix)

3. 2. 대칭 희소 행렬 (Symmetric Sparse Matrix)

3. 3. 블록 대각 행렬 (Block Diagonal Matrix)

4. 활용

성긴 행렬은 0이 아닌 요소가 매우 적다는 특성 때문에 다양한 계산 문제에서 효율적으로 사용된다. 특히 대규모 행렬 연산 과정에서 발생하는 채움(fill-in) 현상, 즉 원래 0이었던 항목이 계산 중에 0이 아닌 값으로 변하는 것을 최소화하여 메모리 사용량과 계산 시간을 절약하는 데 중요한 역할을 한다. 이를 위해 행렬의 구조를 분석하고 행과 열의 순서를 바꾸는 등의 최적화 기법들이 연구되고 있다. (채움 감소 참조)

또한, 수치해석학이나 과학 컴퓨팅 분야에서 자주 등장하는, 성긴 행렬을 포함하는 대규모 선형 방정식 시스템을 푸는 데 효과적으로 활용된다. 반복법이나 직접법과 같은 다양한 알고리즘이 성긴 행렬의 특성을 이용하여 개발되었으며, 이는 문제 해결의 효율성을 크게 높인다. (희소 행렬 방정식 풀이 참조)

4. 1. 채움 감소 (Reducing fill-in)

4. 2. 희소 행렬 방정식 풀이 (Solving sparse matrix equations)

5. 성긴 파일 (Sparse File)

성긴 파일은 파일 내부에 0으로만 채워진 큰 영역이 있을 경우, 디스크 공간을 절약하기 위해 사용하는 파일 형식이다. NTFS 파일 시스템에서는 파일에 '성긴(sparse)' 속성을 지정할 수 있는데, 이 경우 NTFS는 실제 데이터가 기록된 부분에 대해서만 디스크 공간(클러스터)을 할당한다. 데이터가 기록되지 않은 빈 영역은 디스크 공간을 차지하지 않는다.

성긴 파일에서 데이터가 실제로 저장된 부분을 읽으면 해당 데이터가 반환된다. 반면, 데이터가 없는 부분을 읽으면 0이 반환된다. 예를 들어, 윈도우의 인덱싱 서비스는 NTFS 볼륨에 생성하는 목록을 성긴 파일 형태로 저장한다.

파일 시스템 API는 성긴 파일을 복사하거나, 파일 내에서 실제 데이터가 있는 부분과 비어 있는(성긴) 부분을 구분하여 접근하는 기능을 제공한다. 또한, 파일 내 어느 영역에 데이터가 할당되어 있는지 조회할 수도 있다. 이 API를 활용하면 프로그램은 실제 데이터가 저장된 부분만 읽어서 전체 파일 내용을 복원할 수 있다. 이를 통해 디스크 공간을 효율적으로 사용하고 파일 접근 속도를 높일 수 있다.

6. 소프트웨어

성긴 행렬 연산 및 관련 선형 시스템 해법을 지원하는 다양한 오픈 소스 소프트웨어 라이브러리가 존재한다.

7. 역사

'성긴 행렬'이라는 용어는 선구적인 연구를 시작했지만 이후 이 분야를 떠난 해리 마코위츠에 의해 만들어졌을 가능성이 있다.^[11]

참조

_[1] 간행물 2017 IEEE 17th International Conference on Communication Technology (ICCT) IEEE
_[2] 웹사이트 Cerebras Systems Unveils the Industry's First Trillion Transistor Chip https://www.business[...] 2019-08-19
_[3] 간행물 Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory https://www.anl.gov/[...]
_[4] 문서 scipy.sparse.dok_matrix http://docs.scipy.or[...]
_[5] 문서 scipy.sparse.lil_matrix http://docs.scipy.or[...]
_[6] 문서 scipy.sparse.coo_matrix http://docs.scipy.or[...]
_[7] 간행물 Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks https://people.eecs.[...]
_[8] 서적 SIAM
_[9] 간행물 Sparse Matrix Multiplication Package (SMMP) http://www.mgnet.org[...]
_[10] 웹사이트 Yale Sparse Matrix Package https://apps.dtic.mi[...] 1977-04
_[11] 기타 Oral history interview with Harry M. Markowitz http://purl.umn.edu/[...]
_[12] 간행물 An efficient sparse-dense matrix multiplication on a multicore system IEEE
_[13] 뉴스 Argonne National Laboratory Deploys Cerebras CS-1, the World’s Fastest Artificial Intelligence Computer {{!}} Argonne National Laboratory https://www.anl.gov/[...] 2019-12-02
_[14] 웹사이트 Cerebras Systems Unveils the Industry's First Trillion Transistor Chip https://www.business[...] 2019-08-19
_[15] 웹사이트 プロセッサ開発のセンス ～第4回 ベクトル・プロセッサ～ {{!}} 株式会社エヌエスアイテクス （NSITEXE,Inc.） https://www.nsitexe.[...] 2023-02-22
_[16] 문서 疎行列にアクセスする際に行われる、巨大な配列データを大域的にインデックス参照で引いてくるランダムメモリアクセスを多用する操作は、一般的なスカラ型の[[CPU]]やGPGPUにとっては苦手な処理である。
_[17] 문서 Survey of Sparse Matrix Storage Formats http://netlib.org/li[...]
_[18] 문서 Intel® MKL Sparse BLAS Overview | Intel® Developer Zone https://software.int[...]
_[19] 문서 scipy.sparse.coo_matrix https://docs.scipy.o[...]
_[20] 문서 scipy.sparse.csr_matrix https://docs.scipy.o[...]
_[21] 문서 csr_matrix((data, indices, indptr) ... is the standard CSR representation where the column indices for row i are stored in indices[indptr[i]:indptr[i+1]] and their corresponding values are stored in data[indptr[i]:indptr[i+1]]. https://docs.scipy.o[...]
_[22] 문서 Advantages of the CSR format ... efficient row slicing https://docs.scipy.o[...]
_[23] 문서 Disadvantages of the CSR format slow column slicing operations https://docs.scipy.o[...]
_[24] 문서 scipy.sparse.csc_matrix https://docs.scipy.o[...]
_[25] 문서 scipy.sparse.bsr_matrix https://docs.scipy.o[...]
_[26] 문서 매스월드 http://mathworld.wol[...]
_[27] 문서 scipy.sparse.dok_matrix http://docs.scipy.or[...]
_[28] 문서 scipy.sparse.lil_matrix http://docs.scipy.or[...]
_[29] 문서 scipy.sparse.coo_matrix http://docs.scipy.or[...]
_[30] 문서 www.netlib.org http://netlib.org/li[...]
_[31] 인용 Sparse Matrix Multiplication Package (SMMP) http://www.mgnet.org[...] 2017-11-29