En matemáticas numéricas , las matrices jerárquicas (matrices H) [1] [2] [3] se utilizan como aproximaciones de datos dispersos de matrices no dispersas. Mientras que una matriz dispersa de dimensiones se puede representar de manera eficiente en unidades de almacenamiento almacenando solo sus entradas distintas de cero, una matriz no dispersa requeriría unidades de almacenamiento, y utilizar este tipo de matrices para grandes problemas sería, por tanto, prohibitivamente caro en términos de almacenamiento y tiempo de cálculo. Las matrices jerárquicas proporcionan una aproximación que solo requiere unidades de almacenamiento, donde es un parámetro que controla la precisión de la aproximación. En aplicaciones típicas, por ejemplo, al discretizar ecuaciones integrales [4] [5] [6] [7] [8] , [9] preacondicionar los sistemas resultantes de ecuaciones lineales, [10] o resolver ecuaciones diferenciales parciales elípticas [11] [ 12] [13] [14] , un rango proporcional a con una pequeña constante es suficiente para asegurar una precisión de . En comparación con muchas otras representaciones de matrices no dispersas con datos escasos, las matrices jerárquicas ofrecen una gran ventaja: los resultados de las operaciones aritméticas de matrices como la multiplicación, factorización o inversión de matrices se pueden aproximar en operaciones, donde [2]
Idea básica
Las matrices jerárquicas se basan en aproximaciones locales de bajo rango: deje ser conjuntos de índices, y dejar denotar la matriz que tenemos que aproximar. En muchas aplicaciones (ver arriba), podemos encontrar subconjuntos tal que puede ser aproximado por un rangomatriz. Esta aproximación se puede representar en forma factorizada con factores . Mientras que la representación estándar de la matriz requiere unidades de almacenamiento, la representación factorizada requiere sólo unidades. Si no es demasiado grande, los requisitos de almacenamiento se reducen significativamente.
Para aproximar toda la matriz , se divide en una familia de submatrices. Las submatrices grandes se almacenan en representación factorizada, mientras que las submatrices pequeñas se almacenan en representación estándar para mejorar la eficiencia.
Las matrices de bajo rango están estrechamente relacionadas con las expansiones degeneradas utilizadas en la agrupación de paneles y el método rápido multipolar para aproximar operadores integrales. En este sentido, las matrices jerárquicas pueden considerarse las contrapartes algebraicas de estas técnicas.
Aplicación a operadores integrales
Las matrices jerárquicas se utilizan con éxito para tratar ecuaciones integrales, por ejemplo, los operadores potenciales de capa simple y doble que aparecen en el método de elementos de contorno . Un operador típico tiene la forma
El método de Galerkin conduce a entradas de matriz de la forma
dónde y son familias de funciones de base de elementos finitos. Si la función del kerneles suficientemente suave, podemos aproximarlo por interpolación polinomial para obtener
dónde es la familia de puntos de interpolación y es la familia correspondiente de polinomios de Lagrange . Reemplazo por da una aproximación
con los coeficientes
Si elegimos y use los mismos puntos de interpolación para todos , obtenemos .
Evidentemente, cualquier otra aproximación que separe las variables y , por ejemplo, la expansión multipolar, también nos permitiría dividir la integral doble en dos integrales simples y así llegar a una matriz de bajo rango factorizada similar.
De particular interés son las técnicas de aproximación cruzada [6] [7] [15] que utilizan solo las entradas de la matriz originalpara construir una aproximación de rango bajo .
Aplicación a ecuaciones diferenciales parciales elípticas
Dado que el operador de solución de una ecuación diferencial parcial elíptica se puede expresar como un operador integral que involucra la función de Green , no es sorprendente que la inversa de la matriz de rigidez que surge del método de elementos finitos y el método espectral pueda aproximarse mediante una matriz jerárquica.
La función de Green depende de la forma del dominio computacional, por lo que generalmente no se conoce. Sin embargo, se pueden emplear operaciones aritméticas aproximadas para calcular una inversa aproximada sin conocer la función explícitamente.
Sorprendentemente, es posible probar [11] [12] [13] [14] que la inversa se puede aproximar incluso si el operador diferencial involucra coeficientes no suaves y, por lo tanto, la función de Green no es suave.
Operaciones aritmeticas
La innovación más importante del método de matriz jerárquica es el desarrollo de algoritmos eficientes para realizar operaciones aritméticas matriciales (aproximadas) en matrices no dispersas, por ejemplo, para calcular inversas aproximadas, descomposiciones LU y soluciones a ecuaciones matriciales.
El algoritmo central es la multiplicación matriz-matriz eficiente, es decir, el cálculo de para matrices jerárquicas y un factor escalar . El algoritmo requiere que las submatrices de las matrices jerárquicas estén organizadas en una estructura de árbol de bloques y aprovecha las propiedades de las matrices factorizadas de bajo rango para calcular la actualización. en operaciones.
Aprovechando la estructura de bloques, la inversa se puede calcular usando la recursividad para calcular inversas y complementos de Schur de bloques diagonales y combinando ambos usando la multiplicación matriz-matriz. De manera similar, la descomposición LU [16] [17] se puede construir usando solo recursividad y multiplicación. Ambas operaciones también requieren operaciones.
H 2 -matrices
Para tratar problemas muy grandes, la estructura de matrices jerárquicos se puede mejorar: H 2 -matrices [18] [19] reemplazan la estructura general de bajo rango de los bloques por una representación jerárquica estrechamente relacionado con el método rápido multipolar con el fin para reducir la complejidad del almacenamiento a.
En el contexto de los operadores integrales de frontera, reemplazando el rango fijo por rangos dependientes del bloque conduce a aproximaciones que preservan la tasa de convergencia del método del elemento de frontera subyacente en una complejidad de [20] [21]
Las operaciones aritméticas como multiplicación, inversión y factorización Cholesky o LR de matrices H 2 se pueden implementar en base a dos operaciones fundamentales: la multiplicación matriz-vector con submatrices y la actualización de submatrices de bajo rango. Si bien la multiplicación matriz-vector es sencilla, la implementación de actualizaciones eficientes de bajo rango con bases de clúster optimizadas adaptativamente plantea un desafío significativo. [22]
Literatura
- ^ Hackbusch, Wolfgang (1999). "Una aritmética de matriz dispersa basada en matrices H. Parte I: Introducción a las matrices H". Computación . 62 (2): 89–108. doi : 10.1007 / s006070050015 .
- ^ a b Grasedyck, Lars; Hackbusch, Wolfgang (2003). "Construcción y aritmética de matrices H". Computación . 70 (4): 295–334. doi : 10.1007 / s00607-003-0019-1 .
- ^ Hackbusch, Wolfgang (2015). Matrices jerárquicas: algoritmos y análisis . Serie Springer en Matemática Computacional. 49 . Saltador. doi : 10.1007 / 978-3-662-47324-5 . ISBN 978-3-662-47323-8.
- ^ Bebendorf, Mario (2008). Matrices jerárquicas: un medio para resolver de manera eficiente problemas de valores de frontera elípticos . Saltador.
- ^ Hackbusch, Wolfgang; Khoromskij, Boris N. (2000). "Una aritmética de matriz H dispersa. Parte II: Aplicación a problemas multidimensionales". Computación . 64 : 21–47.
- ^ a b Bebendorf, Mario (2000). "Aproximación de matrices de elementos de contorno". Numer. Matemáticas . 86 (4): 565–589. doi : 10.1007 / pl00005410 .
- ^ a b Bebendorf, Mario; Rjasanow, Sergej (2003). "Aproximación adaptativa de bajo rango de matrices de colocación". Computación . 70 : 1–24. CiteSeerX 10.1.1.133.182 . doi : 10.1007 / s00607-002-1469-6 .
- ^ Börm, Steffen; Grasedyck, Lars (2005). "Aproximación cruzada híbrida de operadores integrales". Numer. Matemáticas . 101 (2): 221–249. CiteSeerX 10.1.1.330.8950 . doi : 10.1007 / s00211-005-0618-1 .
- ^ Börm, Steffen; Christophersen, Sven (2016). "Aproximación de operadores integrales por cuadratura de Green y aproximación cruzada anidada". Numer. Matemáticas . 133 (3): 409–442. arXiv : 1404,2234 . doi : 10.1007 / s00211-015-0757-y .
- ^ Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2016). "Existencia de aproximaciones de matriz H a las inversas de matrices BEM: el operador de capa simple". Matemáticas. Comp . 85 (297): 119-152. arXiv : 1311.5028 . doi : 10.1090 / mcom / 2990 .
- ^ a b Bebendorf, Mario; Hackbusch, Wolfgang (2003). "Existencia de aproximaciones de matriz H a la matriz FE inversa de operadores elípticos con-coefficients ". Numer. Math . 95 : 1–28. doi : 10.1007 / s00211-002-0445-6 .
- ^ a b Börm, Steffen (2010). "Aproximación de operadores solución de ecuaciones diferenciales parciales elípticas por matrices H y H 2 ". Numer. Matemáticas . 115 (2): 165-193. doi : 10.1007 / s00211-009-0278-7 .
- ^ a b Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2015). "Aproximabilidad de la matriz H de las inversas de matrices FEM". Numer. Matemáticas . 131 (4): 615–642. arXiv : 1308.0499 . doi : 10.1007 / s00211-015-0706-9 .
- ^ a b Shen, Jie; Wang, Yingwei; Xia, Jianlin (2016). "Métodos espectrales directos estructurados rápidos para ecuaciones diferenciales con coeficientes variables". Revista SIAM de Computación Científica . 38 (1): A28 – A54. doi : 10.1137 / 140986815 .
- ^ Tyrtyshnikov, Eugene (2000). "Aproximación cruzada incompleta en el método mosaico-esqueleto". Computación . 64 (4): 367–380. CiteSeerX 10.1.1.100.6153 . doi : 10.1007 / s006070070031 .
- ^ Bebendorf, Mario (2007). "Por qué las discretizaciones de elementos finitos se pueden factorizar mediante matrices jerárquicas triangulares". SIAM J. Numer. Anal . 45 (4): 1472–1494. doi : 10.1137 / 060669747 .
- ^ Grasedyck, Lars; Kriemann, Ronald; Le Borne, Sabine (2009). "Preacondicionamiento H-LU basado en descomposición de dominios" . Numer. Matemáticas . 112 (4): 565–600. doi : 10.1007 / s00211-009-0218-6 .
- ^ Hackbusch, Wolfgang; Khoromskij, Boris N .; Sauter, Stefan (2002). Sobre matrices H 2 . Conferencias de Matemática Aplicada . págs. 9-29. doi : 10.1007 / 978-3-642-59709-1_2 . ISBN 978-3-642-64094-0.
- ^ Börm, Steffen (2010). Métodos numéricos eficientes para operadores no locales: compresión de matriz H 2 , algoritmos y análisis . EMS Tracts in Mathematics. ISBN 9783037190913.
- ^ Sauter, Stefan (2000). "Agrupación de paneles de orden variable". Computación . 64 (3): 223–261. doi : 10.1007 / s006070050045 .
- ^ Börm, Steffen; Sauter, Stefan (2005). "BEM con complejidad lineal para los operadores integrales de límites clásicos" . Matemáticas. Comp . 74 (251): 1139-1177. doi : 10.1090 / s0025-5718-04-01733-8 .
- ^ Börm, Steffen; Reimer, Knut (2015). "Operaciones aritméticas eficientes para matrices estructuradas por rangos basadas en actualizaciones jerárquicas de rango bajo". Comp. Vis. Sci . 16 (6): 247–258. arXiv : 1402.5056 . doi : 10.1007 / s00791-015-0233-3 .
Software
HLib es una biblioteca de software C que implementa los algoritmos más importantes para-matrices.
AHMED es una biblioteca de software C ++ que se puede descargar con fines educativos.
HLIBpro es una implementación de los algoritmos de matriz jerárquica central para aplicaciones comerciales.
H2Lib es una implementación de código abierto de algoritmos matriciales jerárquicos destinados a la investigación y la enseñanza.
impresionante-jerárquica-matrices es un repositorio que contiene una lista de otras implementaciones de H-Matrices.
HierarchicalMatrices.jl es un paquete de Julia que implementa matrices jerárquicas.