Участник:BoldyrevVV MSU/Параллельная реализация матричного крестового метода - История изменений

BoldyrevVV MSU: add references

2025-11-04T19:13:19Z

add references

BoldyrevVV MSU: add comments

2025-11-04T18:48:11Z

add comments

← Предыдущая версия		Версия от 18:48, 4 ноября 2025
Строка 113:		Строка 113:
	:<math>r \gets r + 1</math>		:<math>r \gets r + 1</math>

	:'''~~если~~'''		'''Eсли''' <math>rnk = 0</math>, то
	:<math>rnk = 0</math>, то
	::<math>j \gets J^*(1)</math>		::<math>j \gets J^*(1)</math>
			'''КонецЕсли'''
	:<math>\texttt{Broadcast}(0, j, j)</math>		:<math>\texttt{Broadcast}(0, j, j)</math>

Строка 124:		Строка 124:
	:<math>\texttt{Gather}\left( 0, \left\{ i, \vert A_{ij} - [U v]_i \vert \right\}, max_i \right)</math>		:<math>\texttt{Gather}\left( 0, \left\{ i, \vert A_{ij} - [U v]_i \vert \right\}, max_i \right)</math>

	:'''~~если~~'''		'''Eсли''' <math>rnk = 0</math>, то
	:<math>rnk = 0</math>, то
	::<math>{i, column_maximum} \gets \max_{k \in [1; p]} (max_i[k])</math>		::<math>{i, column_maximum} \gets \max_{k \in [1; p]} (max_i[k])</math>
			'''КонецЕсли'''


	:<math>\texttt{Broadcast}(0, i, i)</math>		:<math>\texttt{Broadcast}(0, i, i)</math>
Строка 136:		Строка 137:
	:<math>\texttt{Gather}(0, \left\{j, \vert A_{ij} - [u V]_j \vert \right\}, max_j)</math>		:<math>\texttt{Gather}(0, \left\{j, \vert A_{ij} - [u V]_j \vert \right\}, max_j)</math>

	:'''~~если~~'''		'''Eсли''' <math>rnk = 0</math>, то
	:<math>rnk = 0</math>, то
	::<math>{j, maximum} \gets \max_{k \in [1; p]} (maxj[k])</math>		::<math>{j, maximum} \gets \max_{k \in [1; p]} (maxj[k])</math>
			'''КонецЕсли'''

	:<math>\texttt{Broadcast}(0, \left\{j, maximum\right\}, \left\{j, maximum\right\})</math>		:<math>\texttt{Broadcast}(0, \left\{j, maximum\right\}, \left\{j, maximum\right\})</math>

Строка 152:		Строка 154:
	:<math>J \gets J \setminus \left\{ j \right\}</math>		:<math>J \gets J \setminus \left\{ j \right\}</math>

	:'''~~если~~''' <math>rnk = 0</math>, то		'''Eсли''' <math>rnk = 0</math>, то
	::<math>J_* \gets J_* \setminus \left\{ j \right\}</math>		::<math>J_* \gets J_* \setminus \left\{ j \right\}</math>
			'''КонецЕсли'''

	''до тех пор, пока''		''до тех пор, пока''
Строка 159:		Строка 162:

	'''вернуть''' <math>(U, V, r)</math>		'''вернуть''' <math>(U, V, r)</math>
			<br>
	<br>		<br>
	Функция <math>\texttt{Broadcast}\left( i,a,b \right)</math> рассылает переменную a спроцессора <math>i</math> в переменную <math>b</math> всех процессоров; функция <math>\texttt{Gather}\left( i,a,b \right)</math> собирает переменную <math>a</math> всех процессоров в переменную <math>b</math> (таким образом, <math>b</math> массив из переменных <math>a</math> процессора <math>i</math>.		Функция <math>\texttt{Broadcast}\left( i,a,b \right)</math> рассылает переменную a спроцессора <math>i</math> в переменную <math>b</math> всех процессоров; функция <math>\texttt{Gather}\left( i,a,b \right)</math> собирает переменную <math>a</math> всех процессоров в переменную <math>b</math> (таким образом, <math>b</math> массив из переменных <math>a</math> процессора <math>i</math>.
			<br><br>
			Пересчёт нормы текущего приближения легко осуществляется параллельно в условиях реализованного в алгоритме распределения по процессорам матриц <math>U</math> и <math>V</math>. Каждый процессор может вычислять векторы
			:<math>x_{rnk} = u^T[b_m \cdot rnk + 1 : b_m \cdot (rnk + 1)] \cdot U[b_m \cdot rnk + 1 : b_m \cdot (rnk + 1), :]</math>,
			:<math>y_{rnk} = v^T[b_n \cdot rnk + 1 : b_n \cdot (rnk + 1)] \cdot V[:, b_n \cdot rnk + 1 : b_n \cdot (rnk + 1)]</math>.

			Находим суммы
			<math>x = \sum_{rnk=0}^{p} x_{rnk}</math>, <math>y = \sum_{rnk=0}^{p} y_{rnk}</math>,
			каждую с помощью одной операции коллективного взаимодействия процессоров. Вычисляем их скалярное произведение <math>(x, y)</math>. Очевидно, что <math>(x, y) = (U^T u, V v^T)</math>.

			Слагаемые <math>(V v^T, U^T u)</math> и <math>\|\|u\|\|_2^2 \|\|v\|\|_2^2</math>, требуемые для пересчёта нормы, вычисляются аналогично.

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

			Каждый процессор, кроме первого, в данном алгоритме выполняет <math>O\left(\left(\left\lceil \frac{m}{p} \right\rceil + \left\lceil \frac{n}{p} \right\rceil\right) r^2\right)</math> операций и вычисляет <math>O\left(\left(\left\lceil \frac{m}{p} \right\rceil + \left\lceil \frac{n}{p} \right\rceil\right) r\right)</math> элементов матрицы. Первый процессор дополнительно выполняет <math>O(rp)</math> операций.

BoldyrevVV MSU: upd parallel impl

2025-11-04T18:37:30Z

upd parallel impl

Внесённые изменения

BoldyrevVV MSU: fix

2025-11-04T16:46:23Z

fix

← Предыдущая версия		Версия от 16:46, 4 ноября 2025
Строка 50:		Строка 50:
	е. Обновить текущую невязку: <math>A \gets A - C_r \hat{A}r^{-1} R_r</math>;<br>		е. Обновить текущую невязку: <math>A \gets A - C_r \hat{A}r^{-1} R_r</math>;<br>
	ж. Исключить использованные индексы: <math>I \gets I \setminus I_</math>, <math>J \gets J \setminus J_</math>;<br>		ж. Исключить использованные индексы: <math>I \gets I \setminus I_</math>, <math>J \gets J \setminus J_</math>;<br>
	До выполнения критерия остановки.<br>		''До выполнения критерия остановки.''<br><br>
	В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.		В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.

Строка 74:		Строка 74:
	<math>I \gets I \setminus {i}</math>, <math>J \gets J \setminus {j}</math>;		<math>I \gets I \setminus {i}</math>, <math>J \gets J \setminus {j}</math>;
	<br>Вернуть <math>U, V, r</math>.		<br>Вернуть <math>U, V, r</math>.
	<br>'Конец'		<br>''Конец''
	<br>		<br>

BoldyrevVV MSU: fix formula

2025-11-04T16:39:08Z

fix formula

← Предыдущая версия		Версия от 16:39, 4 ноября 2025
Строка 57:		Строка 57:
	''Инициализация:''		''Инициализация:''
	<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0</math>, <math>U \gets []</math>, <math>V \gets []</math>.		<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0</math>, <math>U \gets []</math>, <math>V \gets []</math>.
	''Цикл:''		<br>''Цикл:''
	<br>а. <math>r \gets r + 1</math>;		<br>а. <math>r \gets r + 1</math>;
	<br>б. Найти строку с максимальной невязкой в первом доступном столбце:		<br>б. Найти строку с максимальной невязкой в первом доступном столбце:
Строка 64:		Строка 64:
	<math>j \gets \arg\max{j \in J} \|A_{ij} - [UV]{ij}\|</math>;		<math>j \gets \arg\max{j \in J} \|A_{ij} - [UV]{ij}\|</math>;
	<br><br>г. Проверить критерий остановки:		<br><br>г. Проверить критерий остановки:
	если <math>\|(A - UV){ij}\| \cdot \sqrt{(m - r)(n - r)} < \varepsilon \|UV\|F</math>, то		<br> если <math>\|(A - UV){ij}\| \cdot \sqrt{(m - r)(n - r)} < \varepsilon \|UV\|F</math>, <br> то
	<math>r \gets r - 1</math>, ~~выйти~~ из цикла;		<math>r \gets r - 1</math>, <br> выйти из цикла;
	<br><br>д. Обновить факторы:		<br><br>д. Обновить факторы:
	<math>u \gets \dfrac{A^{(j)} - [UV]^{(j)}}{\sqrt{\|(A - UV){ij}\|}}</math>,		<math>u \gets \dfrac{A^{(j)} - [UV]^{(j)}}{\sqrt{\|(A - UV){ij}\|}}</math>,
Строка 74:		Строка 74:
	<math>I \gets I \setminus {i}</math>, <math>J \gets J \setminus {j}</math>;		<math>I \gets I \setminus {i}</math>, <math>J \gets J \setminus {j}</math>;
	<br>Вернуть <math>U, V, r</math>.		<br>Вернуть <math>U, V, r</math>.
			<br>'Конец'
			<br>

	<br>Здесь <math>A^{(j)}</math> обозначает <math>j</math>-й столбец матрицы <math>A</math>, а <math>A_{(i)}</math> — <math>i</math>-ю строку. Норма Фробениуса <math>\|UV\|_F</math> пересчитывается инкрементально за <math>O((m + n) r)</math> операций, что позволяет сохранить общую сложность алгоритма на уровне <math>O((m + n) r^2)</math>.		<br>Здесь <math>A^{(j)}</math> обозначает <math>j</math>-й столбец матрицы <math>A</math>, а <math>A_{(i)}</math> — <math>i</math>-ю строку. Норма Фробениуса <math>\|UV\|_F</math> пересчитывается инкрементально за <math>O((m + n) r)</math> операций, что позволяет сохранить общую сложность алгоритма на уровне <math>O((m + n) r^2)</math>.

	В параллельной реализации выбор индексов <math>i</math> и <math>j</math> выполняется совместно всеми процессорами с помощью коллективных операций (gather/broadcast), а обновление <math>U</math> и <math>V</math> — локально на каждом процессоре для его части строк/столбцов.		В параллельной реализации выбор индексов <math>i</math> и <math>j</math> выполняется совместно всеми процессорами с помощью коллективных операций (gather/broadcast), а обновление <math>U</math> и <math>V</math> — локально на каждом процессоре для его части строк/столбцов.

BoldyrevVV MSU: fix formula

2025-11-04T16:32:37Z

fix formula

BoldyrevVV MSU: fix formula

2025-11-04T16:29:47Z

fix formula

← Предыдущая версия		Версия от 16:29, 4 ноября 2025
Строка 37:		Строка 37:
	Общая схема крестового метода основана на последовательном выделении строк и столбцов, содержащих подматрицу максимального (или достаточно большого) объёма. В обобщённом виде она выглядит следующим образом:		Общая схема крестового метода основана на последовательном выделении строк и столбцов, содержащих подматрицу максимального (или достаточно большого) объёма. В обобщённом виде она выглядит следующим образом:

	Алгоритм 1. Схема крестового метода<br>		'''Алгоритм 1. Схема крестового метода'''<br>

			''Инициализация:''
	Инициализация:
	<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0		<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0
	</math>.		</math>.
	<br>Повторять:<br>		<br>''Повторять:''<br>
	а. <math>r \gets r + 1</math>;<br>		а. <math>r \gets r + 1</math>;<br>
	б. Найти подмножества индексов <math>I_* \subset I</math>, <math>J_* \subset J</math> (размера <math>k</math>), такие что подматрица <math>A[I_, J_]</math> имеет достаточно большой объём (процедура <math>\texttt{maxvol}</math>);<br>		б. Найти подмножества индексов <math>I_* \subset I</math>, <math>J_* \subset J</math> (размера <math>k</math>), такие что подматрица <math>A[I_, J_]</math> имеет достаточно большой объём (процедура <math>\texttt{maxvol}</math>);<br>
	в. Выбрать столбцы: <math>C_r \gets A[:, J_*]</math>;<br>		в. Выбрать столбцы: <math>C_r \gets A[:, J_*]</math>;<br>
	г. Выбрать строки: <math>R_r \gets A[I_*, :]</math>;<br>		г. Выбрать строки: <math>R_r \gets A[I_*, :]</math>;<br>
	д. Выделить ядро: <math>\hat{A}r \gets A[I, J_]</math>;<br>		д. Выделить ядро: <math>\hat{A}r \gets A[I, J_]</math>;<br>
Строка 54:		Строка 53:
	В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.		В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.

	Алгоритм 2. Крестовый метод (<math>k = 1</math>)		'''Алгоритм 2. Крестовый метод (<math>k = 1</math>)'''

	Инициализация:		''Инициализация:''
	<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0</math>, <math>U \gets []</math>, <math>V \gets []</math>.		<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0</math>, <math>U \gets []</math>, <math>V \gets []</math>.
	Цикл:		''Цикл:''
	<br>а. <math>r \gets r + 1</math>;		<br>а. <math>r \gets r + 1</math>;
	<br>б. Найти строку с максимальной невязкой в первом доступном столбце:		<br>б. Найти строку с максимальной невязкой в первом доступном столбце:

BoldyrevVV MSU: add description

2025-11-04T16:23:11Z

add description

← Предыдущая версия		Версия от 16:23, 4 ноября 2025
Строка 1:		Строка 1:
	~~init~~		{{algorithm
			\| name = Матричный крестовой метод
			\| serial_complexity = <math>O((m + n) r^2)</math>
			\| pf_height = <math>O(r p)</math>
			\| pf_width = <math>O\left(\left\lceil \frac{m}{p} \right\rceil + \left\lceil \frac{n}{p} \right\rceil\right) r</math>
			\| input_data = <math>O((m + n) r)</math> (вычисляются лишь отдельные элементы матрицы)
			\| output_data = <math>O((m + n) r)</math> (факторы <math>U \in \mathbb{R}^{m \times r}</math>, <math>V \in \mathbb{R}^{r \times n}</math>)
			}}

			Основные авторы описания: [[Участник:Желтков\|Д.А. Желтков]], [[Участник:Тыртышников\|Е.Е. Тыртышников]]

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

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

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

			Ключевая идея основана на так называемом '''крестовом разложении''': если известны <math>r</math> строк и <math>r</math> столбцов матрицы, пересечение которых образует невырожденную подматрицу, то вся матрица может быть восстановлена через интерполяцию по этим строкам и столбцам. На практике используется '''адаптивная схема''' с выбором элемента максимальной невязки на каждой итерации (аналог жадного алгоритма), что позволяет обойтись без поиска подматрицы максимального объёма.

			Важнейшее преимущество метода — малая вычислительная стоимость: для построения приближения ранга <math>r</math> требуется <math>O((m + n) r)</math> вычислений элементов матрицы и <math>O((m + n) r^2)</math> арифметических операций.

			В условиях современных суперкомпьютеров и больших размерностей (<math>m, n \sim 10^5</math> и выше) естественным шагом становится параллельная реализация, предложенная в работе Желткова и Тыртышникова (2015). Она распределяет строки и столбцы матрицы между процессорами и использует коллективные операции для глобального выбора доминирующего элемента невязки.

			==== Особенности параллельной реализации ====

			В параллельной версии каждый процессор хранит часть строк и столбцов факторов <math>U</math> и <math>V</math>. На каждой итерации:

			процессоры совместно находят глобальный максимум невязки с помощью операций <math>\texttt{Gather}</math> и <math>\texttt{Broadcast}</math>;
			соответствующие строки и столбцы обновляются локально;
			норма Фробениуса текущего приближения пересчитывается распределённо, без полного сбора данных.
			Эта стратегия позволяет сохранить низкую коммуникационную сложность: каждый процессор выполняет <math>O(r)</math> обменов, а длина каждого сообщения не превышает <math>r</math>. При этом трудоёмкость на один процессор снижается до <math>O\left(\left(\left\lceil \frac{m}{p} \right\rceil + \left\lceil \frac{n}{p} \right\rceil\right) r^2\right)</math>, а количество вычисляемых элементов — до <math>O\left(\left(\left\lceil \frac{m}{p} \right\rceil + \left\lceil \frac{n}{p} \right\rceil\right) r\right)</math>.

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

			Пусть задана матрица <math>A \in \mathbb{R}^{m \times n}</math>. Цель — построить её малоранговое приближение вида <math>A \approx UV</math>, где <math>U \in \mathbb{R}^{m \times r}</math>, <math>V \in \mathbb{R}^{r \times n}</math>, а ранг <math>r \ll \min(m,n)</math>.

			Общая схема крестового метода основана на последовательном выделении строк и столбцов, содержащих подматрицу максимального (или достаточно большого) объёма. В обобщённом виде она выглядит следующим образом:

			Алгоритм 1. Схема крестового метода<br>


			Инициализация:
			<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0
			</math>.
			<br>Повторять:<br>
			а. <math>r \gets r + 1</math>;<br>
			б. Найти подмножества индексов <math>I_* \subset I</math>, <math>J_* \subset J</math> (размера <math>k</math>), такие что подматрица <math>A[I_, J_]</math> имеет достаточно большой объём (процедура <math>\texttt{maxvol}</math>);<br>
			в. Выбрать столбцы: <math>C_r \gets A[:, J_*]</math>;<br>
			г. Выбрать строки: <math>R_r \gets A[I_*, :]</math>;<br>
			д. Выделить ядро: <math>\hat{A}r \gets A[I, J_]</math>;<br>
			е. Обновить текущую невязку: <math>A \gets A - C_r \hat{A}r^{-1} R_r</math>;<br>
			ж. Исключить использованные индексы: <math>I \gets I \setminus I</math>, <math>J \gets J \setminus J_</math>;<br>
			До выполнения критерия остановки.<br>
			В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.

			Алгоритм 2. Крестовый метод (<math>k = 1</math>)

			Инициализация:
			<math>I \gets {1,\dots,m}</math>, <math>J \gets {1,\dots,n}</math>, <math>r \gets 0</math>, <math>U \gets []</math>, <math>V \gets []</math>.
			Цикл:
			<br>а. <math>r \gets r + 1</math>;
			<br>б. Найти строку с максимальной невязкой в первом доступном столбце:
			<math>i \gets \arg\max_{i \in I} \|A_{i, J(1)} - [UV]{i, J(1)}\|</math>;
			<br>в. Найти столбец с максимальной невязкой в найденной строке:
			<math>j \gets \arg\max{j \in J} \|A_{ij} - [UV]{ij}\|</math>;
			<br>г. Проверить критерий остановки:
			если <math>\|(A - UV){ij}\| \cdot \sqrt{(m - r)(n - r)} < \varepsilon \|UV\|F</math>, то
			<math>r \gets r - 1</math>, выйти из цикла;
			<br>д. Обновить факторы:
			<math>u \gets \dfrac{A^{(j)} - [UV]^{(j)}}{\sqrt{\|(A - UV){ij}\|}}</math>,
			<math>v \gets \dfrac{(A_{(i)} - [UV]{(i)}) \cdot \sqrt{\|(A - UV){ij}\|}}{(A - UV)_{ij}}</math>;
			<br>е. Расширить матрицы:
			<math>U \gets [U ; u]</math>, <math>V \gets \begin{bmatrix} V \ v \end{bmatrix}</math>;
			<br>ж. Исключить использованные индексы:
			<math>I \gets I \setminus {i}</math>, <math>J \gets J \setminus {j}</math>;
			<br>Вернуть <math>U, V, r</math>.
			<br>Здесь <math>A^{(j)}</math> обозначает <math>j</math>-й столбец матрицы <math>A</math>, а <math>A_{(i)}</math> — <math>i</math>-ю строку. Норма Фробениуса <math>\|UV\|_F</math> пересчитывается инкрементально за <math>O((m + n) r)</math> операций, что позволяет сохранить общую сложность алгоритма на уровне <math>O((m + n) r^2)</math>.

			В параллельной реализации выбор индексов <math>i</math> и <math>j</math> выполняется совместно всеми процессорами с помощью коллективных операций (gather/broadcast), а обновление <math>U</math> и <math>V</math> — локально на каждом процессоре для его части строк/столбцов.

BoldyrevVV MSU: init

2025-11-03T17:53:52Z

init

Новая страница

init

← Предыдущая версия		Версия от 16:32, 4 ноября 2025
Строка 49:		Строка 49:
	д. Выделить ядро: <math>\hat{A}r \gets A[I, J_]</math>;<br>		д. Выделить ядро: <math>\hat{A}r \gets A[I, J_]</math>;<br>
	е. Обновить текущую невязку: <math>A \gets A - C_r \hat{A}r^{-1} R_r</math>;<br>		е. Обновить текущую невязку: <math>A \gets A - C_r \hat{A}r^{-1} R_r</math>;<br>
	ж. Исключить использованные индексы: <math>I \gets I \setminus I</math>, <math>J \gets J \setminus J_</math>;<br>		ж. Исключить использованные индексы: <math>I \gets I \setminus I_</math>, <math>J \gets J \setminus J_</math>;<br>
	До выполнения критерия остановки.<br>		До выполнения критерия остановки.<br>
	В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.		В рассматриваемой работе используется частный случай этой схемы при <math>k = 1</math>, то есть на каждой итерации выбирается один элемент с максимальной по модулю невязкой. В этом случае подматрица <math>\hat{A}_r</math> — скаляр, а обновление факторов происходит по явным формулам.
Строка 63:		Строка 63:
	<br>в. Найти столбец с максимальной невязкой в найденной строке:		<br>в. Найти столбец с максимальной невязкой в найденной строке:
	<math>j \gets \arg\max{j \in J} \|A_{ij} - [UV]{ij}\|</math>;		<math>j \gets \arg\max{j \in J} \|A_{ij} - [UV]{ij}\|</math>;
	<br>г. Проверить критерий остановки:		<br><br>г. Проверить критерий остановки:
	если <math>\|(A - UV){ij}\| \cdot \sqrt{(m - r)(n - r)} < \varepsilon \|UV\|F</math>, то		если <math>\|(A - UV){ij}\| \cdot \sqrt{(m - r)(n - r)} < \varepsilon \|UV\|F</math>, то
	<math>r \gets r - 1</math>, выйти из цикла;		<math>r \gets r - 1</math>, выйти из цикла;
	<br>д. Обновить факторы:		<br><br>д. Обновить факторы:
	<math>u \gets \dfrac{A^{(j)} - [UV]^{(j)}}{\sqrt{\|(A - UV){ij}\|}}</math>,		<math>u \gets \dfrac{A^{(j)} - [UV]^{(j)}}{\sqrt{\|(A - UV){ij}\|}}</math>,
	<math>v \gets \dfrac{(A_{(i)} - [UV]{(i)}) \cdot \sqrt{\|(A - UV){ij}\|}}{(A - UV)_{ij}}</math>;		<math>v \gets \dfrac{(A_{(i)} - [UV]{(i)}) \cdot \sqrt{\|(A - UV){ij}\|}}{(A - UV)_{ij}}</math>;
	<br>е. Расширить матрицы:		<br><br>е. Расширить матрицы:
	<math>U \gets [U ; u]</math>, <math>V \gets \begin{bmatrix} V \ v \end{bmatrix}</math>;		<math>U \gets [U ; u]</math>, <math>V \gets \begin{bmatrix} V \ v \end{bmatrix}</math>;
	<br>ж. Исключить использованные индексы:		<br>ж. Исключить использованные индексы: