Участник:Asenin/Многомерное шкалирование - История изменений

Asenin: /* Масштабируемость алгоритма и его реализации */

2020-12-04T11:55:50Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 11:55, 4 декабря 2020
Строка 243:		Строка 243:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	[~~https~~:~~//www.overleaf~~.~~com/project/5fc64d3d5d5fe904a987e627/file/5fc8f1823c6e0bda9c4524c9~~ Результаты запуска реализации на Ломоносов-2]
			[[Файл:Timeee 3d.png\|мини\|Результаты запуска реализации cMDS на суперкомпьютере Ломоносов-2]]

	Прокомментируем полученный результат. Действительно получилось значительно ускорить время работы алгоритма за счет распараллеливания самых частых операций вычислительного ядра алгоритма. Однако, сложность итогового алгоритма далека от линейной, причинами этому являются последовательная структура алгоритма на макроуровне (параллелизма удалось достичь лишь на фрагментах микроуровня алгоритма), а также число итераций степенного метода (помним, что на одной итерации за счет параллелизма мы можем достичь линейной сложности) все таки усложняет алгоритм, кроме того, дает вклад билинейная сложность вычисления <math>XX^T</math> перед началом выполнения алгоритма. Увеличение сложности задачи (размера входной матрицы) закономерно приводит к значительному увеличению времени работы, однако параллелизм позволяет компенсировать это увеличение. Тем не менее, получен хороший результат: в случае матрицы <math>40000</math> строк на <math>3000</math> столбцов удалось сократить время работы с порядка 15 минут до около 1 минуты.		Прокомментируем полученный результат. Действительно получилось значительно ускорить время работы алгоритма за счет распараллеливания самых частых операций вычислительного ядра алгоритма. Однако, сложность итогового алгоритма далека от линейной, причинами этому являются последовательная структура алгоритма на макроуровне (параллелизма удалось достичь лишь на фрагментах микроуровня алгоритма), а также число итераций степенного метода (помним, что на одной итерации за счет параллелизма мы можем достичь линейной сложности) все таки усложняет алгоритм, кроме того, дает вклад билинейная сложность вычисления <math>XX^T</math> перед началом выполнения алгоритма. Увеличение сложности задачи (размера входной матрицы) закономерно приводит к значительному увеличению времени работы, однако параллелизм позволяет компенсировать это увеличение. Тем не менее, получен хороший результат: в случае матрицы <math>40000</math> строк на <math>3000</math> столбцов удалось сократить время работы с порядка 15 минут до около 1 минуты.

Asenin: /* Информационный граф */

2020-12-04T11:53:43Z

Информационный граф

← Предыдущая версия		Версия от 11:53, 4 декабря 2020
Строка 197:		Строка 197:

	=== Информационный граф ===		=== Информационный граф ===
	См. изображения с ~~информационная~~ структурой вычисления <math>XX^T</math> и <math>Ar_k</math>		См. изображения с информационной структурой вычисления <math>XX^T</math> и <math>Ar_k</math>
	[[Файл:XXT.png\|мини\|Информационная структура алгоритма вычисления XX^T]]		[[Файл:XXT.png\|мини\|Информационная структура алгоритма вычисления XX^T]]
	[[Файл:Ar k.png\|мини\|Информационная структура алгоритма вычисления Ar_k]]		[[Файл:Ar k.png\|мини\|Информационная структура алгоритма вычисления Ar_k]]

Asenin: /* Информационный граф */

2020-12-04T11:53:04Z

Информационный граф

← Предыдущая версия		Версия от 11:53, 4 декабря 2020
Строка 197:		Строка 197:

	=== Информационный граф ===		=== Информационный граф ===
			См. изображения с информационная структурой вычисления <math>XX^T</math> и <math>Ar_k</math>
	[[Файл:XXT.png\|мини\|Информационная структура алгоритма вычисления XX^T]]		[[Файл:XXT.png\|мини\|Информационная структура алгоритма вычисления XX^T]]
	[[Файл:Ar k.png\|мини\|Информационная структура алгоритма вычисления Ar_k]]		[[Файл:Ar k.png\|мини\|Информационная структура алгоритма вычисления Ar_k]]

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет - нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.		Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет - нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.

Asenin: /* Свойства и структура алгоритмов */

2020-12-04T11:51:30Z

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

← Предыдущая версия		Версия от 11:51, 4 декабря 2020
Строка 197:		Строка 197:

	=== Информационный граф ===		=== Информационный граф ===
	[~~https~~:~~//www.overleaf~~.~~com/project/5fc64d3d5d5fe904a987e627/file/5fc6bb635d5fe92f4888dd33~~ Информационная структура алгоритма вычисления XX^T]		[[Файл:XXT.png\|мини\|Информационная структура алгоритма вычисления XX^T]]
	[~~https~~:~~//www~~.~~overleaf.com/project/5fc64d3d5d5fe904a987e627/file/5fc6c34e5d5fe9a15188f29e~~ Информационная структура алгоритма вычисления Ar_k]		[[Файл:Ar k.png\|мини\|Информационная структура алгоритма вычисления Ar_k]]

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет - нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.		Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет - нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.

Asenin: /* Свойства и структура алгоритмов */

2020-12-03T15:30:55Z

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

← Предыдущая версия		Версия от 15:30, 3 декабря 2020
Строка 112:		Строка 112:
	- Итеративно пересчитываем <math>r_{k+1} = \dfrac{Ar_k}{\|\|Ar_k\|\|}</math> до сходимости, так находим собственный вектор.		- Итеративно пересчитываем <math>r_{k+1} = \dfrac{Ar_k}{\|\|Ar_k\|\|}</math> до сходимости, так находим собственный вектор.

	- Вычисляем <math>\mu_k = \dfrac{r_k^T Ar_k}{r_k^T r_k}</math> --- соответствующее собственное значение.		- Вычисляем <math>\mu_k = \dfrac{r_k^T Ar_k}{r_k^T r_k}</math> - соответствующее собственное значение.


Строка 120:		Строка 120:


	- Вычисляем <math>A_1 = A - \lambda r_k r_k^T</math> --- матрицу, сохраняющую все собственные значения матрицы <math>A</math>, кроме <math>\lambda</math>. В качестве <math>\lambda</math> кладем найденное до этого наибольшее по модулю собственное значение.		- Вычисляем <math>A_1 = A - \lambda r_k r_k^T</math> - матрицу, сохраняющую все собственные значения матрицы <math>A</math>, кроме <math>\lambda</math>. В качестве <math>\lambda</math> кладем найденное до этого наибольшее по модулю собственное значение.

	- Приеняем предыдущие шаги для нахождения следующего по модулю собственного значения, и т.д.		- Приеняем предыдущие шаги для нахождения следующего по модулю собственного значения, и т.д.
Строка 201:		Строка 201:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
	Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет --- нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.		Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет - нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.

	Обсудим ресурса параллелизма вычисления <math>XX^T</math>. По сути это <math>n^2</math> скалярных произведений векторов длины <math>k</math>.		Обсудим ресурса параллелизма вычисления <math>XX^T</math>. По сути это <math>n^2</math> скалярных произведений векторов длины <math>k</math>.

Asenin: /* Существующие реализации алгоритма */

2020-12-03T15:30:03Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 15:30, 3 декабря 2020
Строка 251:		Строка 251:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			Существующие реализации, использующие параллелизма на C++, автору неизвестны. В библиотеке sklearn для языка Python есть метод многомерного шкалирования, однако не гарантируется, что он решает задачу cMDS именно поиском собственных векторов матрицы Грама.

	== Литература ==		== Литература ==

Asenin: /* Масштабируемость алгоритма и его реализации */

2020-12-03T15:28:31Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 15:28, 3 декабря 2020
Строка 242:		Строка 242:

	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
			[https://www.overleaf.com/project/5fc64d3d5d5fe904a987e627/file/5fc8f1823c6e0bda9c4524c9 Результаты запуска реализации на Ломоносов-2]

			Прокомментируем полученный результат. Действительно получилось значительно ускорить время работы алгоритма за счет распараллеливания самых частых операций вычислительного ядра алгоритма. Однако, сложность итогового алгоритма далека от линейной, причинами этому являются последовательная структура алгоритма на макроуровне (параллелизма удалось достичь лишь на фрагментах микроуровня алгоритма), а также число итераций степенного метода (помним, что на одной итерации за счет параллелизма мы можем достичь линейной сложности) все таки усложняет алгоритм, кроме того, дает вклад билинейная сложность вычисления <math>XX^T</math> перед началом выполнения алгоритма. Увеличение сложности задачи (размера входной матрицы) закономерно приводит к значительному увеличению времени работы, однако параллелизм позволяет компенсировать это увеличение. Тем не менее, получен хороший результат: в случае матрицы <math>40000</math> строк на <math>3000</math> столбцов удалось сократить время работы с порядка 15 минут до около 1 минуты.

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Asenin: /* Входные и выходные данные алгоритма */

2020-12-03T15:25:23Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:25, 3 декабря 2020
Строка 229:		Строка 229:
	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	На вход поступает прямоугольная вещественная матрица размера <math>n</math> на <math>k</math>, алгоритм возвращает матрицу размера <math>n</math на <math>p</math>, где <math>p</math> - гиперпараметр, задаваемый пользователем.		На вход поступает прямоугольная вещественная матрица размера <math>n</math> на <math>k</math>, алгоритм возвращает матрицу размера <math>n</math> на <math>p</math>, где <math>p</math> - гиперпараметр, задаваемый пользователем.

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

Asenin: /* Входные и выходные данные алгоритма */

2020-12-03T15:24:36Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 15:24, 3 декабря 2020
Строка 228:		Строка 228:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

			На вход поступает прямоугольная вещественная матрица размера <math>n</math> на <math>k</math>, алгоритм возвращает матрицу размера <math>n</math на <math>p</math>, где <math>p</math> - гиперпараметр, задаваемый пользователем.

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

Asenin: /* Ресурс параллелизма алгоритма */

2020-12-03T15:22:06Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 15:22, 3 декабря 2020
Строка 201:		Строка 201:

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
			Из обсуждения последовательной сложности алгоритма ясно следующее: просматривается последовательная структура на макроуровне, но на уровне каждой подзадачи оперируем с понятиями параллельной природы: матрицы, векторы, их совместные операции. По сложности выделяются первый этап вычисления матрицы Грама со сложностью <math>O(n^2 k)</math> и умножение матрицы на вектор <math>O(n^2)</math>. Причем, вторая операция имеет сильно больший приоритет --- нам нужно умножать матрицу на вектор на каждой итерации степенного метода, а эти итерации будут повторяться до сходимости, то есть потенциально значительное число раз. Все остальные этапы по сути имеют линейную сложность <math>O(n)</math>, за исключением построения новой матрицы <math>A</math>, однако это операцию нужно провести всего <math>p</math> раз (<math>p << n</math>) по сравнению с несравнимо большим число итераций для сходимости степенного метода.

			Обсудим ресурса параллелизма вычисления <math>XX^T</math>. По сути это <math>n^2</math> скалярных произведений векторов длины <math>k</math>.

			Для вычисления <math>XX^T</math> нам потребуется выполнить следующие ярусы:


			<math>n</math> ярусов умножений и сложений, в каждом ярусе <math>nk</math> операций


			Таким образом, по высоте ЯПФ имеем линейную сложность, по ширине билинейную.

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

			Обсудим ресурс параллелизма умножения матрицы на вектор <math>Ar_k</math>.

			Для вычисления <math>Ar_k</math> нам потребуется выполнить следующие ярусы:


			<math>n</math> ярусов умножений, в каждом ярусе <math>n</math> операций


			Таким образом, и по высоте ЯПФ, и по ширине ЯПФ имеем линейную сложность. Это важный результат, т.к. умножение матрицы на вектор - самая частая операция в нашей постановке алгоритма cMDS, потому что встречается на каждой итерации степенного метода.

			Все остальные операции в последовательном алгоритме (см. шаги в предыдущем параграфе), как было выяснено, имеют линейную сложность, причем <<природного>> параллелизма в них нет. Тогда, если мы распараллелим вычисление матрицы Грама и умножение матрицы на вектор, то сложность алгоритма сведется к единразовому вычислению матрицы Грама с билинейной сложностью <math>O(nk)</math>, а затем вычислительное ядро алгоритма будет обладать линейной сложностью <math>O(n)</math> (тут важно понимать, что число итераций степенного метода может несколько ухудшить эту оценку), <math>p</math> раз потребуется вычислить <math>r_k r_k^T</math> за <math>O(n^2)</math> операций.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===