Skip to main content
LibreTexts - Ukrayinska

8.2: Розріджені формати матриць

  1. Last updated
  2. Save as PDF
  • Page ID
    79578

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    8.2.1 Список списків (LIL)

    Формат розрідженої матриці List of Lists (який з невідомих причин скорочено як LIL, а не LOL) є одним з найпростіших розріджених форматів матриць. Він схематично зображений на малюнку нижче. Кожен ненульовий рядок матриці представлений елементом у своєрідній структурі списку, яка називається «зв'язаним списком». Кожен елемент зв'язаного списку записує номер рядка та дані стовпця для записів матриці в цьому рядку. Дані стовпця складаються зі списку, де кожен елемент списку відповідає ненульовому елементу матриці, і зберігає інформацію про (i) номер стовпця та (ii) значення елемента матриці.

    clipboard_e031de9de6a344016e713f78c1e8eea19.png
    Рисунок\(\PageIndex{1}\): Розріджена матриця та її подання у форматі List-of-Lists (LIL).

    Очевидно, цей формат досить ефективний з пам'яттю. Список рядків повинен бути лише таким довгим, як кількість ненульових рядків матриці; решта не вказані. Аналогічним чином, кожен список даних стовпців повинен бути лише такою довгою, як кількість ненульових елементів у цьому рядку. Загальний обсяг необхідної пам'яті пропорційний кількості ненульових елементів незалежно від розміру самої матриці.

    У порівнянні з іншими розрідженими форматами матриць, які ми обговоримо, доступ до окремого елемента матриці у форматі LIL є відносно повільним. Це пов'язано з тим, що пошук заданого матричного індексу\((i,j)\) вимагає кроку через список рядків, щоб знайти елемент з індексом рядка\(i\); і якщо він знайдений, крокуючи рядок стовпця, щоб знайти індекс\(j\). Так, наприклад, пошук елемента в діагональній\(N\times N\) матриці в форматі LIL вимагає\(O(N)\) часу! Як ми побачимо, CSR та CSC формати набагато ефективніші при доступі до елементів. З цієї ж причини матрична арифметика в форматі LIL дуже неефективна.

    Однією з переваг формату LIL, однак, є те, що змінити «структуру розрідженості» матриці відносно легко. Щоб додати новий ненульовий елемент, потрібно просто перейти до списку рядків і (i) вставити новий елемент у зв'язаний список, якщо рядок раніше не був у списку (ця вставка вимагає\(O(1)\) часу), або (ii) змінити список стовпців (який зазвичай дуже короткий, якщо матриця дуже розріджена).

    З цієї причини формат LIL є кращим, якщо вам потрібно побудувати розріджену матрицю, де ненульові елементи не розподіляються жодним корисним шаблоном. Один із способів - створити порожню матрицю, а потім заповнити елементи по черзі, як показано в наступному прикладі. Матриця LIL створюється функцією lil_matrix, яка забезпечується модулем scipy.sparse.

    Ось приклад програми, яка будує матрицю LIL і друкує її:

    from scipy import *
import scipy.sparse as sp

A = sp.lil_matrix((4,5))     # Create empty 4x5 LIL matrix
A[0,1] = 1.0
A[1,1] = 2.0
A[1,2] = -1.0
A[3,0] = 6.6
A[3,4] = 1.4

## Verify the matrix contents by printing it
print(A)

    Коли ми запускаємо вищевказану програму, вона відображає ненульові елементи розрідженої матриці:

     (0, 1)	1.0
 (1, 1)	2.0
 (1, 2)	-1.0
 (3, 0)	6.6
 (3, 4)	1.4

    Ви також можете перетворити розріджену матрицю в звичайний 2D масив, використовуючи метод toarray. Припустимо, ми замінюємо рядок print (A) у вищевказаній програмі на

    B = A.toarray()
print(B)

    В результаті виходить:

    [[ 0.   1.   0.   0.   0. ]
 [ 0.   2.  -1.   0.   0. ]
 [ 0.   0.   0.   0.   0. ]
 [ 6.6  0.   0.   0.   1.4]]

    Примітка: будьте обережні при виклику toarray в фактичному коді. Якщо матриця величезна, 2D масив з'їсть необгрунтовані обсяги пам'яті. Нерідкі випадки роботи з розрідженими матрицями з розмірами на замовлення10 ^ 5\ разів 10 ^ 5, які можуть займати менше 1 Мб пам'яті в розрідженому форматі, але близько 80 Гб пам'яті в форматі масиву!

    8.2.2 Діагональне сховище (DIA)

    Формат Diagonal Storage (DIA) зберігає вміст розрідженої матриці уздовж її діагоналей. Він використовує 2D масив, який ми позначаємо даними, і 1D цілого масиву, який ми позначаємо зміщеннями. Типовий приклад показаний на наступному малюнку:

    clipboard_ed498a7c76b0cd1232cd730e599b951b8.png
    Рисунок\(\PageIndex{2}\): Розріджена матриця та її представлення у форматі Diagonal Storage (DIA).

    Кожен рядок масиву даних зберігає одну з діагоналей матриці, а зміщення [i] записує діагональ, якій відповідає цей рядок даних, зі зміщенням 0, відповідним основній діагоналі. Наприклад, у наведеному вище прикладі рядок\(0\) даних містить записи [6.6,0,0,0,0]), а зміщення [0] містить значення, що вказує на те\(-3\), що запис\(6.6\) відбувається вздовж\(-3\) піддіагоналі, у стовпці\(0\). (Додаткові елементи в цьому рядку даних лежать за межами матриці і ігноруються.) Діагоналі, що містять тільки нуль, опущені.

    Для розріджених матриць з дуже мало ненульових діагоналей, таких як діагональні або тридіагональні матриці, формат DIA дозволяє виконувати дуже швидкі арифметичні операції. Його основне обмеження полягає в тому, що пошук кожного елемента матриці вимагає виконання сліпого пошуку через масив зсувів. Це нормально, якщо не нульових діагоналей дуже мало, так як зсуви будуть невеликими. Але якщо кількість ненульових діагоналей стає великим, продуктивність стає дуже поганою. У найгіршому випадку антидіагональної матриці пошук елементів вимагає\(O(N)\) часу!

    Створити розріджену матрицю в форматі DIA можна за допомогою функції dia_matrix, яка забезпечується модулем scipy.sparse. Ось приклад програми:

    from scipy import *
import scipy.sparse as sp

N = 6  # Matrix size
 
diag0 = -2 * ones(N)
diag1 = ones(N)

A = sp.dia_matrix(([diag1, diag0, diag1], [-1,0,1]), shape=(N,N))

## Verify the matrix contents by printing it
print(A.toarray())

    Тут першим входом в dia_matrix є кортеж форми (дані, зсуви), де дані і зсуви є масивами описаного вище сорту. Це повертає розріджену матрицю у форматі DIA з вказаним вмістом (елементи даних, які лежать за межами матриці, ігноруються). У цьому прикладі матриця тридіагональна з -2 по головній діагоналі і 1 по діагоналям +1 і -1. Запуск вищевказаної програми виводить наступне:

    [[-2.  1.  0.  0.  0.  0.]
 [ 1. -2.  1.  0.  0.  0.]
 [ 0.  1. -2.  1.  0.  0.]
 [ 0.  0.  1. -2.  1.  0.]
 [ 0.  0.  0.  1. -2.  1.]
 [ 0.  0.  0.  0.  1. -2.]]

    Інший спосіб створення матриці DIA - спочатку створити матрицю в іншому форматі (наприклад, звичайний 2D масив), і надати це як вхід для dia_matrix. Це повертає розріджену матрицю з однаковим вмістом у форматі DIA.

    8.2.3 Стиснутий розріджений рядок (CSR)

    Формат стисненого розрідженого рядка (CSR) являє собою розріджену матрицю з використанням трьох масивів, які ми позначаємо даними, індексами та indptr. Приклад показаний на наступному малюнку:

    clipboard_e63d081d1b185bbde3dfc1f34354a9b17.png
    Рисунок\(\PageIndex{3}\): Розріджена матриця та її подання у форматі стисненого розрідженого рядка (CSR).

    Масив, що позначається даними, зберігає значення ненульових елементів матриці, в послідовному порядку зліва направо уздовж кожного ряду, потім з верхнього ряду в нижній. Масив, що позначається індексами, записує індекс стовпця для кожного з цих елементів. У наведеному вище прикладі дані [3] зберігають значення\(6.6\), а індекси [3] мають значення\(0\), що вказує на те, що елемент матриці зі значенням\(6.6\) зустрічається в стовпці\(0\). Ці два масиви мають однакову довжину, рівну кількості ненульових елементів в розрідженій матриці.

    Масив, що позначається indptr (що розшифровується як «покажчик індексу») забезпечує зв'язок між індексами рядків і елементами матриці, але непрямим чином. Його довжина дорівнює кількості рядків матриці (включаючи нульові рядки). Для кожного рядка\(i\), якщо рядок ненульовий, indptr [i] записує індекс у масивах даних та індексів, що відповідають першому ненульовому елементу на рядку\(i\). (Для нульового рядка indptr записує індекс наступного ненульового елемента, що зустрічається в матриці.)

    Наприклад, розглянемо пошук індексу\((1,2)\) на наведеному вище малюнку. Індекс рядка дорівнює 1, тому ми вивчаємо indptr [1] (чиє значення\(1\)) і indptr [2] (чиє значення\(3\)). Це означає, що ненульові елементи для\(1 \le n < 3\) рядків матриці\(1\) відповідають індексам масивів даних та індексів. Ми шукаємо індекси [1] та індекси [2], шукаємо індекс стовпця\(2\). Це знайдено в індексах [2], тому ми шукаємо в даних [2] значення елемента матриці, який є\(-1.0\).

    Зрозуміло, що пошук окремого елемента матриці дуже ефективний. На відміну від формату LIL, де нам потрібно пройти через зв'язаний список, у форматі CSR масив indptr дозволяє нам перейти прямо до даних для відповідного рядка. З цієї ж причини формат CSR є ефективним для операцій розрізання рядків (наприклад, A [4,:]), а також для матрично-векторних добутків типу\(\mathbf{A}\vec{x}\) (який передбачає взяття добутку кожного рядка матриці з вектором\(\vec{x}\)).

    Формат CSR має кілька мінусів. Нарізка стовпців (наприклад, A [:,4]) неефективна, оскільки вимагає пошуку по всіх елементах масиву індексів для відповідного індексу стовпця. Зміни в структурі розрідженості (наприклад, вставлення нових елементів) також дуже неефективні, оскільки всі три масиви повинні бути перевпорядковані.

    Для створення розрідженої матриці в форматі CSR використовуємо функцію csr_matrix, яка забезпечується модулем scipy.sparse. Ось приклад програми:

    from scipy import *
import scipy.sparse as sp

data = [1.0, 2.0, -1.0, 6.6, 1.4]
rows = [0, 1, 1, 3, 3]
cols = [1, 1, 2, 0, 4]

A = sp.csr_matrix((data, [rows, cols]), shape=(4,5))
print(A)

    Тут першим входом до csr_matrix є кортеж форми (data, idx), де data є 1D масивом із зазначенням ненульових елементів матриці, idx [0,:] вказує індекси рядків, а idx [1,:] вказує індекси стовпців. Запуск програми дає очікувані результати:

     (0, 1)	1.0
 (1, 1)	2.0
 (1, 2)	-1.0
 (3, 0)	6.6
 (3, 4)	1.4

    Функція csr_matrix з'ясовує і генерує три CSR масиви автоматично; вам не потрібно розробляти їх самостійно. Але якщо вам подобається, ви можете оглянути вміст CSR масивів безпосередньо:

    >>> A.data
array([ 1. ,  2. , -1. ,  6.6,  1.4])
>>> A.indices
array([1, 1, 2, 0, 4], dtype=int32)
>>> A.indptr
array([0, 1, 3, 3, 5], dtype=int32)

    (Існує додатковий кінцевий елемент\(5\) у масиві indptr. Для простоти ми не згадували про це в вищезгаданому обговоренні, але ви повинні бути в змозі зрозуміти, чому це там.)

    Іншим способом створення CSR-матриці є створення матриці в іншому форматі (наприклад, звичайний 2D масив або розріджена матриця у форматі LIL), і надати це як вхід до csr_matrix. Це повертає вказану матрицю у форматі CSR. Наприклад:

    >>> A = sp.lil_matrix((6,6))
>>> A[0,1] = 4.0
>>> A[2,0] = 5.0
>>> B = sp.csr_matrix(A)

    8.2.4 Стиснутий розріджений стовпець (CSC)

    Формат стисненого розрідженого стовпця (CSC) дуже схожий на формат CSR, за винятком того, що роль рядків і стовпців міняється місцями. Масив даних зберігає ненульові елементи матриці в послідовному порядку зверху вниз уздовж кожного стовпця, потім від крайнього лівого стовпця до крайнього правого. Масив індексів зберігає індекси рядків, і кожен елемент масиву indptr відповідає одному стовпцю матриці. Приклад наведено нижче:

    clipboard_e4e6a46ce5ff9c0267d3b538c7c5ad5a8.png
    Рисунок\(\PageIndex{4}\): Розріджена матриця та її подання у форматі стисненого розрідженого стовпця (CSC).

    Формат CSC ефективний при пошуку матриці, операціях розрізу стовпців (наприклад, A [:,4]) та таких векторно-матричних продуктів, як\(\vec{x}^{\,T} \mathbf{A}\) (що передбачає взяття добутку вектора\(\vec{x}\) з кожним стовпцем матриці). Однак це неефективно для нарізки рядків (наприклад, A [4,:]) та для зміни структури розрідженості.

    Для створення розрідженої матриці в форматі CSC використовуємо функцію csc_matrix. Це аналогічно функції csr_matrix для CSR матриць. Наприклад,

    >>> from scipy import *
>>> import scipy.sparse as sp
>>> data = [1.0, 2.0, -1.0, 6.6, 1.4]
>>> rows = [0, 1, 1, 3, 3]
>>> cols = [1, 1, 2, 0, 4]
>>> 
>>> A = sp.csc_matrix((data, [rows, cols]), shape=(4,5))
>>> A
<4x5 sparse matrix of type '<class 'numpy.float64'>'
  with 5 stored elements in Compressed Sparse Column format>