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

Адаптивный крестовый метод
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(k^2(m+n)) }[/math]
Объём входных данных	[math]\displaystyle{ O(k(m+n)) }[/math]
Объём выходных данных	[math]\displaystyle{ O(k(m+n)) }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(k) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(m+n) }[/math]

Основные авторы описания: П.А.Панов

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

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

Адаптивный крестовый метод (Adaptive Cross Approximation, ACA) — это итерационный алгоритм для построения низкоранговой аппроксимации матриц, который не требует вычисления и хранения всех элементов исходной матрицы. Метод был разработан для эффективной работы с матрицами, возникающими при дискретизации интегральных уравнений и в других приложениях вычислительной математики.

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

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

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

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

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

Инициализация:

• [math]\displaystyle{ j_1 = 1 }[/math] (начальный ведущий столбец)
• [math]\displaystyle{ k = 1 }[/math]

Основные итерационные формулы:

• [math]\displaystyle{ \tilde{u}_k = A_{:,j_k} - \sum_{p=1}^{k-1} u_p (v_p^T)_{j_k} }[/math]
• [math]\displaystyle{ i_k = \arg\max_{1 \leq i \leq m} |(\tilde{u}_k)_i| }[/math]
• [math]\displaystyle{ u_k = \frac{\tilde{u}_k}{(\tilde{u}_k)_{i_k}} }[/math]
• [math]\displaystyle{ \tilde{v}_k^T = A_{i_k,:} - \sum_{p=1}^{k-1} (u_p)_{i_k} v_p^T }[/math]
• [math]\displaystyle{ v_k = \tilde{v}_k }[/math]
• [math]\displaystyle{ j_{k+1} = \arg\max_{1 \leq j \leq n} |(\tilde{v}_k)_j| }[/math]

Критерии остановки:

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

Вычислительные характеристики:

• Сложность одной итерации: [math]\displaystyle{ O(k(m+n)) }[/math]
• Общая сложность: [math]\displaystyle{ O(k^2(m+n)) }[/math]
• Объем памяти: [math]\displaystyle{ O(k(m+n)) }[/math]
• Количество вычисляемых элементов матрицы: [math]\displaystyle{ O(k(m+n)) }[/math] вместо [math]\displaystyle{ O(mn) }[/math]