Иерархическая матрица

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

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

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

Чтобы аппроксимировать всю матрицу $G$ , он разбивается на семейство подматриц. Большие подматрицы хранятся в факторизованном представлении, а маленькие подматрицы хранятся в стандартном представлении для повышения эффективности.

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

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

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

{\mathcal {G}}[u](x)=\int _{\Omega }\kappa (x,y)u(y)\,dy.

Метод Галёркина приводит к матричным элементам вида

g_{ij}=\int _{\Omega }\int _{\Omega }\kappa (x,y)\varphi _{i}(x)\psi _{j}(y)\,dy\,dx,

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

{\tilde {\kappa }}(x,y)=\sum _{\nu =1}^{k}\kappa (x,\xi _{\nu })\ell _{\nu }(y),

где $(\xi _{\nu })_{\nu =1}^{k}$ это семейство точек интерполяции и $(\ell _{\nu })_{\nu =1}^{k}$ — соответствующее семейство полиномов Лагранжа . Замена $\kappa$ к ${\tilde {\kappa }}$ дает приближение

{\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 }

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

a_{i\nu }=\int _{\Omega }\kappa (x,\xi _{\nu })\varphi _{i}(x)\,dx,

b_{j\nu }=\int _{\Omega }\ell _{\nu }(y)\psi _{j}(y)\,dy.

Если мы выберем $t\subseteq I,s\subseteq J$ и использовать одни и те же точки интерполяции для всех $i\in t,j\in s$ , мы получаем $G|_{t\times s}\approx AB^{*}$ .

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

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

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

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

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

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

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

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

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

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

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

Для решения очень больших задач можно улучшить структуру иерархических матриц: ЧАС ²-матрицы ^[18]^[19] заменить общую низкоранговую структуру блоков иерархическим представлением, тесно связанным с методом быстрых мультиполей, чтобы уменьшить сложность хранения до $O(nk)$ .

В контексте граничных интегральных операторов замена фиксированного ранга $k$ блочно-зависимыми рангами приводит к аппроксимациям, сохраняющим скорость сходимости основного метода граничных элементов при сложности $O(n).$ ^[20]^[21]

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

Литература

^ Хакбуш, Вольфганг (1999). «Разреженная матричная арифметика, основанная на H-матрицах. Часть I: Введение в H-матрицы». Вычисление . 62 (2): 89–108. дои : 10.1007/s006070050015 . S2CID 24294140 .
^ Jump up to: ^а ^б Граседик, Ларс; Хакбуш, Вольфганг (2003). «Построение и арифметика H-матриц». Вычисление . 70 (4): 295–334. дои : 10.1007/s00607-003-0019-1 .
^ Хакбуш, Вольфганг (2015). Иерархические матрицы: Алгоритмы и анализ . Ряд Спрингера по вычислительной математике. Том. 49. Спрингер. дои : 10.1007/978-3-662-47324-5 . ISBN 978-3-662-47323-8 .
^ Бебендорф, Марио (2008). Иерархические матрицы: средство эффективного решения эллиптических краевых задач . Спрингер.
^ Хакбуш, Вольфганг; Хоромский, Борис Н. (2000). «Разреженная H-матричная арифметика. Часть II: Применение к многомерным задачам». Вычисление . 64 : 21–47. дои : 10.1007/PL00021408 .
^ Jump up to: ^а ^б Бебендорф, Марио (2000). «Аппроксимация матриц граничных элементов». Число. Математика . 86 (4): 565–589. дои : 10.1007/pl00005410 . S2CID 206858339 .
^ Jump up to: ^а ^б Бебендорф, Марио; Рясанов, Сергей (2003). «Адаптивная низкоранговая аппроксимация коллокационных матриц». Вычисление . 70 : 1–24. CiteSeerX 10.1.1.133.182 . дои : 10.1007/s00607-002-1469-6 . S2CID 16501661 .
^ Бёрм, Штеффен; Граседик, Ларс (2005). «Гибридная перекрестная аппроксимация интегральных операторов». Число. Математика . 101 (2): 221–249. CiteSeerX 10.1.1.330.8950 . дои : 10.1007/s00211-005-0618-1 . S2CID 263882011 .
^ Бёрм, Штеффен; Кристоферсен, Свен (2016). «Приближение интегральных операторов квадратурой Грина и аппроксимацией вложенных крестов». Число. Математика . 133 (3): 409–442. arXiv : 1404.2234 . дои : 10.1007/s00211-015-0757-y . S2CID 253745725 .
^ Фаустманн, Маркус; Меленк, Дж. Маркус; Преториус, Дирк (2016). «Существование H-матричных аппроксимаций обратных матриц БЭМ: оператор простого слоя». Математика. Комп . 85 (297): 119–152. arXiv : 1311.5028 . дои : 10.1090/mcom/2990 . S2CID 10706786 .
^ Jump up to: ^а ^б Бебендорф, Марио; Хакбуш, Вольфганг (2003). «Существование H-матричных аппроксимаций обратной FE-матрицы эллиптических операторов с $L^{\infty }$ -коэффициенты". Число. Математика . 95 : 1–28. doi : 10.1007/s00211-002-0445-6 . S2CID 263876883 .
^ Jump up to: ^а ^б Бёрм, Штеффен (2010). «Приближение операторов решения эллиптических уравнений в частных производных H- и H ²-матрицы». Число. Математика . 115 (2): 165–193. doi : 10.1007/s00211-009-0278-7 . S2CID 7737211 .
^ Jump up to: ^а ^б Фаустманн, Маркус; Меленк, Дж. Маркус; Преториус, Дирк (2015). «H-матричная аппроксимация обратных матриц МКЭ». Число. Математика . 131 (4): 615–642. arXiv : 1308.0499 . дои : 10.1007/s00211-015-0706-9 . S2CID 2619823 .
^ Jump up to: ^а ^б Шен, Цзе; Ван, Инвэй; Ся, Цзяньлинь (2016). «Быстрые структурированные прямые спектральные методы для дифференциальных уравнений с переменными коэффициентами». SIAM Журнал по научным вычислениям . 38 (1): А28–А54. дои : 10.1137/140986815 .
^ Тыртышников, Евгений (2000). «Неполное перекрестное приближение в мозаично-скелетном методе». Вычисление . 64 (4): 367–380. CiteSeerX 10.1.1.100.6153 . дои : 10.1007/s006070070031 . S2CID 15850058 .
^ Бебендорф, Марио (2007). «Почему дискретизация конечных элементов может быть учтена с помощью треугольных иерархических матриц». СИАМ Дж. Нумер. Анал . 45 (4): 1472–1494. дои : 10.1137/060669747 .
^ Граседик, Ларс; Криманн, Рональд; Ле Борн, Сабина (2009). «Предварительная подготовка H-LU на основе декомпозиции домена» . Число. Математика . 112 (4): 565–600. дои : 10.1007/s00211-009-0218-6 .
^ Хакбуш, Вольфганг; Хоромский Борис Н.; Заутер, Стефан (2002). «О H 2-матрицах». Лекции по прикладной математике . стр. 9–29. дои : 10.1007/978-3-642-59709-1_2 . ISBN 978-3-642-64094-0 .
^ Бёрм, Штеффен (2010). Эффективные численные методы для нелокальных операторов: H ²-Матричное сжатие, алгоритмы и анализ . EMS Трактаты по математике. ISBN 9783037190913 .
^ Заутер, Стефан (2000). «Кластеризация панелей переменного порядка». Вычисление . 64 (3): 223–261. дои : 10.1007/s006070050045 . S2CID 36813444 .
^ Бёрм, Штеффен; Заутер, Стефан (2005). «БЭМ с линейной сложностью для классических граничных интегральных операторов» . Математика. Комп . 74 (251): 1139–1177. дои : 10.1090/s0025-5718-04-01733-8 .
^ Бёрм, Штеффен; Реймер, Кнут (2015). «Эффективные арифметические операции для матриц с ранговой структурой на основе иерархических обновлений низкого ранга». Вычисления и визуализация в науке . 16 (6): 247–258. arXiv : 1402.5056 . дои : 10.1007/s00791-015-0233-3 . S2CID 36931036 .

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

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

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

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

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

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

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

[HA99-1] Хакбуш, Вольфганг (1999). «Разреженная матричная арифметика, основанная на H-матрицах. Часть I: Введение в H-матрицы». Вычисление . 62 (2): 89–108. дои : 10.1007/s006070050015 . S2CID 24294140 .

[GRHA02-2] Jump up to: ^а ^б Граседик, Ларс; Хакбуш, Вольфганг (2003). «Построение и арифметика H-матриц». Вычисление . 70 (4): 295–334. дои : 10.1007/s00607-003-0019-1 .

[HA09-3] Хакбуш, Вольфганг (2015). Иерархические матрицы: Алгоритмы и анализ . Ряд Спрингера по вычислительной математике. Том. 49. Спрингер. дои : 10.1007/978-3-662-47324-5 . ISBN 978-3-662-47323-8 .

[MB08-4] Бебендорф, Марио (2008). Иерархические матрицы: средство эффективного решения эллиптических краевых задач . Спрингер.

[HAKH00-5] Хакбуш, Вольфганг; Хоромский, Борис Н. (2000). «Разреженная H-матричная арифметика. Часть II: Применение к многомерным задачам». Вычисление . 64 : 21–47. дои : 10.1007/PL00021408 .

[MB00-6] Jump up to: ^а ^б Бебендорф, Марио (2000). «Аппроксимация матриц граничных элементов». Число. Математика . 86 (4): 565–589. дои : 10.1007/pl00005410 . S2CID 206858339 .

[BERJ03-7] Jump up to: ^а ^б Бебендорф, Марио; Рясанов, Сергей (2003). «Адаптивная низкоранговая аппроксимация коллокационных матриц». Вычисление . 70 : 1–24. CiteSeerX 10.1.1.133.182 . дои : 10.1007/s00607-002-1469-6 . S2CID 16501661 .

[BOGR05-8] Бёрм, Штеффен; Граседик, Ларс (2005). «Гибридная перекрестная аппроксимация интегральных операторов». Число. Математика . 101 (2): 221–249. CiteSeerX 10.1.1.330.8950 . дои : 10.1007/s00211-005-0618-1 . S2CID 263882011 .

[BOCH16-9] Бёрм, Штеффен; Кристоферсен, Свен (2016). «Приближение интегральных операторов квадратурой Грина и аппроксимацией вложенных крестов». Число. Математика . 133 (3): 409–442. arXiv : 1404.2234 . дои : 10.1007/s00211-015-0757-y . S2CID 253745725 .

[FAMEPR16-10] Фаустманн, Маркус; Меленк, Дж. Маркус; Преториус, Дирк (2016). «Существование H-матричных аппроксимаций обратных матриц БЭМ: оператор простого слоя». Математика. Комп . 85 (297): 119–152. arXiv : 1311.5028 . дои : 10.1090/mcom/2990 . S2CID 10706786 .

[BEHA03-11] Jump up to: ^а ^б Бебендорф, Марио; Хакбуш, Вольфганг (2003). «Существование H-матричных аппроксимаций обратной FE-матрицы эллиптических операторов с $L^{\infty }$ -коэффициенты". Число. Математика . 95 : 1–28. doi : 10.1007/s00211-002-0445-6 . S2CID 263876883 .

[BO10-12] Jump up to: ^а ^б Бёрм, Штеффен (2010). «Приближение операторов решения эллиптических уравнений в частных производных H- и H ²-матрицы». Число. Математика . 115 (2): 165–193. doi : 10.1007/s00211-009-0278-7 . S2CID 7737211 .

[FAMEPR13-13] Jump up to: ^а ^б Фаустманн, Маркус; Меленк, Дж. Маркус; Преториус, Дирк (2015). «H-матричная аппроксимация обратных матриц МКЭ». Число. Математика . 131 (4): 615–642. arXiv : 1308.0499 . дои : 10.1007/s00211-015-0706-9 . S2CID 2619823 .

[SWX16-14] Jump up to: ^а ^б Шен, Цзе; Ван, Инвэй; Ся, Цзяньлинь (2016). «Быстрые структурированные прямые спектральные методы для дифференциальных уравнений с переменными коэффициентами». SIAM Журнал по научным вычислениям . 38 (1): А28–А54. дои : 10.1137/140986815 .

[TY00-15] Тыртышников, Евгений (2000). «Неполное перекрестное приближение в мозаично-скелетном методе». Вычисление . 64 (4): 367–380. CiteSeerX 10.1.1.100.6153 . дои : 10.1007/s006070070031 . S2CID 15850058 .

[BE07-16] Бебендорф, Марио (2007). «Почему дискретизация конечных элементов может быть учтена с помощью треугольных иерархических матриц». СИАМ Дж. Нумер. Анал . 45 (4): 1472–1494. дои : 10.1137/060669747 .

[GRKRBO09-17] Граседик, Ларс; Криманн, Рональд; Ле Борн, Сабина (2009). «Предварительная подготовка H-LU на основе декомпозиции домена» . Число. Математика . 112 (4): 565–600. дои : 10.1007/s00211-009-0218-6 .

[HAKHSA02-18] Хакбуш, Вольфганг; Хоромский Борис Н.; Заутер, Стефан (2002). «О H 2-матрицах». Лекции по прикладной математике . стр. 9–29. дои : 10.1007/978-3-642-59709-1_2 . ISBN 978-3-642-64094-0 .

[BO10b-19] Бёрм, Штеффен (2010). Эффективные численные методы для нелокальных операторов: H ²-Матричное сжатие, алгоритмы и анализ . EMS Трактаты по математике. ISBN 9783037190913 .

[SA00-20] Заутер, Стефан (2000). «Кластеризация панелей переменного порядка». Вычисление . 64 (3): 223–261. дои : 10.1007/s006070050045 . S2CID 36813444 .

[BOSA05-21] Бёрм, Штеффен; Заутер, Стефан (2005). «БЭМ с линейной сложностью для классических граничных интегральных операторов» . Математика. Комп . 74 (251): 1139–1177. дои : 10.1090/s0025-5718-04-01733-8 .

[HARE14-22] Бёрм, Штеффен; Реймер, Кнут (2015). «Эффективные арифметические операции для матриц с ранговой структурой на основе иерархических обновлений низкого ранга». Вычисления и визуализация в науке . 16 (6): 247–258. arXiv : 1402.5056 . дои : 10.1007/s00791-015-0233-3 . S2CID 36931036 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]