8.1: Алгебра розрідженої матриці

Last updated
Save as PDF

Page ID: 79570

\( \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}}\)

Коли матриці розріджені, звичайні підходи до матричної арифметиці марнотратні, так як багато часу витрачається на додавання/віднімання або множення на нуль. Наприклад, розглянемо тридіагональну матрицю, розглянуту вище. Щоб виконати добуток\(\mathbf{H} \vec{\psi}\) матриця-вектора звичайним способом, для кожного рядка\(i\) ми повинні обчислити

\[\begin{align} \left(\mathbf{H}\vec{\psi}\right)_i &= \sum_{j=0}^{N-1} H_{ij} \psi_j\\ &= \cdots + \left(0\cdot \psi_{i-2}\right) + \left(H_{i,i-1} \cdot \psi_{i-1}\right) + \left(H_{ii} \cdot \psi_{i}\right) + \left(H_{i,i+1} \cdot \psi_{i+1}\right) + \left(0 \cdot \psi_{i+2}\right) + \cdots \end{align}\]

Сума включає\(O(N)\) арифметичні операції, тому загальна тривалість виконання для всіх\(N\) рядків дорівнює\(O(N^{2})\). Очевидно, однак, більшу частину цього часу витрачається на множення нульових елементів\(\mathbf{H}\) з елементами\(\vec{\psi}\), що не сприяє кінцевому результату. Якби ми могли опустити ці терміни з кожної суми, загальний час виконання продукту буде тільки\(O(N)\).

Однак така економія не може бути досягнута за допомогою структур даних масиву, які ми використовували досі. Щоб ефективно розрахувати матрично-векторний добуток, процесору потрібно знати, які елементи на кожному ряду\(\mathbf{H}\) є ненульовими, щоб він міг пропустити інші. Однак масиви не забезпечують швидкий спосіб визначити, які елементи є ненульовими; єдиний спосіб дізнатися це - пошук блоків зберігання по одному, що вимагає\(O(N)\) часу на кожному рядку. Це знищило б економію часу виконання.

Scipy надає спеціальні структури даних для зберігання розріджених матриць. На відміну від звичайних масивів, ці структури даних сконструйовані так, що нульові елементи опущені, що не тільки економить пам'ять, але і дозволяє значно прискорити певні матричні операції. На відміну від масивів, які можуть представляти не тільки матриці (2D масиви), а й вектори (1D масиви) і тензори вищого рангу (масиви з розмірністю вище 2), ці розріджені структури даних спеціально обмежені матрицями.

Але ось важливий підступ: немає єдиної розрідженої матричної структури даних, яка ідеально підходить для кожного сценарію. Натомість існує декілька форматів розріджених матриць, і кожен формат ефективний лише для певної підмножини матричних операцій або для певних видів розріджених матриць. Тому нам потрібно знати, як реалізуються різні розріджені матричні формати, а також їх переваги та обмеження. З багатьох розріджених форматів матриць, пропонованих Scipy, ми обговоримо чотири: Список списків (LIL), діагональне сховище (DIA), стиснутий розріджений рядок (CSR) та Стиснутий розріджений стовпець (CSC).