희박 행렬

Sparse matrix
희박 행렬 예제
위의 스파스 매트릭스에는 0이 아닌 요소가 9개만 포함되어 있으며 요소가 26개 포함되어 있습니다.희소성은 74%, 밀도는 26%입니다.
유한 요소 문제를 2차원으로 풀 때 얻을 수 있는 희박한 행렬입니다.0이 아닌 요소는 검은색으로 표시됩니다.

수치 분석과 과학 컴퓨팅에서, 스파스 행렬 또는 스파스 배열은 대부분의 요소가 [1]0인 행렬이다.행렬이 희박한 것으로 간주되는 0-값 요소의 비율에 대한 엄격한 정의는 없지만 공통 기준은 0이 아닌 요소의 수가 행 또는 열의 수와 거의 같다는 것입니다.반면 대부분의 요소가 0이 아닌 경우 행렬은 밀도가 [1]높은 것으로 간주됩니다.0 값 요소의 수를 요소의 총 수로 나눈 값(예: m × n 행렬의 경우 m × n)을 행렬의 희소성이라고 부르기도 한다.

개념적으로 희소성은 쌍방향 교호작용이 거의 없는 시스템에 해당합니다.예를 들어, 스프링으로 연결된 볼의 라인이 한 곳에서 다음 곳으로 연결된다고 가정합니다. 이것은 인접한 볼만 결합되기 때문에 희박한 시스템입니다.이와는 대조적으로, 각 공을 다른 모든 공에 연결하는 스프링이 같은 라인의 공이라면, 시스템은 조밀한 매트릭스에 해당합니다.희소성의 개념은 네트워크 이론이나 수치 분석과 같은 결합학 및 응용 분야에서 유용하며, 일반적으로 중요한 데이터 또는 연결 밀도가 낮습니다.큰 스파스 행렬은 편미분 방정식을 풀 때 종종 과학 또는 공학 응용 프로그램에서 나타납니다.

컴퓨터에 희박한 행렬을 저장하고 조작할 때는 행렬의 희박한 구조를 이용하는 특수한 알고리즘과 데이터 구조를 사용하는 것이 유리하며 종종 필요합니다.특수 컴퓨터는 기계 학습 [3]분야에서 흔히 볼 수 있는 희소 [2]매트릭스를 위해 만들어졌다.표준 밀도 매트릭스 구조 및 알고리즘을 사용한 연산은 처리 및 메모리가 0에서 낭비되기 때문에 큰 희박 행렬에 적용되면 느리고 비효율적입니다.스파스 데이터는 기본적으로 압축이 더 용이하므로 필요한 스토리지가 훨씬 적습니다.일부 매우 큰 희박한 행렬은 표준 밀도 매트릭스 알고리즘을 사용하여 조작할 수 없다.

스파스 매트릭스 저장

매트릭스는 일반적으로 2차원 배열로 저장됩니다.어레이 내의 각 엔트리는 매트릭스의 요소i,j a를 나타내며 2개의 인덱스 i 및 j에 의해 액세스된다.일반적으로 i는 위에서 아래로 번호가 매겨진 행 색인이고 j는 왼쪽에서 오른쪽으로 번호가 매겨진 열 색인입니다.m × n 행렬의 경우, 행렬을 이 형식으로 저장하기 위해 필요한 메모리의 양은 m × n에 비례합니다(매트릭스의 치수도 저장해야 한다는 사실과는 무관합니다).

스파스 매트릭스의 경우 0이 아닌 엔트리만 저장함으로써 메모리 요구량을 대폭 줄일 수 있다.0이 아닌 엔트리의 수와 분포에 따라 다른 데이터 구조를 사용할 수 있으며 기본 접근법과 비교하여 메모리를 크게 절약할 수 있습니다.단점은 개별 요소에 접근하는 것이 더 복잡해지고 원래의 매트릭스를 모호하지 않게 복구할 수 있는 추가 구조가 필요하다는 것이다.

형식은 다음 두 그룹으로 나눌 수 있습니다.

  • DOK(Dictionary of Keys), LIL(List of Lists), COO(Coordinate List) 등 효율적인 수정을 지원하는 사용자.일반적으로 행렬을 구성하는 데 사용됩니다.
  • CSR(Compressed Sparse Row) 또는 CSC(Compressed Sparse Column) 등 효율적인 접근 및 매트릭스 조작을 지원하는 것.

키 사전(DOK)

DOK는 요소 값에 매핑(행, 열)하는 사전으로 구성됩니다.사전에서 누락된 요소는 0으로 간주됩니다.이 형식은 희박한 행렬을 랜덤 순서로 증분 구성하는 데 적합하지만 사전적 순서로 0이 아닌 값을 반복하는 데는 적합하지 않습니다.일반적으로 행렬을 이 형식으로 구성한 다음 [4]보다 효율적인 다른 형식으로 변환하여 처리합니다.

리스트 리스트(LIL)

LIL은 각 엔트리에 열 인덱스와 값이 포함된 목록을 한 행에 하나씩 저장합니다.일반적으로 이러한 항목은 빠른 검색을 위해 열 색인별로 정렬됩니다.이것은 증분 행렬 [5]구성에 적합한 또 다른 형식입니다.

좌표 리스트(COO)

COO는 (행, 열, 값) 튜플 리스트를 저장합니다.랜덤 액세스 시간을 단축하기 위해 엔트리가 먼저 행 색인별로 정렬된 후 열 색인별로 정렬되는 것이 이상적입니다.이것은 증분 행렬 [6]구성에 적합한 또 다른 형식입니다.

압축된 스파스 행(CSR, CRS 또는 예일 형식)

CSR(Compressed Sparse Row) 또는 CRS(Compressed Row Storage) 또는 Yale 형식은 각각 0이 아닌 값, 행의 범위 및 열 인덱스를 포함하는 3개의 (1차원) 배열에 의한 행렬 M을 나타냅니다.COO와 비슷하지만 행 인덱스를 압축하기 때문에 이름이 붙여집니다.이 형식을 사용하면 고속 행 액세스와 매트릭스 벡터 곱셈(Mx)이 가능합니다.CSR 형식은 적어도 1960년대 중반부터 사용되어 왔으며 1967년에 [7]처음으로 완전한 설명이 제시되었습니다.

CSR 형식은 3개의 (1차원) 배열(V, COL_INDEX, ROW_INDEX)을 사용하여 sparse m × n 매트릭스 M을 행 형식으로 저장합니다.NNZ는 M의 0이 아닌 엔트리의 수를 나타냅니다.(여기에서는 제로 기반의 인덱스를 사용해야 합니다.)

  • 배열 V 및 COL_INDEX는 길이가 NNZ이며 각각 0이 아닌 값과 이러한 값의 열 인덱스를 포함합니다.
  • ROW_INDEX 배열은 길이가 m + 1이며 지정된 행이 시작되는 V 및 COL_INDEX로 인덱스를 인코딩합니다.이것은, 행 j 위에 있는 비제로의 합계수를 ROW_INDEX[j] 부호화하는 것과 같습니다.마지막 요소는 NNZ, 즉 마지막 유효 지수 NNZ - 1 바로 뒤에 있는 V의 가상 지수이다.

예를 들어, 행렬은

0이 아닌 4개의 요소를 가진 4×4 행렬입니다.

V = [ 5 8 3 6 ]COL _ INDEX = [ 0 1 2 1 ]ROW _ INDEX = [ 0 1 2 3 4 ]

제로의 언어를 가정했을 때요.

행을 추출하려면 먼저 다음을 정의합니다.

row_start = ROW_INDEX[row] row_end = ROW_INDEX[row + 1]

그런 다음 V 및 COL_INDEX에서 row_start에서 시작하여 row_end에서 끝나는 슬라이스를 가져옵니다.

이 행렬의 1행(두 번째 행)을 추출하려면row_start=1그리고.row_end=2그 다음 슬라이스를 만듭니다.V[1:2] = [8]그리고.COL_INDEX[1:2] = [1]이제 1행의 1열에는 값이 8인 요소가 1개 있습니다.

이 경우 CSR 표현에는 13개의 엔트리가 포함되어 있습니다.이 엔트리는 원래 매트릭스에서는 16개요CSR 포맷은 NNZ < (m (n - 1) - 1) / 2 의 경우에만 메모리를 절약합니다.

또 다른 예로는 행렬이 있습니다.

는 8개의 0이 아닌 요소를 가진 4 × 6 매트릭스(24 엔트리)입니다.

V = [ 10 20 30 40 50 60 70 80 ]COL_INDEX = [ 0 1 3 2 3 4 5 ]ROW_INDEX = [ 0 2 4 7 8 ]

전체는 21개의 엔트리로 저장됩니다.8 in V, 8 in COL_INDEX, 5 in ROW_INDEX.

  • ROW_INDEX는 어레이 V을 다음과 같은 행으로 나눕니다.(10, 20) (30, 40) (50, 60, 70) (80)각 행이 시작되고 끝나는 V(및 COL_INDEX)의 인덱스를 나타냅니다.
  • COL_INDEX는 값을 열에 정렬합니다.(10, 20, ...) (0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80).

이 형식에서는 ROW_INDEX의 첫 번째 값은 항상 0이고 마지막 값은 항상 NNZ이기 때문에 어떤 의미에서는 용장성이 있습니다(단, 어레이 길이를 명시적으로 저장할 필요가 있는 프로그래밍 언어에서는 NNZ는 용장성이 없습니다).단, ROW_INDEX[i + 1] - ROW_INDEX[i] 공식은 모든 행 i에 대해 작동하므로 각 행의 길이를 계산할 때 예외적인 경우를 처리할 필요는 없습니다.게다가 이 다중 스토리지의 메모리 비용은 충분히 큰 매트릭스에서는 중요하지 않을 가능성이 있습니다.

(구 및 신) 예일 스파스 매트릭스 형식은 CSR 스킴의 인스턴스입니다.이전 예일 형식은 위에서 설명한 대로 3개의 배열로 작동합니다.새로운 형식은 ROW_INDEX와 COL_INDEX를 단일 배열로 조합하여 매트릭스의 대각선을 [9]개별적으로 처리합니다.

논리 인접 행렬의 경우, 데이터 어레이는 생략할 수 있다.이는 행 배열 내의 엔트리가 2진수 인접 관계를 모델링하기에 충분하기 때문이다.

이것은 예일 [10]대학의 컴퓨터 과학부의 1977년 예일 스파스 매트릭스 패키지 보고서에서 제안되었기 때문에 예일 형식으로 알려져 있을 것이다.

압축된 스파스 컬럼(CSC 또는 CCS)

CSC는 CSR와 비슷하지만 값이 먼저 열 단위로 읽혀지고 각 값에 대해 행 인덱스가 저장되며 열 포인터가 저장됩니다.예를 들어 CSC는 (val, row_ind, col_ptr)입니다.여기서 val은 매트릭스(위에서 아래로, 왼쪽에서 오른쪽으로)가 아닌 값의 배열입니다.row_ind는 값에 대응하는 행인덱스입니다.col_ptr은 각 열이 시작되는 발인덱스 목록입니다.COO 형식을 기준으로 컬럼 인덱스 정보가 압축된다는 사실에 기반합니다.일반적으로 건설에는 다른 형식(LIL, DOK, COO)을 사용합니다.이 형식은 산술 연산, 컬럼 슬라이싱 및 매트릭스 벡터 제품에 효과적입니다.scipy.sparse.csc_matrix를 참조하십시오.이것은 함수를 통해 MATLAB에서 스파스 행렬을 지정하는 전통적인 형식입니다.

특수 구조

띠가 있는

주요 기사: 밴드 매트릭스

스파스 행렬의 중요한 특수 유형은 다음과 같이 정의된 밴드 행렬입니다.매트릭스 A의 낮은 대역폭은 엔트리i,j a가 i > j + p일 때마다 사라지도록 p가 가장 작은 값입니다. 마찬가지로 상한 대역폭은 i < j - p일 때마다 a =0이 되도록i,j p가 가장 작습니다(Golub & Van Loan 1996, 1 1.2.1).예를 들어 삼각행렬은 낮은 대역폭 1과 높은 대역폭 1을 가진다.또 다른 예로 다음 스파스 매트릭스에서는 대역폭의 하한과 상한은 모두 3입니다.명확성을 위해 0은 점으로 표시됩니다.

대역폭 상한이 상당히 작은 행렬은 밴드 매트릭스라고 불리며 일반적인 희박 매트릭스보다 단순한 알고리즘에 적합합니다.또한 조밀한 매트릭스 알고리즘을 적용하여 단순히 적은 수의 인덱스를 루프함으로써 효율을 얻을 수도 있습니다.

행렬 A의 행과 열을 재배치하면 더 낮은 대역폭을 가진 행렬 A'를 얻을 수 있습니다.대역폭을 최소화하기 위해 많은 알고리즘이 설계되어 있습니다.

대각선

대역행렬의 극단적인 경우에 매우 효율적인 구조인 대각행렬은 주요 대각선 내의 엔트리만 1차원 배열로 저장하기 때문에 대각선 n × n 행렬은 n개의 엔트리만 필요로 한다.

대칭

대칭 스파스 매트릭스는 비방향 그래프의 인접 매트릭스로서 발생하며 인접 목록으로 효율적으로 저장할 수 있습니다.

블록 대각선

블록-대각 행렬은 대각 블록을 따라 하위 행렬로 구성됩니다.블록 대각행렬 A는 다음과 같은 형태를 가진다.

여기서k A는 모든 k = 1, ..., n에 대한 제곱 행렬입니다.

충전량 감소

매트릭스 입력은 알고리즘 실행 중에 초기 0에서 0이 아닌 값으로 변경되는 엔트리입니다.알고리즘 중에 사용되는 메모리 요구 사항과 산술 연산 수를 줄이려면 행렬의 행과 열을 전환하여 채우기를 최소화하는 것이 유용합니다.기호 콜레스키 분해는 실제 콜레스키 분해를 수행하기 전에 최악의 필인을 계산하는 데 사용할 수 있습니다.

사용 중인 콜레스키 분해 방법 외에 다른 방법이 있습니다.예를 들어, 최소 제곱법으로 문제를 푸는 경우 QR 인수분해와 같은 직교 방법이 일반적입니다.이론적인 입력은 여전히 동일하지만, 실제적인 측면에서 "허위 비제로"는 방법에 따라 다를 수 있습니다.그리고 이러한 알고리즘의 심볼 버전은 심볼 콜레스키와 같은 방법으로 최악의 경우 채우기를 계산할 수 있습니다.

희박한 행렬 방정식을 푸는 중

희박한 행렬 해법을 위해 반복적 방법과 직접적 방법 모두 존재한다.

공역 구배법 및 GMRES와 같은 반복 에서는 행렬 i{ Ax{ i A가 희박한 행렬 벡터 곱의 연산을 이용한다.전제 조건의 사용은 그러한 반복 방법의 수렴을 상당히 가속화할 수 있다.

소프트웨어

많은 소프트웨어 라이브러리는 스파스 행렬을 지원하며 스파스 행렬 방정식을 위한 솔버를 제공합니다.다음은 오픈 소스입니다.

  • SuiteSparse는 스파스 매트릭스 알고리즘의 스위트로 스파스 선형 시스템의 직접 솔루션에 맞춰져 있습니다.
  • 대형 C 라이브러리인 PETSc는 다양한 매트릭스 스토리지 형식을 위한 다양한 매트릭스 솔버를 포함합니다.
  • Triino는 고밀도 및 희박한 행렬의 저장 및 대응하는 선형 시스템의 솔루션 전용 하위 라이브러리를 갖춘 대형 C++ 라이브러리입니다.
  • Igen3은 여러 개의 스파스 행렬 솔버를 포함하는 C++ 라이브러리입니다.그러나 이들 중 어느 것도 병렬화되지 않습니다.
  • Fortran90으로 작성된 MULTifrontal Massivel Massy Parallel Sparse Direct Solver(멀티프론탈 매시브 패럴렐 다이렉트 솔버)는 전면 솔버입니다.
  • deal.II는 희박한 선형 시스템과 그 솔루션을 위한 하위 라이브러리를 가진 유한 요소 라이브러리입니다.
  • DUNE은 희박한 선형 시스템과 그 솔루션을 위한 하위 라이브러리를 가진 또 다른 유한 요소 라이브러리입니다.
  • 패스틱스
  • 슈퍼LU
  • Armadillo는 BLAS 및 LAPACK용으로 사용하기 쉬운 C++ 래퍼입니다.
  • SciPy는 여러 스파스 매트릭스 형식, 선형 대수 및 솔버를 지원합니다.
  • 스파스 매트릭스(스팸) R 및 Python 패키지.
  • 스파스 어레이를 처리하기 위한 Wolfram 언어 도구
  • ALGLIB는 스파스 선형 대수를 지원하는 C++ 및 C# 라이브러리입니다.
  • Arnoldi 알고리즘을 사용한 희박한 행렬 대각화 및 조작을 위한 ARPACK Fortran 77 라이브러리
  • (실제 또는 복잡한) 스파스 매트릭스 대각화를 위한 SPARS Reference(구) NIST 패키지
  • 대규모 선형 시스템 및 스파스 매트릭스 솔루션을 위한 SLEPc 라이브러리
  • Sympiler는 선형 시스템과 2차 프로그래밍 문제를 해결하기 위한 도메인별 코드 생성기 및 라이브러리입니다.
  • Scikit-learn 스파스 매트릭스를 포함한 데이터 분석을 위한 Python 패키지.
  • sprs는 순수 Rust에서 스파스 매트릭스 데이터 구조와 선형 대수 알고리즘을 구현합니다.
  • Basic Matrix Library(bml)는 C, C++ 및 Fortran의 바인딩을 가진 몇 가지 스파스 매트릭스 형식과 선형 대수 알고리즘을 지원합니다.

역사

스파스 매트릭스라는 용어는 선구적인 작업을 시작했지만 그 [11]후 필드를 떠난 해리 마코위츠에 의해 만들어졌을 가능성이 있다.

「 」를 참조해 주세요.

메모들

  1. ^ a b Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.
  2. ^ "Cerebras Systems Unveils the Industry's First Trillion Transistor Chip". www.businesswire.com. 2019-08-19. Retrieved 2019-12-02. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation
  3. ^ "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer Argonne National Laboratory". www.anl.gov (Press release). Retrieved 2019-12-02. The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.
  4. ^ 참조
  5. ^ 참조
  6. ^ 참조
  7. ^ Buluç, Aydın; Fineman, Jeremy T.; Frigo, Matteo; Gilbert, John R.; Leiserson, Charles E. (2009). Parallel sparse matrix-vector and matrix-transpose-vector multiplication using compressed sparse blocks (PDF). ACM Symp. on Parallelism in Algorithms and Architectures. CiteSeerX 10.1.1.211.5256.
  8. ^ Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.
  9. ^ Bank, Randolph E.; Douglas, Craig C. (1993), "Sparse Matrix Multiplication Package (SMMP)" (PDF), Advances in Computational Mathematics, 1: 127–137, doi:10.1007/BF02070824, S2CID 6412241
  10. ^ Eisenstat, S. C.; Gursky, M. C.; Schultz, M. H.; Sherman, A. H. (April 1977). "Yale Sparse Matrix Package" (PDF). Archived (PDF) from the original on April 6, 2019. Retrieved 6 April 2019.
  11. ^ Harry M. Markowitz의 구술 역사 인터뷰, 9, 10페이지.

레퍼런스


추가 정보

  1. ^ Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.