Иерархическая матрица
Метод аппроксимации

В числовой математике иерархические матрицы (H-матрицы) [1] [2] [3] используются в качестве разреженных по данным аппроксимаций неразреженных матриц. В то время как разреженная матрица размерности может быть эффективно представлена ​​в единицах хранения путем хранения только ее ненулевых элементов, неразреженная матрица потребовала бы единиц хранения, и использование этого типа матриц для больших задач было бы поэтому непозволительно дорогим с точки зрения хранения и времени вычислений. Иерархические матрицы обеспечивают аппроксимацию, требующую только единиц хранения, где - параметр, управляющий точностью аппроксимации. В типичных приложениях, например, при дискретизации интегральных уравнений, [4] [5] [6] [7] [8] [9] предварительной обработке результирующих систем линейных уравнений, [10] или решении эллиптических уравнений в частных производных, [11] [12] [13] [14] ранг, пропорциональный с малой константой, достаточен для обеспечения точности . По сравнению со многими другими разреженными по данным представлениями неразреженных матриц, иерархические матрицы предлагают важное преимущество: результаты матричных арифметических операций, таких как умножение матриц, факторизация или инверсия, могут быть аппроксимированы в операциях, где [2] н {\displaystyle n} О ( н ) {\displaystyle O(n)} О ( н 2 ) {\displaystyle O(n^{2})} О ( н к бревно ⁡ ( н ) ) {\displaystyle O(nk\,\log(n))} к {\displaystyle к} бревно ⁡ ( 1 / ϵ ) γ {\displaystyle \log(1/\epsilon)^{\gamma }} γ {\displaystyle \гамма} ϵ {\displaystyle \epsilon} О ( н к α бревно ⁡ ( н ) β ) {\displaystyle O(nk^{\alpha }\,\log(n)^{\beta })} α , β ∈ { 1 , 2 , 3 } . {\displaystyle \альфа ,\бета \in \{1,2,3\}.}

Основная идея

Иерархические матрицы полагаются на локальные приближения низкого ранга: пусть будут наборами индексов, а пусть обозначает матрицу, которую мы должны аппроксимировать. Во многих приложениях (см. выше) мы можем найти подмножества , которые могут быть аппроксимированы матрицей ранга . Это приближение может быть представлено в факторизованной форме с множителями . В то время как стандартное представление матрицы требует единиц хранения, факторизованное представление требует только единиц. Если не слишком велико, требования к хранению значительно сокращаются. я , Дж. {\displaystyle I,J} Г ∈ Р я × Дж. {\displaystyle G\in {\mathbb {R} }^{I\times J}} т ⊆ я , с ⊆ Дж. {\displaystyle t\subseteq I,s\subseteq J} Г | т × с {\displaystyle G|_{t\times s}} к {\displaystyle к} Г | т × с ≈ А Б ∗ {\displaystyle G|_{t\times s}\approx AB^{*}} А ∈ Р т × к , Б ∈ Р с × к {\displaystyle A\in {\mathbb {R} }^{t\times k},B\in {\mathbb {R} }^{s\times k}} Г | т × с {\displaystyle G|_{t\times s}} О ( ( # т ) ( # с ) ) {\displaystyle O((\#t)(\#s))} О ( к ( # т + # с ) ) {\displaystyle O(k(\#t+\#s))} к {\displaystyle к}

Для аппроксимации всей матрицы она разбивается на семейство подматриц. Большие подматрицы хранятся в факторизованном представлении, в то время как маленькие подматрицы хранятся в стандартном представлении для повышения эффективности. Г {\displaystyle G}

Матрицы низкого ранга тесно связаны с вырожденными разложениями, используемыми в панельной кластеризации, и быстрым мультипольным методом для аппроксимации интегральных операторов. В этом смысле иерархические матрицы можно считать алгебраическими аналогами этих методов.

Применение к интегральным операторам

Иерархические матрицы успешно используются для обработки интегральных уравнений, например, операторов потенциала одинарного и двойного слоя, появляющихся в методе граничных элементов . Типичный оператор имеет вид

Г [ ты ] ( х ) = ∫ Ω к ( х , у ) ты ( у ) г у . {\displaystyle {\mathcal {G}}[u](x)=\int _{\Omega }\kappa (x,y)u(y)\,dy.}

Метод Галеркина приводит к матричным записям вида

г я дж = ∫ Ω ∫ Ω к ( х , у ) φ я ( х ) ψ дж ( у ) г у г х , {\ displaystyle g_ {ij} = \ int _ {\ Omega } \ int _ {\ Omega } \ каппа (x, y) \ varphi _ {i} (x) \ psi _ {j} (y) \, dy \, dx,}

где и являются семействами функций конечного базиса. Если функция ядра достаточно гладкая, мы можем аппроксимировать ее полиномиальной интерполяцией, чтобы получить ( φ я ) я ∈ я {\displaystyle (\varphi _{i})_{i\in I}} ( ψ дж ) дж ∈ Дж. {\displaystyle (\psi _{j})_{j\in J}} к {\displaystyle \каппа}

к ~ ( х , у ) = ∑ ν = 1 к к ( х , ξ ν ) ℓ ν ( у ) , {\displaystyle {\tilde {\kappa }}(x,y)=\sum _{\nu =1}^{k}\kappa (x,\xi _{\nu })\ell _{\nu }(y),}

где — семейство точек интерполяции, а — соответствующее семейство полиномов Лагранжа . Замена на дает приближение ( ξ ν ) ν = 1 к {\displaystyle (\xi _{\nu })_{\nu =1}^{k}} ( ℓ ν ) ν = 1 к {\displaystyle (\ell _{\nu })_{\nu =1}^{k}} к {\displaystyle \каппа} к ~ {\displaystyle {\тильда {\каппа }}}

г ~ я дж = ∫ Ω ∫ Ω к ~ ( х , у ) φ я ( х ) ψ дж ( у ) г у г х = ∑ ν = 1 к ∫ Ω к ( х , ξ ν ) φ я ( х ) г х ∫ Ω ℓ ν ( у ) ψ дж ( у ) г у = ∑ ν = 1 к а я ν б дж ν {\displaystyle {\tilde {g}}_{ij}=\int _{\Omega }\int _{\Omega }{\tilde {\kappa }}(x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx=\sum _{\nu =1}^{k}\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx\int _{\Omega }\ell _{\nu }(y)\psi _{j}(y)\,dy=\sum _{\nu =1}^{k}a_{i\nu }b_{j\nu }}

с коэффициентами

а я ν = ∫ Ω к ( х , ξ ν ) φ я ( х ) г х , {\ displaystyle a_ {i \ nu } = \ int _ {\ Omega } \ каппа (x, \ xi _ {\ nu }) \ varphi _ {i} (x) \, dx,}
б дж ν = ∫ Ω ℓ ν ( у ) ψ дж ( у ) г у . {\ displaystyle b_ {j \ nu } = \ int _ {\ Omega } \ ell _ {\ nu } (y) \ psi _ {j} (y) \, dy.}

Если мы выберем и используем одни и те же точки интерполяции для всех , то получим . т ⊆ я , с ⊆ Дж. {\displaystyle t\subseteq I,s\subseteq J} я ∈ т , дж ∈ с {\displaystyle i\in t,j\in s} Г | т × с ≈ А Б ∗ {\displaystyle G|_{t\times s}\approx AB^{*}}

Очевидно, что любое другое приближение, разделяющее переменные и , например, мультипольное разложение, также позволило бы нам разбить двойной интеграл на два одинарных интеграла и, таким образом, прийти к аналогичной факторизованной матрице низкого ранга. х {\displaystyle x} у {\displaystyle у}

Особый интерес представляют методы перекрестной аппроксимации [6] [7] [15] , которые используют только элементы исходной матрицы для построения аппроксимации низкого ранга . Г {\displaystyle G}

Применение к эллиптическим уравнениям в частных производных

Поскольку оператор решения эллиптического уравнения в частных производных можно выразить как интегральный оператор, включающий функцию Грина , неудивительно, что обратная матрица жесткости, полученная с помощью метода конечных элементов и спектрального метода, может быть аппроксимирована иерархической матрицей.

Функция Грина зависит от формы вычислительной области, поэтому она обычно неизвестна. Тем не менее, приближенные арифметические операции могут быть использованы для вычисления приближенной обратной функции без явного знания функции.

Удивительно, но можно доказать [11] [12] [13] [14] , что обратную функцию можно аппроксимировать, даже если дифференциальный оператор содержит негладкие коэффициенты и, следовательно, функция Грина не является гладкой.

Арифметические операции

Наиболее важным нововведением метода иерархических матриц является разработка эффективных алгоритмов для выполнения (приближенных) матричных арифметических операций над неразреженными матрицами, например, для вычисления приближенных обратных матриц, LU-разложений и решений матричных уравнений.

Центральный алгоритм — эффективное умножение матрицы на матрицу, т. е. вычисление для иерархических матриц и скалярного множителя . Алгоритм требует, чтобы подматрицы иерархических матриц были организованы в блочную древовидную структуру, и использует преимущества свойств факторизованных матриц низкого ранга для вычисления обновленных операций . З = З + α Х И {\displaystyle Z=Z+\альфа XY} Х , И , З {\displaystyle X,Y,Z} α {\displaystyle \альфа} З {\displaystyle Z} О ( н к 2 бревно ⁡ ( н ) 2 ) {\displaystyle O(nk^{2}\,\log(n)^{2})}

Используя преимущества блочной структуры, обратную можно вычислить, используя рекурсию для вычисления обратных и дополнений Шура диагональных блоков и объединяя их с помощью умножения матрицы на матрицу. Аналогичным образом, LU-разложение [16] [17] может быть построено с использованием только рекурсии и умножения. Обе операции также требуют операций. О ( н к 2 бревно ⁡ ( н ) 2 ) {\displaystyle O(nk^{2}\,\log(n)^{2})}

ЧАС2-матрицы

Для обработки очень больших задач можно улучшить структуру иерархических матриц: H 2 -матрицы [18] [19] заменяют общую низкоранговую структуру блоков иерархическим представлением, тесно связанным с быстрым мультипольным методом , чтобы снизить сложность хранения до . О ( н к ) {\displaystyle O(nk)}

В контексте граничных интегральных операторов замена фиксированного ранга рангами, зависящими от блока, приводит к приближениям, которые сохраняют скорость сходимости базового метода граничных элементов при сложности [20] [21] к {\displaystyle к} О ( н ) . {\displaystyle O(n).}

Арифметические операции, такие как умножение, инверсия и факторизация Холецкого или LR матриц H 2 , могут быть реализованы на основе двух фундаментальных операций: умножение матрицы на вектор с подматрицами и обновление подматриц с низким рангом. В то время как умножение матрицы на вектор является простым, реализация эффективных обновлений с низким рангом с адаптивно оптимизированными кластерными базами представляет собой значительную проблему. [22]

Литература

  1. ^ Хакбуш, Вольфганг (1999). «Арифметика разреженных матриц на основе H-матриц. Часть I: Введение в H-матрицы». Computing . 62 (2): 89– 108. doi :10.1007/s006070050015. S2CID  24294140.
  2. ^ ab Граседик, Ларс; Хакбуш, Вольфганг (2003). «Построение и арифметика H-матриц». Computing . 70 (4): 295– 334. doi :10.1007/s00607-003-0019-1.
  3. ^ Хакбуш, Вольфганг (2015). Иерархические матрицы: алгоритмы и анализ . Springer Series in Computational Mathematics. Vol. 49. Springer. doi :10.1007/978-3-662-47324-5. ISBN 978-3-662-47323-8.
  4. ^ Бебендорф, Марио (2008). Иерархические матрицы: средство эффективного решения эллиптических краевых задач . Springer.
  5. ^ Хакбуш, Вольфганг; Хоромский, Борис Н. (2000). «Арифметика разреженной H-матрицы. Часть II: Применение к многомерным задачам». Computing . 64 : 21– 47. doi :10.1007/PL00021408.
  6. ^ ab Bebendorf, Mario (2000). «Аппроксимация матриц граничных элементов». Numer. Math . 86 (4): 565– 589. doi :10.1007/pl00005410. S2CID  206858339.
  7. ^ ab Бебендорф, Марио; Ржасанов, Сергей (2003). «Адаптивная низкоранговая аппроксимация коллокационных матриц». Computing . 70 : 1– 24. CiteSeerX 10.1.1.133.182 . doi :10.1007/s00607-002-1469-6. S2CID  16501661. 
  8. ^ Бёрм, Штеффен; Граседик, Ларс (2005). «Гибридная перекрестная аппроксимация интегральных операторов». Numer. Math . 101 (2): 221– 249. CiteSeerX 10.1.1.330.8950 . doi :10.1007/s00211-005-0618-1. S2CID  263882011. 
  9. ^ Бёрм, Штеффен; Кристоферсен, Свен (2016). «Аппроксимация интегральных операторов квадратурой Грина и вложенной крестовой аппроксимацией». Numer. Math . 133 (3): 409– 442. arXiv : 1404.2234 . doi :10.1007/s00211-015-0757-y. S2CID  253745725.
  10. ^ Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2016). «Существование аппроксимаций H-матриц для обратных матриц BEM: оператор простого слоя». Math. Comp . 85 (297): 119– 152. arXiv : 1311.5028 . doi :10.1090/mcom/2990. S2CID  10706786.
  11. ^ ab Бебендорф, Марио; Хакбуш, Вольфганг (2003). "Существование аппроксимаций H-матрицы к обратной FE-матрице эллиптических операторов с -коэффициентами". Numer. Math . 95 : 1– 28. doi :10.1007/s00211-002-0445-6. S2CID  263876883. Л ∞ {\displaystyle L^{\infty}}
  12. ^ ab Börm, Steffen (2010). "Аппроксимация операторов решения эллиптических уравнений в частных производных H- и H 2 -матрицами". Numer. Math . 115 (2): 165– 193. doi :10.1007/s00211-009-0278-7. S2CID  7737211.
  13. ^ ab Faustmann, Markus; Melenk, J. Markus; Praetorius, Dirk (2015). "H-матричная аппроксимируемость обратных матриц FEM". Numer. Math . 131 (4): 615– 642. arXiv : 1308.0499 . doi : 10.1007/s00211-015-0706-9. S2CID  2619823.
  14. ^ ab Shen, Jie; Wang, Yingwei; Xia, Jianlin (2016). «Быстрые структурированные прямые спектральные методы для дифференциальных уравнений с переменными коэффициентами». SIAM Journal on Scientific Computing . 38 (1): A28 – A54 . doi :10.1137/140986815.
  15. ^ Тыртышников, Евгений (2000). "Неполная крестовая аппроксимация в мозаично-скелетонном методе". Computing . 64 (4): 367– 380. CiteSeerX 10.1.1.100.6153 . doi :10.1007/s006070070031. S2CID  15850058. 
  16. ^ Бебендорф, Марио (2007). «Почему дискретизации конечных элементов могут быть факторизованы треугольными иерархическими матрицами». SIAM J. Numer. Anal . 45 (4): 1472– 1494. doi :10.1137/060669747.
  17. ^ Граседик, Ларс; Криманн, Рональд; Ле Борн, Сабина (2009). «Предварительная обработка H-LU на основе разложения домена». Numer. Math . 112 (4): 565– 600. doi : 10.1007/s00211-009-0218-6 .
  18. ^ Хакбуш, Вольфганг; Хоромский, Борис Н.; Заутер, Стефан (2002). "О матрицах H 2". Лекции по прикладной математике . С.  9–29 . doi :10.1007/978-3-642-59709-1_2. ISBN 978-3-642-64094-0.
  19. ^ Бёрм, Штеффен (2010). Эффективные численные методы для нелокальных операторов: сжатие матрицы H2, алгоритмы и анализ. EMS Tracts in Mathematics. ISBN 9783037190913.
  20. ^ Sauter, Stefan (2000). «Кластеризация панелей переменного порядка». Computing . 64 (3): 223–261 . doi :10.1007/s006070050045. S2CID  36813444.
  21. ^ Бёрм, Штеффен; Заутер, Стефан (2005). «BEM с линейной сложностью для классических граничных интегральных операторов». Math. Comp . 74 (251): 1139– 1177. doi : 10.1090/s0025-5718-04-01733-8 .
  22. ^ Бёрм, Штеффен; Реймер, Кнут (2015). «Эффективные арифметические операции для рангово-структурированных матриц на основе иерархических низкоранговых обновлений». Вычисления и визуализация в науке . 16 (6): 247–258 . arXiv : 1402.5056 . doi : 10.1007/s00791-015-0233-3. S2CID  36931036.

Программное обеспечение

HLib — это программная библиотека на языке C, реализующая важнейшие алгоритмы для иерархических и -матриц. ЧАС 2 {\displaystyle {\mathcal {H}}^{2}}

AHMED — это программная библиотека C++, которую можно загрузить в образовательных целях.

HLIBpro — это реализация основных иерархических матричных алгоритмов для коммерческих приложений.

H2Lib — это реализация иерархических матричных алгоритмов с открытым исходным кодом, предназначенная для исследований и обучения.

awesome-hierarchical-matrices — это репозиторий, содержащий список других реализаций H-матриц.

HierarchicalMatrices.jl — пакет Julia, реализующий иерархические матрицы.

Взято с "https://en.wikipedia.org/w/index.php?title=Иерархическая_матрица&oldid=1225129278"