Bandwidth reduction on sparse matrices by introducing new variables

Reducción del ancho de banda de matrices dispersas mediante la introducción de nuevas variables

Se analiza un método para la reducción del ancho de banda de matrices dispersas, el cual consiste en fraccionar ecuaciones,substituir e introducir nuevas variables, similar a la descomposición en subestructuras utilizada en el método de los elementosfinitos (FEM). Es especialmente útil si el ancho de banda no puede ser reducido intercambiando estratégicamente columnasy líneas. En estos casos, dividir ecuaciones y reordenar líneas y columnas puede reducir el ancho de banda, al costo deintroducir nuevas variables. En comparación con el método de las subestructuras en el FEM, en el cual la descomposiciónestá hecha antes de obtener la matriz del sistema, la metodología que se presenta está aplicada después de obtener el sistemalineal, independiente de su origen. El método está aplicado con éxito en una matriz dispersa en el contexto del FEM, locual resulta en un aumento de eficiencia del algoritmo directo para resolver el sistema lineal.

INTRODUCCIÓN

Un sistema lineal, convenientemente denotado en una notación matricial-vectorial

​$\left[\begin{array}{c}{A}_{11}\dots A_{1n}\\ ⋮\\ A_{n1}\dots A_{nn}\end{array}\right]$$\left[\begin{array}{c}{x}_1\\ ⋮\\ x_n\end{array}\right]$=$\left[\begin{array}{c}{y}_1\\ ⋮\\ y_n\end{array}\right]$

es invariante bajo el intercambio simultáneo de xi y xj y las columnas i y j de la matriz, y el intercambio simultáneo de yi e yj y las filas i y j de la matriz. Dependiendo del algoritmo de solución que deba aplicarse, pueden ser ventajosas diferentes características de la matriz. Si, por ejemplo, se utiliza la eliminación gaussiana, la creación de entradas no nulas (relleno) durante el proceso puede reducirse, bien reordenando el sistema de forma que las entradas no nulas se concentren en la diagonal principal y en las columnas que van hacia arriba desde ella, bien concentrando las entradas no nulas en una banda alrededor de la diagonal principal. Este último caso corresponde a una reducción del ancho de banda de la matriz. El ancho de banda de una matriz está relacionado con la distancia máxima de las entradas no nulas de la matriz respecto a la diagonal principal. Se distingue el ancho de banda izquierdo y el derecho,

​$k_1=\mathrm{m}\mathrm{a}\mathrm{x}(i-j),i>j,A_{ij}\ne 0$    (2)

​$k_2=\mathrm{m}\mathrm{a}\mathrm{x}(j-i),j>i,A_{ij}\ne 0$    (3)

que coinciden para matrices simétricas.El ancho de banda b viene dado por $b=k_1+k_2$. Especialmente los algoritmos de solución directa pueden aprovechar una estructura de bandas, lo que además ayuda a reducir los requisitos de memoria. Para los solucionadores directos, $t_mathrm{cpu} approx cb^2$ se mantiene. En consecuencia, uno está interesado en reordenar el sistema lineal de manera que el ancho de banda de la matriz del sistema se reduzca.​