Una matriz puede tener un millón de posiciones y solo unos miles de números distintos de cero. Guardar todos los ceros desperdicia espacio, pero borrarlos sin guardar sus posiciones destruye la matriz. Vamos a conservar valor y lugar, multiplicar usando solo contribuciones útiles y descubrir por qué una eliminación puede crear números donde antes había ceros.
Si necesitas repasar:
1. La forma cuenta posiciones; nnz cuenta entradas realmente no nulas
Una matriz m×n tiene mn posiciones. nnz es el número matemático de entradas distintas de cero; su densidad es nnz/(mn). Para reconstruir la matriz hay que conocer también dónde están y cuál es su forma, incluidas filas o columnas vacías.
Un formato disperso guarda índices además de valores. En matrices pequeñas o casi llenas, ese coste puede superar el ahorro. Las cifras de memoria que veremos cuentan los vectores de datos declarados y excluyen cabeceras de objetos y otras reservas de una biblioteca concreta.
Calcular ocupación sin confundir ceros y posiciones
Una matriz 4×4 tiene seis entradas no nulas.
Posiciones
4·4=16 lugares posibles.Densidad
6/16=3/8=0,375, es decir, 37,5 %.Ceros
Hay diez posiciones cero, un 62,5 %. Dos matrices con esos mismos números pueden tener patrones muy distintos.
Forma, ocupación y patrón son datos complementarios.
El porcentaje de ceros es uno menos la densidad, no el inverso de nnz.
Estimar memoria con un modelo de almacenamiento explícito
Matriz 1000×1000 con nnz=2998; valores de 8 bytes e índices de 4 bytes.
Densa
Un millón de valores requiere 8 000 000 bytes.
CSR
Valores y columnas requieren 12·2998=35 976 bytes.Los 1001 punteros de fila añaden 4004: total 39 980 bytes.
Comparar
El ahorro de estos vectores es grande por la baja ocupación. El total de una aplicación puede incluir más memoria y la representación no garantiza acelerar cualquier operación.
El coste se obtiene contando valores e índices.
Con estos tamaños, COO de dos índices por entrada usaría 16·2998=47 968 bytes, además de los datos de forma.
2. El patrón permite contar y, a veces, calcular sin almacenar una matriz general
Una diagonal completa n×n tiene n no nulos. Una tridiagonal con sus tres bandas completas tiene n+(n−1)+(n−1)=3n−2 para n≥1. Si alguna entrada permitida vale cero, el nnz real es menor: patrón permitido y ocupación efectiva no son lo mismo.
A veces conocemos una regla que aplica A sin construir todos sus datos. Por ejemplo, una tridiagonal de coeficientes fijos usa vecinos de cada componente. Eso se llama aplicar el operador; puede ahorrar índices, pero requiere conservar condiciones de borde y la regla exacta.
Contar una tridiagonal de tamaño pequeño
Una tridiagonal 4×4 tiene las tres bandas completamente no nulas.
Diagonal
Cuatro entradas.
Vecinas
La superior tiene tres y la inferior otras tres.
Sumar
nnz=4+3+3=10, de 16 posiciones.Para n=1 la misma fórmula da una entrada; no se inventan bandas de longitud negativa.
3n−2 procede de tres conteos, no de tres filas completas.
Si una entrada de esas bandas es cero, se resta al nnz efectivo.
Aplicar una tridiagonal mediante sus vecinos
A tiene diagonal dos y bandas vecinas menos uno; n=4 y x=(1,2,3,4).
Borde
Tomamos x₀ exterior y x₅ exterior iguales a cero si aquí numeramos componentes interiores de uno a cuatro.
Regla
(Ax)ᵢ=2xᵢ−xᵢ₋₁−xᵢ₊₁.Las filas dan cero, cero, cero y cinco.
Resultado
Ax=(0,0,0,5).Basta recorrer los cuatro componentes; la regla incorpora explícitamente los dos bordes.
No es obligatorio guardar una matriz general para aplicar una estructura conocida.
En la última fila, 2·4−3−0=5; no se usa periodicidad sin declararla.
3. COO almacena contribuciones con fila, columna y valor
En formato de coordenadas, cada registro es (i, j, valor). Fijaremos índices desde cero: filas 0,…, m−1 y columnas 0,…, n−1. La forma se guarda aparte; mirar el mayor índice presente no detecta dimensiones finales completamente vacías.
Al ensamblar una matriz pueden llegar varias contribuciones al mismo lugar. Declararemos que se suman, consolidaremos duplicados y eliminaremos ceros exactos para contar nnz. El número de registros sin consolidar puede ser distinto del número de entradas no nulas.
La forma conserva una fila y una columna que no aparecen en los datos
Forma 3×4; registros (0,0,2) y (1,2,5).
Ubicar
La primera fila tiene dos en columna cero. La segunda, cinco en columna dos.
Vacíos
La fila dos y la columna tres no contienen registros; siguen existiendo por la forma 3×4.
Reconstruir
La matriz es [[2,0,0,0],[0,0,5,0],[0,0,0,0]]. Tiene dos no nulos, no forma 2×3.
Los valores presentes no determinan todas las dimensiones.
Un índice de columna cuatro sería inválido para esta forma con base cero.
Cinco registros pueden acabar en un solo no nulo
Forma 3×4; (0,0,2), (0,0,−2), (1,2,5), (1,2,1), (2,0,0).
Duplicados
En (0,0), 2−2=0; en (1,2), 5+1=6.Ceros
La contribución explícita en (2,0) también vale cero.
Consolidar
Tras sumar y eliminar ceros quedan solo (1,2,6): nnz matemático uno, frente a cinco registros iniciales.
Contar registros sin conocer la política de duplicados puede dar un nnz engañoso.
Con otra política de ensamblaje, como reemplazar en lugar de sumar, se definiría otra matriz.
4. CSR usa intervalos de registros para conservar cada fila
CSR guarda valores, columnas y un vector de punteros de longitud m+1.
Su longitud es p[i+1]−p[i]. El primer puntero es cero; el último es el número de registros almacenados.
Los punteros son no decrecientes. Dos consecutivos iguales representan una fila vacía. También comprobamos que valores y columnas tengan la misma longitud y que cada columna esté en rango. Ordenar columnas dentro de cada fila puede facilitar operaciones, pero se declara como propiedad de la representación, no como identidad matemática obligatoria de cualquier almacenamiento.
Leer una fila vacía sin desplazar las siguientes
Forma 4×4; p=[0;2;2;4;6], columnas=[0;2;0;2;1;3], valores=[3;−1;2;4;5;6].
Fila cero
Registros k=0 y 1: tres en columna cero y menos uno en columna dos.
Fila uno
El intervalo 2≤k<2 está vacío.La fila permanece en su lugar.
Otras filas
La fila dos usa k=2,3: valores dos y cuatro en columnas cero y dos. La fila tres usa k=4,5: cinco y seis en columnas uno y tres.
La matriz es [[3,0,−1,0],[0,0,0,0],[2,0,4,0],[0,5,0,6]].
La suma de longitudes de fila es 2+0+2+2=6, igual al último puntero.
Detectar un puntero incompatible antes de multiplicar
Hay seis valores, pero se recibe p=[0;2;1;4;7] para cuatro filas.
Orden
Bajar de dos a uno contradice el orden de intervalos de CSR.
Final
El último puntero siete supera los seis registros disponibles.
Rechazo
La estructura es inválida. No se inventa un séptimo valor ni se calcula una fila con longitud negativa.
Validar la estructura evita una respuesta numérica sin significado.
La comprobación de columnas dentro de 0,…,3 sería adicional, aunque estos punteros fueran correctos.
5. Multiplicar recorre cada fila y consulta la componente indicada por su columna
Para Ax, cada entrada aᵢⱼ multiplica xⱼ y contribuye a yᵢ. En CSR recorremos solo los registros de esa fila. La posición en el vector de valores no es el índice de x: ese índice lo da el vector de columnas.
Un producto con representación sin duplicados requiere del orden de nnz+m operaciones de recorrido e inicialización. También se leen índices y datos; el acceso a memoria puede dominar. Esta estimación no dice que factorizar A, invertirla o multiplicar dos matrices cueste lo mismo.
La columna guardada decide qué dato de x multiplicar
Usar la matriz CSR anterior con x=(1,2,3,4).
Primeras filas
y₀=3·1−1·3=0; la fila uno vacía da y₁=0.Filas restantes
y₂=2·1+4·3=14; y₃=5·2+6·4=34.Salida
Ax=(0,0,14,34).Se realizaron seis productos de entradas no nulas. El primer cero de salida vino de cancelación; el segundo, de una fila vacía.
Una salida cero no implica que la fila no tuviera datos.
Multiplicar por componentes consecutivas sin leer columnas produciría otra operación.
Comprobar una matriz por su acción sobre vectores sencillos
Para la misma A, tomar e₂=(0,0,1,0), con índice dos desde cero.
Seleccionar
Solo la tercera componente de entrada vale uno.
Producto
Ae₂=(−1,0,4,0), exactamente la columna de índice dos.Referencia
Comparar el producto disperso con esa columna reconstruida a mano detecta errores de índices. Repetir con vectores base pequeños comprueba todas las columnas del ejemplo.
Una referencia independiente conserva el significado del producto.
La prueba sobre una matriz pequeña no demuestra que cualquier constructor de CSR sea correcto para cualquier tamaño.
6. El formato se escoge por las operaciones que repetiremos
COO resulta cómodo para recibir contribuciones en cualquier orden. CSR favorece el recorrido por filas y Ax. CSC organiza columnas; estructuras por bloques aprovechan pequeños bloques densos repetidos. Convertir entre formatos tiene coste y puede consolidar duplicados según la biblioteca.
Insertar un dato en vectores comprimidos puede exigir desplazar muchos registros y actualizar punteros. Por eso suele separarse la fase de ensamblaje de la de cálculo repetido. Conocer la matriz no obliga a usar un único formato durante todas sus etapas.
Muchas inserciones y muchos productos piden fases distintas
Se reciben contribuciones de una malla y luego se calculará Ax miles de veces.
Construir
Guardar temporalmente ternas con índices y sumar duplicados permite recibir contribuciones sin desplazar un bloque comprimido en cada llegada.
Preparar
Consolidar y ordenar por filas produce los vectores CSR, verificando forma y rangos.
Reutilizar
Los productos repetidos aprovechan esa estructura ya preparada. El coste de conversión se compara con el número de usos previstos.
Una estructura de construcción puede diferir de la estructura de trabajo.
No se presenta el coste de preparación como cero al comparar alternativas.
Leer como columnas lo que eran filas puede transponer la operación
La matriz A=[[1,2],[0,3]] tiene CSR p=[0;2;3], columnas=[0;1;1], valores=[1;2;3].
Interpretación CSR
La fila cero contiene uno y dos; la fila uno, tres en columna uno.
Otra interpretación
Si esos mismos vectores se interpretan como CSC, los índices internos pasan a ser filas.
Se obtiene [[1,0],[2,3]]=Aᵀ.Comprobar
Para x=(1,1), Ax=(3,3), mientras Aᵀx=(1,5).Compartir datos de vectores no significa compartir el mismo mapa.
El significado del índice depende del formato declarado.
La coincidencia de longitudes en una matriz cuadrada puede esconder esta confusión.
7. La eliminación puede crear relleno y su orden cambia el patrón
Al eliminar una incógnita se combinan filas. Una posición inicialmente cero puede recibir una contribución no nula: eso es relleno. En una matriz simétrica, eliminar un centro puede conectar variables que antes solo se relacionaban a través de él.
Reordenar incógnitas puede reducir relleno, pero hay que permutar matriz, segundo miembro y solución coherentemente. El pivoteo por estabilidad también influye; no se sacrifica automáticamente una condición numérica necesaria por ahorrar unos registros.
Eliminar el centro de una estrella crea conexiones entre sus hojas
A=[[4,1,1,1],[1,2,0,0],[1,0,2,0],[1,0,0,2]].
Pivote central
Al eliminar la primera variable con pivote cuatro, el bloque restante pasa a 2I−(1/4)11ᵀ.
Relleno
Sus diagonales valen 7/4 y las seis posiciones fuera de diagonal valen −1/4. Antes esas seis eran cero.
Otro orden
Eliminar primero las tres hojas evita conectar hojas entre sí en este ejemplo. Cambia el almacenamiento intermedio, no la solución del sistema correctamente permutado.
El nnz inicial no basta para contar memoria de factores.
Los pivotes de este ejemplo son válidos; no se asume que cualquier matriz permita cualquier eliminación sin pivoteo.
Permutar exige transformar también la pregunta y la respuesta
A=[[2,1],[1,3]], b=(4,7); intercambiar las dos incógnitas.
Nuevo orden
Con P que intercambia componentes: A nueva=PAPᵀ=[[3,1],[1,2]], b nuevo=Pb=(7,4).
Resolver
La solución en nuevo orden es z=(2,1).Recuperar
x=Pᵀz=(1,2), y Ax=(4,7).Olvidar la última recuperación asignaría los valores a las variables equivocadas.
Cambiar orden conserva el problema solo si se conserva la correspondencia.
Una permutación simétrica mantiene simetría y positividad definida en el marco real.
8. Descartar un número pequeño aproxima la matriz y puede cambiar su solución
Un cero estructural es una entrada que el modelo define como cero. Un valor pequeño sigue siendo un dato no nulo. Reemplazarlo por cero es una aproximación que debe tener umbral declarado y una evaluación de su efecto.
Una perturbación pequeña de A no garantiza una perturbación pequeña de la solución cuando el problema está mal condicionado o cerca de perder una propiedad. Además de validar índices y reconstruir un ejemplo pequeño, comprobamos residual del sistema original y propiedades que necesite el método posterior.
Una entrada pequeña puede sostener la positividad de una matriz
A tiene filas (1;0,01) y (0,01;0,0002). Se eliminan magnitudes menores que 0,001.
Original
El primer menor principal vale uno y el determinante 0,0002−0,0001=0,0001>0. A es simétrica definida positiva.
Descartar
Solo se borra 0,0002. La matriz aproximada Ã, con filas (1;0,01) y (0,01;0), tiene determinante −0,0001.
Efecto
à es indefinida: una propiedad requerida, por ejemplo, por gradiente conjugado clásico ya no está garantizada.
Pequeño en magnitud no significa prescindible para cualquier objetivo.
El umbral cambió el problema y su estructura espectral.
Medir el efecto sobre una solución conocida
Para esa A, tomar x*=(1,1), de donde b=(1,01;0,0102).
Sistema aproximado
La segunda ecuación de Ãx=b es 0,01x₁=0,0102, luego x₁=1,02.Primera ecuación
1,02+0,01x₂=1,01 da x₂=−1.Comparar
La solución cambió de (1,1) a (1,02;−1), aunque se borrara solo 0,0002. En la A original, el residual de la aproximación es (0;0,0002).
La comprobación se hace contra A original, no solo contra Ã.
Un residual pequeño en escala absoluta todavía necesita interpretación de condicionamiento.
Ahora lo resolvemos de principio a fin.
EJEMPLO RESUELTO 1
Contar una tridiagonal
¿Cuántas entradas no nulas tiene una tridiagonal 5×5 con todas sus bandas no nulas?
Patrón
La matriz es 5×5 y todas las posiciones de sus tres bandas son no nulas.
Diagonal central
Tiene cinco posiciones.
Superior
Tiene cuatro: falta la posición que saldría fuera en el último borde.
Inferior
También tiene cuatro, por el borde opuesto.
Sumar
nnz=5+4+4=13.Control
3·5−2=13.Tridiagonal solo limita posiciones posibles; la respuesta usa explícitamente que las bandas están completas.
13 entradas.
3·5−2=13.
EJEMPLO RESUELTO 2
Multiplicar sin ceros
A=[[2,0,0],[0,3,4],[0,0,5]], x=(1,2,3). Calcula Ax.
Datos
A=[[2,0,0],[0,3,4],[0,0,5]], x=(1,2,3).Cada fila produce una componente de Ax.
Primera fila
2·1=2.Las otras dos entradas son cero.
Segunda fila
3·2+4·3=6+12=18.Tercera fila
5·3=15.Salida
Ax=(2,18,15).Control
Se usaron cuatro productos de entradas no nulas. Sus columnas seleccionan x₁, x₂, x₃ y x₃, respectivamente, si numeramos aquí de uno a tres.
Ax=(2,18,15).
Solo hicieron falta cuatro productos de entradas no nulas.
Los símbolos que hemos usado
- nnz(A)
- Número de entradas matemáticamente no nulas de A.
- Densidad
- nnz dividido por el número total de posiciones.
- COO
- Almacenamiento por ternas fila, columna y valor.
- CSR
- Almacenamiento por filas mediante valores, columnas y punteros al inicio de cada fila.
- Relleno
- Entradas que eran nulas en A y aparecen no nulas en sus factores.
- Ancho de banda
- Distancia de las diagonales ocupadas a la diagonal principal.
Ahora te toca a ti.
Tienes cinco ejercicios. Inténtalos; las pistas te ayudan si te atascas.
Practicar este tema →