Участник:Kaholicl/Адаптивный крестовый метод

2025-11-03T11:52:27Z

Kaholicl:

{{algorithm
| name = Адаптивный крестовый метод
| serial_complexity = <math>O(k^2(m+n))</math>
| pf_height = <math>O(k)</math>
| pf_width = <math>O(m+n)</math>
| input_data = <math>O(k(m+n))</math>
| output_data = <math>O(k(m+n))</math>
}}

Основные авторы описания: [[Участник:Kaholicl|П.А.Панов]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

'''Адаптивный крестовый метод''' (Adaptive Cross Approximation, ACA) — это итерационный алгоритм для построения низкоранговой аппроксимации матриц, который не требует вычисления и хранения всех элементов исходной матрицы. Метод был разработан для эффективной работы с матрицами, возникающими при дискретизации интегральных уравнений и в других приложениях вычислительной математики<ref>Bebendorf M. Hierarchical Matrices: A Means to Efficiently Solve Elliptic Boundary Value Problems. — Springer, 2008.</ref>.

Основная идея метода заключается в построении аппроксимации матрицы <math>A \in \mathbb{R}^{m \times n}</math> в виде произведения двух матриц меньшей размерности: <math>A \approx U_k V_k^T</math>, где <math>U_k \in \mathbb{R}^{m \times k}</math>, <math>V_k \in \mathbb{R}^{n \times k}</math>, и <math>k \ll \min(m,n)</math>. При этом алгоритм вычисляет только <math>O(k(m+n))</math> элементов исходной матрицы вместо полных <math>O(mn)</math>.

=== Математическое описание алгоритма ===

Исходные данные: матрица <math>A</math> (заданная неявно, через функцию вычисления элементов), допустимая погрешность <math>\varepsilon</math>, максимальный ранг <math>k_{max}</math>.

Вычисляемые данные: матрицы <math>U_k = [u_1, \ldots, u_k]</math> и <math>V_k = [v_1, \ldots, v_k]</math> такие, что <math>A \approx U_k V_k^T</math>.

'''Формулы метода:'''

'''Инициализация:'''
* <math>j_1 = 1</math> (начальный ведущий столбец)
* <math>k = 1</math>

'''Основные итерационные формулы:'''
* <math>
\tilde{u}_k = A_{:,j_k} - \sum_{p=1}^{k-1} u_p (v_p^T)_{j_k}
</math>
* <math>
i_k = \arg\max_{1 \leq i \leq m} |(\tilde{u}_k)_i|
</math>
* <math>
u_k = \frac{\tilde{u}_k}{(\tilde{u}_k)_{i_k}}
</math>
* <math>
\tilde{v}_k^T = A_{i_k,:} - \sum_{p=1}^{k-1} (u_p)_{i_k} v_p^T
</math>
* <math>
v_k = \tilde{v}_k
</math>
* <math>
j_{k+1} = \arg\max_{1 \leq j \leq n} |(\tilde{v}_k)_j|
</math>

'''Критерии остановки:'''
* Если <math>\|u_k v_k^T\|_F \leq \varepsilon \|A_k\|_F</math>, где <math>A_k = \sum_{p=1}^k u_p v_p^T</math>
* Или если <math>k = k_{max}</math>
* Иначе: <math>k = k + 1</math>, перейти к следующей итерации

'''Вычислительные характеристики:'''
* Сложность одной итерации: <math>O(k(m+n))</math>
* Общая сложность: <math>O(k^2(m+n))</math>
* Объем памяти: <math>O(k(m+n))</math>
* Количество вычисляемых элементов матрицы: <math>O(k(m+n))</math> вместо <math>O(mn)</math>

Участник:Kaholicl/Адаптивный крестовый метод

2025-11-03T10:07:46Z

Kaholicl: Новая страница: «вправравраврп»

вправравраврп

Алговики - Вклад [ru]

Участник:Kaholicl/Адаптивный крестовый метод

Участник:Kaholicl/Адаптивный крестовый метод