En computación científica , almacenamiento de matriz de horizonte , o SKS, o un almacenamiento de matriz de banda variable , o esquema de almacenamiento de sobre [1] es una forma de una matriz de formato de almacenamiento de matriz dispersa que reduce el requisito de almacenamiento de una matriz más que el almacenamiento en bandas . En el almacenamiento en banda, se almacenan todas las entradas dentro de una distancia fija de la diagonal (llamada medio ancho de banda). En el almacenamiento de horizonte orientado a columnas, solo se almacenan las entradas desde la primera entrada distinta de cero hasta la última entrada distinta de cero en cada columna. También hay almacenamiento de horizonte orientado a filas y, para matrices simétricas, generalmente solo se almacena un triángulo. [2]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/8/85/Skyline_matrix.svg/560px-Skyline_matrix.svg.png)
El almacenamiento del horizonte se ha vuelto muy popular en los códigos de elementos finitos para la mecánica estructural , porque el horizonte se conserva mediante la descomposición de Cholesky (un método para resolver sistemas de ecuaciones lineales con una matriz simétrica definida positiva ; todos los rellenos se encuentran dentro del horizonte) , y los sistemas de ecuaciones de elementos finitos tienen un horizonte relativamente pequeño. Además, el esfuerzo de codificar el horizonte de Cholesky [3] es aproximadamente el mismo que el de Cholesky para matrices con bandas (disponible para matrices con bandas , por ejemplo, en LAPACK ; para un prototipo de código de horizonte, consulte [3] ).
Antes de almacenar una matriz en formato de horizonte, las filas y columnas normalmente se vuelven a numerar para reducir el tamaño del horizonte (el número de entradas almacenadas distintas de cero) y para disminuir el número de operaciones en el algoritmo de Cholesky del horizonte. El mismo algoritmo de renumeración heurística que reduce el ancho de banda también se utiliza para reducir el horizonte. El algoritmo básico y uno de los primeros en hacerlo es el algoritmo inverso de Cuthill-McKee .
Sin embargo, el almacenamiento de horizonte no es tan popular para sistemas muy grandes (muchos millones de ecuaciones) porque el horizonte de Cholesky no se adapta tan fácilmente para la computación paralela masiva , y los métodos dispersos generales, [4] que almacenan solo las entradas distintas de cero de la matriz, se vuelven más eficiente para problemas muy grandes debido a mucho menos relleno.
Ver también
Referencias
- ^ Watkins, David S. (2002), Fundamentos de cálculos matriciales (Segunda ed.), Nueva York: John Wiley & Sons, Inc., p. 60, ISBN 0-471-21394-2
- ^ Barrett, Richard; Baya; Chan; Demmel; Donato; Dongarra; Eijkout; Pozo; Romine; Van der Vorst (1994), "Skyline Storage (SKS)" , Plantillas para la solución de sistemas lineales , SIAM, ISBN 0-89871-328-5
- ^ a b George, Alan; Liu, Joseph WH (1981), Solución informática de grandes sistemas definidos positivos dispersos , Prentice-Hall Inc., ISBN 0-13-165274-5. El libro también contiene la descripción y el código fuente de rutinas simples de matriz dispersa, que siguen siendo útiles incluso si han sido reemplazadas durante mucho tiempo.
- ^ Duff, Iain S .; Erisman, Albert M .; Reid, John K. (1986), Métodos directos para matrices dispersas , Oxford University Press, ISBN 0-19-853408-6