Sparse matrix

Example of sparse matrix $\left({\begin{smallmatrix}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{smallmatrix}}\right)$
The above sparse matrix contains only 9 non-zero elements, with 26 zero elements. Its sparsity is 74%, and its density is 26%.

수치 해석(numerical analysis)과 과학 컴퓨팅(scientific computing)에서, 성긴 행렬(sparse matrix) 또는 성긴 배열(sparse array)은 대부분의 원소가 영인 행렬(matrix)입니다.^[1] 성긴 것으로 여겨지는 행렬에 대한 영-값 원소의 비율에 관한 엄격한 정의는 없지만 공통적인 기준은 비-영 워소의 개수가 행 또는 열의 개수와 거의 같다는 것입니다. 대조적으로, 대부분의 원소가 비-영이면, 행렬은 조밀한(dense) 것으로 고려됩니다.^[1] 영-값 원소의 개수를 원소의 총 개수 (예를 들어, m × n 행렬에 대해 m × n)로 나눈 값은 때때로 행렬의 성김(sparsity)이라고 참조됩니다.

개념적으로, 성김은 쌍별 상호 작용이 거의 없는 시스템에 해당합니다. 예를 들어, 하나에서 다음으로 스프링으로 연결된 공의 줄을 생각해 보십시오: 이것은 인접한 공만 결합될 때 성긴 시스템입니다. 대조적으로, 같은 줄의 공에 각 공을 다른 모든 공에 연결하는 스프링이 있으면, 그 시스템은 조밀한 행렬에 해당합니다. 성김의 개념은 전형적으로 중요한 데이터 또는 연결의 밀도가 낮은 네트워크 이론(network theory)과 수치 해석(numerical analysis)과 같은 조합론(combinatorics)과 응용 분야에서 유용합니다. 큰 성긴 행렬은 부분 미분 방정식(partial differential equations)을 풀 때 과학 또는 공학 응용에 자주 나타납니다.

성긴 행렬을 컴퓨터에 저장하고 조작할 때, 행렬의 성긴 구조의 이점을 취하는 특수 알고리듬(algorithms)과 데이터 구조(data structures)를 사용하는 것이 유익하고 종종 필요합니다. 기계 학습 분야에서 흔히 볼 수 있는^[2] 성긴 행렬을 위해 특수 컴퓨터가 만들어져 왔습니다.^[3] 표준 조밀한-행렬 구조와 알고리듬을 사용하는 연산은 처리 및 메모리가 영들에서 낭비되기 때문에 큰 성긴 행렬에 적용할 때 느리고 비효율적입니다. 성긴 데이터는 본질적으로 더 쉽게 압축되고 따라서 저장 공간이 훨씬 적게 필요합니다. 일부 매우 큰 성긴 행렬은 표준 조밀한-행렬 알고리듬을 사용하여 조작될 수 없습니다.

Storing a sparse matrix

행렬은 전형적으로 2-차원 배열로 저장됩니다. 배열에서 각 엔트리는 행렬의 원소 $a i, j$ 를 나타내며 두 인덱스 $i$ 와 $j$ 에 의해 접근됩니다. 전통적으로, $i$ 는 꼭대기에서 바닥으로 번호-매겨진 행 인덱스이고, $j$ 는 왼쪽에서 오른쪽으로 번호-매겨진 열 인덱스입니다. $m \times n$ 행렬에 대해, 이 형식으로 행렬을 저장하는 데 필요한 메모리 양은 $m \times n$ 에 비례적입니다 (행렬의 차원도 저장해야 한다는 사실은 무시한 것입니다).

성긴 행렬의 경우에서, 상당한 메모리 요구 사항은 비-영 엔트리만 저장함으로써 줄일 수 있습니다. 비-영 엔트리의 개수와 분포에 의존하여, 다른 데이터 구조가 사용될 수 있고 기본 접근 방식과 비교될 때 메모리를 크게 절약할 수 있습니다. 장단점은 개별 원소에 접근하는 것이 더 복잡해지고 원래 행렬을 명확하게 복구할 수 있도록 추가 구조가 필요하다는 것입니다.

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

DOK(키의 사전), LIL (목록의 목록), 또는 COO (좌표 목록)와 같이 효율적인 수정을 지원하는 것. 이것들은 전형적으로 행렬을 구성하기 위해 사용됩니다.
CSR (압축된 성긴 행) 또는 CSC (압축된 성긴 열)와 같은 효율적인 접근 및 행렬 연산을 지원하는 것.

Dictionary of keys (DOK)

DOK는 $(row, column)$ -쌍을 원소의 값에 매핑하는 사전(dictionary)으로 구성됩니다. 사전에서 누락된 원소는 영으로 취합니다. 그 형식은 무작위 순서로 성긴 행렬을 점진적으로 구성하는 데 좋지만, 사전식 순서로 비-영 값을 반복하는 데 나쁩니다. 전형적으로 이 형식으로 행렬을 구성하고 그런-다음 처리를 위해 보다 효율적인 다른 형식으로 변환합니다.^[4]

List of lists (LIL)

LIL은 열 인덱스와 값을 포함하는 각 엔트리를 갖는 하나의 목록당 행을 저장합니다. 전형적으로, 이들 엔트리는 빠른 조회를 위해 열 인덱스에 의해 정렬된 상태로 유지됩니다. 이것은 증분 행렬 구성에 좋은 또 다른 형식입니다.^[5]

Coordinate list (COO)

COO는 $(row, column, value)$ 튜플의 목록을 저장합니다. 이상적으로, 엔트리는 무작위 접근 시간을 개선하기 위해 먼저 행 인덱스에 의해 정렬되고 그런-다음 열 인덱스에 의해 정렬됩니다. 이것은 증분 행렬 구성에 좋은 또 다른 형식입니다.^[6]

Compressed sparse row (CSR, CRS or Yale format)

압축된 성긴 행(compressed sparse row, CSR) 또는 압축된 행 저장소(compressed row storage, CRS) or 예일 형식(Yale format)은 각각 비-영 값, 행의 범위, 및 열 인덱스를 포함하는 3개 (일-차원) 배열에 의한 행렬 $M$ 을 나타냅니다. 그것은 COO와 비슷하지만, 행 인덱스를 압축하며, 따라서 그 이름이 붙여졌습니다. 이 형식은 빠른 행 접근과 행렬-벡터 곱셈 ( $M x$ )을 허용합니다. CSR 형식은 적어도 1960년대 중반부터 사용되어 왔으며, 1967년에 처음 완전한 설명이 나타났습니다.^[7]

CSR 형식은 3개의 (일-차원) 배열 $(V, COL_INDEX, ROW_INDEX)$ 을 사용하여 성긴 $m \times n$ 행렬 $M$ 을 행 형식으로 저장합니다. $NNZ$ 가 $M$ 에서 비-영 엔트리의 개수를 나타낸다고 놓습니다. (여기서는 영-기반 인덱스(zero-based indices)가 사용되어야 함에 주목하십시오.)

배열 $V$ 와 $COL_INDEX$ 는 길이 $NNZ$ 에 있고, 비-영 값과 해당 값의 열 인덱스를 각각 포함합니다.
배열 $ROW_INDEX$ 는 길이 $m + 1$ 에 있고 지정된 행이 시작되는 $V$ 와 $COL_INDEX$ 에서 인덱스를 인코딩합니다. 이것은 행 $j$ 위의 비-영의 총 개수를 인코딩하는 $ROW_INDEX[j]$ 와 동등합니다. 마지막 원소는 $NNZ$ , 즉, 마지막 유효한 인덱스 $NNZ - 1$ 바로 뒤에 있는 $V$ 에서 가상 인덱스입니다.^[8]

예를 들어, 다음 행렬은 ${\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}$ 4 비-영 원소를 갖는 $4 \times 4$ 행렬이며, 따라서

V         = [ 5 8 3 6 ]
COL_INDEX = [ 0 1 2 1 ]
ROW_INDEX = [ 0 1 2 3 4^[9]]

이때 영-인덱스된 언어를 가정합니다.

행을 추출하기 위해, 먼저 다음을 정의합니다:

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에서 값 8을 갖는 열 1에 하나의 원소가 있음을 알고 있습니다.

이 경우에서, CSR 표현은 원래 행렬에서 16개 엔트리와 비교하여 13개의 엔트리를 포함합니다. CSR 형식은 $NNZ < (m (n - 1) - 1) / 2$ 인 경우에만 메모리에 저장됩니다.

또 다른 예제, 다음 행렬은 ${\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}}$ 8개의 비-영 원소를 갖는 $4 \times 6$ 행렬 (24 엔트리)입니다. 따라서

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

전체는 21개의 엔트리로 저장됩니다: $V$ 에 8개, $COL_INDEX$ 에 8개, 및 $ROW_INDEX$ 에 5개입니다.

$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의 첫 번째 값은 항상 영이고 마지막 값은 항상 $NNZ$ 이므로, 그것들은 어떤 의미에서는 중복됩니다 (비록 배열 길이를 명시적으로 저장해야 하는 프로그래밍 언어에서 $NNZ$ 가 중복되지 않을지라도). 그럼에도 불구하고, 이렇게 하면 $ROW_INDEX[i + 1] - ROW_INDEX[i]$ 형식이 임의의 행 $i$ 에 대해 작동하도록 보장하므로 각 행의 길이를 계산할 때 예외적인 경우를 처리할 필요가 없습니다. 더욱이, 이 중복 저장소의 메모리 비용은 충분하게 큰 행렬에 대해 중요하지 않을 수 있습니다.

(이전 및 새로운) 예일 성긴 행렬 형식은 CSR 스킴의 예시입니다. 이전 예일 형식은 세 개의 배열로 위에서 설명한 대로 정확하게 작동합니다; 새로운 형식은 $ROW_INDEX$ 와 $COL_INDEX$ 를 단일 배열로 결합하고 행렬의 대각선을 개별적으로 처리합니다.^[10]

논리적 인접 행렬(logical adjacency matrices)에 대해, 행 배열에 엔트리의 존재가 이항 인접 관계를 모델링하기에 충분하므로 데이터 배열은 생략될 수 있습니다.

1977년 예일 대학 컴퓨터 과학과의 Yale Sparse Matrix Package 보고서에서 제안되었기 때문에 예일 형식으로 알려진 것 같습니다.^[11]

Compressed sparse column (CSC or CCS)

CSC는 값이 열에서 먼저 읽히고, 행 인덱스가 각 값에 대해 저장되고, 열 포인터가 저장된다는 점을 제외하면 CSR과 유사합니다. 예를 들어, CSC는 $(val, row_ind, col_ptr)$ 이며, 여기서 $val$ 은 행렬의 (꼭대기-에서-바닥, 그 다음에 왼쪽에서 오른쪽) 비-영 값의 배열입니다; $row_ind$ 는 값에 해당하는 행 인덱스입니다; 그리고, $col_ptr$ 은 각 열이 시작되는 $val$ 인덱스의 목록입니다. 그 이름은 열 인덱스 정보가 COO 형식에 상대적으로 압축된다는 사실을 기반으로 합니다. 전형적으로 구성을 위해 또 다른 형식 (LIL, DOK, COO)을 사용합니다. 이 형식은 산술 연산, 열 조각화, 및 행렬-벡터 곱에 효율적입니다. scipy.sparse.csc_matrix를 참조하십시오. 이것은 (성긴 함수를 통해) MATLAB에서 성긴 행렬을 지정하기 위한 전통적인 형식입니다.

Special structure

Banded

성긴 행렬의 중요한 특수 유형은 다음과 같이 정의되는 대역 행렬(band matrix)입니다. 행렬 $A$ 의 더 낮은 대역폭은 $i > j + p$ 일 때마다 엔트리 $a i, j$ 가 사라짐을 만족하는 가장 작은 숫자 $p$ 입니다. 마찬가지로, 위쪽 대역폭(upper bandwidth)은 $i < j - p$ 일 때마다 $a i, j = 0$ 임을 만족하는 가장 작은 숫자 $p$ 입니다 (Golub & Van Loan 1996, §1.2.1). 예를 들어, 삼중대각 행렬(tridiagonal matrix)은 아래쪽 대역폭 $1$ 과 위쪽 대역폭 $1$ 을 가집니다. 또 다른 예제로, 다음 성긴 행렬은 아래쪽 대역폭과 위쪽 대역폭이 모두 3과 같습니다. 명확성을 위해 영은 점으로 표시되었음에 유의하십시오. ${\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}$

상당히 작은 위쪽 대역폭과 아래쪽 대역폭을 갖는 행렬은 밴드 행렬로 알려져 있고 종종 일반 성긴 행렬보다 더 간단한 알고리듬에 적합합니다; 또는 때때로 조밀한 행렬 알고리듬을 적용하고 감소된 숫자의 인덱스를 반복함으로써 효율성을 얻을 수 있습니다.

행렬 $A$ 의 행과 열을 재배열함으로써, 아래쪽 대역폭을 갖는 행렬 $A'$ 를 얻을 수 있습니다. 대역폭 최소화(bandwidth minimization)를 위해 여러 알고리듬이 설계되었습니다.

Diagonal

대역 행렬의 극단적인 경우에 대해 매우 효율적인 구조, 대각 행렬(diagonal matrix)은 주요 대각선(main diagonal)에서 엔트리만 일-차원 배열로 저장하는 것이므로, 대각선 $n \times n$ 행렬에는 $n$ 엔트리만 필요합니다.

Symmetric

대칭 성긴 행렬은 비-방향화된 그래프(undirected graph)의 인접 행렬(adjacency matrix)로 발생합니다; 그것은 인접 목록(adjacency list)으로 효율적으로 저장될 수 있습니다.

Block diagonal

블록-대각 행렬(block-diagonal matrix)은 그 대각선 블록을 따라 부분-행렬로 구성됩니다. 블록-대각 행렬 $A$ 는 다음과 같은 형식을 가집니다: $\mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},$

여기서 $A k$ 는 모든 $k = 1, ..., n$ 에 대해 정사각 행렬입니다.

Reducing fill-in

행렬의 채우기(fill-in)는 알고리듬 실행 동안 초기 영에서 비-영 값으로 변경하는 엔트리입니다. 메모리 요구 사항과 알고리듬 동안 사용되는 산술 연산의 개수를 줄이기 위해, 행렬에서 행과 열을 전환함으로써 채우기를 최소화하는 것이 유용합니다. 기호적 숄레스키 분해(symbolic Cholesky decomposition)는 실제 숄레스키 분해(Cholesky decomposition)를 수행하기 전에 가능한 최악의 채우기를 계산하기 위해 사용될 수 있습니다.

쓰이고 있는 숄레스키 분해(Cholesky decomposition) 이외의 다른 방법이 사용됩니다. 직교화 방법 (예를 들어 QR 인수분해)은, 예를 들어, 최소 제곱 방법으로 문제를 풀 때 공통적입니다. 이론적 채우기는 여전히 같지만, 실제 용어에서 "거짓 비-영"은 방법에 따라 다를 수 있습니다. 그리고 그것들 알고리듬의 기호적 버전은 기호적 숄레스키와 같은 방식으로 최악의 경우 채우기를 계산하기 위해 사용될 수 있습니다.

Solving sparse matrix equations

성긴 행렬 해결을 위해 반복 방법(iterative method)과 직접 방법이 모두 존재합니다.

켤레 그래디언트(conjugate gradient) 방법 및 GMRES와 같은 반복 방법은 행렬 $A$ 가 성긴 행렬-벡터 곱 $Ax_{i}$ 의 빠른 계산을 활용합니다. 선조건자(preconditioners)의 사용은 그러한 반복 방법의 수렴을 크게 가속화할 수 있습니다.

Software

많은 소프트웨어 라이브러리는 성긴 행렬을 지원하고, 성긴 행렬 방정식에 대한 해결기를 제공합니다. 다음은 오픈-소스입니다:

SuiteSparse, 성긴 선형 시스템의 직접 해에 맞춰진, 성긴 행렬 알고리듬의 모음.
PETSc, 다양한 행렬 저장 형식을 위한 많은 다른 행렬 해결기를 포함하는 큰 C 라이브러리.
Trilinos, 조밀한 행렬과 성긴 행렬의 저장과 대응하는 선형 시스템의 해 전용 하위-라이브러리가 있는 큰 C++ 라이브러리.
Eigen3는 여러 성긴 행렬 해결기를 포함하는 C++ 라이브러리입니다. 어쨌든, 이들 중 어느 것도 병렬화되지 않습니다.
MUMPS (MUltifrontal Massively Parallel sparse direct Solver), Fortran90으로 쓰인, 정면 해결기(frontal solver)입니다.
deal.II, 성긴 선형 시스템과 그것들의 해에 대한 하위-라이브러리를 가지는 유한 원소 라이브러리입니다.
DUNE, 성긴 선형 시스템과 그것들의 해에 대한 하위-라이브러리를 가지는 또 다른 유한 원소 라이브러리입니다.
PaStix.
SuperLU.
Armadillo는 BLAS 및 LAPACK에 대해 사용자-친화적 C++ 래퍼를 제공합니다.
SciPy는 여러 성긴 행렬 형식, 선형 대수, 및 해결기에 대한 지원을 제공합니다.
성긴 행렬에 대한 SPArse Matrix (spam) R 및 파이썬 패키지.
성긴 배열을 처리하기 위한 Wolfram Language 도구.
ALGLIB는 성긴 선형 대수 지원을 갖는 C++ 및 C# 라이브러리입니다.
성긴 행렬 대각화와 조작을 위한 ARPACK Fortran 77 라이브러리, Arnoldi 알고리듬을 사용합니다.
(실수 또는 복소수) 성긴 행렬 대각화를 위한 SPARSE Reference (old) NIST 패키지.
큰 규모 선형 시스템의 해와 성긴 행렬에 대한 SLEPc 라이브러리.
Sympiler, 선형 시스템과 이차 프로그래밍 문제를 해결하기 위한 도메인-지정 코드 생성기와 라이브러리.
scikit-learn, 기계 학습을 위한 파이썬 라이브러리, 성긴 행렬과 해결기에 대한 지원을 제공합니다.
sprs는 순수한 Rust에서 성긴 행렬 데이터 구조와 선형 대수 알고리듬을 구현합니다.
Basic Matrix Library (bml)는 C, C++, 및 Fortran에 대한 바인딩과 함께 여러 성긴 행렬 형식과 선형 대수 알고리듬을 지원합니다.
SPARSKIT, University of Minnesota의 성긴 행렬 계산을 위한 기본 도구 키트입니다.

History

The term sparse matrix was possibly coined by Harry Markowitz who initiated some pioneering work but then left the field.^[12]

Notes

^ ^a ^b Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). "An efficient sparse-dense matrix multiplication on a multicore system". 2017 IEEE 17th International Conference on Communication Technology (ICCT). IEEE. pp. 1880–1883. 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.
^ "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.
^ "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
^ See scipy.sparse.dok_matrix
^ See scipy.sparse.lil_matrix
^ See scipy.sparse.coo_matrix
^ 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.
^ Saad, Yousef (2003). Iterative methods for sparse linear systems. SIAM.
^ Query: why this element '4'here ?
^ 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
^ 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.
^ Oral history interview with Harry M. Markowitz, pp. 9, 10.

References

Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed.). Baltimore: Johns Hopkins. ISBN 978-0-8018-5414-9.
Stoer, Josef; Bulirsch, Roland (2002). Introduction to Numerical Analysis (3rd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-95452-3.
Tewarson, Reginald P. (May 1973). Sparse Matrices (Part of the Mathematics in Science & Engineering series). Academic Press Inc. (This book, by a professor at the State University of New York at Stony Book, was the first book exclusively dedicated to Sparse Matrices. Graduate courses using this as a textbook were offered at that University in the early 1980s).
Bank, Randolph E.; Douglas, Craig C. "Sparse Matrix Multiplication Package" (PDF).
Pissanetzky, Sergio (1984). Sparse Matrix Technology. Academic Press. ISBN 9780125575805.
Snay, Richard A. (1976). "Reducing the profile of sparse symmetric matrices". Bulletin Géodésique. 50 (4): 341–352. Bibcode:1976BGeod..50..341S. doi:10.1007/BF02521587. hdl:2027/uc1.31210024848523. S2CID 123079384. Also NOAA Technical Memorandum NOS NGS-4, National Geodetic Survey, Rockville, MD.^[1]
Jennifer Scott and Miroslav Tuma: "Algorithms for Sparse Linear Systems", Birkhauser, (2023), DOI: https://doi.org/10.1007/978-3-031-25820-6 (Open Access Book)