8.1: Álgebra de matriz dispersa
- Page ID
- 124928
\( \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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
Cuando las matrices son escasas, los enfoques ordinarios de la aritmética matricial son derrochadores, ya que se dedica mucho tiempo a sumar/restar o multiplicar por cero. Por ejemplo, considere la matriz tridiagonal discutida anteriormente. Para realizar el producto matriz-vector\(\mathbf{H} \vec{\psi}\) de la manera habitual, para cada fila\(i\) debemos calcular
\[\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}\]
La suma implica operaciones\(O(N)\) aritméticas, por lo que el tiempo de ejecución general para todas\(N\) las filas es\(O(N^{2})\). Claramente, sin embargo, la mayor parte de este tiempo se dedica a multiplicar cero elementos de\(\mathbf{H}\) por elementos de\(\vec{\psi}\), lo que no contribuye al resultado final. Si pudiéramos omitir estos términos de cada suma, el tiempo de ejecución general para el producto sería solo\(O(N)\).
Sin embargo, tales ahorros no se pueden lograr con las estructuras de datos de matriz que hemos estado usando hasta ahora. Para calcular el producto matriz-vector de manera eficiente, el procesador necesita saber qué elementos en cada fila de no\(\mathbf{H}\) son cero, para que pueda saltarse el resto. Sin embargo, las matrices no proporcionan una forma rápida de identificar qué elementos son distintos de cero; la única forma de averiguarlo es buscar los bloques de almacenamiento uno por uno, lo que lleva\(O(N)\) tiempo en cada fila. Eso acabaría con los ahorros de tiempo de ejecución.
Scipy proporciona estructuras de datos especiales para almacenar matrices dispersas. A diferencia de las matrices ordinarias, estas estructuras de datos están diseñadas para que se omita cero elementos, lo que no solo ahorra memoria, sino que también permite que ciertas operaciones de matriz se aceleren mucho. A diferencia de las matrices, que pueden representar no solo matrices (matrices 2D) sino también vectores (matrices 1D) y tensores de rango superior (matrices con dimensiones superiores a 2), estas estructuras de datos dispersas están específicamente restringidas a matrices.
Pero aquí hay una captura importante: no hay una estructura de datos de matriz dispersa única que sea ideal para cada escenario. En cambio, hay múltiples formatos de matriz dispersa, y cada formato solo es efectivo para un cierto subconjunto de operaciones de matriz, o para ciertos tipos de matrices dispersas. Por lo tanto, necesitamos saber cómo se implementan los diferentes formatos de matriz dispersa, así como sus beneficios y limitaciones. De los muchos formatos de matriz dispersa que ofrece Scipy, discutiremos cuatro: Lista de listas (LIL), Almacenamiento Diagonal (DIA), Fila dispersa comprimida (CSR) y Columna dispersa comprimida (CSC).