27.4: Rellenar y reordenar

Comenzar material avanzado

La sección anterior se centró en el costo computacional de resolver un sistema lineal gobernado por matrices dispersas con bandas. Esta sección introduce algunas matrices dispersas adicionales y también se discuten conceptos adicionales sobre la eliminación gaussiana para sistemas dispersos.

Sistema cíclico

Primero, mostremos que un pequeño cambio en un sistema físico -y por lo tanto en el sistema lineal correspondiente\(A\) - puede marcar una gran diferencia en el patrón de dispersidad de la matriz factorizada\(U\). Aquí, consideramos una versión modificada del sistema\(n\) -masa-resorte, donde la primera masa está conectada a la última masa, como se muestra en la Figura 27.5. Nos referiremos a este sistema como un sistema “cíclico”, ya que los resortes forman un círculo. Recordemos que un sistema de masa-resorte sin la conexión adicional produce un sistema tridiagonal. Con la conexión extra entre la primera y la última masa, ahora la\((1, n)\) entrada y\((n, 1)\) entrada de la matriz son distintas de cero como se muestra en la Figura\(27.6(\mathrm{a})\) (for\(n=25\)); claramente, la matriz

Figura 27.5: Sistema de masa-resorte “cíclico” con\(n=6\) masas.

a) Matriz original\(A\)

b) inicio de la etapa 5

c) Matriz final\(U\)

Figura 27.6: Ilustración de la eliminación gaussiana aplicada a un sistema de\(25 \times 25\) “flecha”. Las entradas rojas son “rellenadas” introducidas en el proceso de factorización. El pivote para cada paso está marcado por un cuadrado rojo.

ya no es tridiagonal. De hecho, si aplicamos nuestra clasificación estándar para matrices bandeadas, la matriz cíclica se caracterizaría por su ancho de banda de\(m_{\mathrm{b}}=n-1\).

Aplicando la eliminación gaussiana al sistema “cíclico”, inmediatamente reconocemos que la\((1, n)\) entrada de la matriz original “cae” a lo largo de la última columna,\(n-2\) creando rellenos (ver Figuras\(27.6(\mathrm{~b})\) y\(27.6(\mathrm{c}))\). Además, la\((n, 1)\) entrada original también crea una entrada distinta de cero en la fila inferior, que se mueve a través de la matriz con el pivote a medida que la matriz se factoriza. Como resultado, el recuento de operaciones para la factorización del sistema “cíclico” es de hecho similar al de un sistema pentadiagonal: aproximadamente\(14 n\) FLOP. La aplicación de retrosustitución a la matriz factorizada, que contiene aproximadamente\(3 n\) nonceros, requiere\(5 n\) FLOP. Así, la solución del sistema cíclico -que tiene apenas dos entradas distintas de cero más que el sistema tridiagonal- requiere más del doble de operaciones\((19 n\) vs\(8 n)\). Sin embargo, también es importante señalar que este conteo de\(\mathcal{O}(n)\) operaciones es una mejora significativa en comparación con la estimación de\(\mathcal{O}\left(n\left(m_{\mathrm{b}}+1\right)^{2}\right)=\mathcal{O}\left(n^{3}\right)\) operación basada en clasificar el sistema como un “soporte” estándar con un ancho de banda\(m_{\mathrm{b}}=n-1\).

Observamos que la estructura de relleno de\(U\) toma la forma de un horizonte definido por la envolvente de las columnas de la matriz original\(A\). Se trata de un director general.

Reordenación

Al construir un sistema lineal correspondiente a nuestro sistema de masa de resorte, asociamos la\(j^{\text {th }}\) entrada del vector de solución -y por lo tanto la\(j^{\text {th }}\) columna de la matriz- con el desplazamiento de la\(j^{\text {th }}\) masa (contando desde la pared) y asociamos el \(i^{\text {th }}\)ecuación con la condición de equilibrio de fuerza

a)\(A\) (naturales,\(\mathrm{nnz}(A)=460)\)

b)\(U\) (natural,\(\operatorname{nnz}(U)=1009\))

c)\(A^{\prime}\left(\mathrm{AMD}, \operatorname{nnz}\left(A^{\prime}\right)=460\right)\)

d)\(U^{\prime}\left(\mathrm{AMD}, \mathrm{nnz}\left(U^{\prime}\right)=657\right)\)

Figura 27.7: Comparación del patrón de dispersidad y los rellenos de eliminación gaussianos para un sistema de\(n=100\) “soporte” resultante del ordenamiento natural y un sistema equivalente usando el orden de grado mínimo aproximado (AMD).

de la\(i^{\text {th }}\) masa. Si bien este es posiblemente el orden más “natural” para el sistema de masa de resorte, podríamos haber asociado una columna y una fila dadas de la matriz con una condición de desplazamiento y equilibrio de fuerzas diferentes, respectivamente. Obsérvese que este “reordenamiento” de las incógnitas y ecuaciones del sistema lineal equivale a “cambiar” las filas de columnas de la matriz, lo cual se conoce formalmente como permutación. Es importante destacar que podemos describir el mismo sistema físico usando muchos ordenamientos diferentes de las incógnitas y ecuaciones; aunque las matrices parezcan diferentes, estas matrices que describen el mismo sistema físico pueden considerarse equivalentes, ya que todas producen la misma solución para un lado derecho dado (dado ambos la solución y el lado derecho se reordenan de manera consistente).

El reordenamiento puede marcar una diferencia significativa en el número de llenados y el recuento de operaciones. La figura\(27.7\) muestra una comparación del número de rellenos para un sistema\(n=100\) lineal que surge de dos ordenamientos diferentes de una discretización finita diferente de la ecuación de calor bidimensional en una cuadrícula\(10 \times 10\) computacional. En la Figura 27.7 (a) se muestra una matriz de “soporte” de ancho de banda que\(m_{\mathrm{b}}=10\) surge del ordenamiento “natural”. La matriz tiene 460 entradas distintas de cero. Como se discutió en la sección anterior, la eliminación gaussiana de la matriz produce una matriz triangular superior\(U\) con entradas aproximadamente distintas de\(n\left(m_{\mathrm{b}}+1\right)=1100\) cero (más precisamente 1009 para este caso particular), que se muestra en la Figura 27.7 (b). En la Figura 27.7 (c) se muestra un sistema equivalente obtenido utilizando el orden de grado mínimo aproximado (AMD). Esta matriz recién reordenada\(A^{\prime}\) también tiene 460 entradas distintas de cero porque permutar (o cambiar) filas y columnas claramente no cambia el número de no ceros. Por otro lado, la aplicación de la eliminación gaussiana a esta matriz reordenada arroja una matriz triangular superior\(U\) mostrada en la Figura\(27.7(\mathrm{~d})\), la cual solo tiene 657 entradas distintas de cero. Tenga en cuenta que el número de relleno se ha reducido aproximadamente en un factor de dos: desde\(1009-280=729\) para el pedido “natural” hasta\(657-280=377\) para el pedido AMD. (La matriz original\(A\) tiene 280 entradas distintas de cero en la parte triangular superior).

En general, el uso de un pedido adecuado puede reducir significativamente el número de rellenos y, por lo tanto, el costo computacional. En particular, para una matriz dispersa que surge de la discretización de diferencia finita\(n\) desconocida (o elemento finito) de las PDEs bidimensionales, hemos observado que el ordenamiento “natural” produce un sistema “soporte” con\(m_{\mathrm{b}}=\sqrt{n}\); la eliminación gaussiana del sistema produce un superior matriz triangular con entradas distintas de\(n\left(m_{\mathrm{b}}+1\right) \approx n^{3 / 2}\) cero. Por otro lado, el número de rellenos para un mismo sistema con un orden óptimo (es decir, mínimo de llenado) produce una matriz triangular superior con\(\mathcal{O}(n \log (n))\) incógnitas. Por lo tanto, los pedidos pueden tener un impacto significativo tanto en el recuento de operaciones como en el almacenamiento para sistemas lineales dispersos grandes.

Material Avanzado